00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 #ifndef TREE_POLICY_HPP
00046 #define TREE_POLICY_HPP
00047
00048 #include <functional>
00049 #include <ext/pb_assoc/ms_trait.hpp>
00050
00051 namespace pb_assoc
00052 {
00053 struct null_node_updator
00054 {
00055 inline void
00056 swap(null_node_updator& r_other);
00057 };
00058
00059 #include <ext/pb_assoc/detail/tree_policy/null_node_updator_imp.hpp>
00060
00061 template<typename Key, typename Allocator = std::allocator<char> >
00062 class order_statistics_key
00063 {
00064 public:
00065 typedef Allocator allocator;
00066 typedef Key key_type;
00067 typedef typename allocator::template rebind<Key>::other::const_reference
00068 const_key_reference;
00069 typedef typename allocator::template rebind<Key>::other::reference
00070 key_reference;
00071 typedef typename allocator::size_type size_type;
00072
00073 inline explicit
00074 order_statistics_key(const_key_reference r_key = Key());
00075
00076 inline
00077 operator key_reference();
00078
00079 inline
00080 operator key_type() const;
00081
00082 private:
00083
00084 key_type m_key;
00085
00086
00087
00088 mutable size_type m_rank;
00089
00090 template<typename Cntnr>
00091 friend class order_by_key;
00092
00093 template<typename Some_Cmp_Fn, typename Some_Allocator>
00094 friend class order_statistics_key_cmp;
00095
00096 template<typename Some_Key, typename Some_Allocator>
00097 friend class order_statistics_node_updator;
00098
00099 template<typename Cntnr>
00100 friend class find_by_order;
00101
00102 template<typename Cntnr, typename Some_Allocator>
00103 friend class order_statistics_key_verifier;
00104 };
00105
00106 template<typename Cmp_Fn, typename Allocator = std::allocator<char> >
00107 class order_statistics_key_cmp
00108 : public std::binary_function<
00109 order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>,
00110 order_statistics_key<typename Cmp_Fn::second_argument_type, Allocator>, bool>,
00111 private Cmp_Fn
00112 {
00113 public:
00114 typedef Allocator allocator;
00115 typedef Cmp_Fn cmp_fn;
00116
00117 typedef
00118 order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>
00119 key_type;
00120
00121 typedef
00122 typename allocator::template rebind<key_type>::other::const_reference
00123 const_key_reference;
00124
00125 inline
00126 order_statistics_key_cmp();
00127
00128 inline
00129 order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn);
00130
00131 inline bool
00132 operator()(const_key_reference, const_key_reference) const;
00133
00134 inline cmp_fn&
00135 get_cmp_fn();
00136
00137 inline const cmp_fn&
00138 get_cmp_fn() const;
00139 };
00140
00141 #define PB_ASSOC_CLASS_C_DEC \
00142 order_statistics_node_updator<Key, Allocator>
00143
00144 template<typename Key, typename Allocator = std::allocator<char> >
00145 class order_statistics_node_updator
00146 {
00147 public:
00148 typedef Allocator allocator;
00149 typedef order_statistics_key< Key, Allocator> key_type;
00150
00151 typedef
00152 typename Allocator::template rebind<key_type>::other::const_pointer
00153 const_key_pointer;
00154
00155 inline void
00156 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00157
00158 inline void
00159 operator()(const_key_pointer, const_key_pointer, const_key_pointer);
00160
00161 private:
00162 typedef typename Allocator::size_type size_type;
00163 };
00164
00165 #undef PB_ASSOC_CLASS_C_DEC
00166
00167 template<class Cntnr>
00168 class find_by_order
00169 {
00170 public:
00171 typedef Cntnr cntnr;
00172 typedef typename cntnr::iterator iterator;
00173 typedef typename cntnr::const_iterator const_iterator;
00174 typedef typename cntnr::size_type size_type;
00175
00176 inline iterator
00177 operator()(Cntnr& r_c, size_type order) const;
00178
00179 inline const_iterator
00180 operator()(const Cntnr& r_c, size_type order) const;
00181
00182 private:
00183 typedef typename Cntnr::node_iterator node_iterator;
00184 typedef typename Cntnr::const_iterator cntnr_const_it;
00185 typedef typename Cntnr::iterator cntnr_it;
00186
00187 inline static iterator
00188 find(Cntnr& r_c, size_type order);
00189
00190 inline static const_iterator
00191 find(const Cntnr& r_c, size_type order);
00192 };
00193
00194 template<class Cntnr>
00195 class order_by_key
00196 {
00197 public:
00198 typedef Cntnr cntnr;
00199 typedef typename Cntnr::key_type order_statistics_key_type;
00200 typedef typename order_statistics_key_type::key_type
00201 underlying_key_type;
00202 typedef typename cntnr::size_type size_type;
00203
00204 inline size_type
00205 operator()(const Cntnr& r_c, const underlying_key_type& r_key) const;
00206
00207 private:
00208 typedef typename cntnr::const_iterator cntnr_const_it;
00209 typedef typename cntnr::iterator cntnr_it;
00210 };
00211
00212 #include <ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp>
00213 }
00214
00215 #endif // #ifndef TREE_POLICY_HPP