From c0ee85f492872ba164ad3c1c9636aace1de02e96 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Sun, 12 Jul 2020 16:12:18 +0800
Subject: [PATCH 5/5] libstdc++: implement order statistics function in pb_ds
 tree maps

libstdc++-v3/ChangeLog:

	* include/Makefile.am: Add
	  include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
	  and
	  include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp,
	  remove
	  include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp.
	* include/Makefile.in: Regenerate.
	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
	  (PB_DS_BIN_TREE_NAME::find_by_order): Declare new member function.
	  (PB_DS_BIN_TREE_NAME::order_of_key): Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
	  (PB_DS_OV_TREE_NAME::find_by_order): Likewise.
	  (PB_DS_OV_TREE_NAME::order_of_key): Likewise.
	* include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp:
	  New file.
	  (PB_DS_CLASS_C_DEC::find_by_order): Implement.
	  (PB_DS_CLASS_C_DEC::order_of_key): Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp:
	  New file.
	  (PB_DS_CLASS_C_DEC::find_by_order): Implement.
	  (PB_DS_CLASS_C_DEC::order_of_key): Likewise.
	* include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:
	  Delete.
	* include/ext/pb_ds/tree_policy.hpp
	  (tree_order_statistics_node_update): Make it noop, and deprecate.
	* testsuite/ext/pb_ds/example/tree_order_statistics.cc:
	  Remove the usage of deprecated tree_order_statistics_node_update.
	* testsuite/ext/pb_ds/example/tree_order_statistics_join.cc:
	  Likewise.
---
 libstdc++-v3/include/Makefile.am              |  3 +-
 libstdc++-v3/include/Makefile.in              |  3 +-
 .../bin_search_tree_/bin_search_tree_.hpp     | 10 +++
 .../order_statistics_imps.hpp}                | 50 ++++-------
 .../ov_tree_map_/order_statistics_imps.hpp    | 77 ++++++++++++++++
 .../detail/ov_tree_map_/ov_tree_map_.hpp      | 10 +++
 .../include/ext/pb_ds/tree_policy.hpp         | 88 ++-----------------
 .../pb_ds/example/tree_order_statistics.cc    |  9 +-
 .../example/tree_order_statistics_join.cc     |  4 +-
 9 files changed, 125 insertions(+), 129 deletions(-)
 rename libstdc++-v3/include/ext/pb_ds/detail/{tree_policy/order_statistics_imp.hpp => bin_search_tree_/order_statistics_imps.hpp} (71%)
 create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index e131ce04f8c..604821ecda2 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -365,6 +365,7 @@ pb_headers2 = \
 	${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \
+	${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/traits.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \
@@ -467,6 +468,7 @@ pb_headers4 = \
 	${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \
+	${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp
 
@@ -551,7 +553,6 @@ pb_headers7 = \
 	${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
 	${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
 	${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-	${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
 	${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
 	${pb_srcdir}/detail/tree_trace_base.hpp \
 	${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index c0b71e13a32..f7b2c136dbf 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -711,6 +711,7 @@ pb_headers2 = \
 	${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \
+	${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/traits.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \
@@ -813,6 +814,7 @@ pb_headers4 = \
 	${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \
+	${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp
 
@@ -897,7 +899,6 @@ pb_headers7 = \
 	${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
 	${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
 	${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-	${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
 	${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
 	${pb_srcdir}/detail/tree_trace_base.hpp \
 	${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
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 38a3bab0444..d76e822516b 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
@@ -238,6 +238,15 @@ namespace __gnu_pbds
       inline const_reverse_iterator
       rend() const;
 
+      inline iterator
+      find_by_order(size_type order);
+
+      inline const_iterator
+      find_by_order(size_type order) const;
+
+      inline size_type
+      order_of_key(key_const_reference r_key) const;
+
       /// Returns a const node_iterator corresponding to the node at the
       /// root of the tree.
       inline node_const_iterator
@@ -411,6 +420,7 @@ namespace __gnu_pbds
 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
+#include <ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
similarity index 71%
rename from libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp
rename to libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
index a31d5985d18..6358c79c3ba 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
@@ -34,8 +34,8 @@
 // warranty.
 
 /**
- * @file tree_policy/order_statistics_imp.hpp
- * Contains forward declarations for order_statistics_key
+ * @file bin_search_tree_/order_statistics_imps.hpp
+ * Contains an implementation class for bin_search_tree_.
  */
 
 #ifdef PB_DS_CLASS_C_DEC
@@ -51,20 +51,20 @@ find_by_order(size_type order)
   while (it != end_it)
     {
       node_iterator l_it = it.get_l_child();
-      const size_type o = (l_it == end_it)? 0 : l_it.get_metadata();
+      const size_type o = (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size;
 
       if (order == o)
-	return *it;
+        return *it;
       else if (order < o)
-	it = l_it;
+        it = l_it;
       else
         {
-	  order -= o + 1;
-	  it = it.get_r_child();
+          order -= o + 1;
+          it = it.get_r_child();
         }
     }
 
-  return base_type::end_iterator();
+  return iterator(m_p_head);
 }
 
 PB_DS_CLASS_T_DEC
@@ -87,38 +87,20 @@ order_of_key(key_const_reference r_key) const
     {
       node_const_iterator l_it = it.get_l_child();
 
-      if (r_cmp_fn(r_key, this->extract_key(*(*it))))
-	it = l_it;
-      else if (r_cmp_fn(this->extract_key(*(*it)), r_key))
+      if (r_cmp_fn(r_key, PB_DS_V2F(*(*it))))
+        it = l_it;
+      else if (r_cmp_fn(PB_DS_V2F(*(*it)),
+                        r_key))
         {
-	  ord += (l_it == end_it)? 1 : 1 + l_it.get_metadata();
-	  it = it.get_r_child();
+          ord += (l_it == end_it)? 1 : 1 + l_it.m_p_nd->m_subtree_size;
+          it = it.get_r_child();
         }
       else
         {
-	  ord += (l_it == end_it)? 0 : l_it.get_metadata();
-	  it = end_it;
+          ord += (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size;
+          it = end_it;
         }
     }
   return ord;
 }
-
-PB_DS_CLASS_T_DEC
-inline void
-PB_DS_CLASS_C_DEC::
-operator()(node_iterator node_it, node_const_iterator end_nd_it) const
-{
-  node_iterator l_it = node_it.get_l_child();
-  const size_type l_rank = (l_it == end_nd_it) ? 0 : l_it.get_metadata();
-
-  node_iterator r_it = node_it.get_r_child();
-  const size_type r_rank = (r_it == end_nd_it) ? 0 : r_it.get_metadata();
-
-  const_cast<metadata_reference>(node_it.get_metadata())= 1 + l_rank + r_rank;
-}
-
-PB_DS_CLASS_T_DEC
-PB_DS_CLASS_C_DEC::
-~tree_order_statistics_node_update()
-{ }
 #endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp
new file mode 100644
index 00000000000..69c0d543b4c
--- /dev/null
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp
@@ -0,0 +1,77 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005-2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file bin_search_tree_/order_statistics_imps.hpp
+ * Contains an implementation class for bin_search_tree_.
+ */
+
+#ifdef PB_DS_CLASS_C_DEC
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::iterator
+PB_DS_CLASS_C_DEC::
+find_by_order(size_type order)
+{
+  if (order < m_size)
+    return iterator(&m_a_values[order]);
+
+  return end();
+}
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::const_iterator
+PB_DS_CLASS_C_DEC::
+find_by_order(size_type order) const
+{ return const_cast<PB_DS_CLASS_C_DEC*>(this)->find_by_order(order); }
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::size_type
+PB_DS_CLASS_C_DEC::
+order_of_key(key_const_reference r_key) const
+{
+  pointer it = m_a_values;
+  pointer e_it = m_a_values + m_size;
+  while (it != e_it)
+    {
+      pointer mid_it = it + ((e_it - it) >> 1);
+      if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
+        it = ++mid_it;
+      else
+        e_it = mid_it;
+    }
+  return (size_type)(it - m_a_values);
+}
+#endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
index 79ca5b30051..6dfc329eb7e 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
@@ -382,6 +382,15 @@ namespace __gnu_pbds
       end() const
       { return m_end_it; }
 
+      inline iterator
+      find_by_order(size_type order);
+
+      inline const_iterator
+      find_by_order(size_type order) const;
+
+      inline size_type
+      order_of_key(key_const_reference r_key) const;
+
       /// Returns a const node_iterator corresponding to the node at the
       /// root of the tree.
       inline node_const_iterator
@@ -529,6 +538,7 @@ namespace __gnu_pbds
 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
+#include <ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 
 #undef PB_DS_CLASS_C_DEC
diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
index e76b56a9454..1b769578fee 100644
--- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
@@ -55,99 +55,21 @@ namespace __gnu_pbds
 #define PB_DS_CLASS_C_DEC \
   tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>
 
-#define PB_DS_BRANCH_POLICY_BASE \
-  detail::branch_policy<Node_CItr, Node_Itr, _Alloc>
-
-  /// Functor updating ranks of entrees.
   template<typename Node_CItr, typename Node_Itr, 
 	   typename Cmp_Fn, typename _Alloc>
-  class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE
+  class __attribute__((__deprecated__)) tree_order_statistics_node_update
   {
-  private:
-    typedef PB_DS_BRANCH_POLICY_BASE 		       	base_type;
-
   public:
-    typedef Cmp_Fn 					cmp_fn;
-    typedef _Alloc 					allocator_type;
-    typedef typename allocator_type::size_type 		size_type;
-    typedef typename base_type::key_type 		key_type;
-    typedef typename base_type::key_const_reference 	key_const_reference;
-
-    typedef size_type 					metadata_type;
-    typedef Node_CItr 	       			node_const_iterator;
-    typedef Node_Itr 					node_iterator;
-    typedef typename node_const_iterator::value_type 	const_iterator;
-    typedef typename node_iterator::value_type 		iterator;
-
-    /// Finds an entry by __order. Returns a const_iterator to the
-    /// entry with the __order order, or a const_iterator to the
-    /// container object's end if order is at least the size of the
-    /// container object.
-    inline const_iterator
-    find_by_order(size_type) const;
-
-    /// Finds an entry by __order. Returns an iterator to the entry
-    /// with the __order order, or an iterator to the container
-    /// object's end if order is at least the size of the container
-    /// object.
-    inline iterator
-    find_by_order(size_type);
-
-    /// Returns the order of a key within a sequence. For exapmle, if
-    /// r_key is the smallest key, this method will return 0; if r_key
-    /// is a key between the smallest and next key, this method will
-    /// return 1; if r_key is a key larger than the largest key, this
-    /// method will return the size of r_c.
-    inline size_type
-    order_of_key(key_const_reference) const;
-
-  private:
-    /// Const reference to the container's value-type.
-    typedef typename base_type::const_reference 	const_reference;
-
-    /// Const pointer to the container's value-type.
-    typedef typename base_type::const_pointer 		const_pointer;
-
-    /// Const metadata reference.
-    typedef typename detail::rebind_traits<_Alloc, metadata_type>::const_reference
-      metadata_const_reference;
-
-    /// Metadata reference.
-    typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
-      metadata_reference;
-
-    /// Returns the node_const_iterator associated with the tree's root node.
-    virtual node_const_iterator
-    node_begin() const = 0;
-
-    /// Returns the node_iterator associated with the tree's root node.
-    virtual node_iterator
-    node_begin() = 0;
-
-    /// Returns the node_const_iterator associated with a just-after leaf node.
-    virtual node_const_iterator
-    node_end() const = 0;
-
-    /// Returns the node_iterator associated with a just-after leaf node.
-    virtual node_iterator
-    node_end() = 0;
-
-    /// Access to the cmp_fn object.
-    virtual cmp_fn& 
-    get_cmp_fn() = 0;
+    typedef null_type metadata_type;
 
-  protected:
-    /// Updates the rank of a node through a node_iterator node_it;
-    /// end_nd_it is the end node iterator.
     inline void
-    operator()(node_iterator, node_const_iterator) const;
+    operator()(Node_CItr, Node_Itr) {}
 
+  protected:
     virtual
-    ~tree_order_statistics_node_update();
+    ~tree_order_statistics_node_update() {}
   };
 
-#include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
-
 #undef PB_DS_CLASS_T_DEC
 #undef PB_DS_CLASS_C_DEC
 #undef PB_DS_BRANCH_POLICY_BASE
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
index cf4b357bff6..7a2f6f5a234 100644
--- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
@@ -45,23 +45,18 @@
 
 #include <cassert>
 #include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
 
 using namespace std;
 using namespace __gnu_pbds;
 
 // A red-black tree table storing ints and their order
-// statistics. Note that since the tree uses
-// tree_order_statistics_node_update as its update policy, then it
-// includes its methods by_order and order_of_key.
+// statistics.
 typedef
 tree<
   int,
   null_type,
   less<int>,
-  rb_tree_tag,
-  // This policy updates nodes' metadata for order statistics.
-  tree_order_statistics_node_update>
+  rb_tree_tag>
 set_t;
 
 int main()
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
index 2fc51ccdf6c..f8fc45a4344 100644
--- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
@@ -42,7 +42,6 @@
 
 #include <cassert>
 #include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
 
 using namespace std;
 using namespace __gnu_pbds;
@@ -51,8 +50,7 @@ using namespace __gnu_pbds;
 // statistics.
 typedef
 tree<int, char, less<int>,
-     splay_tree_tag,
-     tree_order_statistics_node_update>
+     splay_tree_tag>
 tree_map_t;
 
 int main()
-- 
2.27.0

