1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file tree_policy.hpp 44 * Contains tree-related policies. 45 */ 46 47#ifndef PB_DS_TREE_POLICY_HPP 48#define PB_DS_TREE_POLICY_HPP 49 50#include <iterator> 51#include <ext/pb_ds/detail/type_utils.hpp> 52#include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp> 53 54namespace pb_ds 55{ 56 // A null node updator, indicating that no node updates are required. 57 template<typename Const_Node_Iterator, 58 typename Node_Iterator, 59 typename Cmp_Fn, 60 typename Allocator> 61 struct null_tree_node_update 62 { }; 63 64#define PB_DS_CLASS_T_DEC \ 65 template<typename Const_Node_Iterator, class Node_Iterator, class Cmp_Fn, class Allocator> 66 67#define PB_DS_CLASS_C_DEC \ 68 tree_order_statistics_node_update<Const_Node_Iterator, Node_Iterator, Cmp_Fn, Allocator> 69 70#define PB_DS_BASE_C_DEC \ 71 detail::basic_tree_policy_base<Const_Node_Iterator, Node_Iterator, Allocator> 72 73 // Functor updating ranks of entrees. 74 template<typename Const_Node_Iterator, typename Node_Iterator, 75 typename Cmp_Fn, typename Allocator> 76 class tree_order_statistics_node_update : private PB_DS_BASE_C_DEC 77 { 78 private: 79 typedef PB_DS_BASE_C_DEC base_type; 80 81 public: 82 typedef Cmp_Fn cmp_fn; 83 typedef Allocator allocator; 84 typedef typename allocator::size_type size_type; 85 typedef typename base_type::key_type key_type; 86 typedef typename base_type::const_key_reference const_key_reference; 87 88 typedef size_type metadata_type; 89 typedef Const_Node_Iterator const_node_iterator; 90 typedef Node_Iterator node_iterator; 91 typedef typename const_node_iterator::value_type const_iterator; 92 typedef typename node_iterator::value_type iterator; 93 94 // Finds an entry by __order. Returns a const_iterator to the 95 // entry with the __order order, or a const_iterator to the 96 // container object's end if order is at least the size of the 97 // container object. 98 inline const_iterator 99 find_by_order(size_type order) const; 100 101 // Finds an entry by __order. Returns an iterator to the entry 102 // with the __order order, or an iterator to the container 103 // object's end if order is at least the size of the container 104 // object. 105 inline iterator 106 find_by_order(size_type order); 107 108 // Returns the order of a key within a sequence. For exapmle, if 109 // r_key is the smallest key, this method will return 0; if r_key 110 // is a key between the smallest and next key, this method will 111 // return 1; if r_key is a key larger than the largest key, this 112 // method will return the size of r_c. 113 inline size_type 114 order_of_key(const_key_reference r_key) const; 115 116 private: 117 // Const reference to the container's value-type. 118 typedef typename base_type::const_reference const_reference; 119 120 // Const pointer to the container's value-type. 121 typedef typename base_type::const_pointer const_pointer; 122 123 typedef typename allocator::template rebind<metadata_type>::other metadata_rebind; 124 // Const metadata reference. 125 typedef typename metadata_rebind::const_reference const_metadata_reference; 126 127 // Metadata reference. 128 typedef typename metadata_rebind::reference metadata_reference; 129 130 // Returns the const_node_iterator associated with the tree's root node. 131 virtual const_node_iterator 132 node_begin() const = 0; 133 134 // Returns the node_iterator associated with the tree's root node. 135 virtual node_iterator 136 node_begin() = 0; 137 138 // Returns the const_node_iterator associated with a just-after leaf node. 139 virtual const_node_iterator 140 node_end() const = 0; 141 142 // Returns the node_iterator associated with a just-after leaf node. 143 virtual node_iterator 144 node_end() = 0; 145 146 // Access to the cmp_fn object. 147 virtual cmp_fn& 148 get_cmp_fn() = 0; 149 150 protected: 151 // Updates the rank of a node through a node_iterator node_it; 152 // end_nd_it is the end node iterator. 153 inline void 154 operator()(node_iterator node_it, const_node_iterator end_nd_it) const; 155 156 virtual 157 ~tree_order_statistics_node_update(); 158 }; 159 160#include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp> 161 162#undef PB_DS_CLASS_T_DEC 163#undef PB_DS_CLASS_C_DEC 164#undef PB_DS_BASE_C_DEC 165 166} // namespace pb_ds 167 168#endif 169