1// -*- C++ -*-
2
3// Copyright (C) 2005-2013 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
276