.. _program_listing_file_src_navtk_utils_Ordered.hpp:

Program Listing for File Ordered.hpp
====================================

|exhale_lsh| :ref:`Return to documentation for file <file_src_navtk_utils_Ordered.hpp>` (``src/navtk/utils/Ordered.hpp``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   #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