Program Listing for File sorted.hpp

↰ Return to documentation for file (include/util/sorted.hpp)

// SPDX-FileCopyrightText: 2021 Christian Göhring <mostsig@gmail.com>
// SPDX-License-Identifier: MIT

#ifndef THAT_THIS_UTIL_SORTED_HEADER_IS_ALREADY_INCLUDED
#define THAT_THIS_UTIL_SORTED_HEADER_IS_ALREADY_INCLUDED

#include <algorithm>
#include <array>
#include <forward_list>
#include <functional>
#include <list>
#include <memory>
#include <vector>

#ifdef UTIL_ASSERT
#include <util/assert.hpp>
#endif

namespace util {

template <class Container, class Compare = std::less<typename Container::value_type>>
class sorted {
public:
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;
    using const_reference = const value_type&;
    using const_pointer = const value_type*;
    using const_iterator = typename Container::const_iterator;

    using is_forward_list =
        std::is_same<Container, std::forward_list<value_type, typename Container::allocator_type>>;
    using is_list =
        std::is_same<Container, std::list<value_type, typename Container::allocator_type>>;

    sorted() noexcept = default;
    ~sorted() = default;
    sorted(const sorted&) = default;
    sorted(sorted&&) noexcept = default;
    auto operator=(const sorted&) -> sorted& = default;
    auto operator=(sorted&&) noexcept -> sorted& = default;

    template <class OtherContainer>
    explicit sorted(const OtherContainer& container);
    template <class InputIt>
    sorted(InputIt begin, InputIt end);
    sorted(std::initializer_list<value_type> ilist);

    // element access

    auto at(size_type pos) const -> const_reference;
    auto operator[](size_type pos) const -> const_reference;
    auto front() const -> const_reference;
    auto back() const -> const_reference;
    auto data() const noexcept -> const_pointer;

    // iterators

    auto begin() const noexcept -> const_iterator;
    auto cbegin() const noexcept -> const_iterator;
    auto end() const noexcept -> const_iterator;
    auto cend() const noexcept -> const_iterator;

    // capacity and size

    auto empty() const noexcept -> bool;
    auto size() const noexcept -> size_type;
    auto max_size() const noexcept -> size_type;
    auto capacity() const noexcept -> size_type;
    void reserve(size_type new_cap);
    void shrink_to_fit();
    void resize(size_type count);
    void resize(size_type count, const_reference value);

    // modifiers

    void clear() noexcept;
    auto insert(const_reference value) -> const_iterator;
    auto insert(value_type&& value) -> const_iterator;
    auto insert(std::initializer_list<value_type> ilist) -> const_iterator;
    template <class InputIt>
    void insert(InputIt first, InputIt last);
    template <class... Args>
    auto emplace(Args&&... args) -> const_iterator;
    auto erase(const_iterator pos) -> const_iterator;
    auto erase(const_iterator first, const_iterator last) -> const_iterator;
    void pop_back();
    void pop_front();
    void swap(sorted& other);

private:
    Compare comp = Compare();
    Container container;
};

template <class T, class Allocator = std::allocator<T>>
using sorted_forward_list = sorted<std::forward_list<T, Allocator>>;
template <class T, class Allocator = std::allocator<T>>
using sorted_list = sorted<std::list<T, Allocator>>;
template <class T, class Allocator = std::allocator<T>>
using sorted_vector = sorted<std::vector<T, Allocator>>;

template <class Container, class Compare>
template <class OtherContainer>
sorted<Container, Compare>::sorted(const OtherContainer& container)
    : sorted(container.begin(), container.end()) {}

template <class Container, class Compare>
template <class InputIt>
sorted<Container, Compare>::sorted(InputIt begin, InputIt end) {
    if constexpr (is_forward_list::value) {
        container.assign(begin, end);
        container.sort(comp);
    } else {
        for (; begin != end; ++begin) {
            container.insert(std::lower_bound(container.begin(), container.end(), *begin, comp),
                             *begin);
        }
    }
}

template <class Container, class Compare>
sorted<Container, Compare>::sorted(std::initializer_list<value_type> ilist)
    : sorted(std::begin(ilist), std::end(ilist)) {}

template <class Container, class Compare>
auto sorted<Container, Compare>::at(size_type pos) const -> const_reference {
    if (pos >= size()) {
        throw std::out_of_range{"pos is out of range"};
    }

    if constexpr (is_forward_list::value || is_list::value) {
        auto it = container.begin();
        while (pos--) {
            ++it;
        }
        return *it;
    } else {
        return container.at(pos);
    }
}

template <class Container, class Compare>
auto sorted<Container, Compare>::operator[](size_type pos) const -> const_reference {
#ifdef UTIL_ASSERT
    util_assert(pos < size());
#endif  // UTIL_ASSERT

    if constexpr (is_forward_list::value || is_list::value) {
        auto it = container.begin();
        while (pos--) {
            ++it;
        }
        return *it;
    } else {
        return container.operator[](pos);
    }
}

template <class Container, class Compare>
auto sorted<Container, Compare>::front() const -> const_reference {
    return container.front();
}

template <class Container, class Compare>
auto sorted<Container, Compare>::back() const -> const_reference {
    return container.back();
}

template <class Container, class Compare>
auto sorted<Container, Compare>::data() const noexcept -> const_pointer {
    return container.data();
}

template <class Container, class Compare>
auto sorted<Container, Compare>::size() const noexcept -> size_type {
    if constexpr (is_forward_list::value) {
        size_type size = 0;
        for (auto it = container.begin(), end = container.end(); it != end; ++it) {
            ++size;
        }
        return size;
    } else {
        return container.size();
    }
}

template <class Container, class Compare>
auto sorted<Container, Compare>::capacity() const noexcept -> size_type {
    if constexpr (is_forward_list::value || is_list::value) {
        return container.max_size();
    } else {
        return container.capacity();
    }
}

template <class Container, class Compare>
void sorted<Container, Compare>::clear() noexcept {
    container.clear();
}

template <class Container, class Compare>
auto sorted<Container, Compare>::insert(const_reference value) -> const_iterator {
    if constexpr (is_forward_list::value) {
        container.push_back(value);
        container.sort(comp);
    } else {
        return const_iterator(
            container.insert(std::lower_bound(container.begin(), container.end()), value, comp));
    }
}

template <class Container, class Compare>
auto sorted<Container, Compare>::insert(value_type&& value) -> const_iterator {
    if constexpr (is_forward_list::value) {
        auto it = container.begin();
        if (comp(value, *it)) {
            container.push_front(std::move(value));
            return container.cbegin();
        }

        for (auto next = ++container.begin(), end = container.end(); next != end; ++next, ++it) {
            if (comp(value, *next)) {
                return const_iterator(container.insert_after(it, std::move(value)));
            }
        }

        return const_iterator(container.insert_after(it, std::move(value)));

    } else {
        return const_iterator(container.insert(
            std::lower_bound(container.begin(), container.end(), std::move(value), comp),
            std::move(value)));
    }
}

}  // namespace util

#endif  // THAT_THIS_UTIL_SORTED_HEADER_IS_ALREADY_INCLUDED