libstdc++
trie_policy_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2021 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file trie_policy/trie_policy_base.hpp
38  * Contains an implementation of trie_policy_base.
39  */
40 
41 #ifndef PB_DS_TRIE_POLICY_BASE_HPP
42 #define PB_DS_TRIE_POLICY_BASE_HPP
43 
45 
46 namespace __gnu_pbds
47 {
48  namespace detail
49  {
50  /// Base class for trie policies.
51  template<typename Node_CItr, typename Node_Itr,
52  typename _ATraits, typename _Alloc>
54  : public branch_policy<Node_CItr, Node_Itr, _Alloc>
55  {
57 
58  public:
59  typedef _ATraits access_traits;
60  typedef _Alloc allocator_type;
61  typedef typename allocator_type::size_type size_type;
62  typedef null_type metadata_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;
69 
70  protected:
71  virtual const_iterator
72  end() const = 0;
73 
74  virtual iterator
75  end() = 0;
76 
77  virtual node_const_iterator
78  node_begin() const = 0;
79 
80  virtual node_iterator
81  node_begin() = 0;
82 
83  virtual node_const_iterator
84  node_end() const = 0;
85 
86  virtual node_iterator
87  node_end() = 0;
88 
89  virtual const access_traits&
90  get_access_traits() const = 0;
91 
92  private:
93  typedef typename access_traits::const_iterator e_const_iterator;
95 
96  protected:
97  static size_type
98  common_prefix_len(node_iterator, e_const_iterator,
99  e_const_iterator, const access_traits&);
100 
101  static iterator
102  leftmost_it(node_iterator);
103 
104  static iterator
105  rightmost_it(node_iterator);
106 
107  static bool
108  less(e_const_iterator, e_const_iterator, e_const_iterator,
109  e_const_iterator, const access_traits&);
110  };
111 
112 
113 #define PB_DS_CLASS_T_DEC \
114  template<typename Node_CItr, typename Node_Itr, \
115  typename _ATraits, typename _Alloc>
116 
117 #define PB_DS_CLASS_C_DEC \
118  trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>
119 
120  PB_DS_CLASS_T_DEC
121  typename PB_DS_CLASS_C_DEC::size_type
122  PB_DS_CLASS_C_DEC::
123  common_prefix_len(node_iterator nd_it, e_const_iterator b_r,
124  e_const_iterator e_r, const access_traits& r_traits)
125  {
126  prefix_range_t pref_range = nd_it.valid_prefix();
127 
128  e_const_iterator b_l = pref_range.first;
129  e_const_iterator e_l = pref_range.second;
130 
131  const size_type range_length_l = std::distance(b_l, e_l);
132  const size_type range_length_r = std::distance(b_r, e_r);
133 
134  if (range_length_r < range_length_l)
135  {
136  std::swap(b_l, b_r);
137  std::swap(e_l, e_r);
138  }
139 
140  size_type ret = 0;
141  while (b_l != e_l)
142  {
143  if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r))
144  return ret;
145 
146  ++ret;
147  ++b_l;
148  ++b_r;
149  }
150 
151  return ret;
152  }
153 
154  PB_DS_CLASS_T_DEC
155  typename PB_DS_CLASS_C_DEC::iterator
156  PB_DS_CLASS_C_DEC::
157  leftmost_it(node_iterator nd_it)
158  {
159  if (nd_it.num_children() == 0)
160  return *nd_it;
161 
162  return leftmost_it(nd_it.get_child(0));
163  }
164 
165  PB_DS_CLASS_T_DEC
166  typename PB_DS_CLASS_C_DEC::iterator
167  PB_DS_CLASS_C_DEC::
168  rightmost_it(node_iterator nd_it)
169  {
170  const size_type num_children = nd_it.num_children();
171 
172  if (num_children == 0)
173  return *nd_it;
174 
175  return rightmost_it(nd_it.get_child(num_children - 1));
176  }
177 
178  PB_DS_CLASS_T_DEC
179  bool
180  PB_DS_CLASS_C_DEC::
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)
184  {
185  while (b_l != e_l)
186  {
187  if (b_r == e_r)
188  return false;
189 
190  size_type l_pos = r_traits.e_pos(*b_l);
191  size_type r_pos = r_traits.e_pos(*b_r);
192  if (l_pos != r_pos)
193  return (l_pos < r_pos);
194 
195  ++b_l;
196  ++b_r;
197  }
198  return b_r != e_r;
199  }
200 
201 #undef PB_DS_CLASS_T_DEC
202 #undef PB_DS_CLASS_C_DEC
203 
204  } // namespace detail
205 } // namespace __gnu_pbds
206 
207 #endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP
Base class for trie policies.
Primary template, base class for branch structure policies.
Represents no type, or absence of type, for template tricks.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:211
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.