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
65 {
66  empty_iterator
67 };
68 
69 template<typename _TrieType, typename _C>
71 
72 template<typename _TrieType>
73 struct get_node_stack_type<_TrieType, std::true_type>
74 {
75  using type = typename _TrieType::const_node_stack_type;
76 };
77 
78 template<typename _TrieType>
79 struct get_node_stack_type<_TrieType, std::false_type>
80 {
81  using type = typename _TrieType::node_stack_type;
82 };
83 
84 template<typename _TrieType>
85 class search_results;
86 
87 template<typename _TrieType, bool _IsConst>
89 {
90 protected:
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 = const_t<typename trie_type::trie_node, _IsConst>;
100  using trie_node_child_pos_type =
102 
103  using key_trait_type = typename trie_type::key_trait_type;
104  using key_type = typename key_trait_type::key_type;
105  using key_buffer_type = typename key_trait_type::key_buffer_type;
106  using trie_value_type = typename const_or_not<typename trie_type::value_type, _is_const>::type;
107 
108 public:
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 
116 protected:
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_trait_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_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  } 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 
164 public:
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_trait_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_trait_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_trait_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 
345 template<typename _TrieType>
346 class const_iterator;
347 
348 template<typename _TrieType>
349 class 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 
364 public:
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 
373 template<typename _TrieType>
374 class 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 
394 public:
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 
414 template<typename _TrieType>
415 bool operator==(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
416 {
417  return const_iterator<_TrieType>(left) == right;
418 }
419 
420 template<typename _TrieType>
421 bool operator!=(const iterator<_TrieType>& left, const const_iterator<_TrieType>& right)
422 {
423  return const_iterator<_TrieType>(left) != right;
424 }
425 
426 template<typename _TrieType>
427 bool operator==(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
428 {
429  return left == const_iterator<_TrieType>(right);
430 }
431 
432 template<typename _TrieType>
433 bool operator!=(const const_iterator<_TrieType>& left, const iterator<_TrieType>& right)
434 {
435  return left != const_iterator<_TrieType>(right);
436 }
437 
438 template<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_trait_type = typename trie_type::key_trait_type;
447  using key_type = typename key_trait_type::key_type;
448  using key_buffer_type = typename key_trait_type::key_buffer_type;
449  using key_unit_type = typename key_trait_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 
458 public:
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 
496 template<typename _TrieType>
498 
499 template<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_trait_type = typename trie_type::key_trait_type;
510  using key_type = typename key_trait_type::key_type;
511  using key_buffer_type = typename key_trait_type::key_buffer_type;
512  using key_unit_type = typename key_trait_type::key_unit_type;
513 
514 public:
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 
522 private:
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_trait_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_trait_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 
588 public:
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_trait_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_trait_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_trait_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 
793 template<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_trait_type = typename trie_type::key_trait_type;
801  using key_type = typename key_trait_type::key_type;
802  using key_buffer_type = typename key_trait_type::key_buffer_type;
803  using key_unit_type = typename key_trait_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 
832 public:
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:147
Definition: ref_pair.hpp:38
Definition: global.hpp:165
Definition: trie_map_itr.hpp:70