mdds
trie_map_itr.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2016-2020 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef INCLUDED_MDDS_TRIE_MAP_ITR_HPP
29#define INCLUDED_MDDS_TRIE_MAP_ITR_HPP
30
31#include <utility>
32#include <cassert>
33#include <iostream>
34#ifdef MDDS_TRIE_MAP_DEBUG
35#include <sstream>
36#endif
37
38#include "mdds/global.hpp"
39#include "mdds/ref_pair.hpp"
40
41namespace mdds { namespace trie { namespace detail {
42
43enum class iterator_type
44{
49 normal,
55 end,
61 empty
62};
63
64enum empty_iterator_type
65{
66 empty_iterator
67};
68
69template<typename _TrieType, typename _C>
71
72template<typename _TrieType>
73struct get_node_stack_type<_TrieType, std::true_type>
74{
75 using type = typename _TrieType::const_node_stack_type;
76};
77
78template<typename _TrieType>
79struct get_node_stack_type<_TrieType, std::false_type>
80{
81 using type = typename _TrieType::node_stack_type;
82};
83
84template<typename _TrieType>
85class search_results;
86
87template<typename _TrieType, bool IsConst>
89{
90protected:
91 using trie_type = _TrieType;
92
93 using _is_const = bool_constant<IsConst>;
94
95 friend trie_type;
97
98 using node_stack_type = typename get_node_stack_type<trie_type, _is_const>::type;
99 using trie_node_type = mdds::detail::const_t<typename trie_type::trie_node, IsConst>;
100 using trie_node_child_pos_type = typename mdds::detail::get_iterator_type<
101 typename std::remove_const<trie_node_type>::type::children_type, _is_const>::type;
102
103 using key_traits_type = typename trie_type::key_traits_type;
104 using key_type = typename key_traits_type::key_type;
105 using key_buffer_type = typename key_traits_type::key_buffer_type;
107
108public:
109 // iterator traits
111 using pointer = value_type*;
112 using reference = value_type&;
113 using difference_type = std::ptrdiff_t;
114 using iterator_category = std::bidirectional_iterator_tag;
115
116protected:
117 node_stack_type m_node_stack;
118 key_buffer_type m_buffer;
119 key_type m_current_key;
120 trie_value_type* m_current_value_ptr;
121 iterator_type m_type;
122
123 static trie_node_type* push_child_node_to_stack(
124 node_stack_type& node_stack, key_buffer_type& buf, trie_node_child_pos_type& child_pos)
125 {
126 using ktt = key_traits_type;
127
128 trie_node_type* node = &child_pos->second;
129 ktt::push_back(buf, child_pos->first);
130 node_stack.emplace_back(node, node->children.begin());
131
132 return node;
133 }
134
139 static trie_node_type* descend_to_previus_leaf_node(node_stack_type& node_stack, key_buffer_type& buf)
140 {
141 using ktt = key_traits_type;
142
143 trie_node_type* cur_node = nullptr;
144
145 do
146 {
147 // Keep moving down on the right-most child nodes until the
148 // leaf node is reached.
149
150 auto& si = node_stack.back();
151
152 --si.child_pos;
153 ktt::push_back(buf, si.child_pos->first);
154 cur_node = &si.child_pos->second;
155 node_stack.emplace_back(cur_node, cur_node->children.end());
156 } while (!cur_node->children.empty());
157
158 return cur_node;
159 }
160
161 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
162 {}
163
164public:
165 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
166 {}
167
168 iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf, iterator_type type)
169 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
170 m_current_key(key_traits_type::to_key(m_buffer)), m_current_value_ptr(&m_node_stack.back().node->value),
171 m_type(type)
172 {}
173
174 bool operator==(const iterator_base& other) const
175 {
176 if (m_type != other.m_type)
177 return false;
178
179 if (m_type == iterator_type::empty)
180 return true;
181
182 return m_node_stack.back() == other.m_node_stack.back();
183 }
184
185 bool operator!=(const iterator_base& other) const
186 {
187 return !operator==(other);
188 }
189
190 value_type operator*()
191 {
192 return value_type(m_current_key, *m_current_value_ptr);
193 }
194
195 value_type operator->()
196 {
197 return value_type(m_current_key, *m_current_value_ptr);
198 }
199
200 iterator_base& operator++()
201 {
202 using ktt = key_traits_type;
203
204 trie_node_type* cur_node = m_node_stack.back().node;
205
206 do
207 {
208 if (cur_node->children.empty())
209 {
210 // Current node is a leaf node. Keep moving up the stack until we
211 // reach a parent node with unvisited children.
212
213 while (true)
214 {
215 if (m_node_stack.size() == 1)
216 {
217#ifdef MDDS_TRIE_MAP_DEBUG
218 if (m_type == iterator_type::end)
219 {
220 std::ostringstream os;
221 os << "iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
222 throw general_error(os.str());
223 }
224#endif
225 // We've reached the end position. Bail out.
226 m_type = iterator_type::end;
227 return *this;
228 }
229
230 // Move up one parent and see if it has an unvisited child node.
231 ktt::pop_back(m_buffer);
232 m_node_stack.pop_back();
233 auto& si = m_node_stack.back();
234 ++si.child_pos;
235
236 if (si.child_pos != si.node->children.end())
237 {
238 // Move down to this unvisited child node.
239 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
240 break;
241 }
242 }
243 }
244 else
245 {
246 // Current node has child nodes. Follow the first child node.
247 auto child_pos = cur_node->children.begin();
248 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
249 }
250 } while (!cur_node->has_value);
251
252 m_current_key = ktt::to_key(m_buffer);
253 m_current_value_ptr = &cur_node->value;
254 return *this;
255 }
256
257 iterator_base operator++(int)
258 {
259 iterator_base tmp(*this);
260 operator++();
261 return tmp;
262 }
263
264 iterator_base& operator--()
265 {
266 using ktt = key_traits_type;
267 trie_node_type* cur_node = m_node_stack.back().node;
268
269 if (m_type == iterator_type::end && cur_node->has_value)
270 {
271 assert(m_node_stack.size() == 1);
272 m_type = iterator_type::normal;
273 }
274 else if (m_node_stack.size() == 1)
275 {
276 // This is the end position aka root node. Move down to the
277 // right-most leaf node.
278 auto& si = m_node_stack.back();
279 assert(si.child_pos == cur_node->children.end());
280 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
281 m_type = iterator_type::normal;
282 }
283 else if (cur_node->children.empty())
284 {
285 // This is a leaf node. Keep going up until it finds a parent
286 // node with unvisited child nodes on the left side, then descend
287 // on that path all the way to its leaf.
288
289 do
290 {
291 // Go up one node.
292
293 ktt::pop_back(m_buffer);
294 m_node_stack.pop_back();
295 auto& si = m_node_stack.back();
296 cur_node = si.node;
297
298 if (si.child_pos != cur_node->children.begin())
299 {
300 // Left and down.
301 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
302 assert(cur_node->has_value);
303 }
304 } while (!cur_node->has_value);
305 }
306 else
307 {
308 // Non-leaf node with value. Keep going up until either the root
309 // node or another node with value is reached.
310
311 assert(cur_node->has_value);
312 assert(m_node_stack.back().child_pos == cur_node->children.begin());
313
314 do
315 {
316 // Go up.
317 ktt::pop_back(m_buffer);
318 m_node_stack.pop_back();
319 auto& si = m_node_stack.back();
320 cur_node = si.node;
321
322 if (m_node_stack.size() == 1)
323 {
324 // Root node reached. Left and down.
325 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
326 assert(cur_node->has_value);
327 }
328 } while (!cur_node->has_value);
329 }
330
331 assert(cur_node->has_value);
332 m_current_key = ktt::to_key(m_buffer);
333 m_current_value_ptr = &cur_node->value;
334 return *this;
335 }
336
337 iterator_base operator--(int)
338 {
339 iterator_base tmp(*this);
340 operator--();
341 return tmp;
342 }
343};
344
345template<typename _TrieType>
346class const_iterator;
347
348template<typename _TrieType>
349class iterator : public iterator_base<_TrieType, false>
350{
351 using trie_type = _TrieType;
352
353 friend trie_type;
356
358 using node_stack_type = typename base_type::node_stack_type;
359 using key_buffer_type = typename base_type::key_buffer_type;
360
361 iterator(empty_iterator_type t) : base_type(t)
362 {}
363
364public:
365 iterator() : base_type()
366 {}
367
368 iterator(node_stack_type&& node_stack, key_buffer_type&& buf, iterator_type type)
369 : base_type(std::move(node_stack), std::move(buf), type)
370 {}
371};
372
373template<typename _TrieType>
374class const_iterator : public iterator_base<_TrieType, true>
375{
376 using trie_type = _TrieType;
377
378 friend trie_type;
380
382 using node_stack_type = typename base_type::node_stack_type;
383 using key_buffer_type = typename base_type::key_buffer_type;
384
385 using base_type::m_buffer;
386 using base_type::m_current_key;
387 using base_type::m_current_value_ptr;
388 using base_type::m_node_stack;
389 using base_type::m_type;
390
391 const_iterator(empty_iterator_type t) : base_type(t)
392 {}
393
394public:
396 {}
397
398 const_iterator(node_stack_type&& node_stack, key_buffer_type&& buf, iterator_type type)
399 : base_type(std::move(node_stack), std::move(buf), type)
400 {}
401
403 {
404 m_buffer = it.m_buffer;
405 m_current_key = it.m_current_key;
406 m_current_value_ptr = it.m_current_value_ptr;
407 m_type = it.m_type;
408
409 for (const auto& e : it.m_node_stack)
410 m_node_stack.emplace_back(e.node, e.child_pos);
411 }
412};
413
414template<typename _TrieType>
415bool operator==(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
416{
417 return const_iterator<_TrieType>(left) == right;
418}
419
420template<typename _TrieType>
421bool operator!=(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
422{
423 return const_iterator<_TrieType>(left) != right;
424}
425
426template<typename _TrieType>
427bool operator==(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
428{
429 return left == const_iterator<_TrieType>(right);
430}
431
432template<typename _TrieType>
433bool operator!=(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
434{
435 return left != const_iterator<_TrieType>(right);
436}
437
438template<typename _TrieType>
440{
441 using trie_type = _TrieType;
442 friend trie_type;
443 using node_stack_type = typename trie_type::const_node_stack_type;
444
445 using trie_node = typename trie_type::trie_node;
446 using key_traits_type = typename trie_type::key_traits_type;
447 using key_type = typename key_traits_type::key_type;
448 using key_buffer_type = typename key_traits_type::key_buffer_type;
449 using key_unit_type = typename key_traits_type::key_unit_type;
450
451 const trie_node* m_node;
452 key_buffer_type m_buffer;
453 node_stack_type m_node_stack;
454
455 search_results(const trie_node* node, key_buffer_type&& buf) : m_node(node), m_buffer(buf)
456 {}
457
458public:
459 using const_iterator = typename trie_type::const_iterator;
460
461 const_iterator begin() const
462 {
463 if (!m_node)
464 // empty results.
465 return const_iterator(empty_iterator);
466
467 // Push the root node.
468 key_buffer_type buf(m_buffer);
469 node_stack_type node_stack;
470 node_stack.emplace_back(m_node, m_node->children.begin());
471
472 while (!node_stack.back().node->has_value)
473 {
474 // There should always be at least one value node along the
475 // left-most branch.
476
477 auto it = node_stack.back().child_pos;
478 const_iterator::push_child_node_to_stack(node_stack, buf, it);
479 }
480
481 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
482 }
483
484 const_iterator end() const
485 {
486 if (!m_node)
487 // empty results.
488 return const_iterator(empty_iterator);
489
490 node_stack_type node_stack;
491 node_stack.emplace_back(m_node, m_node->children.end());
492 return const_iterator(std::move(node_stack), key_buffer_type(m_buffer), iterator_type::end);
493 }
494};
495
496template<typename _TrieType>
498
499template<typename _TrieType>
501{
502 using trie_type = _TrieType;
503 friend trie_type;
505
506 using stack_item = typename trie_type::stack_item;
507 using node_stack_type = typename trie_type::node_stack_type;
508
509 using key_traits_type = typename trie_type::key_traits_type;
510 using key_type = typename key_traits_type::key_type;
511 using key_buffer_type = typename key_traits_type::key_buffer_type;
512 using key_unit_type = typename key_traits_type::key_unit_type;
513
514public:
515 // iterator traits
516 using value_type = typename trie_type::key_value_type;
517 using pointer = value_type*;
518 using reference = value_type&;
519 using difference_type = std::ptrdiff_t;
520 using iterator_category = std::bidirectional_iterator_tag;
521
522private:
523 node_stack_type m_node_stack;
524 key_buffer_type m_buffer;
525 value_type m_current_value;
526 iterator_type m_type;
527
532 static void push_child_node_to_stack(node_stack_type& node_stack, key_buffer_type& buf, const uintptr_t* child_pos)
533 {
534 using ktt = key_traits_type;
535
536 const uintptr_t* node_pos = node_stack.back().node_pos;
537
538 key_unit_type c = static_cast<key_unit_type>(*child_pos);
539 ktt::push_back(buf, c);
540 ++child_pos;
541 size_t offset = static_cast<size_t>(*child_pos);
542 node_pos -= offset; // Jump to the head of the child node.
543 const uintptr_t* p = node_pos;
544 ++p;
545 size_t index_size = *p;
546 ++p;
547 child_pos = p;
548 const uintptr_t* child_end = child_pos + index_size;
549
550 // Push it onto the stack.
551 node_stack.emplace_back(node_pos, child_pos, child_end);
552 }
553
554 static const void descend_to_previus_leaf_node(node_stack_type& node_stack, key_buffer_type& buf)
555 {
556 using ktt = key_traits_type;
557
558 const uintptr_t* node_pos = nullptr;
559 size_t index_size = 0;
560
561 do
562 {
563 // Keep moving down on the right-most child nodes until the
564 // leaf node is reached.
565
566 stack_item* si = &node_stack.back();
567 node_pos = si->node_pos;
568 --si->child_pos;
569 size_t offset = *si->child_pos;
570 --si->child_pos;
571 key_unit_type c = *si->child_pos;
572 node_pos -= offset; // Jump to the head of the child node.
573 ktt::push_back(buf, c);
574
575 const uintptr_t* p = node_pos;
576 ++p;
577 index_size = *p;
578 ++p;
579 const uintptr_t* child_pos = p;
580 const uintptr_t* child_end = child_pos + index_size;
581 node_stack.emplace_back(node_pos, child_end, child_end);
582 } while (index_size);
583 }
584
585 packed_iterator_base(empty_iterator_type) : m_type(iterator_type::empty)
586 {}
587
588public:
589 packed_iterator_base() : m_type(iterator_type::normal)
590 {}
591
592 packed_iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf, const typename trie_type::value_type& v)
593 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
594 m_current_value(key_traits_type::to_key(m_buffer), v), m_type(iterator_type::normal)
595 {}
596
597 packed_iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf)
598 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_type(iterator_type::end)
599 {}
600
601 bool operator==(const packed_iterator_base& other) const
602 {
603 if (m_type != other.m_type)
604 return false;
605
606 if (m_type == iterator_type::empty)
607 return true;
608
609 return m_node_stack.back() == other.m_node_stack.back();
610 }
611
612 bool operator!=(const packed_iterator_base& other) const
613 {
614 return !operator==(other);
615 }
616
617 const value_type& operator*()
618 {
619 return m_current_value;
620 }
621
622 const value_type* operator->()
623 {
624 return &m_current_value;
625 }
626
627 packed_iterator_base& operator++()
628 {
629 using ktt = key_traits_type;
630
631 stack_item* si = &m_node_stack.back();
632 const typename trie_type::value_type* pv = nullptr;
633 size_t index_size = *(si->node_pos + 1);
634
635 do
636 {
637 if (!index_size)
638 {
639 // Current node is a leaf node. Keep moving up the stack until we
640 // reach a parent node with unvisited children.
641
642 while (true)
643 {
644 if (m_node_stack.size() == 1)
645 {
646#ifdef MDDS_TRIE_MAP_DEBUG
647 if (m_type == iterator_type::end)
648 {
649 std::ostringstream os;
650 os << "packed_iterator_base::operator++#" << __LINE__ << ": moving past the end position!";
651 throw general_error(os.str());
652 }
653#endif
654 // We've reached the end position. Bail out.
655 m_type = iterator_type::end;
656 return *this;
657 }
658
659 // Move up one parent and see if it has an unvisited child node.
660 ktt::pop_back(m_buffer);
661 m_node_stack.pop_back();
662 si = &m_node_stack.back();
663 std::advance(si->child_pos, 2);
664
665 if (si->child_pos != si->child_end)
666 {
667 // Move down to this unvisited child node.
668 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
669 break;
670 }
671 }
672 }
673 else
674 {
675 // Current node has child nodes. Follow the first child node.
676 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
677 }
678
679 si = &m_node_stack.back();
680 pv = reinterpret_cast<const typename trie_type::value_type*>(*si->node_pos);
681 index_size = *(si->node_pos + 1);
682 } while (!pv);
683
684 assert(pv);
685 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
686
687 return *this;
688 }
689
690 packed_iterator_base operator++(int)
691 {
692 packed_iterator_base tmp(*this);
693 operator++();
694 return tmp;
695 }
696
697 packed_iterator_base& operator--()
698 {
699 using ktt = key_traits_type;
700
701 stack_item* si = &m_node_stack.back();
702 const typename trie_type::value_type* pv =
703 reinterpret_cast<const typename trie_type::value_type*>(*si->node_pos);
704 size_t index_size = *(si->node_pos + 1); // index size for child nodes.
705
706 if (m_type == iterator_type::end && pv)
707 {
708 assert(m_node_stack.size() == 1);
709 m_type = iterator_type::normal;
710 }
711 else if (m_node_stack.size() == 1)
712 {
713 // This is the end position aka root node. Move down to the
714 // right-most leaf node.
715 assert(si->child_pos == si->child_end);
716 descend_to_previus_leaf_node(m_node_stack, m_buffer);
717 si = &m_node_stack.back();
718 pv = reinterpret_cast<const typename trie_type::value_type*>(*si->node_pos);
719 m_type = iterator_type::normal;
720 }
721 else if (!index_size)
722 {
723 // This is a leaf node. Keep going up until it finds a parent
724 // node with unvisited child nodes on the left side, then descend
725 // on that path all the way to its leaf.
726
727 do
728 {
729 // Go up one node.
730
731 ktt::pop_back(m_buffer);
732 m_node_stack.pop_back();
733 si = &m_node_stack.back();
734 const uintptr_t* p = si->node_pos;
735 pv = reinterpret_cast<const typename trie_type::value_type*>(*p);
736 ++p;
737 index_size = *p;
738 ++p;
739 const uintptr_t* first_child = p;
740
741 if (si->child_pos != first_child)
742 {
743 // Left and down.
744 descend_to_previus_leaf_node(m_node_stack, m_buffer);
745 si = &m_node_stack.back();
746 p = si->node_pos;
747 pv = reinterpret_cast<const typename trie_type::value_type*>(*p);
748 assert(pv);
749 }
750 } while (!pv);
751 }
752 else
753 {
754 // Non-leaf node with value. Keep going up until either the root
755 // node or another node with value is reached.
756
757 assert(*si->node_pos); // this node should have a value.
758 assert(si->child_pos == (si->node_pos + 2));
759
760 do
761 {
762 // Go up.
763 ktt::pop_back(m_buffer);
764 m_node_stack.pop_back();
765 si = &m_node_stack.back();
766 pv = reinterpret_cast<const typename trie_type::value_type*>(*si->node_pos);
767
768 if (m_node_stack.size() == 1)
769 {
770 // Root node reached.
771 descend_to_previus_leaf_node(m_node_stack, m_buffer);
772 si = &m_node_stack.back();
773 pv = reinterpret_cast<const typename trie_type::value_type*>(*si->node_pos);
774 assert(pv);
775 }
776 } while (!pv);
777 }
778
779 assert(pv);
780 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
781
782 return *this;
783 }
784
785 packed_iterator_base operator--(int)
786 {
787 packed_iterator_base tmp(*this);
788 operator--();
789 return tmp;
790 }
791};
792
793template<typename _TrieType>
795{
796 using trie_type = _TrieType;
797 friend trie_type;
798 using node_stack_type = typename trie_type::node_stack_type;
799
800 using key_traits_type = typename trie_type::key_traits_type;
801 using key_type = typename key_traits_type::key_type;
802 using key_buffer_type = typename key_traits_type::key_buffer_type;
803 using key_unit_type = typename key_traits_type::key_unit_type;
804
805 const uintptr_t* m_node;
806 key_buffer_type m_buffer;
807
808 packed_search_results(const uintptr_t* node, key_buffer_type&& buf) : m_node(node), m_buffer(std::move(buf))
809 {}
810
811 node_stack_type get_root_node() const
812 {
813 const uintptr_t* p = m_node;
814 ++p;
815 size_t index_size = *p;
816 ++p;
817 const uintptr_t* child_pos = p;
818 const uintptr_t* child_end = child_pos + index_size;
819
820 // Push this child node onto the stack.
821 node_stack_type node_stack;
822 node_stack.emplace_back(m_node, child_pos, child_end);
823 return node_stack;
824 }
825
826 void swap(packed_search_results& other)
827 {
828 std::swap(m_node, other.m_node);
829 std::swap(m_buffer, other.m_buffer);
830 }
831
832public:
834
835 packed_search_results() : m_node(nullptr)
836 {}
837
838 packed_search_results(const packed_search_results& other) : m_node(other.m_node), m_buffer(other.m_buffer)
839 {}
840
841 packed_search_results(packed_search_results&& other) : m_node(other.m_node), m_buffer(std::move(other.m_buffer))
842 {
843 other.m_node = nullptr;
844 }
845
847 {
848 packed_search_results tmp(std::move(other));
849 swap(tmp);
850 return *this;
851 }
852
853 const_iterator begin() const
854 {
855 if (!m_node)
856 // empty results.
857 return const_iterator(empty_iterator);
858
859 // Push the root node.
860 key_buffer_type buf(m_buffer);
861 node_stack_type node_stack = get_root_node();
862
863 while (!node_stack.back().has_value())
864 {
865 // There should always be at least one value node along the
866 // left-most branch.
867
868 const_iterator::push_child_node_to_stack(node_stack, buf, node_stack.back().child_pos);
869 }
870
871 return const_iterator(std::move(node_stack), std::move(buf), *node_stack.back().get_value());
872 }
873
874 const_iterator end() const
875 {
876 if (!m_node)
877 // empty results.
878 return const_iterator(empty_iterator);
879
880 node_stack_type node_stack = get_root_node();
881 auto& si = node_stack.back();
882 si.child_pos = si.child_end;
883 return const_iterator(std::move(node_stack), key_buffer_type(m_buffer));
884 }
885};
886
887}}} // namespace mdds::trie::detail
888
889#endif
Definition: global.hpp:84
Definition: trie_map_itr.hpp:375
Definition: trie_map_itr.hpp:89
static trie_node_type * descend_to_previus_leaf_node(node_stack_type &node_stack, key_buffer_type &buf)
Definition: trie_map_itr.hpp:139
Definition: trie_map_itr.hpp:350
Definition: trie_map_itr.hpp:501
Definition: trie_map_itr.hpp:795
Definition: trie_map_itr.hpp:440
Definition: global.hpp:149
Definition: global.hpp:167
Definition: ref_pair.hpp:38
Definition: trie_map_itr.hpp:70