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 rb_tree_.hpp
44 * Contains an implementation for rb_tree_.
45 */
46/*
47 * This implementation uses an idea from the SGI STL (using a "header" node
48 *    which is needed for efficient iteration).
49 */
50
51#ifdef PB_DS_DATA_TRUE_INDICATOR
52#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
53#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
54#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
55#endif
56#endif
57
58#ifdef PB_DS_DATA_FALSE_INDICATOR
59#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
60#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
61#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
62#endif
63#endif
64
65#include <ext/pb_ds/detail/standard_policies.hpp>
66#include <ext/pb_ds/detail/basic_types.hpp>
67#include <utility>
68#include <vector>
69#include <assert.h>
70#include <debug/debug.h>
71
72namespace pb_ds
73{
74  namespace detail
75  {
76#define PB_DS_CLASS_T_DEC \
77    template<typename Key, typename Mapped, typename Cmp_Fn, \
78	     typename Node_And_It_Traits, typename Allocator>
79
80#ifdef PB_DS_DATA_TRUE_INDICATOR
81#define PB_DS_CLASS_NAME rb_tree_data_
82#endif
83
84#ifdef PB_DS_DATA_TRUE_INDICATOR
85#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_
86#endif
87
88#ifdef PB_DS_DATA_FALSE_INDICATOR
89#define PB_DS_CLASS_NAME rb_tree_no_data_
90#endif
91
92#ifdef PB_DS_DATA_FALSE_INDICATOR
93#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_
94#endif
95
96#define PB_DS_CLASS_C_DEC \
97    PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
98
99#define PB_DS_BASE_C_DEC \
100    PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
101
102#ifdef PB_DS_DATA_TRUE_INDICATOR
103#define PB_DS_V2F(X) (X).first
104#define PB_DS_V2S(X) (X).second
105#define PB_DS_EP2VP(X)& ((X)->m_value)
106#endif
107
108#ifdef PB_DS_DATA_FALSE_INDICATOR
109#define PB_DS_V2F(X) (X)
110#define PB_DS_V2S(X) Mapped_Data()
111#define PB_DS_EP2VP(X)& ((X)->m_value.first)
112#endif
113
114    template<typename Key,
115	     typename Mapped,
116	     typename Cmp_Fn,
117	     typename Node_And_It_Traits,
118	     typename Allocator>
119    class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
120    {
121    private:
122      typedef PB_DS_BASE_C_DEC base_type;
123      typedef typename base_type::node_pointer node_pointer;
124
125    public:
126      typedef Cmp_Fn cmp_fn;
127      typedef Allocator allocator;
128      typedef typename Allocator::size_type size_type;
129      typedef typename Allocator::difference_type difference_type;
130      typedef typename base_type::key_type key_type;
131      typedef typename base_type::key_pointer key_pointer;
132      typedef typename base_type::const_key_pointer const_key_pointer;
133      typedef typename base_type::key_reference key_reference;
134      typedef typename base_type::const_key_reference const_key_reference;
135      typedef typename base_type::mapped_type mapped_type;
136      typedef typename base_type::mapped_pointer mapped_pointer;
137      typedef typename base_type::const_mapped_pointer const_mapped_pointer;
138      typedef typename base_type::mapped_reference mapped_reference;
139      typedef typename base_type::const_mapped_reference const_mapped_reference;
140      typedef typename base_type::value_type value_type;
141      typedef typename base_type::pointer pointer;
142      typedef typename base_type::const_pointer const_pointer;
143      typedef typename base_type::reference reference;
144      typedef typename base_type::const_reference const_reference;
145      typedef typename base_type::point_iterator point_iterator;
146      typedef typename base_type::const_iterator const_point_iterator;
147      typedef typename base_type::iterator iterator;
148      typedef typename base_type::const_iterator const_iterator;
149      typedef typename base_type::reverse_iterator reverse_iterator;
150      typedef typename base_type::const_reverse_iterator const_reverse_iterator;
151      typedef typename base_type::node_update node_update;
152
153
154      PB_DS_CLASS_NAME();
155
156      PB_DS_CLASS_NAME(const Cmp_Fn&);
157
158      PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&);
159
160      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
161
162      void
163      swap(PB_DS_CLASS_C_DEC&);
164
165      template<typename It>
166      void
167      copy_from_range(It, It);
168
169      inline std::pair<point_iterator, bool>
170      insert(const_reference);
171
172      inline mapped_reference
173      operator[](const_key_reference r_key)
174      {
175#ifdef PB_DS_DATA_TRUE_INDICATOR
176	_GLIBCXX_DEBUG_ONLY(assert_valid();)
177	std::pair<point_iterator, bool> ins_pair =
178	base_type::insert_leaf(value_type(r_key, mapped_type()));
179
180	if (ins_pair.second == true)
181	  {
182	    ins_pair.first.m_p_nd->m_red = true;
183	    _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();)
184	    insert_fixup(ins_pair.first.m_p_nd);
185	  }
186	_GLIBCXX_DEBUG_ONLY(assert_valid();)
187	return ins_pair.first.m_p_nd->m_value.second;
188#else
189	insert(r_key);
190	return base_type::s_null_mapped;
191#endif
192      }
193
194      inline bool
195      erase(const_key_reference);
196
197      inline iterator
198      erase(iterator);
199
200      inline reverse_iterator
201      erase(reverse_iterator);
202
203      template<typename Pred>
204      inline size_type
205      erase_if(Pred);
206
207      void
208      join(PB_DS_CLASS_C_DEC&);
209
210      void
211      split(const_key_reference, PB_DS_CLASS_C_DEC&);
212
213    protected:
214
215    private:
216
217#ifdef _GLIBCXX_DEBUG
218      void
219      assert_valid() const;
220
221      size_type
222      assert_node_consistent(const node_pointer) const;
223#endif
224
225      inline static bool
226      is_effectively_black(const node_pointer);
227
228      void
229      initialize();
230
231      void
232      insert_fixup(node_pointer);
233
234      void
235      erase_node(node_pointer);
236
237      void
238      remove_node(node_pointer);
239
240      void
241      remove_fixup(node_pointer, node_pointer);
242
243      void
244      split_imp(node_pointer, PB_DS_CLASS_C_DEC&);
245
246      inline node_pointer
247      split_min();
248
249      std::pair<node_pointer, node_pointer>
250      split_min_imp();
251
252      void
253      join_imp(node_pointer, node_pointer);
254
255      std::pair<node_pointer, node_pointer>
256      find_join_pos_right(node_pointer, size_type, size_type);
257
258      std::pair<node_pointer, node_pointer>
259      find_join_pos_left(node_pointer, size_type, size_type);
260
261      inline size_type
262      black_height(node_pointer);
263
264      void
265      split_at_node(node_pointer, PB_DS_CLASS_C_DEC&);
266    };
267
268#include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
269#include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp>
270#include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp>
271#include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp>
272#include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp>
273#include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp>
274
275#undef PB_DS_CLASS_T_DEC
276#undef PB_DS_CLASS_C_DEC
277#undef PB_DS_CLASS_NAME
278#undef PB_DS_BASE_CLASS_NAME
279#undef PB_DS_BASE_C_DEC
280#undef PB_DS_V2F
281#undef PB_DS_EP2VP
282#undef PB_DS_V2S
283
284  } // namespace detail
285} // namespace pb_ds
286
287