libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file trie_policy/trie_policy_base.hpp 00038 * Contains an implementation of trie_policy_base. 00039 */ 00040 00041 #ifndef PB_DS_TRIE_POLICY_BASE_HPP 00042 #define PB_DS_TRIE_POLICY_BASE_HPP 00043 00044 #include <ext/pb_ds/detail/branch_policy/branch_policy.hpp> 00045 00046 namespace __gnu_pbds 00047 { 00048 namespace detail 00049 { 00050 /// Base class for trie policies. 00051 template<typename Node_CItr, typename Node_Itr, 00052 typename _ATraits, typename _Alloc> 00053 class trie_policy_base 00054 : public branch_policy<Node_CItr, Node_Itr, _Alloc> 00055 { 00056 typedef branch_policy<Node_CItr, Node_Itr, _Alloc> base_type; 00057 00058 public: 00059 typedef _ATraits access_traits; 00060 typedef _Alloc allocator_type; 00061 typedef typename allocator_type::size_type size_type; 00062 typedef null_type metadata_type; 00063 typedef Node_CItr node_const_iterator; 00064 typedef Node_Itr node_iterator; 00065 typedef typename node_const_iterator::value_type const_iterator; 00066 typedef typename node_iterator::value_type iterator; 00067 typedef typename base_type::key_type key_type; 00068 typedef typename base_type::key_const_reference key_const_reference; 00069 00070 protected: 00071 virtual const_iterator 00072 end() const = 0; 00073 00074 virtual iterator 00075 end() = 0; 00076 00077 virtual node_const_iterator 00078 node_begin() const = 0; 00079 00080 virtual node_iterator 00081 node_begin() = 0; 00082 00083 virtual node_const_iterator 00084 node_end() const = 0; 00085 00086 virtual node_iterator 00087 node_end() = 0; 00088 00089 virtual const access_traits& 00090 get_access_traits() const = 0; 00091 00092 private: 00093 typedef typename access_traits::const_iterator e_const_iterator; 00094 typedef std::pair<e_const_iterator, e_const_iterator> prefix_range_t; 00095 00096 protected: 00097 static size_type 00098 common_prefix_len(node_iterator, e_const_iterator, 00099 e_const_iterator, const access_traits&); 00100 00101 static iterator 00102 leftmost_it(node_iterator); 00103 00104 static iterator 00105 rightmost_it(node_iterator); 00106 00107 static bool 00108 less(e_const_iterator, e_const_iterator, e_const_iterator, 00109 e_const_iterator, const access_traits&); 00110 }; 00111 00112 00113 #define PB_DS_CLASS_T_DEC \ 00114 template<typename Node_CItr, typename Node_Itr, \ 00115 typename _ATraits, typename _Alloc> 00116 00117 #define PB_DS_CLASS_C_DEC \ 00118 trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc> 00119 00120 PB_DS_CLASS_T_DEC 00121 typename PB_DS_CLASS_C_DEC::size_type 00122 PB_DS_CLASS_C_DEC:: 00123 common_prefix_len(node_iterator nd_it, e_const_iterator b_r, 00124 e_const_iterator e_r, const access_traits& r_traits) 00125 { 00126 prefix_range_t pref_range = nd_it.valid_prefix(); 00127 00128 e_const_iterator b_l = pref_range.first; 00129 e_const_iterator e_l = pref_range.second; 00130 00131 const size_type range_length_l = std::distance(b_l, e_l); 00132 const size_type range_length_r = std::distance(b_r, e_r); 00133 00134 if (range_length_r < range_length_l) 00135 { 00136 std::swap(b_l, b_r); 00137 std::swap(e_l, e_r); 00138 } 00139 00140 size_type ret = 0; 00141 while (b_l != e_l) 00142 { 00143 if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r)) 00144 return ret; 00145 00146 ++ret; 00147 ++b_l; 00148 ++b_r; 00149 } 00150 00151 return ret; 00152 } 00153 00154 PB_DS_CLASS_T_DEC 00155 typename PB_DS_CLASS_C_DEC::iterator 00156 PB_DS_CLASS_C_DEC:: 00157 leftmost_it(node_iterator nd_it) 00158 { 00159 if (nd_it.num_children() == 0) 00160 return *nd_it; 00161 00162 return leftmost_it(nd_it.get_child(0)); 00163 } 00164 00165 PB_DS_CLASS_T_DEC 00166 typename PB_DS_CLASS_C_DEC::iterator 00167 PB_DS_CLASS_C_DEC:: 00168 rightmost_it(node_iterator nd_it) 00169 { 00170 const size_type num_children = nd_it.num_children(); 00171 00172 if (num_children == 0) 00173 return *nd_it; 00174 00175 return rightmost_it(nd_it.get_child(num_children - 1)); 00176 } 00177 00178 PB_DS_CLASS_T_DEC 00179 bool 00180 PB_DS_CLASS_C_DEC:: 00181 less(e_const_iterator b_l, e_const_iterator e_l, 00182 e_const_iterator b_r, e_const_iterator e_r, 00183 const access_traits& r_traits) 00184 { 00185 while (b_l != e_l) 00186 { 00187 if (b_r == e_r) 00188 return false; 00189 00190 size_type l_pos = r_traits.e_pos(*b_l); 00191 size_type r_pos = r_traits.e_pos(*b_r); 00192 if (l_pos != r_pos) 00193 return (l_pos < r_pos); 00194 00195 ++b_l; 00196 ++b_r; 00197 } 00198 return b_r != e_r; 00199 } 00200 00201 #undef PB_DS_CLASS_T_DEC 00202 #undef PB_DS_CLASS_C_DEC 00203 00204 } // namespace detail 00205 } // namespace __gnu_pbds 00206 00207 #endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP