eventlist.hh

Go to the documentation of this file.

 // This Source Code Form is licensed MPL-2.0: http://mozilla.org/MPL/2.0
#pragma once
 
#include <ase/utils.hh>
#include <algorithm>
#include <any>
 
namespace Ase {
 
template<class Event, class CompareOrder>
struct OrderedEventList : std::vector<Event> {
  using Base = std::vector<Event>;
  using ConstP = std::shared_ptr<const OrderedEventList>;
  explicit     OrderedEventList (const std::vector<Event> &ve);
  const Event* lookup           (const Event &event) const;
  const Event* lookup_after     (const Event &event) const;
private:
  CompareOrder compare_;
};
 
template<class Event, class Compare>
class EventList final {
  using EventVector = std::vector<Event>;
public:
  using Notify = std::function<void (const Event &event, int mod)>;
  using CIter = typename EventVector::const_iterator;
  explicit     EventList      (const Notify &n = {}, const Compare &c = {});
  bool         insert         (const Event &event, Event *replaced = nullptr); 
  bool         replace        (const Event &event, Event *replaced = nullptr); 
  bool         remove         (const Event &event, Event *removed = nullptr); 
  const Event* lookup         (const Event &event) const; 
  const Event* lookup_after   (const Event &event) const; 
  const Event* first          () const; 
  const Event* last           () const; 
  size_t       size           () const; 
  void         clear_silently ();       
  template<class OrderedEventList> typename OrderedEventList::ConstP
  inline       ordered_events ();       
  CIter        begin          () const { return events_.begin(); } 
  CIter        end            () const { return events_.end(); }   
  EventVector  copy           () const { return events_; }
  bool         equals         (const EventVector &ev) const { return ev == events_; }
private:
  EventVector        events_;
  Compare            compare_;
  Notify             notify_;
  std::any           ordered_;
  static_assert (std::is_signed<decltype (std::declval<Compare>() (std::declval<Event>(), std::declval<Event>()))>::value, "REQUIRE: int Compare (const&, const&);");
  void               uncache      ();
  static void        nop          (const Event&, int) {}
};
 
// == Implementation Details ==
template<class Event, class Compare> inline
EventList<Event,Compare>::EventList (const Notify &n, const Compare &c) :
  compare_ (c), notify_ (n)
{
  if (!notify_)
    notify_ = nop;
}
 
template<class Event, class Compare> inline void
EventList<Event,Compare>::clear_silently ()
{
  events_.clear();
  ordered_.reset();
}
 
template<class Event, class Compare> inline void
EventList<Event,Compare>::uncache ()
{
  ordered_.reset();
}
 
template<class Event, class Compare> inline bool
EventList<Event,Compare>::insert (const Event &event, Event *replaced)
{
  uncache();
  if (events_.size() && compare_ (event, events_.back()) > 0)
    {
      events_.push_back (event);
      notify_ (event, +1);      // notify insertion
      return false;             // O(1) fast path for append
    }
  auto insmatch = Aux::binary_lookup_insertion_pos (events_.begin(), events_.end(), compare_, event);
  auto it = insmatch.first;
  if (insmatch.second == true)  // exact match
    {
      if (replaced)
        *replaced = *it;
      *it = event;
      notify_ (event, 0);       // notify change
      return true;
    }
  else
    {
      events_.insert (it, event);
      notify_ (event, +1);      // notify insertion
      return false;
    }
}
 
template<class Event, class Compare> inline bool
EventList<Event,Compare>::replace (const Event &event, Event *replaced)
{
  auto insmatch = Aux::binary_lookup_insertion_pos (events_.begin(), events_.end(), compare_, event);
  if (insmatch.second == true)  // exact match
    {
      uncache();
      auto it = insmatch.first;
      if (replaced)
        *replaced = *it;
      *it = event;
      notify_ (event, 0);       // notify change
      return true;
    }
  return false;
}
 
template<class Event, class Compare> inline bool
EventList<Event,Compare>::remove (const Event &event, Event *removed)
{
  uncache();
  const int cmp = events_.empty() ? +1 : compare_ (event, events_.back());
  if (cmp == 0)
    {
      if (removed)
        *removed = events_.back();
      events_.pop_back();       // O(1) fast path for tail removal
      notify_ (event, -1);      // notify removal
      return true;              // found and removed
    }
  if (cmp < 0)
    {
      auto it = Aux::binary_lookup (events_.begin(), events_.end() - 1, compare_, event);
      if (it != events_.end())
        {
          if (removed)
            *removed = *it;
          events_.erase (it);
          notify_ (event, -1);  // notify removal
          return true;          // found and removed
        }
    }
  return false;                 // none removed
}
 
template<class Event, class Compare> inline const Event*
EventList<Event,Compare>::first() const
{
  return events_.empty() ? nullptr : &events_.front();
}
 
template<class Event, class Compare> inline const Event*
EventList<Event,Compare>::last() const
{
  return events_.empty() ? nullptr : &events_.back();
}
 
template<class Event, class Compare> inline size_t
EventList<Event,Compare>::size () const
{
  return events_.size();
}
 
template<class Event, class Compare> inline const Event*
EventList<Event,Compare>::lookup (const Event &event) const
{
  auto it = Aux::binary_lookup (events_.begin(), events_.end(), compare_, event);
  return it != events_.end() ? &*it : nullptr;
}
 
template<class Event, class Compare> inline const Event*
EventList<Event,Compare>::lookup_after (const Event &event) const
{
  auto it = Aux::binary_lookup_insertion_pos (events_.begin(), events_.end(), compare_, event).first;
  return it != events_.end() ? &*it : nullptr;
}
 
template<class Event, class Compare>
template<class OrderedEventList> inline typename OrderedEventList::ConstP
EventList<Event,Compare>::ordered_events ()
{
  using OrderedEventListP = typename OrderedEventList::ConstP;
  OrderedEventListP *oepp = std::any_cast<OrderedEventListP> (&ordered_);
  if (!oepp)
    {
      ordered_ = std::make_shared<const OrderedEventList> (events_);
      oepp = std::any_cast<OrderedEventListP> (&ordered_);
      ASE_ASSERT_RETURN (oepp, nullptr);
    }
  return *oepp;
}
 
template<class Event, class CompareOrder>
OrderedEventList<Event,CompareOrder>::OrderedEventList (const std::vector<Event> &ve) :
  Base (ve)
{
  auto lesser = [this] (const Event &a, const Event &b) {
    return compare_ (a, b) < 0;
  };
  std::stable_sort (this->begin(), this->end(), lesser);
}
 
template<class Event, class CompareOrder> inline const Event*
OrderedEventList<Event,CompareOrder>::lookup (const Event &event) const
{
  auto it = Aux::binary_lookup (this->begin(), this->end(), compare_, event);
  return it != this->end() ? &*it : nullptr;
}
 
template<class Event, class CompareOrder> inline const Event*
OrderedEventList<Event,CompareOrder>::lookup_after (const Event &event) const
{
  auto it = Aux::binary_lookup_insertion_pos (this->begin(), this->end(), compare_, event).first;
  return it != this->end() ? &*it : nullptr;
}
 
} // Ase