path: root/immer/detail/arrays/with_capacity.hpp

//
// 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/arrays/no_capacity.hpp>

namespace immer {
namespace detail {
namespace arrays {

template <typename T, typename MemoryPolicy>
struct with_capacity
{
    using no_capacity_t = no_capacity<T, MemoryPolicy>;

    using node_t = node<T, MemoryPolicy>;
    using edit_t = typename MemoryPolicy::transience_t::edit;
    using size_t = std::size_t;

    node_t* ptr;
    size_t size;
    size_t capacity;

    static const with_capacity& empty()
    {
        static const with_capacity empty_{node_t::make_n(1), 0, 1};
        return empty_;
    }

    with_capacity(node_t* p, size_t s, size_t c)
        : ptr{p}
        , size{s}
        , capacity{c}
    {}

    with_capacity(const with_capacity& other)
        : with_capacity{other.ptr, other.size, other.capacity}
    {
        inc();
    }

    with_capacity(const no_capacity_t& other)
        : with_capacity{other.ptr, other.size, other.size}
    {
        inc();
    }

    with_capacity(with_capacity&& other)
        : with_capacity{empty()}
    {
        swap(*this, other);
    }

    with_capacity& operator=(const with_capacity& other)
    {
        auto next = other;
        swap(*this, next);
        return *this;
    }

    with_capacity& operator=(with_capacity&& other)
    {
        swap(*this, other);
        return *this;
    }

    friend void swap(with_capacity& x, with_capacity& y)
    {
        using std::swap;
        swap(x.ptr, y.ptr);
        swap(x.size, y.size);
        swap(x.capacity, y.capacity);
    }

    ~with_capacity() { dec(); }

    void inc()
    {
        using immer::detail::get;
        ptr->refs().inc();
    }

    void dec()
    {
        using immer::detail::get;
        if (ptr->refs().dec())
            node_t::delete_n(ptr, size, capacity);
    }

    const T* data() const { return ptr->data(); }
    T* data() { return ptr->data(); }

    T* data_mut(edit_t e)
    {
        if (!ptr->can_mutate(e)) {
            auto p = node_t::copy_e(e, capacity, ptr, size);
            dec();
            ptr = p;
        }
        return data();
    }

    operator no_capacity_t() const
    {
        if (size == capacity) {
            ptr->refs().inc();
            return {ptr, size};
        } else {
            return {node_t::copy_n(size, ptr, size), size};
        }
    }

    template <typename Iter,
              typename Sent,
              std::enable_if_t<is_forward_iterator_v<Iter> &&
                                   compatible_sentinel_v<Iter, Sent>,
                               bool> = true>
    static with_capacity from_range(Iter first, Sent last)
    {
        auto count = static_cast<size_t>(distance(first, last));
        if (count == 0)
            return empty();
        else
            return {node_t::copy_n(count, first, last), count, count};
    }

    template <typename U>
    static with_capacity from_initializer_list(std::initializer_list<U> values)
    {
        using namespace std;
        return from_range(begin(values), end(values));
    }

    static with_capacity from_fill(size_t n, T v)
    {
        return {node_t::fill_n(n, v), n, n};
    }

    template <typename Fn>
    void for_each_chunk(Fn&& fn) const
    {
        std::forward<Fn>(fn)(data(), data() + size);
    }

    template <typename Fn>
    bool for_each_chunk_p(Fn&& fn) const
    {
        return std::forward<Fn>(fn)(data(), data() + size);
    }

    const T& get(std::size_t index) const { return data()[index]; }

    const T& get_check(std::size_t index) const
    {
        if (index >= size)
            throw std::out_of_range{"out of range"};
        return data()[index];
    }

    bool equals(const with_capacity& other) const
    {
        return ptr == other.ptr ||
               (size == other.size &&
                std::equal(data(), data() + size, other.data()));
    }

    static size_t recommend_up(size_t sz, size_t cap)
    {
        auto max = std::numeric_limits<size_t>::max();
        return sz <= cap ? cap
                         : cap >= max / 2 ? max
                                          /* otherwise */
                                          : std::max(2 * cap, sz);
    }

    static size_t recommend_down(size_t sz, size_t cap)
    {
        return sz == 0 ? 1
                       : sz < cap / 2 ? sz * 2 :
                                      /* otherwise */ cap;
    }

    with_capacity push_back(T value) const
    {
        auto cap = recommend_up(size + 1, capacity);
        auto p   = node_t::copy_n(cap, ptr, size);
        try {
            new (p->data() + size) T{std::move(value)};
            return {p, size + 1, cap};
        } catch (...) {
            node_t::delete_n(p, size, cap);
            throw;
        }
    }

    void push_back_mut(edit_t e, T value)
    {
        if (ptr->can_mutate(e) && capacity > size) {
            new (data() + size) T{std::move(value)};
            ++size;
        } else {
            auto cap = recommend_up(size + 1, capacity);
            auto p   = node_t::copy_e(e, cap, ptr, size);
            try {
                new (p->data() + size) T{std::move(value)};
                *this = {p, size + 1, cap};
            } catch (...) {
                node_t::delete_n(p, size, cap);
                throw;
            }
        }
    }

    with_capacity assoc(std::size_t idx, T value) const
    {
        auto p = node_t::copy_n(capacity, ptr, size);
        try {
            p->data()[idx] = std::move(value);
            return {p, size, capacity};
        } catch (...) {
            node_t::delete_n(p, size, capacity);
            throw;
        }
    }

    void assoc_mut(edit_t e, std::size_t idx, T value)
    {
        if (ptr->can_mutate(e)) {
            data()[idx] = std::move(value);
        } else {
            auto p = node_t::copy_n(capacity, ptr, size);
            try {
                p->data()[idx] = std::move(value);
                *this          = {p, size, capacity};
            } catch (...) {
                node_t::delete_n(p, size, capacity);
                throw;
            }
        }
    }

    template <typename Fn>
    with_capacity update(std::size_t idx, Fn&& op) const
    {
        auto p = node_t::copy_n(capacity, ptr, size);
        try {
            auto& elem = p->data()[idx];
            elem       = std::forward<Fn>(op)(std::move(elem));
            return {p, size, capacity};
        } catch (...) {
            node_t::delete_n(p, size, capacity);
            throw;
        }
    }

    template <typename Fn>
    void update_mut(edit_t e, std::size_t idx, Fn&& op)
    {
        if (ptr->can_mutate(e)) {
            auto& elem = data()[idx];
            elem       = std::forward<Fn>(op)(std::move(elem));
        } else {
            auto p = node_t::copy_e(e, capacity, ptr, size);
            try {
                auto& elem = p->data()[idx];
                elem       = std::forward<Fn>(op)(std::move(elem));
                *this      = {p, size, capacity};
            } catch (...) {
                node_t::delete_n(p, size, capacity);
                throw;
            }
        }
    }

    with_capacity take(std::size_t sz) const
    {
        auto cap = recommend_down(sz, capacity);
        auto p   = node_t::copy_n(cap, ptr, sz);
        return {p, sz, cap};
    }

    void take_mut(edit_t e, std::size_t sz)
    {
        if (ptr->can_mutate(e)) {
            destroy_n(data() + size, size - sz);
            size = sz;
        } else {
            auto cap = recommend_down(sz, capacity);
            auto p   = node_t::copy_e(e, cap, ptr, sz);
            *this    = {p, sz, cap};
        }
    }
};

} // namespace arrays
} // namespace detail
} // namespace immer