about summary refs log tree commit diff
path: root/immer/flex_vector_transient.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'immer/flex_vector_transient.hpp')
-rw-r--r--immer/flex_vector_transient.hpp251
1 files changed, 251 insertions, 0 deletions
diff --git a/immer/flex_vector_transient.hpp b/immer/flex_vector_transient.hpp
new file mode 100644
index 000000000000..fe0a6a534e10
--- /dev/null
+++ b/immer/flex_vector_transient.hpp
@@ -0,0 +1,251 @@
+//
+// 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 MemoryPolicy,
+          detail::rbts::bits_t B,
+          detail::rbts::bits_t BL>
+class flex_vector;
+
+template <typename T,
+          typename MemoryPolicy,
+          detail::rbts::bits_t B,
+          detail::rbts::bits_t BL>
+class vector_transient;
+
+/*!
+ * Mutable version of `immer::flex_vector`.
+ *
+ * @rst
+ *
+ * Refer to :doc:`transients` to learn more about when and how to use
+ * the mutable versions of immutable containers.
+ *
+ * @endrst
+ */
+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_transient : MemoryPolicy::transience_t::owner
+{
+    using impl_t  = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>;
+    using base_t  = typename MemoryPolicy::transience_t::owner;
+    using owner_t = typename MemoryPolicy::transience_t::owner;
+
+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 persistent_type = flex_vector<T, MemoryPolicy, B, BL>;
+
+    /*!
+     * Default constructor.  It creates a flex_vector of `size() == 0`.  It
+     * does not allocate memory and its complexity is @f$ O(1) @f$.
+     */
+    flex_vector_transient() = default;
+
+    /*!
+     * Default constructor.  It creates a flex_vector with the same
+     * contents as `v`.  It does not allocate memory and is
+     * @f$ O(1) @f$.
+     */
+    flex_vector_transient(vector_transient<T, MemoryPolicy, B, BL> v)
+        : base_t{std::move(static_cast<base_t&>(v))}
+        , impl_{v.impl_.size,
+                v.impl_.shift,
+                v.impl_.root->inc(),
+                v.impl_.tail->inc()}
+    {}
+
+    /*!
+     * Returns an iterator pointing at the first element of the
+     * collection. It does not allocate memory and its complexity is
+     * @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD iterator begin() const { return {impl_}; }
+
+    /*!
+     * Returns an iterator pointing just after the last element of the
+     * collection. It does not allocate and its complexity is @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD iterator end() const
+    {
+        return {impl_, typename iterator::end_t{}};
+    }
+
+    /*!
+     * Returns an iterator that traverses the collection backwards,
+     * pointing at the first element of the reversed collection. It
+     * does not allocate memory and its complexity is @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD reverse_iterator rbegin() const
+    {
+        return reverse_iterator{end()};
+    }
+
+    /*!
+     * Returns an iterator that traverses the collection backwards,
+     * pointing after the last element of the reversed collection. It
+     * does not allocate memory and its complexity is @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD reverse_iterator rend() const
+    {
+        return reverse_iterator{begin()};
+    }
+
+    /*!
+     * Returns the number of elements in the container.  It does
+     * not allocate memory and its complexity is @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD size_type size() const { return impl_.size; }
+
+    /*!
+     * Returns `true` if there are no elements in the container.  It
+     * does not allocate memory and its complexity is @f$ O(1) @f$.
+     */
+    IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
+
+    /*!
+     * Returns a `const` reference to the element at position `index`.
+     * It is undefined when @f$ 0 index \geq size() @f$.  It does not
+     * allocate memory and its complexity is *effectively* @f$ O(1)
+     * @f$.
+     */
+    reference operator[](size_type index) const { return impl_.get(index); }
+
+    /*!
+     * Returns a `const` reference to the element at position
+     * `index`. It throws an `std::out_of_range` exception when @f$
+     * index \geq size() @f$.  It does not allocate memory and its
+     * complexity is *effectively* @f$ O(1) @f$.
+     */
+    reference at(size_type index) const { return impl_.get_check(index); }
+
+    /*!
+     * Inserts `value` at the end.  It may allocate memory and its
+     * complexity is *effectively* @f$ O(1) @f$.
+     */
+    void push_back(value_type value)
+    {
+        impl_.push_back_mut(*this, std::move(value));
+    }
+
+    /*!
+     * Sets to the value `value` at position `idx`.
+     * Undefined for `index >= size()`.
+     * It may allocate memory and its complexity is
+     * *effectively* @f$ O(1) @f$.
+     */
+    void set(size_type index, value_type value)
+    {
+        impl_.assoc_mut(*this, index, std::move(value));
+    }
+
+    /*!
+     * Updates the vector to contain the result of the expression
+     * `fn((*this)[idx])` at position `idx`.
+     * Undefined for `0 >= size()`.
+     * It may allocate memory and its complexity is
+     * *effectively* @f$ O(1) @f$.
+     */
+    template <typename FnT>
+    void update(size_type index, FnT&& fn)
+    {
+        impl_.update_mut(*this, index, std::forward<FnT>(fn));
+    }
+
+    /*!
+     * Resizes the vector to only contain the first `min(elems, size())`
+     * elements. It may allocate memory and its complexity is
+     * *effectively* @f$ O(1) @f$.
+     */
+    void take(size_type elems) { impl_.take_mut(*this, elems); }
+
+    /*!
+     * Removes the first the first `min(elems, size())`
+     * elements. It may allocate memory and its complexity is
+     * *effectively* @f$ O(1) @f$.
+     */
+    void drop(size_type elems) { impl_.drop_mut(*this, elems); }
+
+    /*!
+     * Appends the contents of the `r` at the end.  It may allocate
+     * memory and its complexity is:
+     * @f$ O(log(max(size_r, size_l))) @f$
+     */
+    void append(flex_vector_transient& r)
+    {
+        r.owner_t::operator=(owner_t{});
+        concat_mut_l(impl_, *this, r.impl_);
+    }
+    void append(flex_vector_transient&& r)
+    {
+        concat_mut_lr_l(impl_, *this, r.impl_, r);
+    }
+
+    /*!
+     * Prepends the contents of the `l` at the beginning.  It may
+     * allocate memory and its complexity is:
+     * @f$ O(log(max(size_r, size_l))) @f$
+     */
+    void prepend(flex_vector_transient& l)
+    {
+        l.owner_t::operator=(owner_t{});
+        concat_mut_r(l.impl_, impl_, *this);
+    }
+    void prepend(flex_vector_transient&& l)
+    {
+        concat_mut_lr_r(l.impl_, l, impl_, *this);
+    }
+
+    /*!
+     * Returns an @a immutable form of this container, an
+     * `immer::flex_vector`.
+     */
+    IMMER_NODISCARD persistent_type persistent() &
+    {
+        this->owner_t::operator=(owner_t{});
+        return persistent_type{impl_};
+    }
+    IMMER_NODISCARD persistent_type persistent() &&
+    {
+        return persistent_type{std::move(impl_)};
+    }
+
+private:
+    friend persistent_type;
+
+    flex_vector_transient(impl_t impl)
+        : impl_(std::move(impl))
+    {}
+
+    impl_t impl_ = impl_t::empty();
+};
+
+} // namespace immer