tree_policy.hpp
Go to the documentation of this file.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 #ifndef PB_DS_TREE_POLICY_HPP
00042 #define PB_DS_TREE_POLICY_HPP
00043
00044 #include <iterator>
00045 #include <ext/pb_ds/detail/type_utils.hpp>
00046 #include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
00047
00048 namespace __gnu_pbds
00049 {
00050
00051 template<typename Const_Node_Iterator,
00052 typename Node_Iterator,
00053 typename Cmp_Fn,
00054 typename Allocator>
00055 struct null_tree_node_update
00056 { };
00057
00058 #define PB_DS_CLASS_T_DEC \
00059 template<typename Const_Node_Iterator, class Node_Iterator, class Cmp_Fn, class Allocator>
00060
00061 #define PB_DS_CLASS_C_DEC \
00062 tree_order_statistics_node_update<Const_Node_Iterator, Node_Iterator, Cmp_Fn, Allocator>
00063
00064 #define PB_DS_BASE_C_DEC \
00065 detail::basic_tree_policy_base<Const_Node_Iterator, Node_Iterator, Allocator>
00066
00067
00068 template<typename Const_Node_Iterator, typename Node_Iterator,
00069 typename Cmp_Fn, typename Allocator>
00070 class tree_order_statistics_node_update : private PB_DS_BASE_C_DEC
00071 {
00072 private:
00073 typedef PB_DS_BASE_C_DEC base_type;
00074
00075 public:
00076 typedef Cmp_Fn cmp_fn;
00077 typedef Allocator allocator_type;
00078 typedef typename allocator_type::size_type size_type;
00079 typedef typename base_type::key_type key_type;
00080 typedef typename base_type::const_key_reference const_key_reference;
00081
00082 typedef size_type metadata_type;
00083 typedef Const_Node_Iterator const_node_iterator;
00084 typedef Node_Iterator node_iterator;
00085 typedef typename const_node_iterator::value_type const_iterator;
00086 typedef typename node_iterator::value_type iterator;
00087
00088
00089
00090
00091
00092 inline const_iterator
00093 find_by_order(size_type order) const;
00094
00095
00096
00097
00098
00099 inline iterator
00100 find_by_order(size_type order);
00101
00102
00103
00104
00105
00106
00107 inline size_type
00108 order_of_key(const_key_reference r_key) const;
00109
00110 private:
00111
00112 typedef typename base_type::const_reference const_reference;
00113
00114
00115 typedef typename base_type::const_pointer const_pointer;
00116
00117 typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind;
00118
00119 typedef typename metadata_rebind::const_reference const_metadata_reference;
00120
00121
00122 typedef typename metadata_rebind::reference metadata_reference;
00123
00124
00125 virtual const_node_iterator
00126 node_begin() const = 0;
00127
00128
00129 virtual node_iterator
00130 node_begin() = 0;
00131
00132
00133 virtual const_node_iterator
00134 node_end() const = 0;
00135
00136
00137 virtual node_iterator
00138 node_end() = 0;
00139
00140
00141 virtual cmp_fn&
00142 get_cmp_fn() = 0;
00143
00144 protected:
00145
00146
00147 inline void
00148 operator()(node_iterator node_it, const_node_iterator end_nd_it) const;
00149
00150 virtual
00151 ~tree_order_statistics_node_update();
00152 };
00153
00154 #include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
00155
00156 #undef PB_DS_CLASS_T_DEC
00157 #undef PB_DS_CLASS_C_DEC
00158 #undef PB_DS_BASE_C_DEC
00159
00160 }
00161
00162 #endif