kblib 0.2.3
General utilities library for modern C++
trie.h
Go to the documentation of this file.
1/* *****************************************************************************
2 * kblib is a general utility library for C++14 and C++17, intended to provide
3 * performant high-level abstractions and more expressive ways to do simple
4 * things.
5 *
6 * Copyright (c) 2021 killerbee
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 * ****************************************************************************/
21
31#ifndef TRIE_H
32#define TRIE_H
33
34#include "tdecl.h"
35
36#if KBLIB_USE_CXX17
37
38# include "sort.h"
39# include "traits.h"
40
41# include <array>
42# include <bitset>
43# include <vector>
44
45namespace KBLIB_NS {
46
47enum class extractor_policy {
50};
51
52template <typename Container>
54 using value_type =
55 typename std::remove_cv<typename std::remove_reference<decltype(
56 *begin(std::declval<Container&>()))>::type>::type;
57};
58
59template <typename Container>
61 using value_type =
62 typename std::remove_cv<typename std::remove_reference<decltype(
63 std::declval<Container&>()[0])>::type>::type;
64
65 template <typename index_type>
66 KBLIB_NODISCARD constexpr static auto subscript(
67 Container&& c, index_type index) noexcept(noexcept(c[index]))
68 -> decltype(auto) {
69 return c[index];
70 }
71};
72
73template <typename Container, typename = void>
75 constexpr static extractor_policy value
76 = extractor_policy::forward_iteration;
77};
78
79template <typename Container>
80struct extractor_policy_for<Container,
81 void_t<decltype(std::declval<Container>()[0])>> {
82 constexpr static extractor_policy value = extractor_policy::random_access;
83};
84
85template <typename Container>
86using default_extractor_t = typename std::conditional<
87 extractor_policy_for<Container>::value == extractor_policy::random_access,
89
90namespace detail {
91
92 template <typename Elem, typename Value>
93 struct node {};
94
95} // namespace detail
96
97template <typename Key, typename T,
98 typename Extractor = default_extractor_t<Key>,
100class trie {
101 public:
102 using key_type = Key;
103 using mapped_type = T;
104 using value_type = std::pair<key_type, mapped_type>;
105 using extractor = Extractor;
107
108 using size_type = std::size_t;
109 using difference_type = std::ptrdiff_t;
110 using reference = T&;
111 using const_reference = const T&;
112 using pointer = T*;
113 using const_pointer = const T*;
114
115 using iterator = void;
116 using const_iterator = void;
117 using reverse_iterator = std::reverse_iterator<iterator>;
118 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
119
120 private:
121 std::unique_ptr<node_type> root;
122
123 public:
124};
125
126template <typename KeyElem, typename T, typename Extractor>
127class trie<KeyElem, T, Extractor, false> {};
128
129template <typename KeyElem, typename T, typename Extractor>
130class trie<KeyElem[], T, Extractor, false> {};
131
132// Array-mapped tries are better for denser sets
133// Tree-based tries are better for sparser sets
134
135// trie_map and trie_set are mostly API compatible with std::map, std::set
136// trie_qmap and trie_qset use proxy iterators to avoid having to store Keys
137// (saves memory, less compatible with stdlib)
138
139template <typename Key, typename = void>
141
142template <typename Key>
143struct default_extract<Key, void_if_t<is_linear_container_v<Key>>> {
144 using value_type = typename Key::value_type;
145 static_assert(static_cast<value_type>(max) < static_cast<std::size_t>(max),
146 "Key too large to index array");
147 // won't overflow because of above assertion
148 KBLIB_CONSTANT_M std::size_t key_cardinality
149 = static_cast<value_type>(max) + std::size_t{1};
150 static_assert(std::is_integral<value_type>::value,
151 "Key elements must be integral");
152
153 KBLIB_NODISCARD static constexpr auto begin(Key& key) noexcept(
154 noexcept(key.begin())) -> decltype(auto) {
155 return key.begin();
156 }
157 KBLIB_NODISCARD static constexpr auto end(Key& key) noexcept(
158 noexcept(key.end())) -> decltype(auto) {
159 return key.end();
160 }
161 KBLIB_NODISCARD static constexpr auto index(
162 Key& key, std::size_t idx) noexcept(noexcept(key[idx]))
163 -> decltype(auto) {
164 return key[idx];
165 }
166};
167
168template <typename KeyElem>
169struct default_extract<KeyElem[], void_if_t<std::is_integral_v<KeyElem>>> {
170 using value_type = KeyElem;
171 static_assert(static_cast<value_type>(max) < static_cast<std::size_t>(max),
172 "Key too large to index array");
173 // won't overflow because of above assertion
174 KBLIB_CONSTANT_M std::size_t key_cardinality
175 = static_cast<value_type>(max) + std::size_t{1};
176 static_assert(std::is_integral<value_type>::value,
177 "Key elements must be integral");
178
179 template <std::size_t Size>
180 KBLIB_NODISCARD static constexpr auto begin(KeyElem (&key)[Size]) noexcept(
181 noexcept(std::begin(key))) -> decltype(auto) {
182 return std::begin(key);
183 }
184 template <std::size_t Size>
185 KBLIB_NODISCARD static constexpr auto end(KeyElem (&key)[Size]) noexcept(
186 noexcept(std::end(key))) -> decltype(auto) {
187 return std::end(key);
188 }
189 template <std::size_t Size>
190 KBLIB_NODISCARD static constexpr auto index(
191 KeyElem (&key)[Size], std::size_t idx) noexcept(noexcept(key[idx]))
192 -> decltype(auto) {
193 return key[idx];
194 }
195};
196
197template <typename Key>
198struct default_extract<Key, void_if_t<is_radix_sortable_v<Key>>>;
199
200// qset: does not store Keys (generates them on-demand)
201// Key: the type used for lookup
202// Extractor: controls how lookup is performed from the key
203// offset_type: used to represent jumps in the internal array. Must be a signed
204// integral type
205template <typename Key, typename Extractor = default_extract<Key>,
206 typename offset_type = std::ptrdiff_t>
208 public:
209 using key_type = Key;
210 using value_type = Key;
211 using size_type = std::size_t;
212 using difference_type = std::ptrdiff_t;
213
217 using const_pointer = const value_type*;
218
219 using extractor = Extractor;
220 using key_elem = typename extractor::value_type;
221 KBLIB_CONSTANT_M std::size_t key_elem_cardinality
222 = extractor::key_cardinality;
223
224 private:
225 // Bitset stores leaf status, array holds jumps, 0 represents no jump (leaf
226 // or no entry)
227 using row_type = std::pair<std::bitset<key_elem_cardinality>,
228 std::array<offset_type, key_elem_cardinality>>;
229 std::vector<row_type> data_;
230};
231
232template <typename Key, typename Extractor = default_extract<Key>,
233 typename offset_type = std::ptrdiff_t>
234class trie_set {
235 public:
236 using key_type = Key;
237 using value_type = Key;
238 using size_type = std::size_t;
239 using difference_type = std::ptrdiff_t;
240
244 using const_pointer = const value_type*;
245
246 using extractor = Extractor;
247 using key_elem = typename extractor::value_type;
248 KBLIB_CONSTANT_M std::size_t key_elem_cardinality
249 = extractor::key_cardinality;
250
251 private:
252 // offset 0 represents no jump (leaf or no entry)
253 using row_type = std::array<std::pair<std::optional<Key>, offset_type>,
254 key_elem_cardinality>;
255 std::vector<row_type> data_;
256};
257
258template <typename Key, typename Value,
259 typename Extractor = default_extract<Key>,
260 typename offset_type = std::ptrdiff_t,
261 template <typename> typename SequenceContainer = std::vector>
262class trie_map {};
263template <typename Key, typename Value,
264 typename Extractor = default_extract<Key>,
265 typename offset_type = std::ptrdiff_t,
266 template <typename> typename SequenceContainer = std::vector>
267class trie_qmap {};
268
269template <typename Key, typename Extractor = default_extract<Key>>
271
272template <typename Key, typename Value,
273 typename Extractor = default_extract<Key>>
275
276} // namespace KBLIB_NS
277
278#endif // KBLIB_USE_CXX17
279
280#endif // TRIE_H
Key key_type
Definition: trie.h:209
value_type & reference
Definition: trie.h:214
value_type * pointer
Definition: trie.h:216
const value_type & const_reference
Definition: trie.h:215
Key value_type
Definition: trie.h:210
typename extractor::value_type key_elem
Definition: trie.h:220
std::size_t size_type
Definition: trie.h:211
std::ptrdiff_t difference_type
Definition: trie.h:212
Extractor extractor
Definition: trie.h:219
const value_type * const_pointer
Definition: trie.h:217
value_type & reference
Definition: trie.h:241
Extractor extractor
Definition: trie.h:246
value_type * pointer
Definition: trie.h:243
const value_type & const_reference
Definition: trie.h:242
std::size_t size_type
Definition: trie.h:238
const value_type * const_pointer
Definition: trie.h:244
std::ptrdiff_t difference_type
Definition: trie.h:239
typename extractor::value_type key_elem
Definition: trie.h:247
Key value_type
Definition: trie.h:237
Key key_type
Definition: trie.h:236
Extractor extractor
Definition: trie.h:105
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: trie.h:118
T mapped_type
Definition: trie.h:103
T * pointer
Definition: trie.h:112
std::size_t size_type
Definition: trie.h:108
T & reference
Definition: trie.h:110
const T * const_pointer
Definition: trie.h:113
std::reverse_iterator< iterator > reverse_iterator
Definition: trie.h:117
void iterator
Definition: trie.h:115
const T & const_reference
Definition: trie.h:111
std::ptrdiff_t difference_type
Definition: trie.h:109
Key key_type
Definition: trie.h:102
void const_iterator
Definition: trie.h:116
std::pair< key_type, mapped_type > value_type
Definition: trie.h:104
typename make_void< Ts... >::type void_t
Definition: fakestd.h:186
constexpr struct kblib::nums::max_t max
typename std::conditional< extractor_policy_for< Container >::value==extractor_policy::random_access, indexer_extractor< Container >, iterator_extractor< Container > >::type default_extractor_t
Definition: trie.h:88
extractor_policy
Definition: trie.h:47
typename void_if< b >::type void_if_t
Definition: fakestd.h:520
constexpr bool is_radix_sortable_v
Definition: sort.h:240
Definition: bits.h:721
{WIP} Provides a fast and generic sorting interface.
static constexpr auto begin(Key &key) noexcept(noexcept(key.begin())) -> decltype(auto)
Definition: trie.h:153
static constexpr auto end(Key &key) noexcept(noexcept(key.end())) -> decltype(auto)
Definition: trie.h:157
static constexpr auto index(Key &key, std::size_t idx) noexcept(noexcept(key[idx])) -> decltype(auto)
Definition: trie.h:161
static constexpr auto end(KeyElem(&key)[Size]) noexcept(noexcept(std::end(key))) -> decltype(auto)
Definition: trie.h:185
static constexpr auto begin(KeyElem(&key)[Size]) noexcept(noexcept(std::begin(key))) -> decltype(auto)
Definition: trie.h:180
static constexpr auto index(KeyElem(&key)[Size], std::size_t idx) noexcept(noexcept(key[idx])) -> decltype(auto)
Definition: trie.h:190
static constexpr auto subscript(Container &&c, index_type index) noexcept(noexcept(c[index])) -> decltype(auto)
Definition: trie.h:66
typename std::remove_cv< typename std::remove_reference< decltype(*begin(std::declval< Container & >()))>::type >::type value_type
Definition: trie.h:56
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_NS
Definition: tdecl.h:113
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:129
#define KBLIB_CONSTANT_M
Definition: tdecl.h:139
Contains some type traits not in the standard library that are useful in the implementation of kblib.