libstdc++
trie_policy_base.hpp
Go to the documentation of this file.
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