libcruft-util/cruft/util/set/dset.hpp

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * Copyright 2020, Danny Robson <danny@nerdcruft.net>
 */

#pragma once

#include "../view.hpp"

#include <algorithm>
#include <initializer_list>
#include <span>

#include <cstddef>


namespace cruft::set {
    /// A multiset container whose storage is a constant capacity fixed at
    /// compile time.
    ///
    /// TODO: ValueT really should be a trivial type given the types of
    ///     assumptions we're making. eg, not calling destructors after
    ///     lifetimes expire during resize.
    template <
        typename ValueT,
        std::size_t MaxV
    >
    struct dset {
    public:
        using value_type = ValueT;
        using pointer = value_type*;
        using const_pointer = value_type const*;
        using reference = value_type&;
        using const_reference = value_type const&;

        using iterator = pointer;
        using const_iterator = const_pointer;

        using size_type = std::size_t;

        dset () = default;
        dset (std::initializer_list<ValueT> _init)
        {
            std::copy (_init.begin (), _init.end (), m_data.begin ());
            m_size = _init.size ();
        }

        decltype(auto) begin (void) const& { return m_data.data (); }
        decltype(auto) end   (void) const& { return begin () + m_size; }

        void clear (void)
        {
            m_size = 0;
        }

        /// A list of items to add to this set.
        ///
        /// Items must be in sorted order.
        void add (std::span<ValueT const>);

        /// Add a number of copies of a specified item to the set.
        void add (std::size_t count, ValueT const &val)
        {
            if (capacity () - size () < count)
                throw std::bad_alloc ();

            auto pos = std::lower_bound (m_data.begin (), m_data.begin () + m_size, val);
            std::copy_backward (pos, m_data.begin () + m_size, m_data.begin () + m_size + count);
            std::fill_n (pos, count, val);
            m_size += count;
        }

        /// Add the value to the set
        void add (ValueT const &val)
        {
            return add (1, val);
        }

        void insert (ValueT const &val)
        {
            return add (val);
        }

        /// A list of items to remove from this store.
        ///
        /// Items must be in sorted order, and must be a subset of this
        /// container.
        template <typename IteratorT>
        void erase (cruft::view<IteratorT> rhs)
        {
            *this = *this - rhs;
        }

        void erase (ValueT const &val)
        {
            erase (cruft::view (&val, 1));
        }

        /// Tests if the list is a subset of this container.
        ///
        /// The list must be sorted.
        bool contains (std::span<ValueT const> rhs) const
        {
            return std::includes (begin (), end (), rhs.begin (), rhs.end ());
        }

        /// Tests if this store contains at least the items in the
        /// supplied store.
        bool contains (dset const &rhs) const
        {
            return contains (std::span<ValueT const> {rhs.m_data.data (), rhs.m_size});
        }

        std::size_t count (ValueT const &val) const
        {
            auto pos = std::find (begin (), end (), val);

            std::size_t tally = 0;
            for ( ; pos != end () && *pos == val; ++pos)
                ++tally;

            return tally;
        }

        dset operator+ (std::span<ValueT const> rhs) const
        {
            if (remain () < rhs.size ())
                throw std::bad_alloc ();

            dset res;
            auto const pos = std::merge (
                begin (),
                end   (),
                rhs.begin (),
                rhs.end   (),
                res.m_data.begin ()
            );
            res.m_size = std::distance (res.m_data.begin (), pos);
            return res;
        }

        template <typename IteratorT>
        dset operator- (cruft::view<IteratorT> rhs) const
        {
            dset res;
            auto const pos = std::set_difference (
                begin (),
                end   (),
                rhs.begin (),
                rhs.end   (),
                res.m_data.begin ()
            );

            res.m_size = std::distance (res.m_data.begin (), pos);
            return res;
        }

        dset& operator+= (std::span<ValueT const>) &;
        dset& operator-= (std::span<ValueT const>) &;

        dset operator+ (dset const &rhs) const
        {
            return *this + std::span (rhs.m_data.data (), rhs.m_size);
        }

        dset operator- (dset const &rhs) const
        {
            return *this - cruft::view (rhs);
        }


        dset& operator+= (dset const &rhs) &
        {
            // TODO: Optimise me.
            return *this = *this + std::span (rhs.m_data.data (), rhs.m_size);
        }

        dset& operator-= (dset const &rhs) &
        {
            // TODO: Optimise me.
            return *this = *this - rhs;
        }


        dset
        operator& (dset const &rhs) const
        {
            dset res;

            auto const pos = std::set_intersection (
                begin (),
                end   (),
                rhs.begin (),
                rhs.end   (),
                res.m_data.begin ()
            );

            res.m_size = std::distance (res.m_data.begin (), pos);

            return res;
        }

        dset& operator&= (dset const &rhs) &;

        bool operator== (dset const &rhs) const
        {
            return std::equal (begin (), end (), rhs.begin (), rhs.end ());
        }

        bool operator!= (dset const &rhs) const
        {
            return !(*this == rhs);
        }

        bool empty (void) const
        {
            return m_size == 0;
        }

        std::size_t size (void) const { return m_size; }

        std::size_t
        capacity (void) const
        {
            return MaxV;
        }

        std::size_t remain (void) const { return capacity () - size (); }

    private:
        std::size_t m_size = 0;
        std::array<value_type, MaxV> m_data;
    };
}