contrib/gcc-4.4/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.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 splay_tree_.hpp
  38  * Contains an implementation class for splay_tree_.
  39  */
  40 /*
  41  * This implementation uses an idea from the SGI STL (using a "header" node
  42  *    which is needed for efficient iteration). Following is the SGI STL
  43  *    copyright.
  44  *
  45  * Copyright (c) 1996,1997
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.    Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.    It is provided "as is" without express or implied warranty.
  55  *
  56  *
  57  * Copyright (c) 1994
  58  * Hewlett-Packard Company
  59  *
  60  * Permission to use, copy, modify, distribute and sell this software
  61  * and its documentation for any purpose is hereby granted without fee,
  62  * provided that the above copyright notice appear in all copies and
  63  * that both that copyright notice and this permission notice appear
  64  * in supporting documentation.    Hewlett-Packard Company makes no
  65  * representations about the suitability of this software for any
  66  * purpose.    It is provided "as is" without express or implied warranty.
  67  *
  68  *
  69  */
  70
  71 #ifdef PB_DS_DATA_TRUE_INDICATOR
  72 #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  73 #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  74 #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  75 #endif
  76 #endif
  77
  78 #ifdef PB_DS_DATA_FALSE_INDICATOR
  79 #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  80 #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  81 #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  82 #endif
  83 #endif
  84
  85 #include <utility>
  86 #include <vector>
  87 #include <assert.h>
  88 #include <debug/debug.h>
  89
  90 namespace __gnu_pbds
  91 {
  92   namespace detail
  93   {
  94 #define PB_DS_CLASS_T_DEC \
  95     template<typename Key, typename Mapped, typename Cmp_Fn, \
  96              typename Node_And_It_Traits, typename Allocator>
  97
  98 #ifdef PB_DS_DATA_TRUE_INDICATOR
  99 #define PB_DS_CLASS_NAME splay_tree_data_
 100 #endif
 101
 102 #ifdef PB_DS_DATA_FALSE_INDICATOR
 103 #define PB_DS_CLASS_NAME splay_tree_no_data_
 104 #endif
 105
 106 #ifdef PB_DS_DATA_TRUE_INDICATOR
 107 #define PB_DS_BASE_CLASS_NAME bin_search_tree_data_
 108 #endif
 109
 110 #ifdef PB_DS_DATA_FALSE_INDICATOR
 111 #define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_
 112 #endif
 113
 114 #define PB_DS_CLASS_C_DEC \
 115     PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 116
 117 #define PB_DS_BASE_C_DEC \
 118     PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 119
 120 #ifdef PB_DS_DATA_TRUE_INDICATOR
 121 #define PB_DS_V2F(X) (X).first
 122 #define PB_DS_V2S(X) (X).second
 123 #define PB_DS_EP2VP(X)& ((X)->m_value)
 124 #endif
 125
 126 #ifdef PB_DS_DATA_FALSE_INDICATOR
 127 #define PB_DS_V2F(X) (X)
 128 #define PB_DS_V2S(X) Mapped_Data()
 129 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 130 #endif
 131
 132     // $p14y 7r33 7481.
 133     template<typename Key, typename Mapped, typename Cmp_Fn,
 134              typename Node_And_It_Traits, typename Allocator>
 135     class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
 136     {
 137     private:
 138       typedef PB_DS_BASE_C_DEC base_type;
 139       typedef typename base_type::node_pointer node_pointer;
 140
 141     public:
 142       typedef Allocator allocator_type;
 143       typedef typename Allocator::size_type size_type;
 144       typedef typename Allocator::difference_type difference_type;
 145       typedef Cmp_Fn cmp_fn;
 146       typedef typename base_type::key_type key_type;
 147       typedef typename base_type::key_pointer key_pointer;
 148       typedef typename base_type::const_key_pointer const_key_pointer;
 149       typedef typename base_type::key_reference key_reference;
 150       typedef typename base_type::const_key_reference const_key_reference;
 151       typedef typename base_type::mapped_type mapped_type;
 152       typedef typename base_type::mapped_pointer mapped_pointer;
 153       typedef typename base_type::const_mapped_pointer const_mapped_pointer;
 154       typedef typename base_type::mapped_reference mapped_reference;
 155       typedef typename base_type::const_mapped_reference const_mapped_reference;
 156       typedef typename base_type::value_type value_type;
 157       typedef typename base_type::pointer pointer;
 158       typedef typename base_type::const_pointer const_pointer;
 159       typedef typename base_type::reference reference;
 160       typedef typename base_type::const_reference const_reference;
 161       typedef typename base_type::point_iterator point_iterator;
 162       typedef typename base_type::const_iterator const_point_iterator;
 163       typedef typename base_type::iterator iterator;
 164       typedef typename base_type::const_iterator const_iterator;
 165       typedef typename base_type::reverse_iterator reverse_iterator;
 166       typedef typename base_type::const_reverse_iterator const_reverse_iterator;
 167       typedef typename base_type::node_update node_update;
 168
 169       PB_DS_CLASS_NAME();
 170
 171       PB_DS_CLASS_NAME(const Cmp_Fn&);
 172
 173       PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&);
 174
 175       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 176
 177       void
 178       swap(PB_DS_CLASS_C_DEC&);
 179
 180       template<typename It>
 181       void
 182       copy_from_range(It, It);
 183
 184       void
 185       initialize();
 186
 187       inline std::pair<point_iterator, bool>
 188       insert(const_reference r_value);
 189
 190       inline mapped_reference
 191       operator[](const_key_reference r_key)
 192       {
 193 #ifdef PB_DS_DATA_TRUE_INDICATOR
 194         _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
 195         std::pair<point_iterator, bool> ins_pair =
 196           insert_leaf_imp(value_type(r_key, mapped_type()));
 197
 198         ins_pair.first.m_p_nd->m_special = false;
 199         _GLIBCXX_DEBUG_ONLY(base_type::assert_valid());
 200         splay(ins_pair.first.m_p_nd);
 201         _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
 202         return ins_pair.first.m_p_nd->m_value.second;
 203 #else
 204         insert(r_key);
 205         return base_type::s_null_mapped;
 206 #endif
 207       }
 208
 209       inline point_iterator
 210       find(const_key_reference);
 211
 212       inline const_point_iterator
 213       find(const_key_reference) const;
 214
 215       inline bool
 216       erase(const_key_reference);
 217
 218       inline iterator
 219       erase(iterator it);
 220
 221       inline reverse_iterator
 222       erase(reverse_iterator);
 223
 224       template<typename Pred>
 225       inline size_type
 226       erase_if(Pred);
 227
 228       void
 229       join(PB_DS_CLASS_C_DEC&);
 230
 231       void
 232       split(const_key_reference, PB_DS_CLASS_C_DEC&);
 233
 234     private:
 235       inline std::pair<point_iterator, bool>
 236       insert_leaf_imp(const_reference);
 237
 238       inline node_pointer
 239       find_imp(const_key_reference);
 240
 241       inline const node_pointer
 242       find_imp(const_key_reference) const;
 243
 244 #ifdef _GLIBCXX_DEBUG
 245       void
 246       assert_valid() const;
 247
 248       void
 249       assert_special_imp(const node_pointer) const;
 250 #endif
 251
 252       void
 253       splay(node_pointer);
 254
 255       inline void
 256       splay_zig_zag_left(node_pointer, node_pointer, node_pointer);
 257
 258       inline void
 259       splay_zig_zag_right(node_pointer, node_pointer, node_pointer);
 260
 261       inline void
 262       splay_zig_zig_left(node_pointer, node_pointer, node_pointer);
 263
 264       inline void
 265       splay_zig_zig_right(node_pointer, node_pointer, node_pointer);
 266
 267       inline void
 268       splay_zz_start(node_pointer, node_pointer, node_pointer);
 269
 270       inline void
 271       splay_zz_end(node_pointer, node_pointer, node_pointer);
 272
 273       inline node_pointer
 274       leftmost(node_pointer);
 275
 276       void
 277       erase_node(node_pointer);
 278     };
 279
 280 #include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
 281 #include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp>
 282 #include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp>
 283 #include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp>
 284 #include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp>
 285 #include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp>
 286 #include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp>
 287
 288 #undef PB_DS_CLASS_T_DEC
 289 #undef PB_DS_CLASS_C_DEC
 290 #undef PB_DS_CLASS_NAME
 291 #undef PB_DS_BASE_CLASS_NAME
 292 #undef PB_DS_BASE_C_DEC
 293 #undef PB_DS_V2F
 294 #undef PB_DS_EP2VP
 295 #undef PB_DS_V2S
 296   } // namespace detail
 297 } // namespace __gnu_pbds
 298