Program Listing for File Ordered.hpp

↰ Return to documentation for file (src/navtk/utils/Ordered.hpp)

#pragma once

#include <deque>

#include <navtk/utils/RingBuffer.hpp>
#include <navtk/utils/algorithm.hpp>

namespace navtk {
namespace utils {

template <typename Data,
          typename Container,
          typename Compare,
          typename SortIterator,
          typename SortCompare>
class Ordered {
public:
    using value_type = Data;
    using iterator = typename Container::iterator;
    using const_iterator = typename Container::const_iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using const_iterator_pair = std::pair<const_iterator, const_iterator>;
    using const_reverse_iterator_pair = std::pair<const_reverse_iterator, const_reverse_iterator>;

    std::size_t size() const { return buffer.size(); }

    bool empty() const { return buffer.empty(); }

    bool full() const { return buffer.full(); }

    void pop_front() { buffer.pop_front(); }

    void pop_back() { buffer.pop_back(); }

    const Data& front() const { return buffer.front(); }

    const Data& back() const { return buffer.back(); }

    iterator erase(const_iterator first, const_iterator last) { return buffer.erase(first, last); }

    iterator begin() { return buffer.begin(); }

    iterator end() { return buffer.end(); }

    reverse_iterator rbegin() { return buffer.rbegin(); }

    reverse_iterator rend() { return buffer.rend(); }

    const_iterator begin() const { return buffer.begin(); }

    const_iterator end() const { return buffer.end(); }

    const_reverse_iterator rbegin() const { return buffer.rbegin(); }

    const_reverse_iterator rend() const { return buffer.rend(); }

    const_iterator cbegin() const { return buffer.cbegin(); }

    const_iterator cend() const { return buffer.cend(); }

    const_reverse_iterator crbegin() const { return buffer.crbegin(); }

    const_reverse_iterator crend() const { return buffer.crend(); }

    void insert(const Data& data) {
        Compare compare;
        if (is_insert_ok(data, buffer, capacity)) {
            pre_insert(data, buffer, capacity);
            bool sort_it = (!buffer.empty()) && (compare(data, buffer.back()));
            // push data on the back of the buffer
            buffer.push_back(data);
            if (sort_it) {
                // minor efficiency if inserted data is very near the end
                auto begin_sort = std::upper_bound(buffer.begin(), buffer.end() - 1, data, compare);
                std::stable_sort(begin_sort, buffer.end(), compare);
            }
            post_insert(data, buffer, capacity);
        }
    }

    const_iterator_pair get_in_range(typename SortIterator::value_type t0,
                                     typename SortIterator::value_type t1) const {
        auto range =
            in_range.get(SortIterator{buffer.cbegin()}, SortIterator{buffer.cend()}, t0, t1);
        return std::make_pair(const_iterator{range.first}, const_iterator{range.second});
    }

    const_iterator_pair get_nearest_neighbors(const typename SortIterator::value_type& t) const {
        auto neighbors =
            nearest_neighbors.get(SortIterator{buffer.cbegin()}, SortIterator{buffer.cend()}, t);
        return std::make_pair(const_iterator{neighbors.first}, const_iterator{neighbors.second});
    }

protected:
    Ordered(std::size_t capacity, std::size_t initial_capacity)
        : capacity(capacity), buffer(Container(initial_capacity)) {}
    virtual ~Ordered() = default;

    Ordered(const Ordered&) = default;

    Ordered& operator=(const Ordered&) = default;

    Ordered(Ordered&&) = default;

    Ordered& operator=(Ordered&&) = default;

private:
    std::size_t capacity;
    Container buffer;
    virtual bool is_insert_ok(const Data&, const Container&, std::size_t) const { return true; }
    virtual void pre_insert(const Data&, Container&, std::size_t) {}
    virtual void post_insert(const Data&, Container&, std::size_t) {}

    InRange<SortIterator, SortCompare> in_range;
    NearestNeighbors<SortIterator, SortCompare> nearest_neighbors;
};

template <typename Data,
          typename Compare      = std::less<Data>,
          typename SortIterator = typename RingBuffer<Data>::const_iterator,
          typename SortCompare  = std::less<Data>>
class OrderedRing final : public Ordered<Data,
                                         typename navtk::utils::RingBuffer<Data>,
                                         Compare,
                                         SortIterator,
                                         SortCompare> {
public:
    explicit OrderedRing(std::size_t capacity)
        : Ordered<Data, RingBuffer<Data>, Compare, SortIterator, SortCompare>(capacity, capacity) {}

private:
    bool is_insert_ok(const Data& data,
                      const RingBuffer<Data>& buffer,
                      std::size_t capacity) const override {
        // if the buffer is full and this element won't fit in order, return false
        return !(buffer.size() == capacity && Compare()(data, buffer.front()));
    }
};

template <typename Data,
          typename Compare      = std::less<Data>,
          typename SortIterator = typename std::deque<Data>::const_iterator,
          typename SortCompare  = std::less<Data>>
class OrderedDeque final
    : public Ordered<Data, typename std::deque<Data>, Compare, SortIterator, SortCompare> {
public:
    explicit OrderedDeque(std::size_t capacity)
        : Ordered<Data, std::deque<Data>, Compare, SortIterator, SortCompare>(capacity, 0) {}

private:
    void post_insert(const Data&, std::deque<Data>& buffer, std::size_t capacity) override {
        // if the buffer is over capacity remove an element from the front
        if (buffer.size() > capacity) {
            buffer.pop_front();
        }
    }
};

}  // namespace utils
}  // namespace navtk