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