1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 <iterator> 45#include <ext/pb_ds/detail/type_utils.hpp> 46#include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp> 47 48namespace __gnu_pbds 49{ 50 // A null node updator, indicating that no node updates are required. 51 template<typename Const_Node_Iterator, 52 typename Node_Iterator, 53 typename Cmp_Fn, 54 typename Allocator> 55 struct null_tree_node_update 56 { }; 57 58#define PB_DS_CLASS_T_DEC \ 59 template<typename Const_Node_Iterator, class Node_Iterator, class Cmp_Fn, class Allocator> 60 61#define PB_DS_CLASS_C_DEC \ 62 tree_order_statistics_node_update<Const_Node_Iterator, Node_Iterator, Cmp_Fn, Allocator> 63 64#define PB_DS_BASE_C_DEC \ 65 detail::basic_tree_policy_base<Const_Node_Iterator, Node_Iterator, Allocator> 66 67 // Functor updating ranks of entrees. 68 template<typename Const_Node_Iterator, typename Node_Iterator, 69 typename Cmp_Fn, typename Allocator> 70 class tree_order_statistics_node_update : private PB_DS_BASE_C_DEC 71 { 72 private: 73 typedef PB_DS_BASE_C_DEC base_type; 74 75 public: 76 typedef Cmp_Fn cmp_fn; 77 typedef Allocator allocator_type; 78 typedef typename allocator_type::size_type size_type; 79 typedef typename base_type::key_type key_type; 80 typedef typename base_type::const_key_reference const_key_reference; 81 82 typedef size_type metadata_type; 83 typedef Const_Node_Iterator const_node_iterator; 84 typedef Node_Iterator node_iterator; 85 typedef typename const_node_iterator::value_type const_iterator; 86 typedef typename node_iterator::value_type iterator; 87 88 // Finds an entry by __order. Returns a const_iterator to the 89 // entry with the __order order, or a const_iterator to the 90 // container object's end if order is at least the size of the 91 // container object. 92 inline const_iterator 93 find_by_order(size_type order) const; 94 95 // Finds an entry by __order. Returns an iterator to the entry 96 // with the __order order, or an iterator to the container 97 // object's end if order is at least the size of the container 98 // object. 99 inline iterator 100 find_by_order(size_type order); 101 102 // Returns the order of a key within a sequence. For exapmle, if 103 // r_key is the smallest key, this method will return 0; if r_key 104 // is a key between the smallest and next key, this method will 105 // return 1; if r_key is a key larger than the largest key, this 106 // method will return the size of r_c. 107 inline size_type 108 order_of_key(const_key_reference r_key) const; 109 110 private: 111 // Const reference to the container's value-type. 112 typedef typename base_type::const_reference const_reference; 113 114 // Const pointer to the container's value-type. 115 typedef typename base_type::const_pointer const_pointer; 116 117 typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind; 118 // Const metadata reference. 119 typedef typename metadata_rebind::const_reference const_metadata_reference; 120 121 // Metadata reference. 122 typedef typename metadata_rebind::reference metadata_reference; 123 124 // Returns the const_node_iterator associated with the tree's root node. 125 virtual const_node_iterator 126 node_begin() const = 0; 127 128 // Returns the node_iterator associated with the tree's root node. 129 virtual node_iterator 130 node_begin() = 0; 131 132 // Returns the const_node_iterator associated with a just-after leaf node. 133 virtual const_node_iterator 134 node_end() const = 0; 135 136 // Returns the node_iterator associated with a just-after leaf node. 137 virtual node_iterator 138 node_end() = 0; 139 140 // Access to the cmp_fn object. 141 virtual cmp_fn& 142 get_cmp_fn() = 0; 143 144 protected: 145 // Updates the rank of a node through a node_iterator node_it; 146 // end_nd_it is the end node iterator. 147 inline void 148 operator()(node_iterator node_it, const_node_iterator end_nd_it) const; 149 150 virtual 151 ~tree_order_statistics_node_update(); 152 }; 153 154#include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp> 155 156#undef PB_DS_CLASS_T_DEC 157#undef PB_DS_CLASS_C_DEC 158#undef PB_DS_BASE_C_DEC 159 160} // namespace __gnu_pbds 161 162#endif 163