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"
41namespace mdds {
namespace trie {
namespace detail {
43enum class iterator_type
64enum empty_iterator_type
69template<
typename _TrieType,
typename _C>
72template<
typename _TrieType>
75 using type =
typename _TrieType::const_node_stack_type;
78template<
typename _TrieType>
81 using type =
typename _TrieType::node_stack_type;
84template<
typename _TrieType>
87template<
typename _TrieType,
bool IsConst>
91 using trie_type = _TrieType;
93 using _is_const = bool_constant<IsConst>;
99 using trie_node_type = mdds::detail::const_t<typename trie_type::trie_node, IsConst>;
101 typename std::remove_const<trie_node_type>::type::children_type, _is_const>::type;
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;
113 using difference_type = std::ptrdiff_t;
114 using iterator_category = std::bidirectional_iterator_tag;
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;
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)
126 using ktt = key_traits_type;
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());
141 using ktt = key_traits_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());
156 }
while (!cur_node->children.empty());
161 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
165 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
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),
174 bool operator==(
const iterator_base& other)
const
176 if (m_type != other.m_type)
179 if (m_type == iterator_type::empty)
182 return m_node_stack.back() == other.m_node_stack.back();
185 bool operator!=(
const iterator_base& other)
const
187 return !operator==(other);
190 value_type operator*()
192 return value_type(m_current_key, *m_current_value_ptr);
195 value_type operator->()
197 return value_type(m_current_key, *m_current_value_ptr);
200 iterator_base& operator++()
202 using ktt = key_traits_type;
204 trie_node_type* cur_node = m_node_stack.back().node;
208 if (cur_node->children.empty())
215 if (m_node_stack.size() == 1)
217#ifdef MDDS_TRIE_MAP_DEBUG
218 if (m_type == iterator_type::end)
220 std::ostringstream os;
221 os <<
"iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
222 throw general_error(os.str());
226 m_type = iterator_type::end;
231 ktt::pop_back(m_buffer);
232 m_node_stack.pop_back();
233 auto& si = m_node_stack.back();
236 if (si.child_pos != si.node->children.end())
239 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
247 auto child_pos = cur_node->children.begin();
248 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
250 }
while (!cur_node->has_value);
252 m_current_key = ktt::to_key(m_buffer);
253 m_current_value_ptr = &cur_node->value;
257 iterator_base operator++(
int)
259 iterator_base tmp(*
this);
264 iterator_base& operator--()
266 using ktt = key_traits_type;
267 trie_node_type* cur_node = m_node_stack.back().node;
269 if (m_type == iterator_type::end && cur_node->has_value)
271 assert(m_node_stack.size() == 1);
272 m_type = iterator_type::normal;
274 else if (m_node_stack.size() == 1)
278 auto& si = m_node_stack.back();
279 assert(si.child_pos == cur_node->children.end());
281 m_type = iterator_type::normal;
283 else if (cur_node->children.empty())
293 ktt::pop_back(m_buffer);
294 m_node_stack.pop_back();
295 auto& si = m_node_stack.back();
298 if (si.child_pos != cur_node->children.begin())
302 assert(cur_node->has_value);
304 }
while (!cur_node->has_value);
311 assert(cur_node->has_value);
312 assert(m_node_stack.back().child_pos == cur_node->children.begin());
317 ktt::pop_back(m_buffer);
318 m_node_stack.pop_back();
319 auto& si = m_node_stack.back();
322 if (m_node_stack.size() == 1)
326 assert(cur_node->has_value);
328 }
while (!cur_node->has_value);
331 assert(cur_node->has_value);
332 m_current_key = ktt::to_key(m_buffer);
333 m_current_value_ptr = &cur_node->value;
337 iterator_base operator--(
int)
339 iterator_base tmp(*
this);
345template<
typename _TrieType>
348template<
typename _TrieType>
351 using trie_type = _TrieType;
358 using node_stack_type =
typename base_type::node_stack_type;
359 using key_buffer_type =
typename base_type::key_buffer_type;
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)
373template<
typename _TrieType>
376 using trie_type = _TrieType;
382 using node_stack_type =
typename base_type::node_stack_type;
383 using key_buffer_type =
typename base_type::key_buffer_type;
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;
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)
404 m_buffer = it.m_buffer;
405 m_current_key = it.m_current_key;
406 m_current_value_ptr = it.m_current_value_ptr;
409 for (
const auto& e : it.m_node_stack)
410 m_node_stack.emplace_back(e.node, e.child_pos);
414template<
typename _TrieType>
420template<
typename _TrieType>
421bool operator!=(
const iterator<_TrieType>& left,
const const_iterator<_TrieType>& right)
423 return const_iterator<_TrieType>(left) != right;
426template<
typename _TrieType>
427bool operator==(
const const_iterator<_TrieType>& left,
const iterator<_TrieType>& right)
429 return left == const_iterator<_TrieType>(right);
432template<
typename _TrieType>
433bool operator!=(
const const_iterator<_TrieType>& left,
const iterator<_TrieType>& right)
435 return left != const_iterator<_TrieType>(right);
438template<
typename _TrieType>
441 using trie_type = _TrieType;
443 using node_stack_type =
typename trie_type::const_node_stack_type;
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;
451 const trie_node* m_node;
452 key_buffer_type m_buffer;
453 node_stack_type m_node_stack;
455 search_results(
const trie_node* node, key_buffer_type&& buf) : m_node(node), m_buffer(buf)
459 using const_iterator =
typename trie_type::const_iterator;
461 const_iterator begin()
const
465 return const_iterator(empty_iterator);
468 key_buffer_type buf(m_buffer);
469 node_stack_type node_stack;
470 node_stack.emplace_back(m_node, m_node->children.begin());
472 while (!node_stack.back().node->has_value)
477 auto it = node_stack.back().child_pos;
478 const_iterator::push_child_node_to_stack(node_stack, buf, it);
481 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
484 const_iterator end()
const
488 return const_iterator(empty_iterator);
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);
496template<
typename _TrieType>
499template<
typename _TrieType>
502 using trie_type = _TrieType;
506 using stack_item =
typename trie_type::stack_item;
507 using node_stack_type =
typename trie_type::node_stack_type;
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;
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;
523 node_stack_type m_node_stack;
524 key_buffer_type m_buffer;
525 value_type m_current_value;
526 iterator_type m_type;
532 static void push_child_node_to_stack(node_stack_type& node_stack, key_buffer_type& buf,
const uintptr_t* child_pos)
534 using ktt = key_traits_type;
536 const uintptr_t* node_pos = node_stack.back().node_pos;
538 key_unit_type c =
static_cast<key_unit_type
>(*child_pos);
539 ktt::push_back(buf, c);
541 size_t offset =
static_cast<size_t>(*child_pos);
543 const uintptr_t* p = node_pos;
545 size_t index_size = *p;
548 const uintptr_t* child_end = child_pos + index_size;
551 node_stack.emplace_back(node_pos, child_pos, child_end);
554 static const void descend_to_previus_leaf_node(node_stack_type& node_stack, key_buffer_type& buf)
556 using ktt = key_traits_type;
558 const uintptr_t* node_pos =
nullptr;
559 size_t index_size = 0;
566 stack_item* si = &node_stack.back();
567 node_pos = si->node_pos;
569 size_t offset = *si->child_pos;
571 key_unit_type c = *si->child_pos;
573 ktt::push_back(buf, c);
575 const uintptr_t* p = node_pos;
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);
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)
598 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_type(iterator_type::end)
603 if (m_type != other.m_type)
606 if (m_type == iterator_type::empty)
609 return m_node_stack.back() == other.m_node_stack.back();
614 return !operator==(other);
617 const value_type& operator*()
619 return m_current_value;
622 const value_type* operator->()
624 return &m_current_value;
629 using ktt = key_traits_type;
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);
644 if (m_node_stack.size() == 1)
646#ifdef MDDS_TRIE_MAP_DEBUG
647 if (m_type == iterator_type::end)
649 std::ostringstream os;
650 os <<
"packed_iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
655 m_type = iterator_type::end;
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);
665 if (si->child_pos != si->child_end)
668 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
676 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
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);
685 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
699 using ktt = key_traits_type;
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);
706 if (m_type == iterator_type::end && pv)
708 assert(m_node_stack.size() == 1);
709 m_type = iterator_type::normal;
711 else if (m_node_stack.size() == 1)
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;
721 else if (!index_size)
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);
739 const uintptr_t* first_child = p;
741 if (si->child_pos != first_child)
744 descend_to_previus_leaf_node(m_node_stack, m_buffer);
745 si = &m_node_stack.back();
747 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*p);
757 assert(*si->node_pos);
758 assert(si->child_pos == (si->node_pos + 2));
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);
768 if (m_node_stack.size() == 1)
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);
780 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
793template<
typename _TrieType>
796 using trie_type = _TrieType;
798 using node_stack_type =
typename trie_type::node_stack_type;
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;
805 const uintptr_t* m_node;
806 key_buffer_type m_buffer;
808 packed_search_results(
const uintptr_t* node, key_buffer_type&& buf) : m_node(node), m_buffer(std::move(buf))
811 node_stack_type get_root_node()
const
813 const uintptr_t* p = m_node;
815 size_t index_size = *p;
817 const uintptr_t* child_pos = p;
818 const uintptr_t* child_end = child_pos + index_size;
821 node_stack_type node_stack;
822 node_stack.emplace_back(m_node, child_pos, child_end);
828 std::swap(m_node, other.m_node);
829 std::swap(m_buffer, other.m_buffer);
843 other.m_node =
nullptr;
860 key_buffer_type buf(m_buffer);
861 node_stack_type node_stack = get_root_node();
863 while (!node_stack.back().has_value())
868 const_iterator::push_child_node_to_stack(node_stack, buf, node_stack.back().child_pos);
871 return const_iterator(std::move(node_stack), std::move(buf), *node_stack.back().get_value());
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));
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