On 13/07/20 16:48 +0800, Xi Ruoyao via Libstdc++ wrote:
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.
Random access iterators require constant time though, so I'm not sure
about this one.
(If I cared about the pbds code I'd also say the comparison ops should
use operator<=> for C++20 mode, but I don't care.)
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 <xry...@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
From 5149d3156b0b1ae5d8cf82c54d041bd47451c995 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry...@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>());
Should this be bool not int?
How does this even compile?
+ }
+
+ 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
