utils_sorted_vector.hpp

#ifndef LXGUI_SORTED_VECTOR_HPP
#define LXGUI_SORTED_VECTOR_HPP
 
#include "lxgui/lxgui.hpp"
 
#include <algorithm>
#include <functional>
#include <memory>
#include <vector>
 
namespace lxgui::utils {
 
template<typename T, typename Cmp = std::less<T>>
class sorted_vector : private std::vector<T> {
    using base = std::vector<T>;
    Cmp compare;
 
public:
    using iterator               = typename base::iterator;
    using const_iterator         = typename base::const_iterator;
    using reverse_iterator       = typename base::reverse_iterator;
    using const_reverse_iterator = typename base::const_reverse_iterator;
 
    sorted_vector() = default;
 
    sorted_vector(const sorted_vector& s) = default;
 
    sorted_vector(sorted_vector&& s) = default;
 
    sorted_vector& operator=(const sorted_vector& s) = default;
 
    sorted_vector& operator=(sorted_vector&& s) = default;
 
    explicit sorted_vector(const base& s) : base(s) {}
 
    explicit sorted_vector(base&& s) : base(std::move(s)) {}
 
    explicit sorted_vector(const Cmp& c) : compare(c) {}
 
    sorted_vector(std::initializer_list<T> l) {
        for (auto& e : l) {
            insert(e);
        }
    }
 
    Cmp& comparator() {
        return compare;
    }
 
    const Cmp& comparator() const {
        return compare;
    }
 
    template<typename U>
    std::pair<iterator, bool> insert(U&& t) {
        if (empty()) {
            base::push_back(std::forward<U>(t));
            return {base::begin(), true};
        } else {
            auto iter = std::lower_bound(base::begin(), base::end(), t, compare);
            if (iter != base::end() && !compare(t, *iter)) {
                return {iter, false};
            } else {
                return {base::insert(iter, std::forward<U>(t)), true};
            }
        }
    }
 
    template<typename U>
    iterator insert_or_assign(U&& t) {
        auto [iter, inserted] = insert(std::forward<U>(t));
        if (!inserted)
            *iter = std::forward<U>(t);
        return iter;
    }
 
    iterator erase(iterator iter) {
        return base::erase(iter);
    }
 
    iterator erase(iterator first, iterator last) {
        return base::erase(first, last);
    }
 
    template<typename Key>
    iterator erase(const Key& k) {
        auto iter = find(k);
        if (iter != end()) {
            return base::erase(iter);
        } else {
            return end();
        }
    }
 
    template<typename Key>
    iterator find(const Key& k) {
        if (!empty()) {
            auto iter = std::lower_bound(begin(), end(), k, compare);
            if (iter != end() && !compare(k, *iter)) {
                return iter;
            }
        }
        return end();
    }
 
    template<typename Key>
    const_iterator find(const Key& k) const {
        if (!empty()) {
            auto iter = std::lower_bound(begin(), end(), k, compare);
            if (iter != end() && !compare(k, *iter)) {
                return iter;
            }
        }
        return end();
    }
 
    using base::back;
    using base::capacity;
    using base::clear;
    using base::empty;
    using base::front;
    using base::max_size;
    using base::pop_back;
    using base::reserve;
    using base::size;
 
    using base::begin;
    using base::end;
    using base::rbegin;
    using base::rend;
};
 
} // namespace lxgui::utils
 
#endif