libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file tree_policy.hpp 00038 * Contains tree-related policies. 00039 */ 00040 00041 #ifndef PB_DS_TREE_POLICY_HPP 00042 #define PB_DS_TREE_POLICY_HPP 00043 00044 #include <bits/c++config.h> 00045 #include <iterator> 00046 #include <ext/pb_ds/detail/type_utils.hpp> 00047 #include <ext/pb_ds/detail/branch_policy/branch_policy.hpp> 00048 00049 namespace __gnu_pbds 00050 { 00051 #define PB_DS_CLASS_T_DEC \ 00052 template<typename Node_CItr, typename Node_Itr, typename Cmp_Fn, \ 00053 typename _Alloc> 00054 00055 #define PB_DS_CLASS_C_DEC \ 00056 tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc> 00057 00058 #define PB_DS_BRANCH_POLICY_BASE \ 00059 detail::branch_policy<Node_CItr, Node_Itr, _Alloc> 00060 00061 /// Functor updating ranks of entrees. 00062 template<typename Node_CItr, typename Node_Itr, 00063 typename Cmp_Fn, typename _Alloc> 00064 class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE 00065 { 00066 private: 00067 typedef PB_DS_BRANCH_POLICY_BASE base_type; 00068 00069 public: 00070 typedef Cmp_Fn cmp_fn; 00071 typedef _Alloc allocator_type; 00072 typedef typename allocator_type::size_type size_type; 00073 typedef typename base_type::key_type key_type; 00074 typedef typename base_type::key_const_reference key_const_reference; 00075 00076 typedef size_type metadata_type; 00077 typedef Node_CItr node_const_iterator; 00078 typedef Node_Itr node_iterator; 00079 typedef typename node_const_iterator::value_type const_iterator; 00080 typedef typename node_iterator::value_type iterator; 00081 00082 /// Finds an entry by __order. Returns a const_iterator to the 00083 /// entry with the __order order, or a const_iterator to the 00084 /// container object's end if order is at least the size of the 00085 /// container object. 00086 inline const_iterator 00087 find_by_order(size_type) const; 00088 00089 /// Finds an entry by __order. Returns an iterator to the entry 00090 /// with the __order order, or an iterator to the container 00091 /// object's end if order is at least the size of the container 00092 /// object. 00093 inline iterator 00094 find_by_order(size_type); 00095 00096 /// Returns the order of a key within a sequence. For exapmle, if 00097 /// r_key is the smallest key, this method will return 0; if r_key 00098 /// is a key between the smallest and next key, this method will 00099 /// return 1; if r_key is a key larger than the largest key, this 00100 /// method will return the size of r_c. 00101 inline size_type 00102 order_of_key(key_const_reference) const; 00103 00104 private: 00105 /// Const reference to the container's value-type. 00106 typedef typename base_type::const_reference const_reference; 00107 00108 /// Const pointer to the container's value-type. 00109 typedef typename base_type::const_pointer const_pointer; 00110 00111 typedef typename _Alloc::template rebind<metadata_type>::other __rebind_m; 00112 00113 /// Const metadata reference. 00114 typedef typename __rebind_m::const_reference metadata_const_reference; 00115 00116 /// Metadata reference. 00117 typedef typename __rebind_m::reference metadata_reference; 00118 00119 /// Returns the node_const_iterator associated with the tree's root node. 00120 virtual node_const_iterator 00121 node_begin() const = 0; 00122 00123 /// Returns the node_iterator associated with the tree's root node. 00124 virtual node_iterator 00125 node_begin() = 0; 00126 00127 /// Returns the node_const_iterator associated with a just-after leaf node. 00128 virtual node_const_iterator 00129 node_end() const = 0; 00130 00131 /// Returns the node_iterator associated with a just-after leaf node. 00132 virtual node_iterator 00133 node_end() = 0; 00134 00135 /// Access to the cmp_fn object. 00136 virtual cmp_fn& 00137 get_cmp_fn() = 0; 00138 00139 protected: 00140 /// Updates the rank of a node through a node_iterator node_it; 00141 /// end_nd_it is the end node iterator. 00142 inline void 00143 operator()(node_iterator, node_const_iterator) const; 00144 00145 virtual 00146 ~tree_order_statistics_node_update(); 00147 }; 00148 00149 #include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp> 00150 00151 #undef PB_DS_CLASS_T_DEC 00152 #undef PB_DS_CLASS_C_DEC 00153 #undef PB_DS_BRANCH_POLICY_BASE 00154 00155 } // namespace __gnu_pbds 00156 00157 #endif