41 #ifndef PB_DS_TREE_POLICY_HPP
42 #define PB_DS_TREE_POLICY_HPP
46 #include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
51 template<
typename Const_Node_Iterator,
52 typename Node_Iterator,
55 struct null_tree_node_update
58 #define PB_DS_CLASS_T_DEC \
59 template<typename Const_Node_Iterator, class Node_Iterator, class Cmp_Fn, class Allocator>
61 #define PB_DS_CLASS_C_DEC \
62 tree_order_statistics_node_update<Const_Node_Iterator, Node_Iterator, Cmp_Fn, Allocator>
64 #define PB_DS_BASE_C_DEC \
65 detail::basic_tree_policy_base<Const_Node_Iterator, Node_Iterator, Allocator>
68 template<
typename Const_Node_Iterator,
typename Node_Iterator,
69 typename Cmp_Fn,
typename Allocator>
70 class tree_order_statistics_node_update :
private PB_DS_BASE_C_DEC
73 typedef PB_DS_BASE_C_DEC base_type;
76 typedef Cmp_Fn cmp_fn;
77 typedef Allocator allocator_type;
78 typedef typename allocator_type::size_type size_type;
79 typedef typename base_type::key_type key_type;
80 typedef typename base_type::const_key_reference const_key_reference;
82 typedef size_type metadata_type;
83 typedef Const_Node_Iterator const_node_iterator;
84 typedef Node_Iterator node_iterator;
85 typedef typename const_node_iterator::value_type const_iterator;
86 typedef typename node_iterator::value_type iterator;
93 find_by_order(size_type order)
const;
100 find_by_order(size_type order);
108 order_of_key(const_key_reference r_key)
const;
112 typedef typename base_type::const_reference const_reference;
115 typedef typename base_type::const_pointer const_pointer;
117 typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind;
119 typedef typename metadata_rebind::const_reference const_metadata_reference;
122 typedef typename metadata_rebind::reference metadata_reference;
125 virtual const_node_iterator
126 node_begin()
const = 0;
129 virtual node_iterator
133 virtual const_node_iterator
134 node_end()
const = 0;
137 virtual node_iterator
148 operator()(node_iterator node_it, const_node_iterator end_nd_it)
const;
151 ~tree_order_statistics_node_update();
154 #include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
156 #undef PB_DS_CLASS_T_DEC
157 #undef PB_DS_CLASS_C_DEC
158 #undef PB_DS_BASE_C_DEC
GNU extensions for policy-based data structures for public use.