static_set.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: BSL-1.0
 
#ifndef TETL_SET_STATIC_SET_HPP
#define TETL_SET_STATIC_SET_HPP
 
#include <etl/_algorithm/lexicographical_compare.hpp>
#include <etl/_algorithm/lower_bound.hpp>
#include <etl/_algorithm/rotate.hpp>
#include <etl/_contracts/check.hpp>
#include <etl/_functional/less.hpp>
#include <etl/_iterator/begin.hpp>
#include <etl/_iterator/data.hpp>
#include <etl/_iterator/end.hpp>
#include <etl/_iterator/rbegin.hpp>
#include <etl/_iterator/rend.hpp>
#include <etl/_iterator/reverse_iterator.hpp>
#include <etl/_iterator/size.hpp>
#include <etl/_vector/static_vector.hpp>
 
namespace etl {

template <typename Key, size_t Capacity, typename Compare = less<Key>>
struct static_set {
private:
    // TODO: Currently static_set only supports default constructible
    // comparators. This is because storing the Compare object would take up at
    // least 1 extra byte. Probably even more because of alignment. The fix is
    // to create a conditional storage struct depending on if the Compare
    // template argument can be default constructed. If so: construct it on
    // demand. If not: store it as a member.
    static_assert(is_default_constructible_v<Compare>);
 
    using storage_type = static_vector<Key, Capacity>;
    storage_type _storage{};
 
public:
    using key_type               = typename storage_type::value_type;
    using value_type             = typename storage_type::value_type;
    using size_type              = size_t;
    using difference_type        = ptrdiff_t;
    using key_compare            = Compare;
    using value_compare          = Compare;
    using reference              = value_type&;
    using const_reference        = value_type const&;
    using pointer                = typename storage_type::pointer;
    using const_pointer          = typename storage_type::const_pointer;
    using iterator               = typename storage_type::pointer;
    using const_iterator         = typename storage_type::const_pointer;
    using reverse_iterator       = etl::reverse_iterator<iterator>;
    using const_reverse_iterator = etl::reverse_iterator<const_iterator>;

    constexpr static_set() = default;

    template <typename InputIt>
        requires(detail::InputIterator<InputIt>)
    constexpr static_set(InputIt first, InputIt last)
    {
        if constexpr (detail::RandomAccessIterator<InputIt>) {
            TETL_PRECONDITION(last - first >= 0);
            TETL_PRECONDITION(static_cast<size_type>(last - first) <= max_size());
        }
 
        insert(first, last);
    }

    constexpr static_set(static_set const& other) = default;

    constexpr static_set(static_set&& other) noexcept(noexcept(etl::move(declval<storage_type>()))) = default;

    constexpr auto operator=(static_set const& other) -> static_set& = default;

    constexpr auto operator=(static_set&& other) noexcept(noexcept(etl::move(declval<storage_type>())))
        -> static_set& = default;

    [[nodiscard]] constexpr auto begin() noexcept -> iterator { return _storage.begin(); }

    [[nodiscard]] constexpr auto begin() const noexcept -> const_iterator { return _storage.begin(); }

    [[nodiscard]] constexpr auto cbegin() const noexcept -> const_iterator { return begin(); }

    [[nodiscard]] constexpr auto end() noexcept -> iterator { return _storage.end(); }

    [[nodiscard]] constexpr auto end() const noexcept -> const_iterator { return _storage.end(); }

    [[nodiscard]] constexpr auto cend() const noexcept -> const_iterator { return end(); }

    [[nodiscard]] constexpr auto rbegin() noexcept -> reverse_iterator { return reverse_iterator(end()); }

    [[nodiscard]] constexpr auto rbegin() const noexcept -> const_reverse_iterator
    {
        return const_reverse_iterator(end());
    }

    [[nodiscard]] constexpr auto crbegin() const noexcept -> const_reverse_iterator { return rbegin(); }

    [[nodiscard]] constexpr auto rend() noexcept -> reverse_iterator { return reverse_iterator(begin()); }

    [[nodiscard]] constexpr auto rend() const noexcept -> const_reverse_iterator
    {
        return const_reverse_iterator(begin());
    }

    [[nodiscard]] constexpr auto crend() const noexcept -> const_reverse_iterator { return rend(); }

    [[nodiscard]] constexpr auto empty() const noexcept -> bool { return _storage.empty(); }

    [[nodiscard]] constexpr auto full() const noexcept -> bool { return _storage.full(); }

    [[nodiscard]] constexpr auto size() const noexcept -> size_type { return _storage.size(); }

    [[nodiscard]] constexpr auto max_size() const noexcept -> size_type { return _storage.max_size(); }

    constexpr auto clear() noexcept -> void { _storage.clear(); }

    constexpr auto insert(value_type&& value) -> pair<iterator, bool>
        requires(is_move_constructible_v<value_type>)
    {
        if (!full()) {
            auto cmp = key_compare{};
            auto* p  = etl::lower_bound(_storage.begin(), _storage.end(), value, cmp);
            if (p == _storage.end() || *(p) != value) {
                _storage.push_back(etl::move(value));
                auto* pos = rotate(p, _storage.end() - 1, _storage.end());
                return make_pair(pos, true);
            }
        }
 
        return pair<iterator, bool>(nullptr, false);
    }

    constexpr auto insert(value_type const& value) noexcept(noexcept(insert(etl::move(declval<key_type>()))))
        -> pair<iterator, bool>
        requires(is_copy_constructible_v<value_type>)
    {
        value_type tmp = value;
        return insert(etl::move(tmp));
    }

    template <typename InputIter>
        requires(detail::InputIterator<InputIter>)
    constexpr auto insert(InputIter first, InputIter last) noexcept(noexcept(insert(declval<key_type>()))) -> void
    {
        for (; first != last; ++first) {
            insert(*first);
        }
    }

    template <typename... Args>
        requires(is_copy_constructible_v<key_type>)
    constexpr auto emplace(Args&&... args) noexcept(noexcept(insert(declval<key_type>()))) -> pair<iterator, bool>
    {
        return insert(value_type(etl::forward<Args>(args)...));
    }

    constexpr auto erase(iterator pos) noexcept -> iterator { return _storage.erase(pos); }

    constexpr auto erase(iterator first, iterator last) -> iterator
    {
        auto res = first;
        for (; first != last; ++first) {
            res = erase(first);
        }
        return res;
    }

    constexpr auto erase(key_type const& key) noexcept -> size_type
    {
        if (auto* pos = etl::lower_bound(begin(), end(), key); pos != end()) {
            erase(pos);
            return 1;
        }
        return 0;
    }

    constexpr auto swap(static_set& other) noexcept(is_nothrow_swappable_v<key_type>) -> void
        requires(is_assignable_v<key_type&, key_type &&>)
    {
        etl::swap(_storage, other._storage);
    }

    [[nodiscard]] constexpr auto count(key_type const& key) const noexcept -> size_type
    {
        return contains(key) ? 1 : 0;
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto count(K const& x) const -> size_type
    {
        return contains(x) ? 1 : 0;
    }

    [[nodiscard]] constexpr auto find(key_type const& key) noexcept -> iterator
    {
        return etl::find(begin(), end(), key);
    }

    [[nodiscard]] constexpr auto find(key_type const& key) const noexcept -> const_iterator
    {
        return etl::find(begin(), end(), key);
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto find(K const& x) -> iterator
    {
        return find_if(begin(), end(), [&x](auto const& val) {
            auto comp = key_compare();
            return comp(val, x);
        });
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto find(K const& x) const -> const_iterator
    {
        return find_if(cbegin(), cend(), [&x](auto const& val) {
            auto comp = key_compare();
            return comp(val, x);
        });
    }

    [[nodiscard]] constexpr auto contains(key_type const& key) const noexcept -> bool { return find(key) != end(); }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto contains(K const& x) const -> bool
    {
        return find(x) != end();
    }

    [[nodiscard]] constexpr auto lower_bound(key_type const& key) -> iterator
    {
        return etl::lower_bound(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto lower_bound(key_type const& key) const -> const_iterator
    {
        return etl::lower_bound(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto lower_bound(K const& key) -> iterator
    {
        return etl::lower_bound(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto lower_bound(K const& key) const -> const_iterator
    {
        return etl::lower_bound(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto upper_bound(key_type const& key) -> iterator
    {
        return etl::upper_bound(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto upper_bound(key_type const& key) const -> const_iterator
    {
        return etl::upper_bound(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto upper_bound(K const& key) -> iterator
    {
        return etl::upper_bound(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto upper_bound(K const& key) const -> const_iterator
    {
        return etl::upper_bound(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto equal_range(key_type const& key) -> iterator
    {
        return etl::equal_range(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto equal_range(key_type const& key) const -> const_iterator
    {
        return etl::equal_range(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto equal_range(K const& key) -> iterator
    {
        return etl::equal_range(begin(), end(), key, key_compare{});
    }

    template <typename K>
        requires(detail::is_transparent_v<key_compare>)
    [[nodiscard]] constexpr auto equal_range(K const& key) const -> const_iterator
    {
        return etl::equal_range(begin(), end(), key, key_compare{});
    }

    [[nodiscard]] constexpr auto key_comp() const noexcept -> key_compare { return key_compare(); }

    [[nodiscard]] constexpr auto value_comp() const noexcept -> value_compare { return value_compare(); }
};

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator==(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return lhs.size() == rhs.size() && equal(begin(lhs), end(lhs), begin(rhs));
}

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator!=(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return !(lhs == rhs);
}

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator<(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return lexicographical_compare(begin(lhs), end(lhs), begin(rhs), end(rhs));
}

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator<=(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return !(rhs < lhs);
}

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator>(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return rhs < lhs;
}

template <typename Key, size_t Capacity, typename Comp>
[[nodiscard]] constexpr auto
operator>=(static_set<Key, Capacity, Comp> const& lhs, static_set<Key, Capacity, Comp> const& rhs) -> bool
{
    return !(lhs < rhs);
}

template <typename Key, size_t Capacity, typename Compare>
constexpr auto swap(static_set<Key, Capacity, Compare>& lhs, static_set<Key, Capacity, Compare>& rhs)
    noexcept(noexcept(lhs.swap(rhs))) -> void
{
    lhs.swap(rhs);
}
 
// /// \brief Erases all elements that satisfy the predicate pred from the
// container.
// ///
// /// https://en.cppreference.com/w/cpp/container/set/erase_if
// template <typename Key, size_t Capacity, typename Compare, typename
// Predicate> constexpr auto erase_if(static_set<Key, Capacity, Compare>&
// c, Predicate pred) ->
//     typename static_set<Key, Capacity, Compare>::size_type
// {
//     auto const old_size = c.size();
//     for (auto i = c.begin(), last = c.end(); i != last;)
//     {
//         if (pred(*i)) { i = c.erase(i); }
//         else
//         {
//             ++i;
//         }
//     }
 
// return old_size - c.size();
// }
 
} // namespace etl
 
#endif // TETL_SET_STATIC_SET_HPP