contrib/libstdc++/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file trie_policy_base.hpp
  44  * Contains an implementation of trie_policy_base.
  45  */
  46
  47 #ifndef PB_DS_TRIE_POLICY_BASE_HPP
  48 #define PB_DS_TRIE_POLICY_BASE_HPP
  49
  50 #include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
  51
  52 namespace pb_ds
  53 {
  54   namespace detail
  55   {
  56
  57 #define PB_DS_CLASS_T_DEC                                               \
  58     template<                                                           \
  59                                                 class Const_Node_Iterator, \
  60                                                 class Node_Iterator,    \
  61                                                 class E_Access_Traits,  \
  62                                                 typename Allocator>
  63
  64 #define PB_DS_CLASS_C_DEC                                               \
  65     trie_policy_base<                                                   \
  66                                                 Const_Node_Iterator,    \
  67                                                 Node_Iterator,          \
  68                                                 E_Access_Traits,        \
  69                                                 Allocator>
  70
  71 #define PB_DS_BASE_C_DEC                                                \
  72     basic_tree_policy_base<                             \
  73                                                                 Const_Node_Iterator, \
  74                                                                 Node_Iterator, \
  75                                                                 Allocator>
  76
  77     template<typename Const_Node_Iterator,
  78              class Node_Iterator,
  79              class E_Access_Traits,
  80              class Allocator>
  81     class trie_policy_base : public PB_DS_BASE_C_DEC
  82     {
  83
  84     public:
  85
  86       typedef E_Access_Traits e_access_traits;
  87
  88       typedef Allocator allocator;
  89
  90       typedef typename allocator::size_type size_type;
  91
  92       typedef null_node_metadata metadata_type;
  93
  94       typedef Const_Node_Iterator const_node_iterator;
  95
  96       typedef Node_Iterator node_iterator;
  97
  98       typedef typename const_node_iterator::value_type const_iterator;
  99
 100       typedef typename node_iterator::value_type iterator;
 101
 102     public:
 103
 104       typedef typename PB_DS_BASE_C_DEC::key_type key_type;
 105
 106       typedef
 107       typename PB_DS_BASE_C_DEC::const_key_reference
 108       const_key_reference;
 109
 110     protected:
 111
 112       virtual const_iterator
 113       end() const = 0;
 114
 115       virtual iterator
 116       end() = 0;
 117
 118       virtual const_node_iterator
 119       node_begin() const = 0;
 120
 121       virtual node_iterator
 122       node_begin() = 0;
 123
 124       virtual const_node_iterator
 125       node_end() const = 0;
 126
 127       virtual node_iterator
 128       node_end() = 0;
 129
 130       virtual const e_access_traits&
 131       get_e_access_traits() const = 0;
 132
 133     private:
 134       typedef
 135       std::pair<
 136       typename e_access_traits::const_iterator,
 137       typename e_access_traits::const_iterator>
 138       prefix_range_t;
 139
 140       typedef PB_DS_BASE_C_DEC base_type;
 141
 142     protected:
 143       static size_type
 144       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);
 145
 146       static iterator
 147       leftmost_it(node_iterator nd_it);
 148
 149       static iterator
 150       rightmost_it(node_iterator nd_it);
 151
 152       static bool
 153       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);
 154     };
 155
 156     PB_DS_CLASS_T_DEC
 157     typename PB_DS_CLASS_C_DEC::size_type
 158     PB_DS_CLASS_C_DEC::
 159     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)
 160     {
 161       prefix_range_t pref_range = nd_it.valid_prefix();
 162
 163       typename e_access_traits::const_iterator b_l = pref_range.first;
 164       typename e_access_traits::const_iterator e_l = pref_range.second;
 165
 166       const size_type range_length_l =
 167         std::distance(b_l, e_l);
 168
 169       const size_type range_length_r =
 170         std::distance(b_r, e_r);
 171
 172       if (range_length_r < range_length_l)
 173         {
 174           std::swap(b_l, b_r);
 175
 176           std::swap(e_l, e_r);
 177         }
 178
 179       size_type ret = 0;
 180
 181       while (b_l != e_l)
 182         {
 183           if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r))
 184             return (ret);
 185
 186           ++ret;
 187
 188           ++b_l;
 189
 190           ++b_r;
 191         }
 192
 193       return (ret);
 194     }
 195
 196     PB_DS_CLASS_T_DEC
 197     typename PB_DS_CLASS_C_DEC::iterator
 198     PB_DS_CLASS_C_DEC::
 199     leftmost_it(node_iterator nd_it)
 200     {
 201       if (nd_it.num_children() == 0)
 202         return (*nd_it);
 203
 204       return (leftmost_it(nd_it.get_child(0)));
 205     }
 206
 207     PB_DS_CLASS_T_DEC
 208     typename PB_DS_CLASS_C_DEC::iterator
 209     PB_DS_CLASS_C_DEC::
 210     rightmost_it(node_iterator nd_it)
 211     {
 212       const size_type num_children = nd_it.num_children();
 213
 214       if (num_children == 0)
 215         return (*nd_it);
 216
 217       return (rightmost_it(nd_it.get_child(num_children - 1)));
 218     }
 219
 220     PB_DS_CLASS_T_DEC
 221     bool
 222     PB_DS_CLASS_C_DEC::
 223     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)
 224     {
 225       while (b_l != e_l)
 226         {
 227           if (b_r == e_r)
 228             return (false);
 229
 230           size_type l_pos =
 231             r_traits.e_pos(*b_l);
 232           size_type r_pos =
 233             r_traits.e_pos(*b_r);
 234
 235           if (l_pos != r_pos)
 236             return (l_pos < r_pos);
 237
 238           ++b_l;
 239           ++b_r;
 240         }
 241
 242       return (b_r != e_r);
 243     }
 244
 245 #undef PB_DS_CLASS_T_DEC
 246
 247 #undef PB_DS_CLASS_C_DEC
 248
 249 #undef PB_DS_BASE_C_DEC
 250
 251   } // namespace detail
 252 } // namespace pb_ds
 253
 254 #endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP
 255