91 using trie_type = _TrieType;
93 using _is_const = std::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_type =
typename trie_type::key_type;
111 using difference_type = std::ptrdiff_t;
112 using iterator_category = std::bidirectional_iterator_tag;
115 node_stack_type m_node_stack;
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_type& buf, trie_node_child_pos_type& child_pos)
124 trie_node_type* node = &child_pos->second;
125 buf.push_back(child_pos->first);
126 node_stack.emplace_back(node, node->children.begin());
137 trie_node_type* cur_node =
nullptr;
144 auto& si = node_stack.back();
147 buf.push_back(si.child_pos->first);
148 cur_node = &si.child_pos->second;
149 node_stack.emplace_back(cur_node, cur_node->children.end());
150 }
while (!cur_node->children.empty());
155 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
159 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
162 iterator_base(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
163 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_current_key(m_buffer),
164 m_current_value_ptr(&m_node_stack.back().node->value), m_type(type)
167 bool operator==(
const iterator_base& other)
const
169 if (m_type != other.m_type)
172 if (m_type == iterator_type::empty)
175 return m_node_stack.back() == other.m_node_stack.back();
178 bool operator!=(
const iterator_base& other)
const
180 return !operator==(other);
183 value_type operator*()
185 return value_type(m_current_key, *m_current_value_ptr);
188 value_type operator->()
190 return value_type(m_current_key, *m_current_value_ptr);
193 iterator_base& operator++()
195 trie_node_type* cur_node = m_node_stack.back().node;
199 if (cur_node->children.empty())
206 if (m_node_stack.size() == 1)
208#ifdef MDDS_TRIE_MAP_DEBUG
209 if (m_type == iterator_type::end)
211 std::ostringstream os;
212 os <<
"iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
213 throw general_error(os.str());
217 m_type = iterator_type::end;
223 m_node_stack.pop_back();
224 auto& si = m_node_stack.back();
227 if (si.child_pos != si.node->children.end())
230 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
238 auto child_pos = cur_node->children.begin();
239 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
241 }
while (!cur_node->has_value);
243 m_current_key = m_buffer;
244 m_current_value_ptr = &cur_node->value;
248 iterator_base operator++(
int)
250 iterator_base tmp(*
this);
255 iterator_base& operator--()
257 trie_node_type* cur_node = m_node_stack.back().node;
259 if (m_type == iterator_type::end && cur_node->has_value)
261 assert(m_node_stack.size() == 1);
262 m_type = iterator_type::normal;
264 else if (m_node_stack.size() == 1)
268 auto& si = m_node_stack.back();
269 assert(si.child_pos == cur_node->children.end());
271 m_type = iterator_type::normal;
273 else if (cur_node->children.empty())
284 m_node_stack.pop_back();
285 auto& si = m_node_stack.back();
288 if (si.child_pos != cur_node->children.begin())
292 assert(cur_node->has_value);
294 }
while (!cur_node->has_value);
301 assert(cur_node->has_value);
302 assert(m_node_stack.back().child_pos == cur_node->children.begin());
308 m_node_stack.pop_back();
309 auto& si = m_node_stack.back();
312 if (m_node_stack.size() == 1)
316 assert(cur_node->has_value);
318 }
while (!cur_node->has_value);
321 assert(cur_node->has_value);
322 m_current_key = m_buffer;
323 m_current_value_ptr = &cur_node->value;
327 iterator_base operator--(
int)
329 iterator_base tmp(*
this);
431 using trie_type = _TrieType;
433 using node_stack_type =
typename trie_type::const_node_stack_type;
435 using trie_node =
typename trie_type::trie_node;
436 using key_type =
typename trie_type::key_type;
437 using key_unit_type =
typename key_type::value_type;
439 const trie_node* m_node;
441 node_stack_type m_node_stack;
443 search_results(
const trie_node* node, key_type&& buf) : m_node(node), m_buffer(buf)
447 using const_iterator =
typename trie_type::const_iterator;
449 const_iterator begin()
const
453 return const_iterator(empty_iterator);
456 key_type buf(m_buffer);
457 node_stack_type node_stack;
458 node_stack.emplace_back(m_node, m_node->children.begin());
460 while (!node_stack.back().node->has_value)
465 auto it = node_stack.back().child_pos;
466 const_iterator::push_child_node_to_stack(node_stack, buf, it);
469 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
472 const_iterator end()
const
476 return const_iterator(empty_iterator);
478 node_stack_type node_stack;
479 node_stack.emplace_back(m_node, m_node->children.end());
480 return const_iterator(std::move(node_stack), key_type(m_buffer), iterator_type::end);
490 using trie_type = TrieT;
494 using stack_item =
typename trie_type::stack_item;
495 using node_stack_type =
typename trie_type::node_stack_type;
497 using key_type =
typename trie_type::key_type;
498 using size_type =
typename trie_type::size_type;
499 using trie_value_type =
typename trie_type::value_type;
500 using value_store_type =
typename trie_type::value_store_type;
501 using pack_value_type =
typename trie_type::pack_value_type;
502 using key_unit_type =
typename key_type::value_type;
509 using difference_type = std::ptrdiff_t;
510 using iterator_category = std::bidirectional_iterator_tag;
513 const value_store_type* m_value_store =
nullptr;
514 node_stack_type m_node_stack;
516 pack_value_type m_current_value = trie_type::null_value;
517 iterator_type m_type;
523 static void push_child_node_to_stack(
524 const value_store_type* value_store, node_stack_type& node_stack, key_type& buf,
525 const pack_value_type* child_pos)
528 const auto* node_pos = node_stack.back().node_pos;
530 key_unit_type c =
static_cast<key_unit_type
>(*child_pos);
533 auto offset =
static_cast<size_type
>(*child_pos);
535 const auto* p = node_pos;
537 size_type index_size = *p;
540 const auto* child_end = child_pos + index_size;
543 node_stack.emplace_back(value_store, node_pos, child_pos, child_end);
546 static const void descend_to_previous_leaf_node(node_stack_type& node_stack, key_type& buf)
548 const pack_value_type* node_pos =
nullptr;
549 size_t index_size = 0;
556 stack_item* si = &node_stack.back();
557 node_pos = si->node_pos;
559 size_t offset = *si->child_pos;
561 key_unit_type c = *si->child_pos;
565 const auto* p = node_pos;
569 const auto* child_pos = p;
570 const auto* child_end = child_pos + index_size;
571 node_stack.emplace_back(node_stack.back().value_store, node_pos, child_end, child_end);
572 }
while (index_size);
583 const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf, pack_value_type pos)
584 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
585 m_current_value(pos), m_type(iterator_type::normal)
588 packed_iterator_base(
const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf)
589 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
590 m_type(iterator_type::end)
595 if (m_type != other.m_type)
598 if (m_type == iterator_type::empty)
601 return m_node_stack.back() == other.m_node_stack.back();
606 return !operator==(other);
611 assert(m_value_store);
612 assert(m_current_value != trie_type::null_value);
613 return value_type(m_buffer, (*m_value_store)[m_current_value]);
618 assert(m_value_store);
619 assert(m_current_value != trie_type::null_value);
620 return value_type(m_buffer, (*m_value_store)[m_current_value]);
625 stack_item* si = &m_node_stack.back();
626 pack_value_type v = trie_type::null_value;
627 size_t index_size = *(si->node_pos + 1);
638 if (m_node_stack.size() == 1)
640#ifdef MDDS_TRIE_MAP_DEBUG
641 if (m_type == iterator_type::end)
643 std::ostringstream os;
644 os <<
"packed_iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
649 m_type = iterator_type::end;
655 m_node_stack.pop_back();
656 si = &m_node_stack.back();
657 std::advance(si->child_pos, 2);
659 if (si->child_pos != si->child_end)
662 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
670 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
673 si = &m_node_stack.back();
675 index_size = *(si->node_pos + 1);
676 }
while (v == trie_type::null_value);
678 assert(v != trie_type::null_value);
693 stack_item* si = &m_node_stack.back();
694 pack_value_type v = *si->node_pos;
695 size_t index_size = *(si->node_pos + 1);
697 if (m_type == iterator_type::end && v != trie_type::null_value)
699 assert(m_node_stack.size() == 1);
700 m_type = iterator_type::normal;
702 else if (m_node_stack.size() == 1)
706 assert(si->child_pos == si->child_end);
707 descend_to_previous_leaf_node(m_node_stack, m_buffer);
708 si = &m_node_stack.back();
710 m_type = iterator_type::normal;
712 else if (!index_size)
723 m_node_stack.pop_back();
724 si = &m_node_stack.back();
725 const auto* p = si->node_pos;
730 const auto* first_child = p;
732 if (si->child_pos != first_child)
735 descend_to_previous_leaf_node(m_node_stack, m_buffer);
736 si = &m_node_stack.back();
739 assert(v != trie_type::null_value);
741 }
while (v == trie_type::null_value);
748 assert(*si->node_pos);
749 assert(si->child_pos == (si->node_pos + 2));
755 m_node_stack.pop_back();
756 si = &m_node_stack.back();
759 if (m_node_stack.size() == 1)
762 descend_to_previous_leaf_node(m_node_stack, m_buffer);
763 si = &m_node_stack.back();
765 assert(v != trie_type::null_value);
767 }
while (v == trie_type::null_value);
770 assert(v != trie_type::null_value);
787 using trie_type = _TrieType;
789 using node_stack_type =
typename trie_type::node_stack_type;
790 using value_store_type =
typename trie_type::value_store_type;
791 using pack_value_type =
typename trie_type::pack_value_type;
793 using key_type =
typename trie_type::key_type;
794 using key_unit_type =
typename key_type::value_type;
796 const value_store_type* m_value_store =
nullptr;
797 const pack_value_type* m_node =
nullptr;
800 packed_search_results(
const value_store_type* value_store,
const pack_value_type* node, key_type&& buf)
801 : m_value_store(value_store), m_node(node), m_buffer(std::move(buf))
803 assert(m_value_store);
806 node_stack_type get_root_node()
const
808 const auto* p = m_node;
810 size_t index_size = *p;
812 const auto* child_pos = p;
813 const auto* child_end = child_pos + index_size;
816 node_stack_type node_stack;
817 node_stack.emplace_back(m_value_store, m_node, child_pos, child_end);
823 std::swap(m_node, other.m_node);
824 std::swap(m_buffer, other.m_buffer);
838 other.m_node =
nullptr;
855 key_type buf(m_buffer);
856 node_stack_type node_stack = get_root_node();
858 while (!node_stack.back().has_value())
863 const_iterator::push_child_node_to_stack(m_value_store, node_stack, buf, node_stack.back().child_pos);
866 return const_iterator(m_value_store, std::move(node_stack), std::move(buf), node_stack.back().get_value_pos());
875 node_stack_type node_stack = get_root_node();
876 auto& si = node_stack.back();
877 si.child_pos = si.child_end;
878 return const_iterator(m_value_store, std::move(node_stack), key_type(m_buffer));