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