mdds
Loading...
Searching...
No Matches
trie_map_itr.hpp
1// SPDX-FileCopyrightText: 2016 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include <utility>
8#include <cassert>
9#include <iostream>
10#ifdef MDDS_TRIE_MAP_DEBUG
11#include <sstream>
12#endif
13
14#include "mdds/global.hpp"
15#include "mdds/ref_pair.hpp"
16
17namespace mdds { namespace trie { namespace detail {
18
19enum class iterator_type
20{
25 normal,
31 end,
37 empty
38};
39
40enum empty_iterator_type
41{
42 empty_iterator
43};
44
45template<typename TrieType, typename C>
47
48template<typename TrieType>
49struct get_node_stack_type<TrieType, std::true_type>
50{
51 using type = typename TrieType::const_node_stack_type;
52};
53
54template<typename TrieType>
55struct get_node_stack_type<TrieType, std::false_type>
56{
57 using type = typename TrieType::node_stack_type;
58};
59
60template<typename TrieType>
61class search_results;
62
63template<typename TrieType, bool IsConst>
64class iterator_base
65{
66protected:
67 using trie_type = TrieType;
68
69 using is_const_type = std::bool_constant<IsConst>;
70
71 friend trie_type;
73
74 using node_stack_type = typename get_node_stack_type<trie_type, is_const_type>::type;
75 using trie_node_type = mdds::detail::const_t<typename trie_type::trie_node, IsConst>;
76 using trie_node_child_pos_type = typename mdds::detail::get_iterator_type<
77 typename std::remove_const<trie_node_type>::type::children_type, is_const_type>::type;
78
79 using key_type = typename trie_type::key_type;
81
82public:
83 // iterator traits
84 using value_type = mdds::ref_pair<typename std::add_const<key_type>::type, trie_value_type>;
85 using pointer = value_type*;
86 using reference = value_type&;
87 using difference_type = std::ptrdiff_t;
88 using iterator_category = std::bidirectional_iterator_tag;
89
90protected:
91 node_stack_type m_node_stack;
92 key_type m_buffer;
93 key_type m_current_key;
94 trie_value_type* m_current_value_ptr;
95 iterator_type m_type;
96
97 static trie_node_type* push_child_node_to_stack(
98 node_stack_type& node_stack, key_type& buf, trie_node_child_pos_type& child_pos)
99 {
100 trie_node_type* node = &child_pos->second;
101 buf.push_back(child_pos->first);
102 node_stack.emplace_back(node, node->children.begin());
103
104 return node;
105 }
106
111 static trie_node_type* descend_to_previus_leaf_node(node_stack_type& node_stack, key_type& buf)
112 {
113 trie_node_type* cur_node = nullptr;
114
115 do
116 {
117 // Keep moving down on the right-most child nodes until the
118 // leaf node is reached.
119
120 auto& si = node_stack.back();
121
122 --si.child_pos;
123 buf.push_back(si.child_pos->first);
124 cur_node = &si.child_pos->second;
125 node_stack.emplace_back(cur_node, cur_node->children.end());
126 } while (!cur_node->children.empty());
127
128 return cur_node;
129 }
130
131 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
132 {}
133
134public:
135 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
136 {}
137
138 iterator_base(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
139 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_current_key(m_buffer),
140 m_current_value_ptr(&m_node_stack.back().node->value), m_type(type)
141 {}
142
143 bool operator==(const iterator_base& other) const
144 {
145 if (m_type != other.m_type)
146 return false;
147
148 if (m_type == iterator_type::empty)
149 return true;
150
151 return m_node_stack.back() == other.m_node_stack.back();
152 }
153
154 value_type operator*()
155 {
156 return value_type(m_current_key, *m_current_value_ptr);
157 }
158
159 value_type operator->()
160 {
161 return value_type(m_current_key, *m_current_value_ptr);
162 }
163
164 iterator_base& operator++()
165 {
166 trie_node_type* cur_node = m_node_stack.back().node;
167
168 do
169 {
170 if (cur_node->children.empty())
171 {
172 // Current node is a leaf node. Keep moving up the stack until we
173 // reach a parent node with unvisited children.
174
175 while (true)
176 {
177 if (m_node_stack.size() == 1)
178 {
179#ifdef MDDS_TRIE_MAP_DEBUG
180 if (m_type == iterator_type::end)
181 {
182 std::ostringstream os;
183 os << "iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
184 throw general_error(os.str());
185 }
186#endif
187 // We've reached the end position. Bail out.
188 m_type = iterator_type::end;
189 return *this;
190 }
191
192 // Move up one parent and see if it has an unvisited child node.
193 m_buffer.pop_back();
194 m_node_stack.pop_back();
195 auto& si = m_node_stack.back();
196 ++si.child_pos;
197
198 if (si.child_pos != si.node->children.end())
199 {
200 // Move down to this unvisited child node.
201 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
202 break;
203 }
204 }
205 }
206 else
207 {
208 // Current node has child nodes. Follow the first child node.
209 auto child_pos = cur_node->children.begin();
210 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
211 }
212 } while (!cur_node->has_value);
213
214 m_current_key = m_buffer;
215 m_current_value_ptr = &cur_node->value;
216 return *this;
217 }
218
219 iterator_base operator++(int)
220 {
221 iterator_base tmp(*this);
222 operator++();
223 return tmp;
224 }
225
226 iterator_base& operator--()
227 {
228 trie_node_type* cur_node = m_node_stack.back().node;
229
230 if (m_type == iterator_type::end && cur_node->has_value)
231 {
232 assert(m_node_stack.size() == 1);
233 m_type = iterator_type::normal;
234 }
235 else if (m_node_stack.size() == 1)
236 {
237 // This is the end position aka root node. Move down to the
238 // right-most leaf node.
239 auto& si = m_node_stack.back();
240 assert(si.child_pos == cur_node->children.end());
241 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
242 m_type = iterator_type::normal;
243 }
244 else if (cur_node->children.empty())
245 {
246 // This is a leaf node. Keep going up until it finds a parent
247 // node with unvisited child nodes on the left side, then descend
248 // on that path all the way to its leaf.
249
250 do
251 {
252 // Go up one node.
253
254 m_buffer.pop_back();
255 m_node_stack.pop_back();
256 auto& si = m_node_stack.back();
257 cur_node = si.node;
258
259 if (si.child_pos != cur_node->children.begin())
260 {
261 // Left and down.
262 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
263 assert(cur_node->has_value);
264 }
265 } while (!cur_node->has_value);
266 }
267 else
268 {
269 // Non-leaf node with value. Keep going up until either the root
270 // node or another node with value is reached.
271
272 assert(cur_node->has_value);
273 assert(m_node_stack.back().child_pos == cur_node->children.begin());
274
275 do
276 {
277 // Go up.
278 m_buffer.pop_back();
279 m_node_stack.pop_back();
280 auto& si = m_node_stack.back();
281 cur_node = si.node;
282
283 if (m_node_stack.size() == 1)
284 {
285 // Root node reached. Left and down.
286 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
287 assert(cur_node->has_value);
288 }
289 } while (!cur_node->has_value);
290 }
291
292 assert(cur_node->has_value);
293 m_current_key = m_buffer;
294 m_current_value_ptr = &cur_node->value;
295 return *this;
296 }
297
298 iterator_base operator--(int)
299 {
300 iterator_base tmp(*this);
301 operator--();
302 return tmp;
303 }
304};
305
306template<typename TrieType>
307class const_iterator;
308
309template<typename TrieType>
310class iterator : public iterator_base<TrieType, false>
311{
312 using trie_type = TrieType;
313
314 friend trie_type;
317
318 using base_type = iterator_base<trie_type, false>;
319 using node_stack_type = typename base_type::node_stack_type;
320 using key_type = typename base_type::key_type;
321
322 iterator(empty_iterator_type t) : base_type(t)
323 {}
324
325public:
326 iterator() : base_type()
327 {}
328
329 iterator(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
330 : base_type(std::move(node_stack), std::move(buf), type)
331 {}
332};
333
334template<typename TrieType>
335class const_iterator : public iterator_base<TrieType, true>
336{
337 using trie_type = TrieType;
338
339 friend trie_type;
341
342 using base_type = iterator_base<trie_type, true>;
343 using node_stack_type = typename base_type::node_stack_type;
344 using key_type = typename base_type::key_type;
345
346 using base_type::m_buffer;
347 using base_type::m_current_key;
348 using base_type::m_current_value_ptr;
349 using base_type::m_node_stack;
350 using base_type::m_type;
351
352 const_iterator(empty_iterator_type t) : base_type(t)
353 {}
354
355public:
356 const_iterator() : base_type()
357 {}
358
359 const_iterator(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
360 : base_type(std::move(node_stack), std::move(buf), type)
361 {}
362
363 const_iterator(const iterator<TrieType>& it) : base_type()
364 {
365 m_buffer = it.m_buffer;
366 m_current_key = it.m_current_key;
367 m_current_value_ptr = it.m_current_value_ptr;
368 m_type = it.m_type;
369
370 for (const auto& e : it.m_node_stack)
371 m_node_stack.emplace_back(e.node, e.child_pos);
372 }
373};
374
375template<typename TrieType>
376bool operator==(const iterator<TrieType>& left, const const_iterator<TrieType>& right)
377{
378 return const_iterator<TrieType>(left) == right;
379}
380
381template<typename TrieType>
382bool operator==(const const_iterator<TrieType>& left, const iterator<TrieType>& right)
383{
384 return left == const_iterator<TrieType>(right);
385}
386
387template<typename TrieType>
388class search_results
389{
390 using trie_type = TrieType;
391 friend trie_type;
392 using node_stack_type = typename trie_type::const_node_stack_type;
393
394 using trie_node = typename trie_type::trie_node;
395 using key_type = typename trie_type::key_type;
396 using key_unit_type = typename key_type::value_type;
397
398 const trie_node* m_node;
399 key_type m_buffer;
400 node_stack_type m_node_stack;
401
402 search_results(const trie_node* node, key_type&& buf) : m_node(node), m_buffer(std::move(buf))
403 {}
404
405public:
406 using const_iterator = typename trie_type::const_iterator;
407
408 const_iterator begin() const
409 {
410 if (!m_node)
411 // empty results.
412 return const_iterator(empty_iterator);
413
414 // Push the root node.
415 key_type buf(m_buffer);
416 node_stack_type node_stack;
417 node_stack.emplace_back(m_node, m_node->children.begin());
418
419 while (!node_stack.back().node->has_value)
420 {
421 // There should always be at least one value node along the
422 // left-most branch.
423
424 auto it = node_stack.back().child_pos;
425 const_iterator::push_child_node_to_stack(node_stack, buf, it);
426 }
427
428 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
429 }
430
431 const_iterator end() const
432 {
433 if (!m_node)
434 // empty results.
435 return const_iterator(empty_iterator);
436
437 node_stack_type node_stack;
438 node_stack.emplace_back(m_node, m_node->children.end());
439 return const_iterator(std::move(node_stack), key_type(m_buffer), iterator_type::end);
440 }
441};
442
443template<typename TrieType>
445
446template<typename TrieT>
447class packed_iterator_base
448{
449 using trie_type = TrieT;
450 friend trie_type;
452
453 using stack_item = typename trie_type::stack_item;
454 using node_stack_type = typename trie_type::node_stack_type;
455
456 using key_type = typename trie_type::key_type;
457 using size_type = typename trie_type::size_type;
458 using trie_value_type = typename trie_type::value_type;
459 using value_store_type = typename trie_type::value_store_type;
460 using pack_value_type = typename trie_type::pack_value_type;
461 using key_unit_type = typename key_type::value_type;
462
463public:
464 // iterator traits
465 using value_type = mdds::ref_pair<std::add_const_t<key_type>, std::add_const_t<trie_value_type>>;
466 using pointer = value_type*;
467 using reference = value_type&;
468 using difference_type = std::ptrdiff_t;
469 using iterator_category = std::bidirectional_iterator_tag;
470
471private:
472 const value_store_type* m_value_store = nullptr;
473 node_stack_type m_node_stack;
474 key_type m_buffer;
475 pack_value_type m_current_value = trie_type::null_value;
476 iterator_type m_type;
477
482 static void push_child_node_to_stack(
483 const value_store_type* value_store, node_stack_type& node_stack, key_type& buf,
484 const pack_value_type* child_pos)
485 {
486 assert(value_store);
487 const auto* node_pos = node_stack.back().node_pos;
488
489 key_unit_type c = static_cast<key_unit_type>(*child_pos);
490 buf.push_back(c);
491 ++child_pos;
492 auto offset = static_cast<size_type>(*child_pos);
493 node_pos -= offset; // Jump to the head of the child node.
494 const auto* p = node_pos;
495 ++p;
496 size_type index_size = *p;
497 ++p;
498 child_pos = p;
499 const auto* child_end = child_pos + index_size;
500
501 // Push it onto the stack.
502 node_stack.emplace_back(value_store, node_pos, child_pos, child_end);
503 }
504
505 static void descend_to_previous_leaf_node(node_stack_type& node_stack, key_type& buf)
506 {
507 const pack_value_type* node_pos = nullptr;
508 size_t index_size = 0;
509
510 do
511 {
512 // Keep moving down on the right-most child nodes until the
513 // leaf node is reached.
514
515 stack_item* si = &node_stack.back();
516 node_pos = si->node_pos;
517 --si->child_pos;
518 size_t offset = *si->child_pos;
519 --si->child_pos;
520 key_unit_type c = *si->child_pos;
521 node_pos -= offset; // Jump to the head of the child node.
522 buf.push_back(c);
523
524 const auto* p = node_pos;
525 ++p;
526 index_size = *p;
527 ++p;
528 const auto* child_pos = p;
529 const auto* child_end = child_pos + index_size;
530 node_stack.emplace_back(node_stack.back().value_store, node_pos, child_end, child_end);
531 } while (index_size);
532 }
533
534 packed_iterator_base(empty_iterator_type) : m_type(iterator_type::empty)
535 {}
536
537public:
538 packed_iterator_base() : m_type(iterator_type::normal)
539 {}
540
541 packed_iterator_base(
542 const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf, pack_value_type pos)
543 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
544 m_current_value(pos), m_type(iterator_type::normal)
545 {}
546
547 packed_iterator_base(const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf)
548 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
549 m_type(iterator_type::end)
550 {}
551
552 bool operator==(const packed_iterator_base& other) const
553 {
554 if (m_type != other.m_type)
555 return false;
556
557 if (m_type == iterator_type::empty)
558 return true;
559
560 return m_node_stack.back() == other.m_node_stack.back();
561 }
562
563 value_type operator*()
564 {
565 assert(m_value_store);
566 assert(m_current_value != trie_type::null_value);
567 return value_type(m_buffer, (*m_value_store)[m_current_value]);
568 }
569
570 value_type operator->()
571 {
572 assert(m_value_store);
573 assert(m_current_value != trie_type::null_value);
574 return value_type(m_buffer, (*m_value_store)[m_current_value]);
575 }
576
577 packed_iterator_base& operator++()
578 {
579 stack_item* si = &m_node_stack.back();
580 pack_value_type v = trie_type::null_value;
581 size_t index_size = *(si->node_pos + 1);
582
583 do
584 {
585 if (!index_size)
586 {
587 // Current node is a leaf node. Keep moving up the stack until we
588 // reach a parent node with unvisited children.
589
590 while (true)
591 {
592 if (m_node_stack.size() == 1)
593 {
594#ifdef MDDS_TRIE_MAP_DEBUG
595 if (m_type == iterator_type::end)
596 {
597 std::ostringstream os;
598 os << "packed_iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
599 throw general_error(os.str());
600 }
601#endif
602 // We've reached the end position. Bail out.
603 m_type = iterator_type::end;
604 return *this;
605 }
606
607 // Move up one parent and see if it has an unvisited child node.
608 m_buffer.pop_back();
609 m_node_stack.pop_back();
610 si = &m_node_stack.back();
611 std::advance(si->child_pos, 2);
612
613 if (si->child_pos != si->child_end)
614 {
615 // Move down to this unvisited child node.
616 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
617 break;
618 }
619 }
620 }
621 else
622 {
623 // Current node has child nodes. Follow the first child node.
624 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
625 }
626
627 si = &m_node_stack.back();
628 v = *si->node_pos;
629 index_size = *(si->node_pos + 1);
630 } while (v == trie_type::null_value);
631
632 assert(v != trie_type::null_value);
633 m_current_value = v;
634
635 return *this;
636 }
637
638 packed_iterator_base operator++(int)
639 {
640 packed_iterator_base tmp(*this);
641 operator++();
642 return tmp;
643 }
644
645 packed_iterator_base& operator--()
646 {
647 stack_item* si = &m_node_stack.back();
648 pack_value_type v = *si->node_pos;
649 size_t index_size = *(si->node_pos + 1); // index size for child nodes.
650
651 if (m_type == iterator_type::end && v != trie_type::null_value)
652 {
653 assert(m_node_stack.size() == 1);
654 m_type = iterator_type::normal;
655 }
656 else if (m_node_stack.size() == 1)
657 {
658 // This is the end position aka root node. Move down to the
659 // right-most leaf node.
660 assert(si->child_pos == si->child_end);
661 descend_to_previous_leaf_node(m_node_stack, m_buffer);
662 si = &m_node_stack.back();
663 v = *si->node_pos;
664 m_type = iterator_type::normal;
665 }
666 else if (!index_size)
667 {
668 // This is a leaf node. Keep going up until it finds a parent
669 // node with unvisited child nodes on the left side, then descend
670 // on that path all the way to its leaf.
671
672 do
673 {
674 // Go up one node.
675
676 m_buffer.pop_back();
677 m_node_stack.pop_back();
678 si = &m_node_stack.back();
679 const auto* p = si->node_pos;
680 v = *p;
681 ++p;
682 index_size = *p;
683 ++p;
684 const auto* first_child = p;
685
686 if (si->child_pos != first_child)
687 {
688 // Left and down.
689 descend_to_previous_leaf_node(m_node_stack, m_buffer);
690 si = &m_node_stack.back();
691 p = si->node_pos;
692 v = *p;
693 assert(v != trie_type::null_value);
694 }
695 } while (v == trie_type::null_value);
696 }
697 else
698 {
699 // Non-leaf node with value. Keep going up until either the root
700 // node or another node with value is reached.
701
702 assert(*si->node_pos); // this node should have a value.
703 assert(si->child_pos == (si->node_pos + 2));
704
705 do
706 {
707 // Go up.
708 m_buffer.pop_back();
709 m_node_stack.pop_back();
710 si = &m_node_stack.back();
711 v = *si->node_pos;
712
713 if (m_node_stack.size() == 1)
714 {
715 // Root node reached.
716 descend_to_previous_leaf_node(m_node_stack, m_buffer);
717 si = &m_node_stack.back();
718 v = *si->node_pos;
719 assert(v != trie_type::null_value);
720 }
721 } while (v == trie_type::null_value);
722 }
723
724 assert(v != trie_type::null_value);
725 m_current_value = v;
726
727 return *this;
728 }
729
730 packed_iterator_base operator--(int)
731 {
732 packed_iterator_base tmp(*this);
733 operator--();
734 return tmp;
735 }
736};
737
738template<typename TrieType>
739class packed_search_results
740{
741 using trie_type = TrieType;
742 friend trie_type;
743 using node_stack_type = typename trie_type::node_stack_type;
744 using value_store_type = typename trie_type::value_store_type;
745 using pack_value_type = typename trie_type::pack_value_type;
746
747 using key_type = typename trie_type::key_type;
748 using key_unit_type = typename key_type::value_type;
749
750 const value_store_type* m_value_store = nullptr;
751 const pack_value_type* m_node = nullptr;
752 key_type m_buffer;
753
754 packed_search_results(const value_store_type* value_store, const pack_value_type* node, key_type&& buf)
755 : m_value_store(value_store), m_node(node), m_buffer(std::move(buf))
756 {
757 assert(m_value_store);
758 }
759
760 node_stack_type get_root_node() const
761 {
762 const auto* p = m_node;
763 ++p;
764 size_t index_size = *p;
765 ++p;
766 const auto* child_pos = p;
767 const auto* child_end = child_pos + index_size;
768
769 // Push this child node onto the stack.
770 node_stack_type node_stack;
771 node_stack.emplace_back(m_value_store, m_node, child_pos, child_end);
772 return node_stack;
773 }
774
775 void swap(packed_search_results& other)
776 {
777 std::swap(m_node, other.m_node);
778 std::swap(m_buffer, other.m_buffer);
779 }
780
781public:
782 using const_iterator = packed_iterator_base<trie_type>;
783
784 packed_search_results() : m_node(nullptr)
785 {}
786
787 packed_search_results(const packed_search_results& other) : m_node(other.m_node), m_buffer(other.m_buffer)
788 {}
789
790 packed_search_results(packed_search_results&& other) : m_node(other.m_node), m_buffer(std::move(other.m_buffer))
791 {
792 other.m_node = nullptr;
793 }
794
795 packed_search_results& operator=(packed_search_results other)
796 {
797 packed_search_results tmp(std::move(other));
798 swap(tmp);
799 return *this;
800 }
801
802 const_iterator begin() const
803 {
804 if (!m_node)
805 // empty results.
806 return const_iterator(empty_iterator);
807
808 // Push the root node.
809 key_type buf(m_buffer);
810 node_stack_type node_stack = get_root_node();
811
812 while (!node_stack.back().has_value())
813 {
814 // There should always be at least one value node along the
815 // left-most branch.
816
817 const_iterator::push_child_node_to_stack(m_value_store, node_stack, buf, node_stack.back().child_pos);
818 }
819
820 return const_iterator(m_value_store, std::move(node_stack), std::move(buf), node_stack.back().get_value_pos());
821 }
822
823 const_iterator end() const
824 {
825 if (!m_node)
826 // empty results.
827 return const_iterator(empty_iterator);
828
829 node_stack_type node_stack = get_root_node();
830 auto& si = node_stack.back();
831 si.child_pos = si.child_end;
832 return const_iterator(m_value_store, std::move(node_stack), key_type(m_buffer));
833 }
834};
835
836}}} // namespace mdds::trie::detail
Definition global.hpp:54
Definition trie_map_itr.hpp:336
Definition trie_map_itr.hpp:65
static trie_node_type * descend_to_previus_leaf_node(node_stack_type &node_stack, key_type &buf)
Definition trie_map_itr.hpp:111
Definition trie_map_itr.hpp:311
Definition trie_map_itr.hpp:448
Definition trie_map_itr.hpp:740
Definition trie_map_itr.hpp:389
Definition global.hpp:104
Definition global.hpp:140
Definition ref_pair.hpp:24
Definition trie_map_itr.hpp:46