* Re: [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
@ 2020-07-13 8:39 ` Xi Ruoyao
2020-07-13 8:40 ` [PATCH 1/5] " Xi Ruoyao
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:39 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy, xry111
[-- Attachment #1: Type: text/plain, Size: 469 bytes --]
> The first patch removes two redundant statements which are confusing. It
> should
> be applied anyway, disregarding other patches.
The patch is attached, to prevent my mail client from destroying it :(.
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
(insert_leaf_new, insert_imp_empty): remove redundant statements.
--
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0001-libstdc-remove-two-redundant-statements-in-pb_ds-bin.patch --]
[-- Type: text/x-patch, Size: 1498 bytes --]
From 4eea45261ebf974ddf02f6154166c5cb6aa180da 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:10:52 +0800
Subject: [PATCH 1/5] libstdc++: remove two redundant statements in pb_ds
binary tree
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
(insert_leaf_new, insert_imp_empty): remove redundant statements.
---
.../ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp | 2 --
1 file changed, 2 deletions(-)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
index 3942da05600..bdc10379af6 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
@@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
}
p_new_nd->m_p_parent = p_nd;
- p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
PB_DS_ASSERT_NODE_CONSISTENT(p_nd)
update_to_top(p_new_nd, (node_update* )this);
@@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value)
m_p_head->m_p_parent = p_new_node;
p_new_node->m_p_parent = m_p_head;
- p_new_node->m_p_left = p_new_node->m_p_right = 0;
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
update_to_top(m_p_head->m_p_parent, (node_update*)this);
--
2.27.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 1/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
2020-07-13 8:39 ` Xi Ruoyao
@ 2020-07-13 8:40 ` Xi Ruoyao
2020-07-13 8:42 ` [PATCH 2/5] " Xi Ruoyao
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:40 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy, xry111
[-- Attachment #1: Type: text/plain, Size: 540 bytes --]
> The first patch removes two redundant statements which are confusing. It
> should
> be applied anyway, disregarding other patches.
The patch is attached, to prevent my mail client from destroying it :(.
Please ignore a previous duplication of this mail with wrong title :(.
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
(insert_leaf_new, insert_imp_empty): remove redundant statements.
--
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0001-libstdc-remove-two-redundant-statements-in-pb_ds-bin.patch --]
[-- Type: text/x-patch, Size: 1498 bytes --]
From 4eea45261ebf974ddf02f6154166c5cb6aa180da 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:10:52 +0800
Subject: [PATCH 1/5] libstdc++: remove two redundant statements in pb_ds
binary tree
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
(insert_leaf_new, insert_imp_empty): remove redundant statements.
---
.../ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp | 2 --
1 file changed, 2 deletions(-)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
index 3942da05600..bdc10379af6 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
@@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
}
p_new_nd->m_p_parent = p_nd;
- p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
PB_DS_ASSERT_NODE_CONSISTENT(p_nd)
update_to_top(p_new_nd, (node_update* )this);
@@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value)
m_p_head->m_p_parent = p_new_node;
p_new_node->m_p_parent = m_p_head;
- p_new_node->m_p_left = p_new_node->m_p_right = 0;
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
update_to_top(m_p_head->m_p_parent, (node_update*)this);
--
2.27.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 2/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
2020-07-13 8:39 ` Xi Ruoyao
2020-07-13 8:40 ` [PATCH 1/5] " Xi Ruoyao
@ 2020-07-13 8:42 ` Xi Ruoyao
2020-07-13 8:45 ` [PATCH 3/5] " Xi Ruoyao
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:42 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy
[-- Attachment #1: Type: text/plain, Size: 851 bytes --]
> 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 <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0002-libstdc-maintain-subtree-size-in-pb_ds-binary-search.patch --]
[-- Type: text/x-patch, Size: 6211 bytes --]
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
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 3/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
` (2 preceding siblings ...)
2020-07-13 8:42 ` [PATCH 2/5] " Xi Ruoyao
@ 2020-07-13 8:45 ` Xi Ruoyao
2020-07-13 8:48 ` [PATCH 4/5] " Xi Ruoyao
2020-07-13 8:51 ` [PATCH 5/5] " Xi Ruoyao
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:45 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy, xry111
[-- Attachment #1: Type: text/plain, Size: 480 bytes --]
> The second and third patch together resolve PR 81806.
The attached patch modifies split_finish to use the subtree size we maintained
in the previous patch, resolving libstdc++/81806.
libstdc++-v3/ChangeLog:
PR libstdc++/81806
* include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
(split_finish): Use maintained size, instead of calling
std::distance.
--
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0003-libstdc-use-maintained-size-when-split-pb_ds-binary-.patch --]
[-- Type: text/x-patch, Size: 1351 bytes --]
From 4434da1b2b45797204f4fd978dcc4fbba4b17c6e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Fri, 10 Jul 2020 21:38:09 +0800
Subject: [PATCH 3/5] libstdc++: use maintained size when split pb_ds binary
search trees
libstdc++-v3/ChangeLog:
PR libstdc++/81806
* include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
(split_finish): Use maintained size, instead of calling
std::distance.
---
.../ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
index d08288f186d..fb924b4434b 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
@@ -133,7 +133,9 @@ PB_DS_CLASS_C_DEC::
split_finish(PB_DS_CLASS_C_DEC& other)
{
other.initialize_min_max();
- other.m_size = std::distance(other.begin(), other.end());
+ other.m_size = 0;
+ if (other.m_p_head->m_p_parent != 0)
+ other.m_size = other.m_p_head->m_p_parent->m_subtree_size;
m_size -= other.m_size;
initialize_min_max();
PB_DS_ASSERT_VALID((*this))
--
2.27.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 4/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
` (3 preceding siblings ...)
2020-07-13 8:45 ` [PATCH 3/5] " Xi Ruoyao
@ 2020-07-13 8:48 ` Xi Ruoyao
2020-07-13 8:51 ` [PATCH 5/5] " Xi Ruoyao
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:48 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy, xry111
[-- Attachment #1: Type: text/plain, Size: 1537 bytes --]
> The fourth patch converts the point_iterator of rb_tree and splay_tree based
> maps to random access iterator. With the subtree size kept we can implement
> the
> operators required by random access iterator in logarithm time.
The patch is attached.
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
(bin_search_tree_const_it_::size_type): New typedef.
(bin_search_tree_it_::difference_type): Likewise.
(bin_search_tree_const_it_::inc): New overloads.
(bin_search_tree_const_it_::dec): Likewise.
(bin_search_tree_const_it_::order): New member function.
(bin_search_tree_const_it_::operator+=): New operator.
(bin_search_tree_const_it_::operator-=): Likewise.
(bin_search_tree_const_it_::operator+): Likewise.
(bin_search_tree_const_it_::operator-): Likewise.
(bin_search_tree_const_it_::operator<): Likewise.
(bin_search_tree_const_it_::operator<=): Likewise.
(bin_search_tree_const_it_::operator>): Likewise.
(bin_search_tree_const_it_::operator>=): Likewise.
(bin_search_tree_const_it_::operator[]): Likewise.
(bin_search_tree_it_::operator+=): Likewise.
(bin_search_tree_it_::operator-=): Likewise.
(bin_search_tree_it_::operator+): Likewise.
(bin_search_tree_it_::operator-): Likewise.
(bin_search_tree_it_::operator[]): Likewise.
(bin_search_tree_const_it_::iterator_category):
Change to std::random_access_iterator_tag.
--
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0004-libstdc-make-pb_ds-binary-search-tree-point-iterator.patch --]
[-- Type: text/x-patch, Size: 10475 bytes --]
From 5149d3156b0b1ae5d8cf82c54d041bd47451c995 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Sat, 11 Jul 2020 23:32:36 +0800
Subject: [PATCH 4/5] libstdc++: make pb_ds binary search tree point iterator
random accessible
libstdc++-v3/ChangeLog:
* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
(bin_search_tree_const_it_::size_type): New typedef.
(bin_search_tree_it_::difference_type): Likewise.
(bin_search_tree_const_it_::inc): New overloads.
(bin_search_tree_const_it_::dec): Likewise.
(bin_search_tree_const_it_::order): New member function.
(bin_search_tree_const_it_::operator+=): New operator.
(bin_search_tree_const_it_::operator-=): Likewise.
(bin_search_tree_const_it_::operator+): Likewise.
(bin_search_tree_const_it_::operator-): Likewise.
(bin_search_tree_const_it_::operator<): Likewise.
(bin_search_tree_const_it_::operator<=): Likewise.
(bin_search_tree_const_it_::operator>): Likewise.
(bin_search_tree_const_it_::operator>=): Likewise.
(bin_search_tree_const_it_::operator[]): Likewise.
(bin_search_tree_it_::operator+=): Likewise.
(bin_search_tree_it_::operator-=): Likewise.
(bin_search_tree_it_::operator+): Likewise.
(bin_search_tree_it_::operator-): Likewise.
(bin_search_tree_it_::operator[]): Likewise.
(bin_search_tree_const_it_::iterator_category):
Change to std::random_access_iterator_tag.
---
.../bin_search_tree_/point_iterators.hpp | 277 +++++++++++++++++-
1 file changed, 276 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
index eb2f4fdbfd2..f7efe79290a 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
@@ -105,8 +105,9 @@ namespace __gnu_pbds
class bin_search_tree_const_it_
{
public:
- typedef std::bidirectional_iterator_tag iterator_category;
+ typedef std::random_access_iterator_tag iterator_category;
typedef typename _Alloc::difference_type difference_type;
+ typedef typename _Alloc::size_type size_type;
typedef Value_Type value_type;
typedef Pointer pointer;
typedef Const_Pointer const_pointer;
@@ -185,6 +186,28 @@ namespace __gnu_pbds
return ret_it;
}
+ inline PB_DS_TREE_CONST_IT_C_DEC&
+ operator+=(difference_type dif)
+ {
+ inc(dif, integral_constant<int,Is_Forward_Iterator>());
+ return *this;
+ }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC
+ operator+(difference_type dif) const
+ {
+ PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+ ret_it += dif;
+ return ret_it;
+ }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC&
+ operator-=(difference_type dif)
+ {
+ dec(dif, integral_constant<int,Is_Forward_Iterator>());
+ return *this;
+ }
+
inline PB_DS_TREE_CONST_IT_C_DEC&
operator--()
{
@@ -200,6 +223,54 @@ namespace __gnu_pbds
return ret_it;
}
+ inline PB_DS_TREE_CONST_IT_C_DEC
+ operator-(difference_type dif) const
+ {
+ PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+ ret_it -= dif;
+ return ret_it;
+ }
+
+ inline const_reference
+ operator[](difference_type dif) const
+ {
+ return *operator+(dif);
+ }
+
+ inline bool
+ operator<(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+ {
+ return order() < rhs.order();
+ }
+
+ inline bool
+ operator<=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+ {
+ return order() <= rhs.order();
+ }
+
+ inline bool
+ operator>(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+ {
+ return order() >= rhs.order();
+ }
+
+ inline bool
+ operator>=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+ {
+ return order() >= rhs.order();
+ }
+
+ inline difference_type
+ operator-(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+ {
+ size_type r = order(), l = rhs.order();
+ if (r >= l)
+ return static_cast<difference_type>(r - l);
+ else
+ return -static_cast<difference_type>(l - r);
+ }
+
protected:
inline void
inc(false_type)
@@ -266,6 +337,171 @@ namespace __gnu_pbds
m_p_nd = p_y;
}
+ Node_Pointer find_by_order_in_subtree(size_type order)
+ {
+ Node_Pointer p_nd = m_p_nd;
+
+ while (p_nd != 0)
+ {
+ Node_Pointer p_left = p_nd->m_p_left;
+ const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+ if (order == o)
+ break;
+ else if (order < o)
+ p_nd = p_left;
+ else
+ {
+ order -= o + 1;
+ p_nd = p_nd->m_p_right;
+ }
+ }
+
+ return p_nd;
+ }
+
+ inline void
+ inc(difference_type dif, false_type)
+ { dec(dif, true_type()); }
+
+ void
+ inc(difference_type dif, true_type)
+ {
+ if (dif < 0)
+ {
+ dec(-dif, true_type());
+ return;
+ }
+
+ size_type d = static_cast<size_type>(dif);
+
+ if (d != 0 &&
+ m_p_nd->special() &&
+ m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ {
+ --d;
+ m_p_nd = m_p_nd->m_p_left;
+ }
+
+ while (d != 0)
+ {
+ Node_Pointer p_right = m_p_nd->m_p_right;
+ const size_type o = (p_right == 0 ? 0 : p_right->m_subtree_size);
+
+ if (o >= d)
+ {
+ m_p_nd = m_p_nd->m_p_right;
+ m_p_nd = find_by_order_in_subtree(d - 1);
+ break;
+ }
+
+ d -= o + 1;
+
+ while (m_p_nd == m_p_nd->m_p_parent->m_p_right)
+ m_p_nd = m_p_nd->m_p_parent;
+
+ m_p_nd = m_p_nd->m_p_parent;
+ }
+ }
+
+ inline void
+ dec(difference_type dif, false_type)
+ { inc(dif, true_type()); }
+
+ void
+ dec(difference_type dif, true_type)
+ {
+ if (dif < 0)
+ {
+ inc(-dif, true_type());
+ return;
+ }
+
+ size_type d = static_cast<size_type>(dif);
+
+ if (d != 0 &&
+ m_p_nd->special() &&
+ m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ {
+ --d;
+ m_p_nd = m_p_nd->m_p_right;
+ }
+
+ while (d != 0)
+ {
+ Node_Pointer p_left = m_p_nd->m_p_left;
+ const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+ if (o >= d)
+ {
+ m_p_nd = m_p_nd->m_p_left;
+ m_p_nd = find_by_order_in_subtree(o - d);
+ break;
+ }
+
+ d -= o + 1;
+
+ while (m_p_nd == m_p_nd->m_p_parent->m_p_left)
+ m_p_nd = m_p_nd->m_p_parent;
+
+ m_p_nd = m_p_nd->m_p_parent;
+ }
+ }
+
+ inline size_type
+ order() const
+ {
+ return order(integral_constant<int, Is_Forward_Iterator>());
+ }
+
+ size_type
+ order(true_type) const
+ {
+ if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ return m_p_nd->m_p_parent->m_subtree_size;
+
+ Node_Pointer p_left = m_p_nd->m_p_left;
+ size_type ret = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+ for (Node_Pointer p_nd = m_p_nd;
+ p_nd->m_p_parent->m_p_parent != p_nd;
+ p_nd = p_nd->m_p_parent)
+ {
+ if (p_nd->m_p_parent->m_p_right == p_nd)
+ {
+ ret += 1;
+ if (p_nd->m_p_parent->m_p_left != 0)
+ ret += p_nd->m_p_parent->m_p_left->m_subtree_size;
+ }
+ }
+
+ return ret;
+ }
+
+ size_type
+ order(false_type) const
+ {
+ if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ return m_p_nd->m_p_parent->m_subtree_size;
+
+ Node_Pointer p_right = m_p_nd->m_p_right;
+ size_type ret = (p_right == 0 ? 0 : p_right->m_subtree_size);
+
+ for (Node_Pointer p_nd = m_p_nd;
+ p_nd->m_p_parent->m_p_parent != p_nd;
+ p_nd = p_nd->m_p_parent)
+ {
+ if (p_nd->m_p_parent->m_p_left == p_nd)
+ {
+ ret += 1;
+ if (p_nd->m_p_parent->m_p_right != 0)
+ ret += p_nd->m_p_parent->m_p_right->m_subtree_size;
+ }
+ }
+
+ return ret;
+ }
+
public:
Node_Pointer m_p_nd;
};
@@ -282,6 +518,8 @@ namespace __gnu_pbds
class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
{
public:
+ typedef typename _Alloc::difference_type difference_type;
+
inline
bin_search_tree_it_(const Node_Pointer p_nd = 0)
: PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
@@ -337,6 +575,21 @@ namespace __gnu_pbds
return ret_it;
}
+ inline PB_DS_TREE_IT_C_DEC&
+ operator+=(difference_type dif)
+ {
+ PB_DS_TREE_CONST_IT_C_DEC:: operator+=(dif);
+ return *this;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC
+ operator+(difference_type dif) const
+ {
+ PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+ ret_it += dif;
+ return ret_it;
+ }
+
inline PB_DS_TREE_IT_C_DEC&
operator--()
{
@@ -352,8 +605,30 @@ namespace __gnu_pbds
return ret_it;
}
+ inline PB_DS_TREE_IT_C_DEC&
+ operator-=(difference_type dif)
+ {
+ PB_DS_TREE_CONST_IT_C_DEC:: operator-=(dif);
+ return *this;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC
+ operator-(difference_type dif) const
+ {
+ PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+ ret_it -= dif;
+ return ret_it;
+ }
+
+ inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
+ operator[](difference_type dif) const
+ {
+ return *operator+(dif);
+ }
+
protected:
typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
+
};
#undef PB_DS_TREE_CONST_IT_C_DEC
--
2.27.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 5/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)
2020-07-13 8:37 [PATCH 0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) Xi Ruoyao
` (4 preceding siblings ...)
2020-07-13 8:48 ` [PATCH 4/5] " Xi Ruoyao
@ 2020-07-13 8:51 ` Xi Ruoyao
5 siblings, 0 replies; 7+ messages in thread
From: Xi Ruoyao @ 2020-07-13 8:51 UTC (permalink / raw)
To: gcc-patches, libstdc++; +Cc: Oleksandr Kulkov, Raihat Zaman Neloy, xry111
[-- Attachment #1: Type: text/plain, Size: 1763 bytes --]
> 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.
--
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
[-- Attachment #2: 0005-libstdc-implement-order-statistics-function-in-pb_ds.patch --]
[-- Type: text/x-patch, Size: 19628 bytes --]
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
^ permalink raw reply [flat|nested] 7+ messages in thread