\hypertarget{trie_8h_source}{}\doxysection{trie.\+h}
\label{trie_8h_source}\index{kblib/trie.h@{kblib/trie.h}}
\mbox{\hyperlink{trie_8h}{Go to the documentation of this file.}}
\begin{DoxyCode}{0}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00001}00001 \textcolor{comment}{/* *****************************************************************************}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00002}00002 \textcolor{comment}{ * kblib is a general utility library for C++14 and C++17, intended to provide}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00003}00003 \textcolor{comment}{ * performant high-\/level abstractions and more expressive ways to do simple}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00004}00004 \textcolor{comment}{ * things.}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00005}00005 \textcolor{comment}{ *}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00006}00006 \textcolor{comment}{ * Copyright (c) 2021 killerbee}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00007}00007 \textcolor{comment}{ *}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00008}00008 \textcolor{comment}{ * This program is free software: you can redistribute it and/or modify}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00009}00009 \textcolor{comment}{ * it under the terms of the GNU General Public License as published by}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00010}00010 \textcolor{comment}{ * the Free Software Foundation, either version 3 of the License, or}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00011}00011 \textcolor{comment}{ * (at your option) any later version.}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00012}00012 \textcolor{comment}{ *}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00013}00013 \textcolor{comment}{ * This program is distributed in the hope that it will be useful,}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00014}00014 \textcolor{comment}{ * but WITHOUT ANY WARRANTY; without even the implied warranty of}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00015}00015 \textcolor{comment}{ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00016}00016 \textcolor{comment}{ * GNU General Public License for more details.}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00017}00017 \textcolor{comment}{ *}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00018}00018 \textcolor{comment}{ * You should have received a copy of the GNU General Public License}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00019}00019 \textcolor{comment}{ * along with this program.  If not, see <https://www.gnu.org/licenses/>.}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00020}00020 \textcolor{comment}{ * ****************************************************************************/}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00021}00021 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00031}00031 \textcolor{preprocessor}{\#ifndef TRIE\_H}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00032}00032 \textcolor{preprocessor}{\#define TRIE\_H}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00033}00033 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00034}00034 \textcolor{preprocessor}{\#include "{}\mbox{\hyperlink{tdecl_8h}{tdecl.h}}"{}}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00035}00035 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00036}00036 \textcolor{preprocessor}{\#if KBLIB\_USE\_CXX17}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00037}00037 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00038}00038 \textcolor{preprocessor}{\#  include "{}\mbox{\hyperlink{sort_8h}{sort.h}}"{}}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00039}00039 \textcolor{preprocessor}{\#  include "{}\mbox{\hyperlink{traits_8h}{traits.h}}"{}}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00040}00040 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00041}00041 \textcolor{preprocessor}{\#  include <array>}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00042}00042 \textcolor{preprocessor}{\#  include <bitset>}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00043}00043 \textcolor{preprocessor}{\#  include <vector>}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00044}00044 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00045}00045 \textcolor{keyword}{namespace }\mbox{\hyperlink{tdecl_8h_a4b5c574c663a392148218cd4410fd7a1}{KBLIB\_NS}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00046}00046 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00047}\mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145f}{00047}} \textcolor{keyword}{enum class} \mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145f}{extractor\_policy}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00048}00048    \mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145fa982690af3684bc526ae7a353bc6ef61e}{forward\_iteration}},}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00049}00049    \mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145fa298bbb8f070170fc998ccac67856211b}{random\_access}},}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00050}00050 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00051}00051 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00052}00052 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Container>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00053}\mbox{\hyperlink{structkblib_1_1iterator__extractor}{00053}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1iterator__extractor}{iterator\_extractor}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00054}\mbox{\hyperlink{structkblib_1_1iterator__extractor_ad1f43466b71d939be18855ad7f65b1e5}{00054}}    \textcolor{keyword}{using }\mbox{\hyperlink{structkblib_1_1iterator__extractor_ad1f43466b71d939be18855ad7f65b1e5}{value\_type}} =}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00055}00055        \textcolor{keyword}{typename} std::remove\_cv<\textcolor{keyword}{typename} std::remove\_reference<\textcolor{keyword}{decltype}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00056}00056            *begin(std::declval<Container\&>()))>::type>::type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00057}00057 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00058}00058 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00059}00059 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Container>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00060}\mbox{\hyperlink{structkblib_1_1indexer__extractor}{00060}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1indexer__extractor}{indexer\_extractor}} : \mbox{\hyperlink{structkblib_1_1iterator__extractor}{iterator\_extractor}}<Container> \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00061}\mbox{\hyperlink{structkblib_1_1indexer__extractor_af1c55294fce0fdbf93fe03055bd6ee89}{00061}}    \textcolor{keyword}{using }\mbox{\hyperlink{structkblib_1_1iterator__extractor_ad1f43466b71d939be18855ad7f65b1e5}{value\_type}} =}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00062}00062        \textcolor{keyword}{typename} std::remove\_cv<\textcolor{keyword}{typename} std::remove\_reference<\textcolor{keyword}{decltype}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00063}00063            std::declval<Container\&>()[0])>::type>::type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00064}00064 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00065}00065    \textcolor{keyword}{template} <\textcolor{keyword}{typename} index\_type>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00066}\mbox{\hyperlink{structkblib_1_1indexer__extractor_ab922d7f79c418f24d12d2abed7619c2d}{00066}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{constexpr} \textcolor{keyword}{static} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1indexer__extractor_ab922d7f79c418f24d12d2abed7619c2d}{subscript}}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00067}00067        Container\&\& c, index\_type index) \textcolor{keyword}{noexcept}(\textcolor{keyword}{noexcept}(c[index]))}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00068}00068        -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00069}00069       \textcolor{keywordflow}{return} c[index];}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00070}00070    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00071}00071 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00072}00072 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00073}00073 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Container, \textcolor{keyword}{typename} = \textcolor{keywordtype}{void}>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00074}\mbox{\hyperlink{structkblib_1_1extractor__policy__for}{00074}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1extractor__policy__for}{extractor\_policy\_for}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00075}\mbox{\hyperlink{structkblib_1_1extractor__policy__for_a0f2346a4fb1a393f64dcbe666b5d9c4f}{00075}}    \textcolor{keyword}{constexpr} \textcolor{keyword}{static} \mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145f}{extractor\_policy}} value}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00076}00076        = extractor\_policy::forward\_iteration;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00077}00077 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00078}00078 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00079}00079 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Container>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00080}\mbox{\hyperlink{structkblib_1_1extractor__policy__for_3_01_container_00_01void__t_3_01decltype_07std_1_1declval_544819f885a6e23bd6f87dda9bacc3f2}{00080}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1extractor__policy__for}{extractor\_policy\_for}}<Container,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00081}00081                             \mbox{\hyperlink{namespacekblib_1_1fakestd_a2df414d5a1a1f59c8f33520890755f84}{void\_t}}<decltype(\mbox{\hyperlink{namespacestd}{std}}::declval<Container>()[0])>> \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00082}\mbox{\hyperlink{structkblib_1_1extractor__policy__for_3_01_container_00_01void__t_3_01decltype_07std_1_1declval_544819f885a6e23bd6f87dda9bacc3f2_afa8ca6f705a7d4e5922c717efbd3a8f2}{00082}}    \textcolor{keyword}{constexpr} \textcolor{keyword}{static} \mbox{\hyperlink{namespacekblib_a54f01b64a070a7f3e916ec21e1d0145f}{extractor\_policy}} value = extractor\_policy::random\_access;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00083}00083 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00084}00084 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00085}00085 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Container>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00086}\mbox{\hyperlink{namespacekblib_a0ec1db9166c1c7928e764aa17e4f01e6}{00086}} \textcolor{keyword}{using }\mbox{\hyperlink{namespacekblib_a0ec1db9166c1c7928e764aa17e4f01e6}{default\_extractor\_t}} = \textcolor{keyword}{typename} std::conditional<}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00087}00087     \mbox{\hyperlink{structkblib_1_1extractor__policy__for}{extractor\_policy\_for<Container>::value}} == extractor\_policy::random\_access,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00088}00088     \mbox{\hyperlink{structkblib_1_1indexer__extractor}{indexer\_extractor<Container>}}, \mbox{\hyperlink{structkblib_1_1iterator__extractor}{iterator\_extractor<Container>}}>::type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00089}00089 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00090}00090 \textcolor{keyword}{namespace }detail \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00091}00091 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00092}00092    \textcolor{keyword}{template} <\textcolor{keyword}{typename} Elem, \textcolor{keyword}{typename} Value>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00093}\mbox{\hyperlink{structkblib_1_1detail_1_1node}{00093}}    \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1detail_1_1node}{node}} \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00094}00094 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00095}00095 \} \textcolor{comment}{// namespace detail}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00096}00096 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00097}00097 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} T,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00098}00098           \textcolor{keyword}{typename} Extractor = \mbox{\hyperlink{namespacekblib_a0ec1db9166c1c7928e764aa17e4f01e6}{default\_extractor\_t<Key>}},}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00099}00099           \textcolor{keywordtype}{bool} = \mbox{\hyperlink{structkblib_1_1is__linear__container}{kblib::is\_linear\_container<Key>::value}}>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00100}\mbox{\hyperlink{classkblib_1_1trie}{00100}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie}{trie}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00101}00101  \textcolor{keyword}{public}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00102}\mbox{\hyperlink{classkblib_1_1trie_ad7935fc8e14a3fac10037a384d9568d4}{00102}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_ad7935fc8e14a3fac10037a384d9568d4}{key\_type}} = Key;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00103}\mbox{\hyperlink{classkblib_1_1trie_a30dd0e81833b0400a8e245ef7200b9a9}{00103}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a30dd0e81833b0400a8e245ef7200b9a9}{mapped\_type}} = T;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00104}\mbox{\hyperlink{classkblib_1_1trie_aede07af27dd224aadc4ab856b18964b2}{00104}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_aede07af27dd224aadc4ab856b18964b2}{value\_type}} = std::pair<key\_type, mapped\_type>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00105}\mbox{\hyperlink{classkblib_1_1trie_a1c2587f2073383c66f4a7f139bed1c35}{00105}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a1c2587f2073383c66f4a7f139bed1c35}{extractor}} = Extractor;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00106}\mbox{\hyperlink{classkblib_1_1trie_ae33f0bf01cb7ffa772c9e4c039434864}{00106}}    \textcolor{keyword}{using }\mbox{\hyperlink{structkblib_1_1detail_1_1node}{node\_type}} = \mbox{\hyperlink{structkblib_1_1detail_1_1node}{detail::node<typename extractor::value\_type, value\_type>}};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00107}00107 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00108}\mbox{\hyperlink{classkblib_1_1trie_a4e46b941164d27286cdafbbc3022ebd0}{00108}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a4e46b941164d27286cdafbbc3022ebd0}{size\_type}} = std::size\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00109}\mbox{\hyperlink{classkblib_1_1trie_ab45698024fb9151687da6106163b67ed}{00109}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_ab45698024fb9151687da6106163b67ed}{difference\_type}} = std::ptrdiff\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00110}\mbox{\hyperlink{classkblib_1_1trie_a4f7a93d627b8062d24d11726ea39813e}{00110}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a4f7a93d627b8062d24d11726ea39813e}{reference}} = T\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00111}\mbox{\hyperlink{classkblib_1_1trie_a9b789fe484d48a1508c19bb0f375de07}{00111}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a9b789fe484d48a1508c19bb0f375de07}{const\_reference}} = \textcolor{keyword}{const} T\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00112}\mbox{\hyperlink{classkblib_1_1trie_a3b902ee66ad99bc5c39939ab47e8984b}{00112}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a3b902ee66ad99bc5c39939ab47e8984b}{pointer}} = T*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00113}\mbox{\hyperlink{classkblib_1_1trie_a71643ae34b4b75f7c0b5174ea1f500bd}{00113}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a71643ae34b4b75f7c0b5174ea1f500bd}{const\_pointer}} = \textcolor{keyword}{const} T*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00114}00114 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00115}\mbox{\hyperlink{classkblib_1_1trie_a7aebb27a546149c5a8289173eb5c1263}{00115}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a7aebb27a546149c5a8289173eb5c1263}{iterator}} = void;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00116}\mbox{\hyperlink{classkblib_1_1trie_adb744a97b30676352357ddf31b9b69bf}{00116}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_adb744a97b30676352357ddf31b9b69bf}{const\_iterator}} = void;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00117}\mbox{\hyperlink{classkblib_1_1trie_a76851afb5f034db1f75a1357f8c5a556}{00117}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a76851afb5f034db1f75a1357f8c5a556}{reverse\_iterator}} = std::reverse\_iterator<iterator>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00118}\mbox{\hyperlink{classkblib_1_1trie_a207e54c6bfceeaca30bd371801664693}{00118}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie_a207e54c6bfceeaca30bd371801664693}{const\_reverse\_iterator}} = std::reverse\_iterator<const\_iterator>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00119}00119 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00120}00120  \textcolor{keyword}{private}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00121}00121    std::unique\_ptr<node\_type> root;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00122}00122 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00123}00123  \textcolor{keyword}{public}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00124}00124 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00125}00125 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00126}00126 \textcolor{keyword}{template} <\textcolor{keyword}{typename} KeyElem, \textcolor{keyword}{typename} T, \textcolor{keyword}{typename} Extractor>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00127}\mbox{\hyperlink{classkblib_1_1trie_3_01_key_elem_00_01_t_00_01_extractor_00_01false_01_4}{00127}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie}{trie}}<KeyElem, T, Extractor, false> \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00128}00128 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00129}00129 \textcolor{keyword}{template} <\textcolor{keyword}{typename} KeyElem, \textcolor{keyword}{typename} T, \textcolor{keyword}{typename} Extractor>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00130}\mbox{\hyperlink{classkblib_1_1trie_3_01_key_elem_0f_0e_00_01_t_00_01_extractor_00_01false_01_4}{00130}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie}{trie}}<KeyElem[], T, Extractor, false> \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00131}00131 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00132}00132 \textcolor{comment}{// Array-\/mapped tries are better for denser sets}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00133}00133 \textcolor{comment}{// Tree-\/based tries are better for sparser sets}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00134}00134 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00135}00135 \textcolor{comment}{// trie\_map and trie\_set are mostly API compatible with std::map, std::set}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00136}00136 \textcolor{comment}{// trie\_qmap and trie\_qset use proxy iterators to avoid having to store Keys}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00137}00137 \textcolor{comment}{// (saves memory, less compatible with stdlib)}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00138}00138 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00139}00139 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} = \textcolor{keywordtype}{void}>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00140}\mbox{\hyperlink{structkblib_1_1default__extract}{00140}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract}};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00141}00141 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00142}00142 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00143}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4}{00143}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract}}<Key, \mbox{\hyperlink{namespacekblib_ab3cc24416f0b9a6504e1c6a437ed6230}{void\_if\_t}}<is\_linear\_container\_v<Key>>> \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00144}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_a0226eeae5adde861f761efcdd1f80a78}{00144}}    \textcolor{keyword}{using }\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_a0226eeae5adde861f761efcdd1f80a78}{value\_type}} = \textcolor{keyword}{typename} Key::value\_type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00145}00145    \textcolor{keyword}{static\_assert}(\textcolor{keyword}{static\_cast<}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_a0226eeae5adde861f761efcdd1f80a78}{value\_type}}\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}) < \textcolor{keyword}{static\_cast<}std::size\_t\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}),}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00146}00146                  \textcolor{stringliteral}{"{}Key too large to index array"{}});}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00147}00147    \textcolor{comment}{// won't overflow because of above assertion}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00148}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_ade2d31af20d2c2563d568e216d1a06b0}{00148}}    \mbox{\hyperlink{tdecl_8h_ab79256916a9652cd2d1771ae9a38799f}{KBLIB\_CONSTANT\_M}} std::size\_t key\_cardinality}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00149}00149        = \textcolor{keyword}{static\_cast<}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_a0226eeae5adde861f761efcdd1f80a78}{value\_type}}\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}) + std::size\_t\{1\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00150}00150    \textcolor{keyword}{static\_assert}(std::is\_integral<value\_type>::value,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00151}00151                  \textcolor{stringliteral}{"{}Key elements must be integral"{}});}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00152}00152 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00153}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_ab50c62522c6cd0c2f55151b92b5b6fb9}{00153}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_ab50c62522c6cd0c2f55151b92b5b6fb9}{begin}}(Key\& key) \textcolor{keyword}{noexcept}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00154}00154        \textcolor{keyword}{noexcept}(key.begin())) -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00155}00155       \textcolor{keywordflow}{return} key.begin();}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00156}00156    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00157}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_abef2014be3076cd2242fcc4f2c9a45b5}{00157}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_abef2014be3076cd2242fcc4f2c9a45b5}{end}}(Key\& key) \textcolor{keyword}{noexcept}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00158}00158        \textcolor{keyword}{noexcept}(key.end())) -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00159}00159       \textcolor{keywordflow}{return} key.end();}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00160}00160    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00161}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_ad7a00f68c930abe7572484b05c73c456}{00161}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_00_01void__if__t_3_01is__linear__container__v_3_01_key_01_4_01_4_01_4_ad7a00f68c930abe7572484b05c73c456}{index}}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00162}00162        Key\& key, std::size\_t idx) \textcolor{keyword}{noexcept}(\textcolor{keyword}{noexcept}(key[idx]))}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00163}00163        -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00164}00164       \textcolor{keywordflow}{return} key[idx];}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00165}00165    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00166}00166 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00167}00167 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00168}00168 \textcolor{keyword}{template} <\textcolor{keyword}{typename} KeyElem>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00169}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4}{00169}} \textcolor{keyword}{struct }\mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract}}<KeyElem[], \mbox{\hyperlink{namespacekblib_ab3cc24416f0b9a6504e1c6a437ed6230}{void\_if\_t}}<\mbox{\hyperlink{namespacestd}{std}}::is\_integral\_v<KeyElem>>> \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00170}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a3ae95b0106f1978de28eab8f7c5963c2}{00170}}    \textcolor{keyword}{using }\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a3ae95b0106f1978de28eab8f7c5963c2}{value\_type}} = KeyElem;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00171}00171    \textcolor{keyword}{static\_assert}(\textcolor{keyword}{static\_cast<}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a3ae95b0106f1978de28eab8f7c5963c2}{value\_type}}\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}) < \textcolor{keyword}{static\_cast<}std::size\_t\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}),}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00172}00172                  \textcolor{stringliteral}{"{}Key too large to index array"{}});}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00173}00173    \textcolor{comment}{// won't overflow because of above assertion}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00174}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a183d200b24a79708ffdb2f1cf7311308}{00174}}    \mbox{\hyperlink{tdecl_8h_ab79256916a9652cd2d1771ae9a38799f}{KBLIB\_CONSTANT\_M}} std::size\_t key\_cardinality}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00175}00175        = \textcolor{keyword}{static\_cast<}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a3ae95b0106f1978de28eab8f7c5963c2}{value\_type}}\textcolor{keyword}{>}(\mbox{\hyperlink{namespacekblib_1_1nums_a64067ecc4167ce1cfe32860ef5c1dc47}{max}}) + std::size\_t\{1\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00176}00176    \textcolor{keyword}{static\_assert}(std::is\_integral<value\_type>::value,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00177}00177                  \textcolor{stringliteral}{"{}Key elements must be integral"{}});}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00178}00178 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00179}00179    \textcolor{keyword}{template} <std::\textcolor{keywordtype}{size\_t} Size>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00180}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_aa12784d0ba3248cc70f678c5fd49ad16}{00180}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_aa12784d0ba3248cc70f678c5fd49ad16}{begin}}(KeyElem (\&key)[Size]) \textcolor{keyword}{noexcept}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00181}00181        \textcolor{keyword}{noexcept}(std::begin(key))) -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00182}00182       \textcolor{keywordflow}{return} std::begin(key);}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00183}00183    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00184}00184    \textcolor{keyword}{template} <std::\textcolor{keywordtype}{size\_t} Size>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00185}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a63f34812e8e043cd2f180d92c89bed28}{00185}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_a63f34812e8e043cd2f180d92c89bed28}{end}}(KeyElem (\&key)[Size]) \textcolor{keyword}{noexcept}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00186}00186        \textcolor{keyword}{noexcept}(std::end(key))) -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00187}00187       \textcolor{keywordflow}{return} std::end(key);}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00188}00188    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00189}00189    \textcolor{keyword}{template} <std::\textcolor{keywordtype}{size\_t} Size>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00190}\mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_afcc85dda23116e129368c4a40b627998}{00190}}    \mbox{\hyperlink{tdecl_8h_a7f62d0731631a0e7675f45924b7f5ea0}{KBLIB\_NODISCARD}} \textcolor{keyword}{static} \textcolor{keyword}{constexpr} \textcolor{keyword}{auto} \mbox{\hyperlink{structkblib_1_1default__extract_3_01_key_elem_0f_0e_00_01void__if__t_3_01std_1_1is__integral__v_3_01_key_elem_01_4_01_4_01_4_afcc85dda23116e129368c4a40b627998}{index}}(}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00191}00191        KeyElem (\&key)[Size], std::size\_t idx) \textcolor{keyword}{noexcept}(\textcolor{keyword}{noexcept}(key[idx]))}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00192}00192        -\/> \textcolor{keyword}{decltype}(\textcolor{keyword}{auto}) \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00193}00193       \textcolor{keywordflow}{return} key[idx];}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00194}00194    \}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00195}00195 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00196}00196 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00197}00197 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00198}00198 \textcolor{keyword}{struct }default\_extract<Key, \mbox{\hyperlink{namespacekblib_ab3cc24416f0b9a6504e1c6a437ed6230}{void\_if\_t}}<\mbox{\hyperlink{namespacekblib_ab58211612f119bcfedd22ca4ef9999de}{is\_radix\_sortable\_v}}<Key>>>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00199}00199 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00200}00200 \textcolor{comment}{// qset: does not store Keys (generates them on-\/demand)}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00201}00201 \textcolor{comment}{// Key: the type used for lookup}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00202}00202 \textcolor{comment}{// Extractor: controls how lookup is performed from the key}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00203}00203 \textcolor{comment}{// offset\_type: used to represent jumps in the internal array. Must be a signed}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00204}00204 \textcolor{comment}{// integral type}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00205}00205 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Extractor = default\_extract<Key>,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00206}00206           \textcolor{keyword}{typename} offset\_type = std::ptrdiff\_t>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00207}\mbox{\hyperlink{classkblib_1_1trie__qset}{00207}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie__qset}{trie\_qset}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00208}00208  \textcolor{keyword}{public}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00209}\mbox{\hyperlink{classkblib_1_1trie__qset_a1794d0295187adf0853e238777961f64}{00209}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a1794d0295187adf0853e238777961f64}{key\_type}} = Key;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00210}\mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{00210}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{value\_type}} = Key;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00211}\mbox{\hyperlink{classkblib_1_1trie__qset_aa5f9982d4db63275e0eece9805e1a804}{00211}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_aa5f9982d4db63275e0eece9805e1a804}{size\_type}} = std::size\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00212}\mbox{\hyperlink{classkblib_1_1trie__qset_aaa88c953e8bce8a877457c985451382b}{00212}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_aaa88c953e8bce8a877457c985451382b}{difference\_type}} = std::ptrdiff\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00213}00213 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00214}\mbox{\hyperlink{classkblib_1_1trie__qset_a4037c16dc87a9c7b7c56c2676a0a0247}{00214}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a4037c16dc87a9c7b7c56c2676a0a0247}{reference}} = \mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{value\_type}}\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00215}\mbox{\hyperlink{classkblib_1_1trie__qset_a4da9a231e62685f33c15f605212c7faa}{00215}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a4da9a231e62685f33c15f605212c7faa}{const\_reference}} = \textcolor{keyword}{const} \mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{value\_type}}\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00216}\mbox{\hyperlink{classkblib_1_1trie__qset_a47fae8487cb676a3641ea03187a6c807}{00216}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a47fae8487cb676a3641ea03187a6c807}{pointer}} = \mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{value\_type}}*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00217}\mbox{\hyperlink{classkblib_1_1trie__qset_afd915f7267b9d447712192b96a639698}{00217}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_afd915f7267b9d447712192b96a639698}{const\_pointer}} = \textcolor{keyword}{const} \mbox{\hyperlink{classkblib_1_1trie__qset_a8082d0c954680ec7e41e5c11dcf0f550}{value\_type}}*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00218}00218 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00219}\mbox{\hyperlink{classkblib_1_1trie__qset_ada297382b7a7a5cc91506f2812e23536}{00219}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_ada297382b7a7a5cc91506f2812e23536}{extractor}} = Extractor;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00220}\mbox{\hyperlink{classkblib_1_1trie__qset_a838bf89ecf6f728f343a25899854beb4}{00220}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__qset_a838bf89ecf6f728f343a25899854beb4}{key\_elem}} = \textcolor{keyword}{typename} extractor::value\_type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00221}\mbox{\hyperlink{classkblib_1_1trie__qset_a07ca16057442b483df0a994152280ad7}{00221}}    \mbox{\hyperlink{tdecl_8h_ab79256916a9652cd2d1771ae9a38799f}{KBLIB\_CONSTANT\_M}} std::size\_t key\_elem\_cardinality}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00222}00222        = extractor::key\_cardinality;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00223}00223 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00224}00224  \textcolor{keyword}{private}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00225}00225    \textcolor{comment}{// Bitset stores leaf status, array holds jumps, 0 represents no jump (leaf}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00226}00226    \textcolor{comment}{// or no entry)}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00227}00227    \textcolor{keyword}{using }row\_type = std::pair<std::bitset<key\_elem\_cardinality>,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00228}00228                               std::array<offset\_type, key\_elem\_cardinality>>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00229}00229    std::vector<row\_type> data\_;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00230}00230 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00231}00231 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00232}00232 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Extractor = default\_extract<Key>,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00233}00233           \textcolor{keyword}{typename} offset\_type = std::ptrdiff\_t>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00234}\mbox{\hyperlink{classkblib_1_1trie__set}{00234}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie__set}{trie\_set}} \{}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00235}00235  \textcolor{keyword}{public}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00236}\mbox{\hyperlink{classkblib_1_1trie__set_ab6b130b92ceb1051826f3ad10c6603b0}{00236}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_ab6b130b92ceb1051826f3ad10c6603b0}{key\_type}} = Key;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00237}\mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{00237}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{value\_type}} = Key;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00238}\mbox{\hyperlink{classkblib_1_1trie__set_a5eca53f887167988d7d0aea4b46f3796}{00238}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a5eca53f887167988d7d0aea4b46f3796}{size\_type}} = std::size\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00239}\mbox{\hyperlink{classkblib_1_1trie__set_a9e31a76b63974a64fce6df5f4cae2011}{00239}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a9e31a76b63974a64fce6df5f4cae2011}{difference\_type}} = std::ptrdiff\_t;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00240}00240 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00241}\mbox{\hyperlink{classkblib_1_1trie__set_a0cf23804faa3c86bb3c217b1bb7f8d24}{00241}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a0cf23804faa3c86bb3c217b1bb7f8d24}{reference}} = \mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{value\_type}}\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00242}\mbox{\hyperlink{classkblib_1_1trie__set_a504281b7fc17ee4bc6cddc52e7aa2c23}{00242}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a504281b7fc17ee4bc6cddc52e7aa2c23}{const\_reference}} = \textcolor{keyword}{const} \mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{value\_type}}\&;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00243}\mbox{\hyperlink{classkblib_1_1trie__set_a444bef25549d764b6df9ab9a30bc8e25}{00243}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a444bef25549d764b6df9ab9a30bc8e25}{pointer}} = \mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{value\_type}}*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00244}\mbox{\hyperlink{classkblib_1_1trie__set_a6e61f910c2054ddaad133fa138f8d9c9}{00244}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a6e61f910c2054ddaad133fa138f8d9c9}{const\_pointer}} = \textcolor{keyword}{const} \mbox{\hyperlink{classkblib_1_1trie__set_aa9d5de4ff55c464b52f4747e71bddfba}{value\_type}}*;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00245}00245 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00246}\mbox{\hyperlink{classkblib_1_1trie__set_a340aaea03dc8d898847b5b4c2fcfa627}{00246}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_a340aaea03dc8d898847b5b4c2fcfa627}{extractor}} = Extractor;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00247}\mbox{\hyperlink{classkblib_1_1trie__set_aa747bc386d628e7d94de0686a060efab}{00247}}    \textcolor{keyword}{using }\mbox{\hyperlink{classkblib_1_1trie__set_aa747bc386d628e7d94de0686a060efab}{key\_elem}} = \textcolor{keyword}{typename} extractor::value\_type;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00248}\mbox{\hyperlink{classkblib_1_1trie__set_a340cae6993e4af290d905683fa5e008a}{00248}}    \mbox{\hyperlink{tdecl_8h_ab79256916a9652cd2d1771ae9a38799f}{KBLIB\_CONSTANT\_M}} std::size\_t key\_elem\_cardinality}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00249}00249        = extractor::key\_cardinality;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00250}00250 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00251}00251  \textcolor{keyword}{private}:}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00252}00252    \textcolor{comment}{// offset 0 represents no jump (leaf or no entry)}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00253}00253    \textcolor{keyword}{using }row\_type = std::array<std::pair<std::optional<Key>, offset\_type>,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00254}00254                                key\_elem\_cardinality>;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00255}00255    std::vector<row\_type> data\_;}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00256}00256 \};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00257}00257 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00258}00258 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Value,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00259}00259           \textcolor{keyword}{typename} Extractor = \mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract<Key>}},}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00260}00260           \textcolor{keyword}{typename} offset\_type = std::ptrdiff\_t,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00261}00261           \textcolor{keyword}{template} <\textcolor{keyword}{typename}> \textcolor{keyword}{typename} SequenceContainer = std::vector>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00262}\mbox{\hyperlink{classkblib_1_1trie__map}{00262}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie__map}{trie\_map}} \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00263}00263 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Value,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00264}00264           \textcolor{keyword}{typename} Extractor = \mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract<Key>}},}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00265}00265           \textcolor{keyword}{typename} offset\_type = std::ptrdiff\_t,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00266}00266           \textcolor{keyword}{template} <\textcolor{keyword}{typename}> \textcolor{keyword}{typename} SequenceContainer = std::vector>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00267}\mbox{\hyperlink{classkblib_1_1trie__qmap}{00267}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1trie__qmap}{trie\_qmap}} \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00268}00268 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00269}00269 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Extractor = default\_extract<Key>>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00270}\mbox{\hyperlink{classkblib_1_1sparse__trie__set}{00270}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1sparse__trie__set}{sparse\_trie\_set}} \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00271}00271 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00272}00272 \textcolor{keyword}{template} <\textcolor{keyword}{typename} Key, \textcolor{keyword}{typename} Value,}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00273}00273           \textcolor{keyword}{typename} Extractor = \mbox{\hyperlink{structkblib_1_1default__extract}{default\_extract<Key>}}>}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00274}\mbox{\hyperlink{classkblib_1_1sparse__trie__map}{00274}} \textcolor{keyword}{class }\mbox{\hyperlink{classkblib_1_1sparse__trie__map}{sparse\_trie\_map}} \{\};}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00275}00275 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00276}00276 \} \textcolor{comment}{// namespace KBLIB\_NS}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00277}00277 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00278}00278 \textcolor{preprocessor}{\#endif }\textcolor{comment}{// KBLIB\_USE\_CXX17}}
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00279}00279 }
\DoxyCodeLine{\Hypertarget{trie_8h_source_l00280}00280 \textcolor{preprocessor}{\#endif }\textcolor{comment}{// TRIE\_H}}

\end{DoxyCode}