xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
1*e4b17023SJohn Marino // -*- C++ -*-
2*e4b17023SJohn Marino 
3*e4b17023SJohn Marino // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
4*e4b17023SJohn Marino //
5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library.  This library is free
6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the terms
7*e4b17023SJohn Marino // of the GNU General Public License as published by the Free Software
8*e4b17023SJohn Marino // Foundation; either version 3, or (at your option) any later
9*e4b17023SJohn Marino // version.
10*e4b17023SJohn Marino 
11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, but
12*e4b17023SJohn Marino // WITHOUT ANY WARRANTY; without even the implied warranty of
13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14*e4b17023SJohn Marino // General Public License for more details.
15*e4b17023SJohn Marino 
16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional
17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version
18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation.
19*e4b17023SJohn Marino 
20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and
21*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program;
22*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>.
24*e4b17023SJohn Marino 
25*e4b17023SJohn Marino // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26*e4b17023SJohn Marino 
27*e4b17023SJohn Marino // Permission to use, copy, modify, sell, and distribute this software
28*e4b17023SJohn Marino // is hereby granted without fee, provided that the above copyright
29*e4b17023SJohn Marino // notice appears in all copies, and that both that copyright notice
30*e4b17023SJohn Marino // and this permission notice appear in supporting documentation. None
31*e4b17023SJohn Marino // of the above authors, nor IBM Haifa Research Laboratories, make any
32*e4b17023SJohn Marino // representation about the suitability of this software for any
33*e4b17023SJohn Marino // purpose. It is provided "as is" without express or implied
34*e4b17023SJohn Marino // warranty.
35*e4b17023SJohn Marino 
36*e4b17023SJohn Marino /**
37*e4b17023SJohn Marino  * @file tree_policy.hpp
38*e4b17023SJohn Marino  * Contains tree-related policies.
39*e4b17023SJohn Marino  */
40*e4b17023SJohn Marino 
41*e4b17023SJohn Marino #ifndef PB_DS_TREE_POLICY_HPP
42*e4b17023SJohn Marino #define PB_DS_TREE_POLICY_HPP
43*e4b17023SJohn Marino 
44*e4b17023SJohn Marino #include <bits/c++config.h>
45*e4b17023SJohn Marino #include <iterator>
46*e4b17023SJohn Marino #include <ext/pb_ds/detail/type_utils.hpp>
47*e4b17023SJohn Marino #include <ext/pb_ds/detail/branch_policy/branch_policy.hpp>
48*e4b17023SJohn Marino 
49*e4b17023SJohn Marino namespace __gnu_pbds
50*e4b17023SJohn Marino {
51*e4b17023SJohn Marino #define PB_DS_CLASS_T_DEC \
52*e4b17023SJohn Marino   template<typename Node_CItr, typename Node_Itr, typename Cmp_Fn, \
53*e4b17023SJohn Marino 	   typename _Alloc>
54*e4b17023SJohn Marino 
55*e4b17023SJohn Marino #define PB_DS_CLASS_C_DEC \
56*e4b17023SJohn Marino   tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>
57*e4b17023SJohn Marino 
58*e4b17023SJohn Marino #define PB_DS_BRANCH_POLICY_BASE \
59*e4b17023SJohn Marino   detail::branch_policy<Node_CItr, Node_Itr, _Alloc>
60*e4b17023SJohn Marino 
61*e4b17023SJohn Marino   /// Functor updating ranks of entrees.
62*e4b17023SJohn Marino   template<typename Node_CItr, typename Node_Itr,
63*e4b17023SJohn Marino 	   typename Cmp_Fn, typename _Alloc>
64*e4b17023SJohn Marino   class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE
65*e4b17023SJohn Marino   {
66*e4b17023SJohn Marino   private:
67*e4b17023SJohn Marino     typedef PB_DS_BRANCH_POLICY_BASE 		       	base_type;
68*e4b17023SJohn Marino 
69*e4b17023SJohn Marino   public:
70*e4b17023SJohn Marino     typedef Cmp_Fn 					cmp_fn;
71*e4b17023SJohn Marino     typedef _Alloc 					allocator_type;
72*e4b17023SJohn Marino     typedef typename allocator_type::size_type 		size_type;
73*e4b17023SJohn Marino     typedef typename base_type::key_type 		key_type;
74*e4b17023SJohn Marino     typedef typename base_type::key_const_reference 	key_const_reference;
75*e4b17023SJohn Marino 
76*e4b17023SJohn Marino     typedef size_type 					metadata_type;
77*e4b17023SJohn Marino     typedef Node_CItr 	       			node_const_iterator;
78*e4b17023SJohn Marino     typedef Node_Itr 					node_iterator;
79*e4b17023SJohn Marino     typedef typename node_const_iterator::value_type 	const_iterator;
80*e4b17023SJohn Marino     typedef typename node_iterator::value_type 		iterator;
81*e4b17023SJohn Marino 
82*e4b17023SJohn Marino     /// Finds an entry by __order. Returns a const_iterator to the
83*e4b17023SJohn Marino     /// entry with the __order order, or a const_iterator to the
84*e4b17023SJohn Marino     /// container object's end if order is at least the size of the
85*e4b17023SJohn Marino     /// container object.
86*e4b17023SJohn Marino     inline const_iterator
87*e4b17023SJohn Marino     find_by_order(size_type) const;
88*e4b17023SJohn Marino 
89*e4b17023SJohn Marino     /// Finds an entry by __order. Returns an iterator to the entry
90*e4b17023SJohn Marino     /// with the __order order, or an iterator to the container
91*e4b17023SJohn Marino     /// object's end if order is at least the size of the container
92*e4b17023SJohn Marino     /// object.
93*e4b17023SJohn Marino     inline iterator
94*e4b17023SJohn Marino     find_by_order(size_type);
95*e4b17023SJohn Marino 
96*e4b17023SJohn Marino     /// Returns the order of a key within a sequence. For exapmle, if
97*e4b17023SJohn Marino     /// r_key is the smallest key, this method will return 0; if r_key
98*e4b17023SJohn Marino     /// is a key between the smallest and next key, this method will
99*e4b17023SJohn Marino     /// return 1; if r_key is a key larger than the largest key, this
100*e4b17023SJohn Marino     /// method will return the size of r_c.
101*e4b17023SJohn Marino     inline size_type
102*e4b17023SJohn Marino     order_of_key(key_const_reference) const;
103*e4b17023SJohn Marino 
104*e4b17023SJohn Marino   private:
105*e4b17023SJohn Marino     /// Const reference to the container's value-type.
106*e4b17023SJohn Marino     typedef typename base_type::const_reference 	const_reference;
107*e4b17023SJohn Marino 
108*e4b17023SJohn Marino     /// Const pointer to the container's value-type.
109*e4b17023SJohn Marino     typedef typename base_type::const_pointer 		const_pointer;
110*e4b17023SJohn Marino 
111*e4b17023SJohn Marino     typedef typename _Alloc::template rebind<metadata_type>::other __rebind_m;
112*e4b17023SJohn Marino 
113*e4b17023SJohn Marino     /// Const metadata reference.
114*e4b17023SJohn Marino     typedef typename __rebind_m::const_reference       metadata_const_reference;
115*e4b17023SJohn Marino 
116*e4b17023SJohn Marino     /// Metadata reference.
117*e4b17023SJohn Marino     typedef typename __rebind_m::reference 		metadata_reference;
118*e4b17023SJohn Marino 
119*e4b17023SJohn Marino     /// Returns the node_const_iterator associated with the tree's root node.
120*e4b17023SJohn Marino     virtual node_const_iterator
121*e4b17023SJohn Marino     node_begin() const = 0;
122*e4b17023SJohn Marino 
123*e4b17023SJohn Marino     /// Returns the node_iterator associated with the tree's root node.
124*e4b17023SJohn Marino     virtual node_iterator
125*e4b17023SJohn Marino     node_begin() = 0;
126*e4b17023SJohn Marino 
127*e4b17023SJohn Marino     /// Returns the node_const_iterator associated with a just-after leaf node.
128*e4b17023SJohn Marino     virtual node_const_iterator
129*e4b17023SJohn Marino     node_end() const = 0;
130*e4b17023SJohn Marino 
131*e4b17023SJohn Marino     /// Returns the node_iterator associated with a just-after leaf node.
132*e4b17023SJohn Marino     virtual node_iterator
133*e4b17023SJohn Marino     node_end() = 0;
134*e4b17023SJohn Marino 
135*e4b17023SJohn Marino     /// Access to the cmp_fn object.
136*e4b17023SJohn Marino     virtual cmp_fn&
137*e4b17023SJohn Marino     get_cmp_fn() = 0;
138*e4b17023SJohn Marino 
139*e4b17023SJohn Marino   protected:
140*e4b17023SJohn Marino     /// Updates the rank of a node through a node_iterator node_it;
141*e4b17023SJohn Marino     /// end_nd_it is the end node iterator.
142*e4b17023SJohn Marino     inline void
143*e4b17023SJohn Marino     operator()(node_iterator, node_const_iterator) const;
144*e4b17023SJohn Marino 
145*e4b17023SJohn Marino     virtual
146*e4b17023SJohn Marino     ~tree_order_statistics_node_update();
147*e4b17023SJohn Marino   };
148*e4b17023SJohn Marino 
149*e4b17023SJohn Marino #include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
150*e4b17023SJohn Marino 
151*e4b17023SJohn Marino #undef PB_DS_CLASS_T_DEC
152*e4b17023SJohn Marino #undef PB_DS_CLASS_C_DEC
153*e4b17023SJohn Marino #undef PB_DS_BRANCH_POLICY_BASE
154*e4b17023SJohn Marino 
155*e4b17023SJohn Marino } // namespace __gnu_pbds
156*e4b17023SJohn Marino 
157*e4b17023SJohn Marino #endif
158