1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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_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 44#include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp> 45 46namespace __gnu_pbds 47{ 48 namespace detail 49 { 50 51#define PB_DS_CLASS_T_DEC \ 52 template< \ 53 class Const_Node_Iterator, \ 54 class Node_Iterator, \ 55 class E_Access_Traits, \ 56 typename Allocator> 57 58#define PB_DS_CLASS_C_DEC \ 59 trie_policy_base< \ 60 Const_Node_Iterator, \ 61 Node_Iterator, \ 62 E_Access_Traits, \ 63 Allocator> 64 65#define PB_DS_BASE_C_DEC \ 66 basic_tree_policy_base< \ 67 Const_Node_Iterator, \ 68 Node_Iterator, \ 69 Allocator> 70 71 template<typename Const_Node_Iterator, 72 class Node_Iterator, 73 class E_Access_Traits, 74 class Allocator> 75 class trie_policy_base : public PB_DS_BASE_C_DEC 76 { 77 78 public: 79 80 typedef E_Access_Traits e_access_traits; 81 82 typedef Allocator allocator_type; 83 84 typedef typename allocator_type::size_type size_type; 85 86 typedef null_node_metadata metadata_type; 87 88 typedef Const_Node_Iterator const_node_iterator; 89 90 typedef Node_Iterator node_iterator; 91 92 typedef typename const_node_iterator::value_type const_iterator; 93 94 typedef typename node_iterator::value_type iterator; 95 96 public: 97 98 typedef typename PB_DS_BASE_C_DEC::key_type key_type; 99 100 typedef 101 typename PB_DS_BASE_C_DEC::const_key_reference 102 const_key_reference; 103 104 protected: 105 106 virtual const_iterator 107 end() const = 0; 108 109 virtual iterator 110 end() = 0; 111 112 virtual const_node_iterator 113 node_begin() const = 0; 114 115 virtual node_iterator 116 node_begin() = 0; 117 118 virtual const_node_iterator 119 node_end() const = 0; 120 121 virtual node_iterator 122 node_end() = 0; 123 124 virtual const e_access_traits& 125 get_e_access_traits() const = 0; 126 127 private: 128 typedef 129 std::pair< 130 typename e_access_traits::const_iterator, 131 typename e_access_traits::const_iterator> 132 prefix_range_t; 133 134 typedef PB_DS_BASE_C_DEC base_type; 135 136 protected: 137 static size_type 138 common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits); 139 140 static iterator 141 leftmost_it(node_iterator nd_it); 142 143 static iterator 144 rightmost_it(node_iterator nd_it); 145 146 static bool 147 less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits); 148 }; 149 150 PB_DS_CLASS_T_DEC 151 typename PB_DS_CLASS_C_DEC::size_type 152 PB_DS_CLASS_C_DEC:: 153 common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits) 154 { 155 prefix_range_t pref_range = nd_it.valid_prefix(); 156 157 typename e_access_traits::const_iterator b_l = pref_range.first; 158 typename e_access_traits::const_iterator e_l = pref_range.second; 159 160 const size_type range_length_l = 161 std::distance(b_l, e_l); 162 163 const size_type range_length_r = 164 std::distance(b_r, e_r); 165 166 if (range_length_r < range_length_l) 167 { 168 std::swap(b_l, b_r); 169 170 std::swap(e_l, e_r); 171 } 172 173 size_type ret = 0; 174 175 while (b_l != e_l) 176 { 177 if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r)) 178 return (ret); 179 180 ++ret; 181 182 ++b_l; 183 184 ++b_r; 185 } 186 187 return (ret); 188 } 189 190 PB_DS_CLASS_T_DEC 191 typename PB_DS_CLASS_C_DEC::iterator 192 PB_DS_CLASS_C_DEC:: 193 leftmost_it(node_iterator nd_it) 194 { 195 if (nd_it.num_children() == 0) 196 return (*nd_it); 197 198 return (leftmost_it(nd_it.get_child(0))); 199 } 200 201 PB_DS_CLASS_T_DEC 202 typename PB_DS_CLASS_C_DEC::iterator 203 PB_DS_CLASS_C_DEC:: 204 rightmost_it(node_iterator nd_it) 205 { 206 const size_type num_children = nd_it.num_children(); 207 208 if (num_children == 0) 209 return (*nd_it); 210 211 return (rightmost_it(nd_it.get_child(num_children - 1))); 212 } 213 214 PB_DS_CLASS_T_DEC 215 bool 216 PB_DS_CLASS_C_DEC:: 217 less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits) 218 { 219 while (b_l != e_l) 220 { 221 if (b_r == e_r) 222 return (false); 223 224 size_type l_pos = 225 r_traits.e_pos(*b_l); 226 size_type r_pos = 227 r_traits.e_pos(*b_r); 228 229 if (l_pos != r_pos) 230 return (l_pos < r_pos); 231 232 ++b_l; 233 ++b_r; 234 } 235 236 return (b_r != e_r); 237 } 238 239#undef PB_DS_CLASS_T_DEC 240 241#undef PB_DS_CLASS_C_DEC 242 243#undef PB_DS_BASE_C_DEC 244 245 } // namespace detail 246} // namespace __gnu_pbds 247 248#endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP 249 250