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