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
@@ -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 \
@@ -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 \
@@ -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>
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
@@ -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
new file mode 100644
@@ -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
@@ -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
@@ -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
@@ -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()
@@ -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