67 using trie_type = TrieType;
69 using is_const_type = std::bool_constant<IsConst>;
75 using trie_node_type = mdds::detail::const_t<typename trie_type::trie_node, IsConst>;
77 typename std::remove_const<trie_node_type>::type::children_type, is_const_type>::type;
79 using key_type =
typename trie_type::key_type;
85 using pointer = value_type*;
86 using reference = value_type&;
87 using difference_type = std::ptrdiff_t;
88 using iterator_category = std::bidirectional_iterator_tag;
91 node_stack_type m_node_stack;
93 key_type m_current_key;
94 trie_value_type* m_current_value_ptr;
97 static trie_node_type* push_child_node_to_stack(
98 node_stack_type& node_stack, key_type& buf, trie_node_child_pos_type& child_pos)
100 trie_node_type* node = &child_pos->second;
101 buf.push_back(child_pos->first);
102 node_stack.emplace_back(node, node->children.begin());
113 trie_node_type* cur_node =
nullptr;
120 auto& si = node_stack.back();
123 buf.push_back(si.child_pos->first);
124 cur_node = &si.child_pos->second;
125 node_stack.emplace_back(cur_node, cur_node->children.end());
126 }
while (!cur_node->children.empty());
131 iterator_base(empty_iterator_type) : m_current_value_ptr(nullptr), m_type(iterator_type::empty)
135 iterator_base() : m_current_value_ptr(nullptr), m_type(iterator_type::normal)
138 iterator_base(node_stack_type&& node_stack, key_type&& buf, iterator_type type)
139 : m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)), m_current_key(m_buffer),
140 m_current_value_ptr(&m_node_stack.back().node->value), m_type(type)
143 bool operator==(
const iterator_base& other)
const
145 if (m_type != other.m_type)
148 if (m_type == iterator_type::empty)
151 return m_node_stack.back() == other.m_node_stack.back();
154 value_type operator*()
156 return value_type(m_current_key, *m_current_value_ptr);
159 value_type operator->()
161 return value_type(m_current_key, *m_current_value_ptr);
164 iterator_base& operator++()
166 trie_node_type* cur_node = m_node_stack.back().node;
170 if (cur_node->children.empty())
177 if (m_node_stack.size() == 1)
179#ifdef MDDS_TRIE_MAP_DEBUG
180 if (m_type == iterator_type::end)
182 std::ostringstream os;
183 os <<
"iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
184 throw general_error(os.str());
188 m_type = iterator_type::end;
194 m_node_stack.pop_back();
195 auto& si = m_node_stack.back();
198 if (si.child_pos != si.node->children.end())
201 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
209 auto child_pos = cur_node->children.begin();
210 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
212 }
while (!cur_node->has_value);
214 m_current_key = m_buffer;
215 m_current_value_ptr = &cur_node->value;
219 iterator_base operator++(
int)
221 iterator_base tmp(*
this);
226 iterator_base& operator--()
228 trie_node_type* cur_node = m_node_stack.back().node;
230 if (m_type == iterator_type::end && cur_node->has_value)
232 assert(m_node_stack.size() == 1);
233 m_type = iterator_type::normal;
235 else if (m_node_stack.size() == 1)
239 auto& si = m_node_stack.back();
240 assert(si.child_pos == cur_node->children.end());
242 m_type = iterator_type::normal;
244 else if (cur_node->children.empty())
255 m_node_stack.pop_back();
256 auto& si = m_node_stack.back();
259 if (si.child_pos != cur_node->children.begin())
263 assert(cur_node->has_value);
265 }
while (!cur_node->has_value);
272 assert(cur_node->has_value);
273 assert(m_node_stack.back().child_pos == cur_node->children.begin());
279 m_node_stack.pop_back();
280 auto& si = m_node_stack.back();
283 if (m_node_stack.size() == 1)
287 assert(cur_node->has_value);
289 }
while (!cur_node->has_value);
292 assert(cur_node->has_value);
293 m_current_key = m_buffer;
294 m_current_value_ptr = &cur_node->value;
298 iterator_base operator--(
int)
300 iterator_base tmp(*
this);
390 using trie_type = TrieType;
392 using node_stack_type =
typename trie_type::const_node_stack_type;
394 using trie_node =
typename trie_type::trie_node;
395 using key_type =
typename trie_type::key_type;
396 using key_unit_type =
typename key_type::value_type;
398 const trie_node* m_node;
400 node_stack_type m_node_stack;
402 search_results(
const trie_node* node, key_type&& buf) : m_node(node), m_buffer(std::move(buf))
406 using const_iterator =
typename trie_type::const_iterator;
408 const_iterator begin()
const
412 return const_iterator(empty_iterator);
415 key_type buf(m_buffer);
416 node_stack_type node_stack;
417 node_stack.emplace_back(m_node, m_node->children.begin());
419 while (!node_stack.back().node->has_value)
424 auto it = node_stack.back().child_pos;
425 const_iterator::push_child_node_to_stack(node_stack, buf, it);
428 return const_iterator(std::move(node_stack), std::move(buf), iterator_type::normal);
431 const_iterator end()
const
435 return const_iterator(empty_iterator);
437 node_stack_type node_stack;
438 node_stack.emplace_back(m_node, m_node->children.end());
439 return const_iterator(std::move(node_stack), key_type(m_buffer), iterator_type::end);
447class packed_iterator_base
449 using trie_type = TrieT;
453 using stack_item =
typename trie_type::stack_item;
454 using node_stack_type =
typename trie_type::node_stack_type;
456 using key_type =
typename trie_type::key_type;
457 using size_type =
typename trie_type::size_type;
458 using trie_value_type =
typename trie_type::value_type;
459 using value_store_type =
typename trie_type::value_store_type;
460 using pack_value_type =
typename trie_type::pack_value_type;
461 using key_unit_type =
typename key_type::value_type;
466 using pointer = value_type*;
467 using reference = value_type&;
468 using difference_type = std::ptrdiff_t;
469 using iterator_category = std::bidirectional_iterator_tag;
472 const value_store_type* m_value_store =
nullptr;
473 node_stack_type m_node_stack;
475 pack_value_type m_current_value = trie_type::null_value;
476 iterator_type m_type;
482 static void push_child_node_to_stack(
483 const value_store_type* value_store, node_stack_type& node_stack, key_type& buf,
484 const pack_value_type* child_pos)
487 const auto* node_pos = node_stack.back().node_pos;
489 key_unit_type c =
static_cast<key_unit_type
>(*child_pos);
492 auto offset =
static_cast<size_type
>(*child_pos);
494 const auto* p = node_pos;
496 size_type index_size = *p;
499 const auto* child_end = child_pos + index_size;
502 node_stack.emplace_back(value_store, node_pos, child_pos, child_end);
505 static void descend_to_previous_leaf_node(node_stack_type& node_stack, key_type& buf)
507 const pack_value_type* node_pos =
nullptr;
508 size_t index_size = 0;
515 stack_item* si = &node_stack.back();
516 node_pos = si->node_pos;
518 size_t offset = *si->child_pos;
520 key_unit_type c = *si->child_pos;
524 const auto* p = node_pos;
528 const auto* child_pos = p;
529 const auto* child_end = child_pos + index_size;
530 node_stack.emplace_back(node_stack.back().value_store, node_pos, child_end, child_end);
531 }
while (index_size);
534 packed_iterator_base(empty_iterator_type) : m_type(iterator_type::empty)
538 packed_iterator_base() : m_type(iterator_type::normal)
541 packed_iterator_base(
542 const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf, pack_value_type pos)
543 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
544 m_current_value(pos), m_type(iterator_type::normal)
547 packed_iterator_base(
const value_store_type* value_store, node_stack_type&& node_stack, key_type&& buf)
548 : m_value_store(value_store), m_node_stack(std::move(node_stack)), m_buffer(std::move(buf)),
549 m_type(iterator_type::end)
552 bool operator==(
const packed_iterator_base& other)
const
554 if (m_type != other.m_type)
557 if (m_type == iterator_type::empty)
560 return m_node_stack.back() == other.m_node_stack.back();
563 value_type operator*()
565 assert(m_value_store);
566 assert(m_current_value != trie_type::null_value);
567 return value_type(m_buffer, (*m_value_store)[m_current_value]);
570 value_type operator->()
572 assert(m_value_store);
573 assert(m_current_value != trie_type::null_value);
574 return value_type(m_buffer, (*m_value_store)[m_current_value]);
577 packed_iterator_base& operator++()
579 stack_item* si = &m_node_stack.back();
580 pack_value_type v = trie_type::null_value;
581 size_t index_size = *(si->node_pos + 1);
592 if (m_node_stack.size() == 1)
594#ifdef MDDS_TRIE_MAP_DEBUG
595 if (m_type == iterator_type::end)
597 std::ostringstream os;
598 os <<
"packed_iterator_base::operator++#" << __LINE__ <<
": moving past the end position!";
603 m_type = iterator_type::end;
609 m_node_stack.pop_back();
610 si = &m_node_stack.back();
611 std::advance(si->child_pos, 2);
613 if (si->child_pos != si->child_end)
616 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
624 push_child_node_to_stack(m_value_store, m_node_stack, m_buffer, si->child_pos);
627 si = &m_node_stack.back();
629 index_size = *(si->node_pos + 1);
630 }
while (v == trie_type::null_value);
632 assert(v != trie_type::null_value);
638 packed_iterator_base operator++(
int)
640 packed_iterator_base tmp(*
this);
645 packed_iterator_base& operator--()
647 stack_item* si = &m_node_stack.back();
648 pack_value_type v = *si->node_pos;
649 size_t index_size = *(si->node_pos + 1);
651 if (m_type == iterator_type::end && v != trie_type::null_value)
653 assert(m_node_stack.size() == 1);
654 m_type = iterator_type::normal;
656 else if (m_node_stack.size() == 1)
660 assert(si->child_pos == si->child_end);
661 descend_to_previous_leaf_node(m_node_stack, m_buffer);
662 si = &m_node_stack.back();
664 m_type = iterator_type::normal;
666 else if (!index_size)
677 m_node_stack.pop_back();
678 si = &m_node_stack.back();
679 const auto* p = si->node_pos;
684 const auto* first_child = p;
686 if (si->child_pos != first_child)
689 descend_to_previous_leaf_node(m_node_stack, m_buffer);
690 si = &m_node_stack.back();
693 assert(v != trie_type::null_value);
695 }
while (v == trie_type::null_value);
702 assert(*si->node_pos);
703 assert(si->child_pos == (si->node_pos + 2));
709 m_node_stack.pop_back();
710 si = &m_node_stack.back();
713 if (m_node_stack.size() == 1)
716 descend_to_previous_leaf_node(m_node_stack, m_buffer);
717 si = &m_node_stack.back();
719 assert(v != trie_type::null_value);
721 }
while (v == trie_type::null_value);
724 assert(v != trie_type::null_value);
730 packed_iterator_base operator--(
int)
732 packed_iterator_base tmp(*
this);
739class packed_search_results
741 using trie_type = TrieType;
743 using node_stack_type =
typename trie_type::node_stack_type;
744 using value_store_type =
typename trie_type::value_store_type;
745 using pack_value_type =
typename trie_type::pack_value_type;
747 using key_type =
typename trie_type::key_type;
748 using key_unit_type =
typename key_type::value_type;
750 const value_store_type* m_value_store =
nullptr;
751 const pack_value_type* m_node =
nullptr;
754 packed_search_results(
const value_store_type* value_store,
const pack_value_type* node, key_type&& buf)
755 : m_value_store(value_store), m_node(node), m_buffer(std::move(buf))
757 assert(m_value_store);
760 node_stack_type get_root_node()
const
762 const auto* p = m_node;
764 size_t index_size = *p;
766 const auto* child_pos = p;
767 const auto* child_end = child_pos + index_size;
770 node_stack_type node_stack;
771 node_stack.emplace_back(m_value_store, m_node, child_pos, child_end);
775 void swap(packed_search_results& other)
777 std::swap(m_node, other.m_node);
778 std::swap(m_buffer, other.m_buffer);
784 packed_search_results() : m_node(
nullptr)
787 packed_search_results(
const packed_search_results& other) : m_node(other.m_node), m_buffer(other.m_buffer)
790 packed_search_results(packed_search_results&& other) : m_node(other.m_node), m_buffer(std::move(other.m_buffer))
792 other.m_node =
nullptr;
795 packed_search_results& operator=(packed_search_results other)
797 packed_search_results tmp(std::move(other));
802 const_iterator begin()
const
806 return const_iterator(empty_iterator);
809 key_type buf(m_buffer);
810 node_stack_type node_stack = get_root_node();
812 while (!node_stack.back().has_value())
817 const_iterator::push_child_node_to_stack(m_value_store, node_stack, buf, node_stack.back().child_pos);
820 return const_iterator(m_value_store, std::move(node_stack), std::move(buf), node_stack.back().get_value_pos());
823 const_iterator end()
const
827 return const_iterator(empty_iterator);
829 node_stack_type node_stack = get_root_node();
830 auto& si = node_stack.back();
831 si.child_pos = si.child_end;
832 return const_iterator(m_value_store, std::move(node_stack), key_type(m_buffer));