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/rrbtree.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 rrbtree_iterator
20 : iterator_facade<rrbtree_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 = rrbtree<T, MP, B, BL>;
28 using region_t = std::tuple<const T*, size_t, size_t>;
29
30 struct end_t {};
31
32 const tree_t& impl() const { return *v_; }
33 size_t index() const { return i_; }
34
35 rrbtree_iterator() = default;
36
37 rrbtree_iterator(const tree_t& v)
38 : v_ { &v }
39 , i_ { 0 }
40 , curr_ { nullptr, ~size_t{}, ~size_t{} }
41 {
42 }
43
44 rrbtree_iterator(const tree_t& v, end_t)
45 : v_ { &v }
46 , i_ { v.size }
47 , curr_ { nullptr, ~size_t{}, ~size_t{} }
48 {}
49
50private:
51 friend iterator_core_access;
52
53 const tree_t* v_;
54 size_t i_;
55 mutable region_t curr_;
56
57 void increment()
58 {
59 using std::get;
60 assert(i_ < v_->size);
61 ++i_;
62 }
63
64 void decrement()
65 {
66 using std::get;
67 assert(i_ > 0);
68 --i_;
69 }
70
71 void advance(std::ptrdiff_t n)
72 {
73 using std::get;
74 assert(n <= 0 || i_ + static_cast<size_t>(n) <= v_->size);
75 assert(n >= 0 || static_cast<size_t>(-n) <= i_);
76 i_ += n;
77 }
78
79 bool equal(const rrbtree_iterator& other) const
80 {
81 return i_ == other.i_;
82 }
83
84 std::ptrdiff_t distance_to(const rrbtree_iterator& other) const
85 {
86 return other.i_ > i_
87 ? static_cast<std::ptrdiff_t>(other.i_ - i_)
88 : - static_cast<std::ptrdiff_t>(i_ - other.i_);
89 }
90
91 const T& dereference() const
92 {
93 using std::get;
94 if (i_ < get<1>(curr_) || i_ >= get<2>(curr_))
95 curr_ = v_->region_for(i_);
96 return get<0>(curr_)[i_ - get<1>(curr_)];
97 }
98};
99
100} // namespace rbts
101} // namespace detail
102} // namespace immer
103