From patchwork Mon Jul 13 08:51:09 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327780 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=H+wrggCk; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4B4y7158yFz9sDX for ; Mon, 13 Jul 2020 18:51:24 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 20863385041F; Mon, 13 Jul 2020 08:51:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 20863385041F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594630282; bh=X4KhYyDFKIUKvNtnlgwJL5bFnlJvFT2gaIZjp44u2cY=; h=Subject:To:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=H+wrggCkxE21CWLBVc2qWqVTRmWo/EiXrr0E0xGCoD5cI5qrQZxSB033bpafzhukf bLLiyjYvtUqdiFLSPnUHNM2xKstTlbKvUJ5+ULTcC54KIe+TblUlMnQrrJ7nnALsbu 2kOOZPfkCWKV7sjLJnhTSvjly6/S9zZTUGmkLY+M= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mengyan1223.wang (mengyan1223.wang [89.208.246.23]) by sourceware.org (Postfix) with ESMTPS id CDC103857031; Mon, 13 Jul 2020 08:51:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org CDC103857031 Received: from xry111-X57S1 (unknown [113.140.11.5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature ECDSA (P-384) server-digest SHA384) (Client did not present a certificate) (Authenticated sender: xry111@mengyan1223.wang) by mengyan1223.wang (Postfix) with ESMTPSA id 3BEB2661B7; Mon, 13 Jul 2020 04:51:15 -0400 (EDT) Message-ID: Subject: [PATCH 5/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) To: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Date: Mon, 13 Jul 2020 16:51:09 +0800 In-Reply-To: <67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang> References: <67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang> User-Agent: Evolution 3.36.3 MIME-Version: 1.0 X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_SHORT, RCVD_IN_ABUSEAT, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Xi Ruoyao via Gcc-patches From: Xi Ruoyao Reply-To: Xi Ruoyao Cc: Raihat Zaman Neloy , Oleksandr Kulkov , xry111@mengyan1223.wang Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" > The fifth patch moves the functionality of tree_order_statistics_node_update > into the implementation of binary search trees (they are now order-statistics > trees), makes tree_order_statistics_node_update no-op, and deprecates it. The patch is attached. 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. From c0ee85f492872ba164ad3c1c9636aace1de02e96 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= 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 #include #include +#include #include #include #include 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(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 +// . + +// 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(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 #include #include +#include #include #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 -#define PB_DS_BRANCH_POLICY_BASE \ - detail::branch_policy - - /// Functor updating ranks of entrees. template - 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 - #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 #include -#include 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, - 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 #include -#include using namespace std; using namespace __gnu_pbds; @@ -51,8 +50,7 @@ using namespace __gnu_pbds; // statistics. typedef tree, - splay_tree_tag, - tree_order_statistics_node_update> + splay_tree_tag> tree_map_t; int main() -- 2.27.0