28 #ifndef INCLUDED_MDDS_TRIE_MAP_ITR_HPP
29 #define INCLUDED_MDDS_TRIE_MAP_ITR_HPP
34 #ifdef MDDS_TRIE_MAP_DEBUG
38 #include "mdds/global.hpp"
39 #include "mdds/ref_pair.hpp"
41 namespace mdds {
namespace trie {
namespace detail {
43 enum class iterator_type
64 enum empty_iterator_type { empty_iterator };
66 template<
typename _TrieType,
typename _C>
69 template<
typename _TrieType>
72 using type =
typename _TrieType::const_node_stack_type;
75 template<
typename _TrieType>
78 using type =
typename _TrieType::node_stack_type;
81 template<
typename _TrieType>
84 template<
typename _TrieType,
bool _IsConst>
88 using trie_type = _TrieType;
90 using _is_const = bool_constant<_IsConst>;
96 using trie_node_type = const_t<typename trie_type::trie_node, _IsConst>;
97 using trie_node_child_pos_type =
99 typename std::remove_const<trie_node_type>::type::children_type, _is_const>::type;
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;
111 using difference_type = std::ptrdiff_t;
112 using iterator_category = std::bidirectional_iterator_tag;
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;
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)
125 using ktt = key_trait_type;
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());
139 node_stack_type& node_stack, key_buffer_type& buf)
141 using ktt = key_trait_type;
143 trie_node_type* cur_node =
nullptr;
150 auto& si = node_stack.back();
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());
157 while (!cur_node->children.empty());
162 iterator_base(empty_iterator_type) : m_type(iterator_type::empty) {}
165 iterator_base() : m_type(iterator_type::normal) {}
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),
175 bool operator== (
const iterator_base& other)
const
177 if (m_type != other.m_type)
180 if (m_type == iterator_type::empty)
183 return m_node_stack.back() == other.m_node_stack.back();
186 bool operator!= (
const iterator_base& other)
const
188 return !operator==(other);
191 value_type operator*()
193 return value_type(m_current_key, *m_current_value_ptr);
196 value_type operator->()
198 return value_type(m_current_key, *m_current_value_ptr);
201 iterator_base& operator++()
203 using ktt = key_trait_type;
205 trie_node_type* cur_node = m_node_stack.back().node;
209 if (cur_node->children.empty())
216 if (m_node_stack.size() == 1)
218 #ifdef MDDS_TRIE_MAP_DEBUG
219 if (m_type == iterator_type::end)
221 std::ostringstream os;
222 os <<
"iterator_base::operator++#" << __LINE__
223 <<
": moving past the end position!";
224 throw general_error(os.str());
228 m_type = iterator_type::end;
233 ktt::pop_back(m_buffer);
234 m_node_stack.pop_back();
235 auto& si = m_node_stack.back();
238 if (si.child_pos != si.node->children.end())
241 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
249 auto child_pos = cur_node->children.begin();
250 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
253 while (!cur_node->has_value);
255 m_current_key = ktt::to_key(m_buffer);
256 m_current_value_ptr = &cur_node->value;
260 iterator_base operator++(
int)
262 iterator_base tmp(*
this);
267 iterator_base& operator--()
269 using ktt = key_trait_type;
270 trie_node_type* cur_node = m_node_stack.back().node;
272 if (m_type == iterator_type::end && cur_node->has_value)
274 assert(m_node_stack.size() == 1);
275 m_type = iterator_type::normal;
277 else if (m_node_stack.size() == 1)
281 auto& si = m_node_stack.back();
282 assert(si.child_pos == cur_node->children.end());
284 m_type = iterator_type::normal;
286 else if (cur_node->children.empty())
296 ktt::pop_back(m_buffer);
297 m_node_stack.pop_back();
298 auto& si = m_node_stack.back();
301 if (si.child_pos != cur_node->children.begin())
305 assert(cur_node->has_value);
308 while (!cur_node->has_value);
315 assert(cur_node->has_value);
316 assert(m_node_stack.back().child_pos == cur_node->children.begin());
321 ktt::pop_back(m_buffer);
322 m_node_stack.pop_back();
323 auto& si = m_node_stack.back();
326 if (m_node_stack.size() == 1)
330 assert(cur_node->has_value);
333 while (!cur_node->has_value);
336 assert(cur_node->has_value);
337 m_current_key = ktt::to_key(m_buffer);
338 m_current_value_ptr = &cur_node->value;
342 iterator_base operator--(
int)
344 iterator_base tmp(*
this);
350 template<
typename _TrieType>
351 class const_iterator;
353 template<
typename _TrieType>
356 using trie_type = _TrieType;
363 using node_stack_type =
typename base_type::node_stack_type;
364 using key_buffer_type =
typename base_type::key_buffer_type;
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)
376 template<
typename _TrieType>
379 using trie_type = _TrieType;
385 using node_stack_type =
typename base_type::node_stack_type;
386 using key_buffer_type =
typename base_type::key_buffer_type;
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;
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)
405 m_buffer = it.m_buffer;
406 m_current_key = it.m_current_key;
407 m_current_value_ptr = it.m_current_value_ptr;
410 for (
const auto& e : it.m_node_stack)
411 m_node_stack.emplace_back(e.node, e.child_pos);
415 template<
typename _TrieType>
421 template<
typename _TrieType>
422 bool operator!=(
const iterator<_TrieType>& left,
const const_iterator<_TrieType>& right)
424 return const_iterator<_TrieType>(left) != right;
427 template<
typename _TrieType>
428 bool operator==(
const const_iterator<_TrieType>& left,
const iterator<_TrieType>& right)
430 return left == const_iterator<_TrieType>(right);
433 template<
typename _TrieType>
434 bool operator!=(
const const_iterator<_TrieType>& left,
const iterator<_TrieType>& right)
436 return left != const_iterator<_TrieType>(right);
439 template<
typename _TrieType>
442 using trie_type = _TrieType;
444 using node_stack_type =
typename trie_type::const_node_stack_type;
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;
452 const trie_node* m_node;
453 key_buffer_type m_buffer;
454 node_stack_type m_node_stack;
457 m_node(node), m_buffer(buf) {}
460 using const_iterator =
typename trie_type::const_iterator;
462 const_iterator begin()
const
466 return const_iterator(empty_iterator);
469 key_buffer_type buf(m_buffer);
470 node_stack_type node_stack;
471 node_stack.emplace_back(m_node, m_node->children.begin());
473 while (!node_stack.back().node->has_value)
478 auto it = node_stack.back().child_pos;
479 const_iterator::push_child_node_to_stack(node_stack, buf, it);
482 return const_iterator(
483 std::move(node_stack), std::move(buf), iterator_type::normal);
486 const_iterator end()
const
490 return const_iterator(empty_iterator);
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);
499 template<
typename _TrieType>
502 template<
typename _TrieType>
505 using trie_type = _TrieType;
509 using stack_item =
typename trie_type::stack_item;
510 using node_stack_type =
typename trie_type::node_stack_type;
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;
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;
526 node_stack_type m_node_stack;
527 key_buffer_type m_buffer;
528 value_type m_current_value;
529 iterator_type m_type;
535 static void push_child_node_to_stack(
536 node_stack_type& node_stack, key_buffer_type& buf,
const uintptr_t* child_pos)
538 using ktt = key_trait_type;
540 const uintptr_t* node_pos = node_stack.back().node_pos;
542 key_unit_type c =
static_cast<key_unit_type
>(*child_pos);
543 ktt::push_back(buf, c);
545 size_t offset =
static_cast<size_t>(*child_pos);
547 const uintptr_t* p = node_pos;
549 size_t index_size = *p;
552 const uintptr_t* child_end = child_pos + index_size;
555 node_stack.emplace_back(node_pos, child_pos, child_end);
558 static const void descend_to_previus_leaf_node(
559 node_stack_type& node_stack, key_buffer_type& buf)
561 using ktt = key_trait_type;
563 const uintptr_t* node_pos =
nullptr;
564 size_t index_size = 0;
571 stack_item* si = &node_stack.back();
572 node_pos = si->node_pos;
574 size_t offset = *si->child_pos;
576 key_unit_type c = *si->child_pos;
578 ktt::push_back(buf, c);
580 const uintptr_t* p = node_pos;
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);
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) {}
603 m_node_stack(std::move(node_stack)),
604 m_buffer(std::move(buf)),
605 m_type(iterator_type::end) {}
609 if (m_type != other.m_type)
612 if (m_type == iterator_type::empty)
615 return m_node_stack.back() == other.m_node_stack.back();
620 return !operator==(other);
623 const value_type& operator*()
625 return m_current_value;
628 const value_type* operator->()
630 return &m_current_value;
635 using ktt = key_trait_type;
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);
650 if (m_node_stack.size() == 1)
652 #ifdef MDDS_TRIE_MAP_DEBUG
653 if (m_type == iterator_type::end)
655 std::ostringstream os;
656 os <<
"packed_iterator_base::operator++#"
657 << __LINE__ <<
": moving past the end position!";
662 m_type = iterator_type::end;
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);
672 if (si->child_pos != si->child_end)
675 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
683 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
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);
693 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
707 using ktt = key_trait_type;
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);
714 if (m_type == iterator_type::end && pv)
716 assert(m_node_stack.size() == 1);
717 m_type = iterator_type::normal;
719 else if (m_node_stack.size() == 1)
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;
729 else if (!index_size)
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);
747 const uintptr_t* first_child = p;
749 if (si->child_pos != first_child)
752 descend_to_previus_leaf_node(m_node_stack, m_buffer);
753 si = &m_node_stack.back();
755 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*p);
766 assert(*si->node_pos);
767 assert(si->child_pos == (si->node_pos+2));
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);
777 if (m_node_stack.size() == 1)
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);
790 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
803 template<
typename _TrieType>
806 using trie_type = _TrieType;
808 using node_stack_type =
typename trie_type::node_stack_type;
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;
815 const uintptr_t* m_node;
816 key_buffer_type m_buffer;
819 m_node(node), m_buffer(std::move(buf)) {}
821 node_stack_type get_root_node()
const
823 const uintptr_t* p = m_node;
825 size_t index_size = *p;
827 const uintptr_t* child_pos = p;
828 const uintptr_t* child_end = child_pos + index_size;
831 node_stack_type node_stack;
832 node_stack.emplace_back(m_node, child_pos, child_end);
838 std::swap(m_node, other.m_node);
839 std::swap(m_buffer, other.m_buffer);
848 m_node(other.m_node), m_buffer(other.m_buffer) {}
851 m_node(other.m_node), m_buffer(std::move(other.m_buffer))
853 other.m_node =
nullptr;
870 key_buffer_type buf(m_buffer);
871 node_stack_type node_stack = get_root_node();
873 while (!node_stack.back().has_value())
878 const_iterator::push_child_node_to_stack(node_stack, buf, node_stack.back().child_pos);
882 std::move(node_stack), std::move(buf), *node_stack.back().get_value());
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));
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