Squashed 'third_party/immer/' content from commit ad3e3556d

git-subtree-dir: third_party/immer
git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e

1 files changed, 98 insertions, 0 deletions

diff --git a/immer/detail/rbts/rrbtree_iterator.hpp b/immer/detail/rbts/rrbtree_iterator.hpp
new file mode 100644
index 000000000000..af967774e7ef
--- /dev/null
+++ b/immer/detail/rbts/rrbtree_iterator.hpp
@@ -0,0 +1,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