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