https://gcc.gnu.org/g:2e27df6cbd05a3ee742434b7f50dbff5f363b487
commit r16-771-g2e27df6cbd05a3ee742434b7f50dbff5f363b487
Author: Xℹ Ruoyao <xry...@mengyan1223.wang>
Date: Fri Jul 10 20:58:04 2020 +0800
libstdc++: maintain subtree size in pb_ds binary search trees
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/rb_tree_map_/node.hpp
(rb_tree_node_::size_type): New typedef.
(rb_tree_node_::m_subtree_size): New field.
* include/ext/pb_ds/detail/splay_tree_/node.hpp
(splay_tree_node_::size_type): New typedef.
(splay_tree_node_::m_subtree_size): New field.
* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
(PB_DS_BIN_TREE_NAME::update_subtree_size): Declare new member
function.
* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
(update_subtree_size): Define.
(apply_update, update_to_top): Call update_subtree_size.
Diff:
---
.../detail/bin_search_tree_/bin_search_tree_.hpp | 3 +++
.../detail/bin_search_tree_/rotate_fn_imps.hpp | 31 +++++++++++++++++++---
.../include/ext/pb_ds/detail/rb_tree_map_/node.hpp | 8 ++++++
.../include/ext/pb_ds/detail/splay_tree_/node.hpp | 8 ++++++
4 files changed, 46 insertions(+), 4 deletions(-)
diff --git
a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
index 6088709998a3..a8c73b55b89d 100644
---
a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
+++
b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
@@ -304,6 +304,9 @@ namespace __gnu_pbds
inline void
rotate_parent(node_pointer);
+ inline void
+ update_subtree_size(node_pointer);
+
inline void
apply_update(node_pointer, null_node_update_pointer);
diff --git
a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
index 069b17f08de2..8cadce2349bd 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
@@ -122,8 +122,23 @@ rotate_parent(node_pointer p_nd)
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
-apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
-{ }
+update_subtree_size(node_pointer p_nd)
+{
+ size_type size = 1;
+ if (p_nd->m_p_left)
+ size += p_nd->m_p_left->m_subtree_size;
+ if (p_nd->m_p_right)
+ size += p_nd->m_p_right->m_subtree_size;
+ p_nd->m_subtree_size = size;
+}
+
+PB_DS_CLASS_T_DEC
+inline void
+PB_DS_CLASS_C_DEC::
+apply_update(node_pointer p_nd, null_node_update_pointer /*p_update*/)
+{
+ update_subtree_size(p_nd);
+}
PB_DS_CLASS_T_DEC
template<typename Node_Update_>
@@ -131,6 +146,7 @@ inline void
PB_DS_CLASS_C_DEC::
apply_update(node_pointer p_nd, Node_Update_* /*p_update*/)
{
+ update_subtree_size(p_nd);
node_update::operator()(node_iterator(p_nd),
node_const_iterator(static_cast<node_pointer>(0)));
}
@@ -152,7 +168,14 @@ update_to_top(node_pointer p_nd, Node_Update_* p_update)
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
-update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
-{ }
+update_to_top(node_pointer p_nd, null_node_update_pointer /*p_update */)
+{
+ while (p_nd != m_p_head)
+ {
+ update_subtree_size(p_nd);
+
+ p_nd = p_nd->m_p_parent;
+ }
+}
#endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
index f229be7342c6..3803ddb19c5d 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
@@ -58,6 +58,9 @@ namespace __gnu_pbds
typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
node_pointer;
+ typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type
+ size_type;
+
typedef typename rebind_traits<_Alloc, metadata_type>::reference
metadata_reference;
@@ -88,6 +91,7 @@ namespace __gnu_pbds
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
+ size_type m_subtree_size;
value_type m_value;
bool m_red;
metadata_type m_metadata;
@@ -100,6 +104,9 @@ namespace __gnu_pbds
typedef Value_Type value_type;
typedef null_type metadata_type;
+ typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type
+ size_type;
+
typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
node_pointer;
@@ -116,6 +123,7 @@ namespace __gnu_pbds
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
+ size_type m_subtree_size;
value_type m_value;
bool m_red;
};
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
index 961afbe8664b..b5fbb500c8e0 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
@@ -56,6 +56,9 @@ namespace __gnu_pbds
typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
node_pointer;
+ typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type
+ size_type;
+
typedef typename rebind_traits<_Alloc, metadata_type>::reference
metadata_reference;
@@ -85,6 +88,7 @@ namespace __gnu_pbds
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
+ size_type m_subtree_size;
metadata_type m_metadata;
};
@@ -98,6 +102,9 @@ namespace __gnu_pbds
typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
node_pointer;
+ typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type
+ size_type;
+
inline bool
special() const
{ return m_special; }
@@ -111,6 +118,7 @@ namespace __gnu_pbds
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
+ size_type m_subtree_size;
value_type m_value;
bool m_special;
};
