diff options
Diffstat (limited to 'third_party/immer/immer/detail/hamts/champ_iterator.hpp')
-rw-r--r-- | third_party/immer/immer/detail/hamts/champ_iterator.hpp | 148 |
1 files changed, 0 insertions, 148 deletions
diff --git a/third_party/immer/immer/detail/hamts/champ_iterator.hpp b/third_party/immer/immer/detail/hamts/champ_iterator.hpp deleted file mode 100644 index 72673b41be03..000000000000 --- a/third_party/immer/immer/detail/hamts/champ_iterator.hpp +++ /dev/null @@ -1,148 +0,0 @@ -// -// 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/hamts/champ.hpp> -#include <immer/detail/iterator_facade.hpp> - -namespace immer { -namespace detail { -namespace hamts { - -template <typename T, typename Hash, typename Eq, typename MP, bits_t B> -struct champ_iterator - : iterator_facade<champ_iterator<T, Hash, Eq, MP, B>, - std::forward_iterator_tag, - T, - const T&, - std::ptrdiff_t, - const T*> -{ - using tree_t = champ<T, Hash, Eq, MP, B>; - using node_t = typename tree_t::node_t; - - struct end_t - {}; - - champ_iterator() = default; - - champ_iterator(const tree_t& v) - : depth_{0} - { - if (v.root->datamap()) { - cur_ = v.root->values(); - end_ = v.root->values() + popcount(v.root->datamap()); - } else { - cur_ = end_ = nullptr; - } - path_[0] = &v.root; - ensure_valid_(); - } - - champ_iterator(const tree_t& v, end_t) - : cur_{nullptr} - , end_{nullptr} - , depth_{0} - { - path_[0] = &v.root; - } - - champ_iterator(const champ_iterator& other) - : cur_{other.cur_} - , end_{other.end_} - , depth_{other.depth_} - { - std::copy(other.path_, other.path_ + depth_ + 1, path_); - } - -private: - friend iterator_core_access; - - T* cur_; - T* end_; - count_t depth_; - node_t* const* path_[max_depth<B> + 1]; - - void increment() - { - ++cur_; - ensure_valid_(); - } - - bool step_down() - { - if (depth_ < max_depth<B>) { - auto parent = *path_[depth_]; - if (parent->nodemap()) { - ++depth_; - path_[depth_] = parent->children(); - auto child = *path_[depth_]; - if (depth_ < max_depth<B>) { - if (child->datamap()) { - cur_ = child->values(); - end_ = cur_ + popcount(child->datamap()); - } - } else { - cur_ = child->collisions(); - end_ = cur_ + child->collision_count(); - } - return true; - } - } - return false; - } - - bool step_right() - { - while (depth_ > 0) { - auto parent = *path_[depth_ - 1]; - auto last = parent->children() + popcount(parent->nodemap()); - auto next = path_[depth_] + 1; - if (next < last) { - path_[depth_] = next; - auto child = *path_[depth_]; - if (depth_ < max_depth<B>) { - if (child->datamap()) { - cur_ = child->values(); - end_ = cur_ + popcount(child->datamap()); - } - } else { - cur_ = child->collisions(); - end_ = cur_ + child->collision_count(); - } - return true; - } - --depth_; - } - return false; - } - - void ensure_valid_() - { - while (cur_ == end_) { - while (step_down()) - if (cur_ != end_) - return; - if (!step_right()) { - // end of sequence - assert(depth_ == 0); - cur_ = end_ = nullptr; - return; - } - } - } - - bool equal(const champ_iterator& other) const { return cur_ == other.cur_; } - - const T& dereference() const { return *cur_; } -}; - -} // namespace hamts -} // namespace detail -} // namespace immer |