libstdc++
splay_tree_.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 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
76namespace __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
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213