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