libstdc++
splay_tree_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2018 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_/splay_tree_.hpp
38  * Contains an implementation class for splay trees.
39  */
40 /*
41  * This implementation uses an idea from the SGI STL (using a @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 #include <utility>
72 #include <vector>
73 #include <assert.h>
74 #include <debug/debug.h>
75 
76 namespace __gnu_pbds
77 {
78  namespace detail
79  {
80 #ifdef PB_DS_DATA_TRUE_INDICATOR
81 # define PB_DS_S_TREE_NAME splay_tree_map
82 # define PB_DS_S_TREE_BASE_NAME bin_search_tree_map
83 #endif
84 
85 #ifdef PB_DS_DATA_FALSE_INDICATOR
86 # define PB_DS_S_TREE_NAME splay_tree_set
87 # define PB_DS_S_TREE_BASE_NAME bin_search_tree_set
88 #endif
89 
90 #define PB_DS_CLASS_T_DEC \
91  template<typename Key, typename Mapped, typename Cmp_Fn, \
92  typename Node_And_It_Traits, typename _Alloc>
93 
94 #define PB_DS_CLASS_C_DEC \
95  PB_DS_S_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
96 
97 #define PB_DS_S_TREE_BASE \
98  PB_DS_S_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
99 
100 
101  /**
102  * @brief Splay tree.
103  * @ingroup branch-detail
104  */
105  template<typename Key, typename Mapped, typename Cmp_Fn,
106  typename Node_And_It_Traits, typename _Alloc>
107  class PB_DS_S_TREE_NAME : public PB_DS_S_TREE_BASE
108  {
109  private:
110  typedef PB_DS_S_TREE_BASE base_type;
111 #ifdef _GLIBCXX_DEBUG
112  typedef base_type debug_base;
113 #endif
114  typedef typename base_type::node_pointer node_pointer;
115 
116  public:
117  typedef splay_tree_tag container_category;
118  typedef _Alloc allocator_type;
119  typedef typename _Alloc::size_type size_type;
120  typedef typename _Alloc::difference_type difference_type;
121  typedef Cmp_Fn cmp_fn;
122  typedef typename base_type::key_type key_type;
123  typedef typename base_type::key_pointer key_pointer;
124  typedef typename base_type::key_const_pointer key_const_pointer;
125  typedef typename base_type::key_reference key_reference;
126  typedef typename base_type::key_const_reference key_const_reference;
127  typedef typename base_type::mapped_type mapped_type;
128  typedef typename base_type::mapped_pointer mapped_pointer;
129  typedef typename base_type::mapped_const_pointer mapped_const_pointer;
130  typedef typename base_type::mapped_reference mapped_reference;
131  typedef typename base_type::mapped_const_reference mapped_const_reference;
132  typedef typename base_type::value_type value_type;
133  typedef typename base_type::pointer pointer;
134  typedef typename base_type::const_pointer const_pointer;
135  typedef typename base_type::reference reference;
136  typedef typename base_type::const_reference const_reference;
137  typedef typename base_type::point_iterator point_iterator;
138  typedef typename base_type::const_iterator point_const_iterator;
139  typedef typename base_type::iterator iterator;
140  typedef typename base_type::const_iterator const_iterator;
141  typedef typename base_type::reverse_iterator reverse_iterator;
142  typedef typename base_type::const_reverse_iterator const_reverse_iterator;
143  typedef typename base_type::node_update node_update;
144 
145  PB_DS_S_TREE_NAME();
146 
147  PB_DS_S_TREE_NAME(const Cmp_Fn&);
148 
149  PB_DS_S_TREE_NAME(const Cmp_Fn&, const node_update&);
150 
151  PB_DS_S_TREE_NAME(const PB_DS_CLASS_C_DEC&);
152 
153  void
154  swap(PB_DS_CLASS_C_DEC&);
155 
156  template<typename It>
157  void
158  copy_from_range(It, It);
159 
160  void
161  initialize();
162 
163  inline std::pair<point_iterator, bool>
164  insert(const_reference r_value);
165 
166  inline mapped_reference
167  operator[](key_const_reference r_key)
168  {
169 #ifdef PB_DS_DATA_TRUE_INDICATOR
170  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
171  std::pair<point_iterator, bool> ins_pair =
172  insert_leaf_imp(value_type(r_key, mapped_type()));
173 
174  ins_pair.first.m_p_nd->m_special = false;
175  _GLIBCXX_DEBUG_ONLY(base_type::assert_valid(__FILE__, __LINE__));
176  splay(ins_pair.first.m_p_nd);
177  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
178  return ins_pair.first.m_p_nd->m_value.second;
179 #else
180  insert(r_key);
181  return base_type::s_null_type;
182 #endif
183  }
184 
185  inline point_iterator
186  find(key_const_reference);
187 
188  inline point_const_iterator
189  find(key_const_reference) const;
190 
191  inline bool
192  erase(key_const_reference);
193 
194  inline iterator
195  erase(iterator it);
196 
197  inline reverse_iterator
198  erase(reverse_iterator);
199 
200  template<typename Pred>
201  inline size_type
202  erase_if(Pred);
203 
204  void
205  join(PB_DS_CLASS_C_DEC&);
206 
207  void
208  split(key_const_reference, PB_DS_CLASS_C_DEC&);
209 
210  private:
211  inline std::pair<point_iterator, bool>
212  insert_leaf_imp(const_reference);
213 
214  inline node_pointer
215  find_imp(key_const_reference);
216 
217  inline const node_pointer
218  find_imp(key_const_reference) const;
219 
220 #ifdef _GLIBCXX_DEBUG
221  void
222  assert_valid(const char* file, int line) const;
223 
224  void
225  assert_special_imp(const node_pointer, const char* file, int line) const;
226 #endif
227 
228  void
229  splay(node_pointer);
230 
231  inline void
232  splay_zig_zag_left(node_pointer, node_pointer, node_pointer);
233 
234  inline void
235  splay_zig_zag_right(node_pointer, node_pointer, node_pointer);
236 
237  inline void
238  splay_zig_zig_left(node_pointer, node_pointer, node_pointer);
239 
240  inline void
241  splay_zig_zig_right(node_pointer, node_pointer, node_pointer);
242 
243  inline void
244  splay_zz_start(node_pointer, node_pointer, node_pointer);
245 
246  inline void
247  splay_zz_end(node_pointer, node_pointer, node_pointer);
248 
249  inline node_pointer
250  leftmost(node_pointer);
251 
252  void
253  erase_node(node_pointer);
254  };
255 
256 #define PB_DS_ASSERT_BASE_NODE_CONSISTENT(_Node) \
257  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, \
258  __FILE__, __LINE__);)
259 
260 #include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
261 #include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp>
262 #include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp>
263 #include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp>
264 #include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp>
265 #include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp>
266 #include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp>
267 
268 #undef PB_DS_ASSERT_BASE_NODE_CONSISTENT
269 #undef PB_DS_CLASS_T_DEC
270 #undef PB_DS_CLASS_C_DEC
271 #undef PB_DS_S_TREE_NAME
272 #undef PB_DS_S_TREE_BASE_NAME
273 #undef PB_DS_S_TREE_BASE
274  } // namespace detail
275 } // namespace __gnu_pbds
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:51