[2/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)

From 248ab526b766070d348d676ebf9f9c7b16c3a93e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@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