1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/detail/rbts/rbtree.hpp>
12#include <immer/detail/iterator_facade.hpp>
13
14namespace immer {
15namespace detail {
16namespace rbts {
17
18template <typename T, typename MP, bits_t B, bits_t BL>
19struct rbtree_iterator
20 : iterator_facade<rbtree_iterator<T, MP, B, BL>,
21 std::random_access_iterator_tag,
22 T,
23 const T&,
24 std::ptrdiff_t,
25 const T*>
26{
27 using tree_t = rbtree<T, MP, B, BL>;
28
29 struct end_t {};
30
31 rbtree_iterator() = default;
32
33 rbtree_iterator(const tree_t& v)
34 : v_ { &v }
35 , i_ { 0 }
36 , base_ { ~size_t{} }
37 , curr_ { nullptr }
38 {}
39
40 rbtree_iterator(const tree_t& v, end_t)
41 : v_ { &v }
42 , i_ { v.size }
43 , base_ { ~size_t{} }
44 , curr_ { nullptr }
45 {}
46
47 const tree_t& impl() const { return *v_; }
48 size_t index() const { return i_; }
49
50private:
51 friend iterator_core_access;
52
53 const tree_t* v_;
54 size_t i_;
55 mutable size_t base_;
56 mutable const T* curr_ = nullptr;
57
58 void increment()
59 {
60 assert(i_ < v_->size);
61 ++i_;
62 }
63
64 void decrement()
65 {
66 assert(i_ > 0);
67 --i_;
68 }
69
70 void advance(std::ptrdiff_t n)
71 {
72 assert(n <= 0 || i_ + static_cast<size_t>(n) <= v_->size);
73 assert(n >= 0 || static_cast<size_t>(-n) <= i_);
74 i_ += n;
75 }
76
77 bool equal(const rbtree_iterator& other) const
78 {
79 return i_ == other.i_;
80 }
81
82 std::ptrdiff_t distance_to(const rbtree_iterator& other) const
83 {
84 return other.i_ > i_
85 ? static_cast<std::ptrdiff_t>(other.i_ - i_)
86 : - static_cast<std::ptrdiff_t>(i_ - other.i_);
87 }
88
89 const T& dereference() const
90 {
91 auto base = i_ & ~mask<BL>;
92 if (base_ != base) {
93 base_ = base;
94 curr_ = v_->array_for(i_);
95 }
96 return curr_[i_ & mask<BL>];
97 }
98};
99
100} // namespace rbts
101} // namespace detail
102} // namespace immer
103