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
96namespace pb_ds
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 pb_ds
304
305