> The second and third patch together resolve PR 81806.
The attached patch keeps the subtree size in binary search tree nodes.
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_map_/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.
--
Xi Ruoyao <xry...@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
From 248ab526b766070d348d676ebf9f9c7b16c3a93e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry...@mengyan1223.wang>
Date: Fri, 10 Jul 2020 20:58:04 +0800
Subject: [PATCH 2/5] 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_map_/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.
---
.../bin_search_tree_/bin_search_tree_.hpp | 3 ++
.../bin_search_tree_/rotate_fn_imps.hpp | 31 ++++++++++++++++---
.../ext/pb_ds/detail/rb_tree_map_/node.hpp | 8 +++++
.../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 32dcb6ee020..38a3bab0444 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 1f18243a859..72ccfeb16a2 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 de2d92a59b6..802562ad4f2 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 5c7b5d43c2b..d83b44deaae 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;
};
--
2.27.0
