flex_vector.hpp

Go to the documentation of this file.

//
// 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/rbts/rrbtree.hpp>
#include <immer/detail/rbts/rrbtree_iterator.hpp>
#include <immer/memory_policy.hpp>

namespace immer {

template <typename T,
          typename MP,
          detail::rbts::bits_t B,
          detail::rbts::bits_t BL>
class vector;

template <typename T,
          typename MP,
          detail::rbts::bits_t B,
          detail::rbts::bits_t BL>
class flex_vector_transient;

template <typename T,
          typename MemoryPolicy   = default_memory_policy,
          detail::rbts::bits_t B  = default_bits,
          detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>
class flex_vector
{
    using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>;

    using move_t =
        std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;

public:
    static constexpr auto bits = B;
    static constexpr auto bits_leaf = BL;
    using memory_policy = MemoryPolicy;

    using value_type = T;
    using reference = const T&;
    using size_type = detail::rbts::size_t;
    using difference_type = std::ptrdiff_t;
    using const_reference = const T&;

    using iterator         = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>;
    using const_iterator   = iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;

    using transient_type   = flex_vector_transient<T, MemoryPolicy, B, BL>;

    flex_vector() = default;

    flex_vector(std::initializer_list<T> values)
        : impl_{impl_t::from_initializer_list(values)}
    {}

    template <typename Iter, typename Sent,
              std::enable_if_t
              <detail::compatible_sentinel_v<Iter, Sent>, bool> = true>
    flex_vector(Iter first, Sent last)
        : impl_{impl_t::from_range(first, last)}
    {}

    flex_vector(size_type n, T v = {})
        : impl_{impl_t::from_fill(n, v)}
    {}

    flex_vector(vector<T, MemoryPolicy, B, BL> v)
        : impl_ { v.impl_.size, v.impl_.shift,
                  v.impl_.root->inc(), v.impl_.tail->inc() }
    {}

    iterator begin() const { return {impl_}; }

    iterator end()   const { return {impl_, typename iterator::end_t{}}; }

    reverse_iterator rbegin() const { return reverse_iterator{end()}; }

    reverse_iterator rend()   const { return reverse_iterator{begin()}; }

    size_type size() const { return impl_.size; }

    bool empty() const { return impl_.size == 0; }

    const T& back() const { return impl_.back(); }

    const T& front() const { return impl_.front(); }

    reference operator[] (size_type index) const
    { return impl_.get(index); }

    reference at(size_type index) const
    { return impl_.get_check(index); }

    bool operator==(const flex_vector& other) const
    { return impl_.equals(other.impl_); }
    bool operator!=(const flex_vector& other) const
    { return !(*this == other); }

    flex_vector push_back(value_type value) const&
    { return impl_.push_back(std::move(value)); }

    decltype(auto) push_back(value_type value) &&
    { return push_back_move(move_t{}, std::move(value)); }

    flex_vector push_front(value_type value) const
    { return flex_vector{}.push_back(value) + *this; }

    flex_vector set(size_type index, value_type value) const&
    { return impl_.assoc(index, std::move(value)); }

    decltype(auto) set(size_type index, value_type value) &&
    { return set_move(move_t{}, index, std::move(value)); }

    template <typename FnT>
    flex_vector update(size_type index, FnT&& fn) const&
    { return impl_.update(index, std::forward<FnT>(fn)); }

    template <typename FnT>
    decltype(auto) update(size_type index, FnT&& fn) &&
    { return update_move(move_t{}, index, std::forward<FnT>(fn)); }

    flex_vector take(size_type elems) const&
    { return impl_.take(elems); }

    decltype(auto) take(size_type elems) &&
    { return take_move(move_t{}, elems); }

    flex_vector drop(size_type elems) const&
    { return impl_.drop(elems); }

    decltype(auto) drop(size_type elems) &&
    { return drop_move(move_t{}, elems); }

    friend flex_vector operator+ (const flex_vector& l, const flex_vector& r)
    { return l.impl_.concat(r.impl_); }

    friend decltype(auto) operator+ (flex_vector&& l, const flex_vector& r)
    { return concat_move(move_t{}, std::move(l), r); }

    friend decltype(auto) operator+ (const flex_vector& l, flex_vector&& r)
    { return concat_move(move_t{}, l, std::move(r)); }

    friend decltype(auto) operator+ (flex_vector&& l, flex_vector&& r)
    { return concat_move(move_t{}, std::move(l), std::move(r)); }

    flex_vector insert(size_type pos, T value) const&
    { return take(pos).push_back(std::move(value)) + drop(pos); }
    decltype(auto) insert(size_type pos, T value) &&
    {
        using std::move;
        auto rs = drop(pos);
        return std::move(*this).take(pos).push_back(
            std::move(value)) + std::move(rs);
    }

    flex_vector insert(size_type pos, flex_vector value) const&
    { return take(pos) + std::move(value) + drop(pos); }
    decltype(auto) insert(size_type pos, flex_vector value) &&
    {
        using std::move;
        auto rs = drop(pos);
        return std::move(*this).take(pos) + std::move(value) + std::move(rs);
    }

    flex_vector erase(size_type pos) const&
    { return take(pos) + drop(pos + 1); }
    decltype(auto) erase(size_type pos) &&
    {
        auto rs = drop(pos + 1);
        return std::move(*this).take(pos) + std::move(rs);
    }

    flex_vector erase(size_type pos, size_type lpos) const&
    { return lpos > pos ? take(pos) + drop(lpos) : *this; }
    decltype(auto) erase(size_type pos, size_type lpos) &&
    {
        if (lpos > pos) {
            auto rs = drop(lpos);
            return std::move(*this).take(pos) + std::move(rs);
        } else {
            return std::move(*this);
        }
    }

    transient_type transient() const&
    { return transient_type{ impl_ }; }
    transient_type transient() &&
    { return transient_type{ std::move(impl_) }; }

    // Semi-private
    const impl_t& impl() const { return impl_; }

#if IMMER_DEBUG_PRINT
    void debug_print(std::ostream& out=std::cerr) const
    { impl_.debug_print(out); }
#endif

private:
    friend transient_type;

    flex_vector(impl_t impl)
        : impl_(std::move(impl))
    {
#if IMMER_DEBUG_PRINT
        // force the compiler to generate debug_print, so we can call
        // it from a debugger
        [](volatile auto){}(&flex_vector::debug_print);
#endif
    }

    flex_vector&& push_back_move(std::true_type, value_type value)
    { impl_.push_back_mut({}, std::move(value)); return std::move(*this); }
    flex_vector push_back_move(std::false_type, value_type value)
    { return impl_.push_back(std::move(value)); }

    flex_vector&& set_move(std::true_type, size_type index, value_type value)
    { impl_.assoc_mut({}, index, std::move(value)); return std::move(*this); }
    flex_vector set_move(std::false_type, size_type index, value_type value)
    { return impl_.assoc(index, std::move(value)); }

    template <typename Fn>
    flex_vector&& update_move(std::true_type, size_type index, Fn&& fn)
    { impl_.update_mut({}, index, std::forward<Fn>(fn)); return std::move(*this); }
    template <typename Fn>
    flex_vector update_move(std::false_type, size_type index, Fn&& fn)
    { return impl_.update(index, std::forward<Fn>(fn)); }

    flex_vector&& take_move(std::true_type, size_type elems)
    { impl_.take_mut({}, elems); return std::move(*this); }
    flex_vector take_move(std::false_type, size_type elems)
    { return impl_.take(elems); }

    flex_vector&& drop_move(std::true_type, size_type elems)
    { impl_.drop_mut({}, elems); return std::move(*this); }
    flex_vector drop_move(std::false_type, size_type elems)
    { return impl_.drop(elems); }

    static flex_vector&& concat_move(std::true_type, flex_vector&& l, const flex_vector& r)
    { concat_mut_l(l.impl_, {}, r.impl_); return std::move(l); }
    static flex_vector&& concat_move(std::true_type, const flex_vector& l, flex_vector&& r)
    { concat_mut_r(l.impl_, r.impl_, {}); return std::move(r); }
    static flex_vector&& concat_move(std::true_type, flex_vector&& l, flex_vector&& r)
    { concat_mut_lr_l(l.impl_, {}, r.impl_, {}); return std::move(l); }
    static flex_vector concat_move(std::false_type, const flex_vector& l, const flex_vector& r)
    { return l.impl_.concat(r.impl_); }

    impl_t impl_ = impl_t::empty();
};

} // namespace immer