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"
40 namespace mdds {
namespace trie {
namespace detail {
42 enum class iterator_type
63 enum empty_iterator_type { empty_iterator };
65 template<
typename _TrieType>
68 template<
typename _TrieType>
71 typedef _TrieType trie_type;
73 friend search_results<trie_type>;
75 typedef typename trie_type::node_stack_type node_stack_type;
77 typedef typename trie_type::trie_node trie_node;
78 typedef typename trie_type::key_trait_type key_trait_type;
79 typedef typename key_trait_type::key_type key_type;
80 typedef typename key_trait_type::key_buffer_type key_buffer_type;
81 typedef typename key_trait_type::key_unit_type key_unit_type;
85 typedef typename trie_type::key_value_type value_type;
86 typedef value_type* pointer;
87 typedef value_type& reference;
88 typedef std::ptrdiff_t difference_type;
89 typedef std::bidirectional_iterator_tag iterator_category;
92 node_stack_type m_node_stack;
93 key_buffer_type m_buffer;
94 value_type m_current_value;
97 static const trie_node* push_child_node_to_stack(
98 node_stack_type& node_stack, key_buffer_type& buf,
99 const typename trie_node::children_type::const_iterator& child_pos)
101 using ktt = key_trait_type;
103 const trie_node* node = &child_pos->second;
104 ktt::push_back(buf, child_pos->first);
105 node_stack.emplace_back(node, node->children.begin());
114 static const trie_node* descend_to_previus_leaf_node(
115 node_stack_type& node_stack, key_buffer_type& buf)
117 using ktt = key_trait_type;
119 const trie_node* cur_node =
nullptr;
126 auto& si = node_stack.back();
129 ktt::push_back(buf, si.child_pos->first);
130 cur_node = &si.child_pos->second;
131 node_stack.emplace_back(cur_node, cur_node->children.end());
133 while (!cur_node->children.empty());
138 iterator_base(empty_iterator_type) : m_type(iterator_type::empty) {}
143 iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf, iterator_type type) :
144 m_node_stack(std::move(node_stack)),
145 m_buffer(std::move(buf)),
146 m_current_value(key_trait_type::to_key(m_buffer), m_node_stack.back().node->value),
152 if (m_type != other.m_type)
155 if (m_type == iterator_type::empty)
158 return m_node_stack.back() == other.m_node_stack.back();
161 bool operator!= (
const iterator_base& other)
const
163 return !operator==(other);
166 const value_type& operator*()
168 return m_current_value;
171 const value_type* operator->()
173 return &m_current_value;
176 iterator_base& operator++()
178 using ktt = key_trait_type;
180 const trie_node* cur_node = m_node_stack.back().node;
184 if (cur_node->children.empty())
191 if (m_node_stack.size() == 1)
193 #ifdef MDDS_TRIE_MAP_DEBUG
194 if (m_type == iterator_type::end)
196 std::ostringstream os;
197 os <<
"iterator_base::operator++#" << __LINE__
198 <<
": moving past the end position!";
199 throw general_error(os.str());
203 m_type = iterator_type::end;
208 ktt::pop_back(m_buffer);
209 m_node_stack.pop_back();
210 auto& si = m_node_stack.back();
213 if (si.child_pos != si.node->children.end())
216 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, si.child_pos);
224 auto child_pos = cur_node->children.begin();
225 cur_node = push_child_node_to_stack(m_node_stack, m_buffer, child_pos);
228 while (!cur_node->has_value);
230 m_current_value = value_type(ktt::to_key(m_buffer), cur_node->value);
234 iterator_base operator++(
int)
236 iterator_base tmp(*
this);
241 iterator_base& operator--()
243 using ktt = key_trait_type;
244 const trie_node* cur_node = m_node_stack.back().node;
246 if (m_type == iterator_type::end && cur_node->has_value)
248 assert(m_node_stack.size() == 1);
249 m_type = iterator_type::normal;
251 else if (m_node_stack.size() == 1)
255 auto& si = m_node_stack.back();
256 assert(si.child_pos == cur_node->children.end());
257 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
258 m_type = iterator_type::normal;
260 else if (cur_node->children.empty())
270 ktt::pop_back(m_buffer);
271 m_node_stack.pop_back();
272 auto& si = m_node_stack.back();
275 if (si.child_pos != cur_node->children.begin())
278 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
279 assert(cur_node->has_value);
282 while (!cur_node->has_value);
289 assert(cur_node->has_value);
290 assert(m_node_stack.back().child_pos == cur_node->children.begin());
295 ktt::pop_back(m_buffer);
296 m_node_stack.pop_back();
297 auto& si = m_node_stack.back();
300 if (m_node_stack.size() == 1)
303 cur_node = descend_to_previus_leaf_node(m_node_stack, m_buffer);
304 assert(cur_node->has_value);
307 while (!cur_node->has_value);
310 assert(cur_node->has_value);
311 m_current_value = value_type(ktt::to_key(m_buffer), cur_node->value);
315 iterator_base operator--(
int)
317 iterator_base tmp(*
this);
323 template<
typename _TrieType>
326 typedef _TrieType trie_type;
328 typedef typename trie_type::node_stack_type node_stack_type;
330 typedef typename trie_type::trie_node trie_node;
331 typedef typename trie_type::key_trait_type key_trait_type;
332 typedef typename key_trait_type::key_type key_type;
333 typedef typename key_trait_type::key_buffer_type key_buffer_type;
334 typedef typename key_trait_type::key_unit_type key_unit_type;
336 const trie_node* m_node;
337 key_buffer_type m_buffer;
338 node_stack_type m_node_stack;
340 search_results(
const trie_node* node, key_buffer_type&& buf) :
341 m_node(node), m_buffer(buf) {}
344 typedef iterator_base<trie_type> const_iterator;
346 const_iterator begin()
const
350 return const_iterator(empty_iterator);
353 key_buffer_type buf(m_buffer);
354 node_stack_type node_stack;
355 node_stack.emplace_back(m_node, m_node->children.begin());
357 while (!node_stack.back().node->has_value)
362 auto it = node_stack.back().child_pos;
363 const_iterator::push_child_node_to_stack(node_stack, buf, it);
366 return const_iterator(
367 std::move(node_stack), std::move(buf), iterator_type::normal);
370 const_iterator end()
const
374 return const_iterator(empty_iterator);
376 node_stack_type node_stack;
377 node_stack.emplace_back(m_node, m_node->children.end());
378 return const_iterator(
379 std::move(node_stack), key_buffer_type(m_buffer), iterator_type::end);
383 template<
typename _TrieType>
384 class packed_search_results;
386 template<
typename _TrieType>
387 class packed_iterator_base
389 typedef _TrieType trie_type;
391 friend packed_search_results<trie_type>;
393 typedef typename trie_type::stack_item stack_item;
394 typedef typename trie_type::node_stack_type node_stack_type;
396 typedef typename trie_type::key_trait_type key_trait_type;
397 typedef typename key_trait_type::key_type key_type;
398 typedef typename key_trait_type::key_buffer_type key_buffer_type;
399 typedef typename key_trait_type::key_unit_type key_unit_type;
403 typedef typename trie_type::key_value_type value_type;
404 typedef value_type* pointer;
405 typedef value_type& reference;
406 typedef std::ptrdiff_t difference_type;
407 typedef std::bidirectional_iterator_tag iterator_category;
410 node_stack_type m_node_stack;
411 key_buffer_type m_buffer;
412 value_type m_current_value;
413 iterator_type m_type;
419 static void push_child_node_to_stack(
420 node_stack_type& node_stack, key_buffer_type& buf,
const uintptr_t* child_pos)
422 using ktt = key_trait_type;
424 const uintptr_t* node_pos = node_stack.back().node_pos;
426 key_unit_type c =
static_cast<key_unit_type
>(*child_pos);
427 ktt::push_back(buf, c);
429 size_t offset =
static_cast<size_t>(*child_pos);
431 const uintptr_t* p = node_pos;
433 size_t index_size = *p;
436 const uintptr_t* child_end = child_pos + index_size;
439 node_stack.emplace_back(node_pos, child_pos, child_end);
442 static const void descend_to_previus_leaf_node(
443 node_stack_type& node_stack, key_buffer_type& buf)
445 using ktt = key_trait_type;
447 const uintptr_t* node_pos =
nullptr;
448 size_t index_size = 0;
455 stack_item* si = &node_stack.back();
456 node_pos = si->node_pos;
458 size_t offset = *si->child_pos;
460 key_unit_type c = *si->child_pos;
462 ktt::push_back(buf, c);
464 const uintptr_t* p = node_pos;
468 const uintptr_t* child_pos = p;
469 const uintptr_t* child_end = child_pos + index_size;
470 node_stack.emplace_back(node_pos, child_end, child_end);
475 packed_iterator_base(empty_iterator_type) : m_type(iterator_type::empty) {}
478 packed_iterator_base() : m_type(iterator_type::normal) {}
480 packed_iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf,
const typename trie_type::value_type& v) :
481 m_node_stack(std::move(node_stack)),
482 m_buffer(std::move(buf)),
483 m_current_value(key_trait_type::to_key(m_buffer), v),
484 m_type(iterator_type::normal) {}
486 packed_iterator_base(node_stack_type&& node_stack, key_buffer_type&& buf) :
487 m_node_stack(std::move(node_stack)),
488 m_buffer(std::move(buf)),
489 m_type(iterator_type::end) {}
491 bool operator== (
const packed_iterator_base& other)
const
493 if (m_type != other.m_type)
496 if (m_type == iterator_type::empty)
499 return m_node_stack.back() == other.m_node_stack.back();
502 bool operator!= (
const packed_iterator_base& other)
const
504 return !operator==(other);
507 const value_type& operator*()
509 return m_current_value;
512 const value_type* operator->()
514 return &m_current_value;
517 packed_iterator_base& operator++()
519 using ktt = key_trait_type;
521 stack_item* si = &m_node_stack.back();
522 const typename trie_type::value_type* pv =
nullptr;
523 size_t index_size = *(si->node_pos+1);
534 if (m_node_stack.size() == 1)
536 #ifdef MDDS_TRIE_MAP_DEBUG
537 if (m_type == iterator_type::end)
539 std::ostringstream os;
540 os <<
"packed_iterator_base::operator++#"
541 << __LINE__ <<
": moving past the end position!";
542 throw general_error(os.str());
546 m_type = iterator_type::end;
551 ktt::pop_back(m_buffer);
552 m_node_stack.pop_back();
553 si = &m_node_stack.back();
554 std::advance(si->child_pos, 2);
556 if (si->child_pos != si->child_end)
559 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
567 push_child_node_to_stack(m_node_stack, m_buffer, si->child_pos);
570 si = &m_node_stack.back();
571 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*si->node_pos);
572 index_size = *(si->node_pos+1);
577 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
582 packed_iterator_base operator++(
int)
584 packed_iterator_base tmp(*
this);
589 packed_iterator_base& operator--()
591 using ktt = key_trait_type;
593 stack_item* si = &m_node_stack.back();
594 const typename trie_type::value_type* pv =
595 reinterpret_cast<const typename trie_type::value_type*
>(*si->node_pos);
596 size_t index_size = *(si->node_pos+1);
598 if (m_type == iterator_type::end && pv)
600 assert(m_node_stack.size() == 1);
601 m_type = iterator_type::normal;
603 else if (m_node_stack.size() == 1)
607 assert(si->child_pos == si->child_end);
608 descend_to_previus_leaf_node(m_node_stack, m_buffer);
609 si = &m_node_stack.back();
610 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*si->node_pos);
611 m_type = iterator_type::normal;
613 else if (!index_size)
623 ktt::pop_back(m_buffer);
624 m_node_stack.pop_back();
625 si = &m_node_stack.back();
626 const uintptr_t* p = si->node_pos;
627 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*p);
631 const uintptr_t* first_child = p;
633 if (si->child_pos != first_child)
636 descend_to_previus_leaf_node(m_node_stack, m_buffer);
637 si = &m_node_stack.back();
639 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*p);
650 assert(*si->node_pos);
651 assert(si->child_pos == (si->node_pos+2));
656 ktt::pop_back(m_buffer);
657 m_node_stack.pop_back();
658 si = &m_node_stack.back();
659 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*si->node_pos);
661 if (m_node_stack.size() == 1)
664 descend_to_previus_leaf_node(m_node_stack, m_buffer);
665 si = &m_node_stack.back();
666 pv =
reinterpret_cast<const typename trie_type::value_type*
>(*si->node_pos);
674 m_current_value = value_type(ktt::to_key(m_buffer), *pv);
679 packed_iterator_base operator--(
int)
681 packed_iterator_base tmp(*
this);
687 template<
typename _TrieType>
688 class packed_search_results
690 typedef _TrieType trie_type;
692 typedef typename trie_type::node_stack_type node_stack_type;
694 typedef typename trie_type::key_trait_type key_trait_type;
695 typedef typename key_trait_type::key_type key_type;
696 typedef typename key_trait_type::key_buffer_type key_buffer_type;
697 typedef typename key_trait_type::key_unit_type key_unit_type;
699 const uintptr_t* m_node;
700 key_buffer_type m_buffer;
702 packed_search_results(
const uintptr_t* node, key_buffer_type&& buf) :
703 m_node(node), m_buffer(std::move(buf)) {}
705 node_stack_type get_root_node()
const
707 const uintptr_t* p = m_node;
709 size_t index_size = *p;
711 const uintptr_t* child_pos = p;
712 const uintptr_t* child_end = child_pos + index_size;
715 node_stack_type node_stack;
716 node_stack.emplace_back(m_node, child_pos, child_end);
720 void swap(packed_search_results& other)
722 std::swap(m_node, other.m_node);
723 std::swap(m_buffer, other.m_buffer);
727 typedef packed_iterator_base<trie_type> const_iterator;
729 packed_search_results() : m_node(nullptr) {}
731 packed_search_results(
const packed_search_results& other) :
732 m_node(other.m_node), m_buffer(other.m_buffer) {}
734 packed_search_results(packed_search_results&& other) :
735 m_node(other.m_node), m_buffer(std::move(other.m_buffer))
737 other.m_node =
nullptr;
740 packed_search_results& operator= (packed_search_results other)
742 packed_search_results tmp(std::move(other));
747 const_iterator begin()
const
751 return const_iterator(empty_iterator);
754 key_buffer_type buf(m_buffer);
755 node_stack_type node_stack = get_root_node();
757 while (!node_stack.back().has_value())
762 const_iterator::push_child_node_to_stack(node_stack, buf, node_stack.back().child_pos);
765 return const_iterator(
766 std::move(node_stack), std::move(buf), *node_stack.back().get_value());
769 const_iterator end()
const
773 return const_iterator(empty_iterator);
775 node_stack_type node_stack = get_root_node();
776 auto& si = node_stack.back();
777 si.child_pos = si.child_end;
778 return const_iterator(std::move(node_stack), key_buffer_type(m_buffer));