1// -*- C++ -*- 2 3// Copyright (C) 2005 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 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 31 32// Permission to use, copy, modify, sell, and distribute this software 33// is hereby granted without fee, provided that the above copyright 34// notice appears in all copies, and that both that copyright notice and 35// this permission notice appear in supporting documentation. None of 36// the above authors, nor IBM Haifa Research Laboratories, make any 37// representation about the suitability of this software for any 38// purpose. It is provided "as is" without express or implied warranty. 39 40/* 41 * @file tree_policy.hpp 42 * Contains tree-related policies. 43 */ 44 45#ifndef TREE_POLICY_HPP 46#define TREE_POLICY_HPP 47 48#include <functional> 49#include <ext/pb_assoc/ms_trait.hpp> 50 51namespace pb_assoc 52{ 53 struct null_node_updator 54 { 55 inline void 56 swap(null_node_updator& r_other); 57 }; 58 59#include <ext/pb_assoc/detail/tree_policy/null_node_updator_imp.hpp> 60 61 template<typename Key, typename Allocator = std::allocator<char> > 62 class order_statistics_key 63 { 64 public: 65 typedef Allocator allocator; 66 typedef Key key_type; 67 typedef typename allocator::template rebind<Key>::other::const_reference 68 const_key_reference; 69 typedef typename allocator::template rebind<Key>::other::reference 70 key_reference; 71 typedef typename allocator::size_type size_type; 72 73 inline explicit 74 order_statistics_key(const_key_reference r_key = Key()); 75 76 inline 77 operator key_reference(); 78 79 inline 80 operator key_type() const; 81 82 private: 83 // The logical key of the entry. 84 key_type m_key; 85 86 // The number of entries in the subtree rooted at the node of 87 // this element. 88 mutable size_type m_rank; 89 90 template<typename Cntnr> 91 friend class order_by_key; 92 93 template<typename Some_Cmp_Fn, typename Some_Allocator> 94 friend class order_statistics_key_cmp; 95 96 template<typename Some_Key, typename Some_Allocator> 97 friend class order_statistics_node_updator; 98 99 template<typename Cntnr> 100 friend class find_by_order; 101 102 template<typename Cntnr, typename Some_Allocator> 103 friend class order_statistics_key_verifier; 104 }; 105 106 template<typename Cmp_Fn, typename Allocator = std::allocator<char> > 107 class order_statistics_key_cmp 108 : public std::binary_function< 109 order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>, 110 order_statistics_key<typename Cmp_Fn::second_argument_type, Allocator>, bool>, 111 private Cmp_Fn 112 { 113 public: 114 typedef Allocator allocator; 115 typedef Cmp_Fn cmp_fn; 116 117 typedef 118 order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator> 119 key_type; 120 121 typedef 122 typename allocator::template rebind<key_type>::other::const_reference 123 const_key_reference; 124 125 inline 126 order_statistics_key_cmp(); 127 128 inline 129 order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn); 130 131 inline bool 132 operator()(const_key_reference, const_key_reference) const; 133 134 inline cmp_fn& 135 get_cmp_fn(); 136 137 inline const cmp_fn& 138 get_cmp_fn() const; 139 }; 140 141#define PB_ASSOC_CLASS_C_DEC \ 142 order_statistics_node_updator<Key, Allocator> 143 144 template<typename Key, typename Allocator = std::allocator<char> > 145 class order_statistics_node_updator 146 { 147 public: 148 typedef Allocator allocator; 149 typedef order_statistics_key< Key, Allocator> key_type; 150 151 typedef 152 typename Allocator::template rebind<key_type>::other::const_pointer 153 const_key_pointer; 154 155 inline void 156 swap(PB_ASSOC_CLASS_C_DEC& r_other); 157 158 inline void 159 operator()(const_key_pointer, const_key_pointer, const_key_pointer); 160 161 private: 162 typedef typename Allocator::size_type size_type; 163 }; 164 165#undef PB_ASSOC_CLASS_C_DEC 166 167 template<class Cntnr> 168 class find_by_order 169 { 170 public: 171 typedef Cntnr cntnr; 172 typedef typename cntnr::iterator iterator; 173 typedef typename cntnr::const_iterator const_iterator; 174 typedef typename cntnr::size_type size_type; 175 176 inline iterator 177 operator()(Cntnr& r_c, size_type order) const; 178 179 inline const_iterator 180 operator()(const Cntnr& r_c, size_type order) const; 181 182 private: 183 typedef typename Cntnr::node_iterator node_iterator; 184 typedef typename Cntnr::const_iterator cntnr_const_it; 185 typedef typename Cntnr::iterator cntnr_it; 186 187 inline static iterator 188 find(Cntnr& r_c, size_type order); 189 190 inline static const_iterator 191 find(const Cntnr& r_c, size_type order); 192 }; 193 194 template<class Cntnr> 195 class order_by_key 196 { 197 public: 198 typedef Cntnr cntnr; 199 typedef typename Cntnr::key_type order_statistics_key_type; 200 typedef typename order_statistics_key_type::key_type 201 underlying_key_type; 202 typedef typename cntnr::size_type size_type; 203 204 inline size_type 205 operator()(const Cntnr& r_c, const underlying_key_type& r_key) const; 206 207 private: 208 typedef typename cntnr::const_iterator cntnr_const_it; 209 typedef typename cntnr::iterator cntnr_it; 210 }; 211 212#include <ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp> 213} // namespace pb_assoc 214 215#endif // #ifndef TREE_POLICY_HPP 216