41#ifndef PB_DS_TRIE_POLICY_BASE_HPP
42#define PB_DS_TRIE_POLICY_BASE_HPP
51 template<
typename Node_CItr,
typename Node_Itr,
52 typename _ATraits,
typename _Alloc>
59 typedef _ATraits access_traits;
60 typedef _Alloc allocator_type;
61 typedef typename allocator_type::size_type size_type;
63 typedef Node_CItr node_const_iterator;
64 typedef Node_Itr node_iterator;
65 typedef typename node_const_iterator::value_type const_iterator;
66 typedef typename node_iterator::value_type iterator;
67 typedef typename base_type::key_type key_type;
68 typedef typename base_type::key_const_reference key_const_reference;
71 virtual const_iterator
77 virtual node_const_iterator
78 node_begin()
const = 0;
83 virtual node_const_iterator
89 virtual const access_traits&
90 get_access_traits()
const = 0;
93 typedef typename access_traits::const_iterator e_const_iterator;
98 common_prefix_len(node_iterator, e_const_iterator,
99 e_const_iterator,
const access_traits&);
102 leftmost_it(node_iterator);
105 rightmost_it(node_iterator);
108 less(e_const_iterator, e_const_iterator, e_const_iterator,
109 e_const_iterator,
const access_traits&);
113#define PB_DS_CLASS_T_DEC \
114 template<typename Node_CItr, typename Node_Itr, \
115 typename _ATraits, typename _Alloc>
117#define PB_DS_CLASS_C_DEC \
118 trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>
121 typename PB_DS_CLASS_C_DEC::size_type
123 common_prefix_len(node_iterator nd_it, e_const_iterator b_r,
124 e_const_iterator e_r,
const access_traits& r_traits)
126 prefix_range_t pref_range = nd_it.valid_prefix();
128 e_const_iterator b_l = pref_range.first;
129 e_const_iterator e_l = pref_range.second;
134 if (range_length_r < range_length_l)
143 if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r))
155 typename PB_DS_CLASS_C_DEC::iterator
157 leftmost_it(node_iterator nd_it)
159 if (nd_it.num_children() == 0)
162 return leftmost_it(nd_it.get_child(0));
166 typename PB_DS_CLASS_C_DEC::iterator
168 rightmost_it(node_iterator nd_it)
170 const size_type num_children = nd_it.num_children();
172 if (num_children == 0)
175 return rightmost_it(nd_it.get_child(num_children - 1));
181 less(e_const_iterator b_l, e_const_iterator e_l,
182 e_const_iterator b_r, e_const_iterator e_r,
183 const access_traits& r_traits)
190 size_type l_pos = r_traits.e_pos(*b_l);
191 size_type r_pos = r_traits.e_pos(*b_r);
193 return (l_pos < r_pos);
201#undef PB_DS_CLASS_T_DEC
202#undef PB_DS_CLASS_C_DEC
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU extensions for policy-based data structures for public use.
Struct holding two objects of arbitrary type.
Represents no type, or absence of type, for template tricks.
Primary template, base class for branch structure policies.
Base class for trie policies.