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(-)
@@ -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