bbst/iterator.hpp

View this file on GitHub
Last update: 2024-11-09 00:49:07+00:00
Include: #include "bbst/iterator.hpp"

Depends on

prelude.hpp

Required by

bbst/implicit_treap.hpp

Verified with

Code

#pragma once
#include "prelude.hpp"

template <class Self, class Node, class T, bool Const>
class bidirectional_iterator_impl {
 public:
  using difference_type = ptrdiff_t;
  using value_type = T;
  using pointer = conditional_t<Const, const T *, T *>;
  using reference = conditional_t<Const, const T &, T &>;
  using iterator_category = bidirectional_iterator_tag;

 private:
  using self_type = Self;
  using node_pointer = conditional_t<Const, const Node *, Node *>;

 public:
  bidirectional_iterator_impl(Node *p) : ptr(p) { }
  bidirectional_iterator_impl(const Node *p = nullptr) : ptr(p) {} // ill-formed if !Const
  // reference operator*() const { return ptr->*Val(); }
  // pointer operator->() const { return &**this; }
  bool operator==(self_type rhs) const { return ptr == rhs.ptr; }
  bool operator!=(self_type rhs) const { return ptr != rhs.ptr; }
  self_type &operator++() {
    if (ptr->r) {
      ptr = ptr->r;
      while (ptr->l) ptr = ptr->l;
    } else {
      while (ptr->par->r == ptr) ptr = ptr->par;
      ptr = ptr->par;
    }
    return *(self_type *)this;
  }
  self_type operator++(int) {
    self_type res(ptr);
    ++*this;
    return res;
  }
  self_type &operator--() {
    if (ptr->l) {
      ptr = ptr->l;
      while (ptr->r) ptr = ptr->r;
    } else {
      while (ptr->par->l == ptr) ptr = ptr->par;
      ptr = ptr->par;
    }
    return *(self_type *)this;
  }
  self_type operator--(int) {
    self_type res(ptr);
    --*this;
    return res;
  }

  node_pointer ptr;
};

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "bbst/iterator.hpp"

template <class Self, class Node, class T, bool Const>
class bidirectional_iterator_impl {
 public:
  using difference_type = ptrdiff_t;
  using value_type = T;
  using pointer = conditional_t<Const, const T *, T *>;
  using reference = conditional_t<Const, const T &, T &>;
  using iterator_category = bidirectional_iterator_tag;

 private:
  using self_type = Self;
  using node_pointer = conditional_t<Const, const Node *, Node *>;

 public:
  bidirectional_iterator_impl(Node *p) : ptr(p) { }
  bidirectional_iterator_impl(const Node *p = nullptr) : ptr(p) {} // ill-formed if !Const
  // reference operator*() const { return ptr->*Val(); }
  // pointer operator->() const { return &**this; }
  bool operator==(self_type rhs) const { return ptr == rhs.ptr; }
  bool operator!=(self_type rhs) const { return ptr != rhs.ptr; }
  self_type &operator++() {
    if (ptr->r) {
      ptr = ptr->r;
      while (ptr->l) ptr = ptr->l;
    } else {
      while (ptr->par->r == ptr) ptr = ptr->par;
      ptr = ptr->par;
    }
    return *(self_type *)this;
  }
  self_type operator++(int) {
    self_type res(ptr);
    ++*this;
    return res;
  }
  self_type &operator--() {
    if (ptr->l) {
      ptr = ptr->l;
      while (ptr->r) ptr = ptr->r;
    } else {
      while (ptr->par->l == ptr) ptr = ptr->par;
      ptr = ptr->par;
    }
    return *(self_type *)this;
  }
  self_type operator--(int) {
    self_type res(ptr);
    --*this;
    return res;
  }

  node_pointer ptr;
};