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