libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.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 find_fn_imps.hpp
  44  * Contains an implementation class for bin_search_tree_.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 inline typename PB_DS_CLASS_C_DEC::point_iterator
  49 PB_DS_CLASS_C_DEC::
  50 find(const_key_reference r_key)
  51 {
  52   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  53   node_pointer p_nd = find_imp(r_key);
  54
  55   if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type)
  56     {
  57       _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
  58       return end();
  59     }
  60
  61   if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key))
  62     {
  63       _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
  64       return iterator(p_nd);
  65     }
  66
  67   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
  68   return end();
  69 }
  70
  71 PB_DS_CLASS_T_DEC
  72 inline typename PB_DS_CLASS_C_DEC::const_point_iterator
  73 PB_DS_CLASS_C_DEC::
  74 find(const_key_reference r_key) const
  75 {
  76   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  77
  78   const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key);
  79
  80   if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type)
  81     {
  82       _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
  83       return end();
  84     }
  85
  86   if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key))
  87     {
  88       _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
  89       return const_iterator(const_cast<node_pointer>(p_nd));
  90     }
  91
  92   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
  93   return end();
  94 }
  95
  96 PB_DS_CLASS_T_DEC
  97 inline typename PB_DS_CLASS_C_DEC::node_pointer
  98 PB_DS_CLASS_C_DEC::
  99 find_imp(const_key_reference r_key)
 100 {
 101   if (empty())
 102     return (NULL);
 103
 104   typename synth_e_access_traits::const_iterator b_it =
 105     synth_e_access_traits::begin(r_key);
 106   typename synth_e_access_traits::const_iterator e_it =
 107     synth_e_access_traits::end(r_key);
 108
 109   node_pointer p_nd = m_p_head->m_p_parent;
 110   _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
 111
 112   while (p_nd->m_type != pat_trie_leaf_node_type)
 113     {
 114       _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
 115       node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it,  e_it,  this);
 116
 117       if (p_next_nd == NULL)
 118         return p_nd;
 119       p_nd = p_next_nd;
 120     }
 121   return p_nd;
 122 }
 123
 124 PB_DS_CLASS_T_DEC
 125 inline typename PB_DS_CLASS_C_DEC::node_pointer
 126 PB_DS_CLASS_C_DEC::
 127 lower_bound_imp(const_key_reference r_key)
 128 {
 129   if (empty())
 130     return (m_p_head);
 131
 132   node_pointer p_nd = m_p_head->m_p_parent;
 133   _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
 134
 135   typename PB_DS_CLASS_C_DEC::const_e_iterator b_it =
 136     synth_e_access_traits::begin(r_key);
 137
 138   typename PB_DS_CLASS_C_DEC::const_e_iterator e_it =
 139     synth_e_access_traits::end(r_key);
 140
 141   size_type checked_ind = 0;
 142   while (true)
 143     {
 144       if (p_nd->m_type == pat_trie_leaf_node_type)
 145         {
 146           if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key))
 147             return p_nd;
 148           iterator it(p_nd);
 149           ++it;
 150           return it.m_p_nd;
 151         }
 152
 153       _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
 154       const size_type new_checked_ind =
 155         static_cast<internal_node_pointer>(p_nd)->get_e_ind();
 156
 157       p_nd =
 158         static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node(                b_it, e_it, checked_ind, this);
 159       checked_ind = new_checked_ind;
 160     }
 161 }
 162
 163 PB_DS_CLASS_T_DEC
 164 inline typename PB_DS_CLASS_C_DEC::point_iterator
 165 PB_DS_CLASS_C_DEC::
 166 lower_bound(const_key_reference r_key)
 167 { return point_iterator(lower_bound_imp(r_key)); }
 168
 169 PB_DS_CLASS_T_DEC
 170 inline typename PB_DS_CLASS_C_DEC::const_point_iterator
 171 PB_DS_CLASS_C_DEC::
 172 lower_bound(const_key_reference r_key) const
 173 {
 174   return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key));
 175 }
 176
 177 PB_DS_CLASS_T_DEC
 178 inline typename PB_DS_CLASS_C_DEC::point_iterator
 179 PB_DS_CLASS_C_DEC::
 180 upper_bound(const_key_reference r_key)
 181 {
 182   point_iterator l_bound_it = lower_bound(r_key);
 183
 184   _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() ||
 185                    !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it),
 186                                                     r_key));
 187
 188   if (l_bound_it == end() ||
 189       synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it)))
 190     return l_bound_it;
 191
 192   return ++l_bound_it;
 193 }
 194
 195 PB_DS_CLASS_T_DEC
 196 inline typename PB_DS_CLASS_C_DEC::const_point_iterator
 197 PB_DS_CLASS_C_DEC::
 198 upper_bound(const_key_reference r_key) const
 199 {
 200   const_point_iterator l_bound_it = lower_bound(r_key);
 201
 202   _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() ||
 203                    !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it),
 204                                                     r_key));
 205
 206   if (l_bound_it == end() ||
 207       synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it)))
 208     return l_bound_it;
 209   return ++l_bound_it;
 210 }
 211
 212 PB_DS_CLASS_T_DEC
 213 inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 214 PB_DS_CLASS_C_DEC::
 215 pref_begin(const_node_pointer p_nd)
 216 {
 217   if (p_nd->m_type == pat_trie_leaf_node_type)
 218     return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value())));
 219
 220   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
 221   return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it();
 222 }
 223
 224 PB_DS_CLASS_T_DEC
 225 inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 226 PB_DS_CLASS_C_DEC::
 227 pref_end(const_node_pointer p_nd)
 228 {
 229   if (p_nd->m_type == pat_trie_leaf_node_type)
 230     return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value())));
 231
 232   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
 233   return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it();
 234 }
 235
 236 PB_DS_CLASS_T_DEC
 237 inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 238 PB_DS_CLASS_C_DEC::
 239 leftmost_descendant(const_node_pointer p_nd)
 240 {
 241   if (p_nd->m_type == pat_trie_leaf_node_type)
 242     return static_cast<const_leaf_pointer>(p_nd);
 243   return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant();
 244 }
 245
 246 PB_DS_CLASS_T_DEC
 247 inline typename PB_DS_CLASS_C_DEC::leaf_pointer
 248 PB_DS_CLASS_C_DEC::
 249 leftmost_descendant(node_pointer p_nd)
 250 {
 251   if (p_nd->m_type == pat_trie_leaf_node_type)
 252     return static_cast<leaf_pointer>(p_nd);
 253   return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
 254 }
 255
 256 PB_DS_CLASS_T_DEC
 257 inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 258 PB_DS_CLASS_C_DEC::
 259 rightmost_descendant(const_node_pointer p_nd)
 260 {
 261   if (p_nd->m_type == pat_trie_leaf_node_type)
 262     return static_cast<const_leaf_pointer>(p_nd);
 263   return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant();
 264 }
 265
 266 PB_DS_CLASS_T_DEC
 267 inline typename PB_DS_CLASS_C_DEC::leaf_pointer
 268 PB_DS_CLASS_C_DEC::
 269 rightmost_descendant(node_pointer p_nd)
 270 {
 271   if (p_nd->m_type == pat_trie_leaf_node_type)
 272     return static_cast<leaf_pointer>(p_nd);
 273   return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
 274 }
 275