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