libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp

   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
  46 namespace __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