1// -*- C++ -*-
2
3// Copyright (C) 2005 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
32// Permission to use, copy, modify, sell, and distribute this software
33// is hereby granted without fee, provided that the above copyright
34// notice appears in all copies, and that both that copyright notice and
35// this permission notice appear in supporting documentation. None of
36// the above authors, nor IBM Haifa Research Laboratories, make any
37// representation about the suitability of this software for any
38// purpose. It is provided "as is" without express or implied warranty.
39
40/*
41 * @file tree_policy.hpp
42 * Contains tree-related policies.
43 */
44
45#ifndef TREE_POLICY_HPP
46#define TREE_POLICY_HPP
47
48#include <functional>
49#include <ext/pb_assoc/ms_trait.hpp>
50
51namespace pb_assoc
52{
53  struct null_node_updator
54  {
55    inline void
56    swap(null_node_updator& r_other);
57  };
58
59#include <ext/pb_assoc/detail/tree_policy/null_node_updator_imp.hpp>
60
61  template<typename Key, typename Allocator = std::allocator<char> >
62    class order_statistics_key
63    {
64    public:
65      typedef Allocator 			allocator;
66      typedef Key 				key_type;
67      typedef typename allocator::template rebind<Key>::other::const_reference
68      						const_key_reference;
69      typedef typename allocator::template rebind<Key>::other::reference
70      						key_reference;
71      typedef typename allocator::size_type 	size_type;
72
73      inline explicit
74      order_statistics_key(const_key_reference r_key = Key());
75
76      inline
77      operator key_reference();
78
79      inline
80      operator key_type() const;
81
82    private:
83      // The logical key of the entry.
84      key_type m_key;
85
86      // The number of entries in the subtree rooted at the node of
87      // this element.
88      mutable size_type m_rank;
89
90      template<typename Cntnr>
91        friend class order_by_key;
92
93      template<typename Some_Cmp_Fn, typename Some_Allocator>
94        friend class order_statistics_key_cmp;
95
96      template<typename Some_Key, typename Some_Allocator>
97        friend class order_statistics_node_updator;
98
99      template<typename Cntnr>
100        friend class find_by_order;
101
102      template<typename Cntnr, typename Some_Allocator>
103        friend class order_statistics_key_verifier;
104  };
105
106  template<typename Cmp_Fn, typename Allocator = std::allocator<char> >
107    class order_statistics_key_cmp
108    : public std::binary_function<
109      order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>,
110      order_statistics_key<typename Cmp_Fn::second_argument_type, Allocator>, bool>,
111    private Cmp_Fn
112    {
113    public:
114      typedef Allocator allocator;
115      typedef Cmp_Fn cmp_fn;
116
117      typedef
118      order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>
119      key_type;
120
121      typedef
122      typename allocator::template rebind<key_type>::other::const_reference
123      const_key_reference;
124
125      inline
126      order_statistics_key_cmp();
127
128      inline
129      order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn);
130
131      inline bool
132      operator()(const_key_reference, const_key_reference) const;
133
134      inline cmp_fn&
135      get_cmp_fn();
136
137      inline const cmp_fn&
138      get_cmp_fn() const;
139    };
140
141#define PB_ASSOC_CLASS_C_DEC \
142	order_statistics_node_updator<Key, Allocator>
143
144  template<typename Key, typename Allocator = std::allocator<char> >
145    class order_statistics_node_updator
146    {
147    public:
148      typedef Allocator allocator;
149      typedef order_statistics_key< Key, Allocator> key_type;
150
151      typedef
152      typename Allocator::template rebind<key_type>::other::const_pointer
153      const_key_pointer;
154
155      inline void
156      swap(PB_ASSOC_CLASS_C_DEC& r_other);
157
158      inline void
159      operator()(const_key_pointer, const_key_pointer, const_key_pointer);
160
161    private:
162      typedef typename Allocator::size_type size_type;
163    };
164
165#undef PB_ASSOC_CLASS_C_DEC
166
167  template<class Cntnr>
168    class find_by_order
169    {
170    public:
171      typedef Cntnr 				cntnr;
172      typedef typename cntnr::iterator 		iterator;
173      typedef typename cntnr::const_iterator	const_iterator;
174      typedef typename cntnr::size_type 	size_type;
175
176      inline iterator
177      operator()(Cntnr& r_c, size_type order) const;
178
179      inline const_iterator
180      operator()(const Cntnr& r_c, size_type order) const;
181
182    private:
183      typedef typename Cntnr::node_iterator 	node_iterator;
184      typedef typename Cntnr::const_iterator 	cntnr_const_it;
185      typedef typename Cntnr::iterator 		cntnr_it;
186
187      inline static iterator
188      find(Cntnr& r_c, size_type order);
189
190      inline static const_iterator
191      find(const Cntnr& r_c, size_type order);
192    };
193
194  template<class Cntnr>
195    class order_by_key
196    {
197    public:
198      typedef Cntnr 				cntnr;
199      typedef typename Cntnr::key_type 		order_statistics_key_type;
200      typedef typename order_statistics_key_type::key_type
201      						underlying_key_type;
202      typedef typename cntnr::size_type 	size_type;
203
204      inline size_type
205      operator()(const Cntnr& r_c, const underlying_key_type& r_key) const;
206
207    private:
208      typedef typename cntnr::const_iterator cntnr_const_it;
209      typedef typename cntnr::iterator cntnr_it;
210    };
211
212#include <ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp>
213} // namespace pb_assoc
214
215#endif // #ifndef TREE_POLICY_HPP
216