/* LICENSE:
  =========================================================================
    CMPack'03 Source Code Release for OPEN-R SDK v1.0
    Copyright (C) 2003 Multirobot Lab [Project Head: Manuela Veloso]
    School of Computer Science, Carnegie Mellon University
    All rights reserved.
  ========================================================================= */

/*! \file Events.h
    \brief The interface for the event propagation system.
 */

#ifndef INCLUDED_Events_h
#define INCLUDED_Events_h

#include "../headers/DogTypes.h"

#include <map>
#include <set>
#include <string>
#include <vector>

//! Represents a list of events.
/*! Used mainly for representing the events that cause a event update to happen. */
class EventList {
private:
  std::vector<uint> events;
public:
  typedef std::vector<uint>::iterator iterator;
  typedef std::vector<uint>::const_iterator const_iterator;

  //! Add an event to the list
  /*! \param id the event id to add
   */
  void add(uint id) {events.push_back(id);}

  //! Returns true if the event is in the list
  /*! \param event_id the event id to test for the presence of
      \return true iff the event is present in the list
  */
  bool present(uint event_id) const;

  //! Get an iterator to the beginning of the list
  iterator begin();
  //! Get an iterator to the beginning of the list
  const_iterator begin() const;
  //! Get an iterator to past the end of the list
  iterator end();
  //! Get an iterator to past the end of the list
  const_iterator end() const;
};

//! An event handler that produces a result.
/*! An EventProcessor listens to other event processors for updates.
    When one of the input EventProcessors has a new update, the update
    function is called to react to the new information.  Each EventProcessor
    should have a get function which can be used to access the output
    of the EventProcessor.  This function is not included in the
    signature since the return value may be different for different
    EventProcessors.
*/
class EventProcessor {
private:
public:
  //! A static function type which returns a new EventProcessor.
  /*! The EventManager uses functions matching this type to generate
      EventProcessors as needed.
  */
  typedef EventProcessor *(*EventProcessorGenerator)();

  //! Initializes connections to EventProcessors that this one needs to listen to.
  /*! The function makes connections to all of the EventProcessors that this one
      needs to get events from.
      \return true if all necessary connections could be made and false otherwise
  */
  virtual bool initConnections();

  //! Handles any updating that needs to be done in response to the events listened for.
  /*! Handles the updates that need to be done in response to events from EventProcessors
      that this EventProcessor is listening to.

      Note that this function may not actually do the work required to generate the
      output of the EventProcessor.  Many EventProcessors are implemented using lazy
      updates when the get function is called to save processing time when they are
      not needed.

      \param events stores the events that cause this function to be called.
      \param time the timestamp at which this update is considered to be occurring
      \return true if the output returned by get() may have changed in response to this update
  */
  virtual bool update(ulong time,const EventList *events);

  // all event processors should implement a function of one of the following forms
  // struct EventData *get(ulong time);
  // void get(ulong time);
};

//! A utility class to make it easier to implement lazy updates when the get() function is called.
class EventCacheTracker {
private:
  ulong available_time;
  ulong cache_time;
public:
  //! Constructor
  EventCacheTracker();
  
  //! Indicates that new data can be calculated for cache.
  /*! \param time the time that this update became available
   */
  void updateAvailable(ulong time);
  //! Tests whether cache should be recalculated.
  /*! \param requested_time the time for which output is being requested
      \return true if the cache needs updated
  */
  bool shouldUpdate(ulong requested_time);
  //! Indicates that the cache data has been recalculated.
  /*! \param time the time at which the cache was updated
   */
  void cacheUpdated(ulong time);
};

//! Internal class used for keeping track of updates that still need to be done.
struct PendingEvent {
  //! The id of the EventProcessor that needs to be updated.
  uint id_to_update;
  //! The events that caused this update.
  EventList events;
};

//! Internal class used for sorting pending events by topological order.  Used in stl's sort(). 
class PendingEventOrderer {
private:
  //! A map from EventProcessor ids to indices in a valid topological order.
  /*! Higher number are earlier in the topological order. */
  std::map<uint,uint> *id_order;

public:
  PendingEventOrderer(std::map<uint,uint> *_id_order);
  PendingEventOrderer(const PendingEventOrderer &x);

  bool operator()(PendingEvent * const &x,PendingEvent * const &y) const;
};

//! Manages event propagation and connections between EventProcessors.
class EventManager {
private:
  //! Constructor.
  EventManager();

  /*! \name Graph structure encoding
   * Members encoding the structure of the graph.
   */
  //@{
  typedef std::multimap<uint,uint> ConnectionMap;

  //! true if the implementation names have been read
  bool read_implementation_names;
  //! mapping from virtual names to implementation names
  std::map<std::string, std::string> implementation_names;
  //! number of ids currently in use
  uint num_ids;
  //! mapping from EventProcessor name to id number
  std::map<std::string, uint> ids;
  //! mapping from id number to EventProcessor name
  std::vector<std::string> event_proc_names;
  //! mapping from id number to EventProcessorGenerator
  std::vector<EventProcessor::EventProcessorGenerator> event_proc_gens;
  //! mapping from id number to EventProcessor
  std::vector<EventProcessor *> event_procs;
  //! multimap from id number of talker to id numbers of listeners
  ConnectionMap connections;
  //! true if id_order is up to date, false if it needs regenerated
  bool id_order_valid;
  //! Map from id number to graph order number, larger numbers are earlier in graph
  std::map<uint,uint> id_order;
  //@}

  /*! \name Propagation state encoding
   * Members encoding the current state of event propagation.
   */
  //@{
  typedef std::set<PendingEvent *, PendingEventOrderer> PendingEventQueue;
  PendingEventQueue event_queue;
  //@}

  //! Gets the connection coming out from id_from
  /*! \param id_from the id the update is coming from
      \param ids_to1 an iterator to set to point to the first id the update is going to
      \param ids_to2 an iterator to set to a past the end value for ids the update goes to
  */
  void getConnections(uint id_from,ConnectionMap::iterator &ids_to1,ConnectionMap::iterator &ids_to2)
  {
    std::pair<std::multimap<uint,uint>::iterator,std::multimap<uint,uint>::iterator> id_range;
    
    id_range = connections.equal_range(id_from);
    ids_to1 = id_range.first;
    ids_to2 = id_range.second;
  }

  //! Request access to an event processor, instantiating it if necessary.
  /*! \param name the string name of the EventProcessor
      \return A pointer to the EventProcessor
  */
  EventProcessor *getEventProcessor(std::string name);

  //! Add a connection to the graph.
  /*! \param id_from the id the update comes from (the talker)
      \param id_to the id the update goes to (the listener)
  */
  void addConnection(uint id_from,uint id_to);

  //! Ensures the mapping from virtual names to implementation names is filled.
  void ensureImplementationNamesRead();

  //! Helper routine for updateIdOrder().
  void updateIdOrder(uint id,uint &time,std::set<uint> &ids_seen);
  //! Updates id_order to be a valid topological order.
  void updateIdOrder();
  //! Ensures that id_order is a valid topological order (runs updateIdOrder if necessary)
  void ensureIdOrderValid();

public:
  //! Static routine to get the one and only instance of the EventManager.
  static EventManager *getManager();

  //! Add an event processor the set of available EventProcessors.
  /* \param name the name of the event processor
     \param event_proc_gen the function to use to generate the EventProcessor if someone requests it.
  */
  void addEventProcessor(std::string name,EventProcessor::EventProcessorGenerator event_proc_gen);

  //! Request the id of an event processor, instantiating it if necessary.
  /*! \param name the name of the EventProcessor
      \return the id of the event processor or ~OU if the EventProcessor does not exist.
  */
  uint getEventProcessorId(std::string name);

  //! Request an event processor.
  /*! Note that this function will not instantiate the EventProcessor
      \param id the id of an EventProcessor or ~OU
      \return the EventProcessor requested or NULL on error or being passed ~0U
  */
  EventProcessor *getEventProcessor(uint id);

  //! Subscribe id_listener to id_talker's output.
  /*! \param id_listener the id of the EventProcessor who is requesting updates.
      \param id_talker the id of the EventProcessor producing updates
      \return the EventProcessor of the talker
  */
  EventProcessor *listenEventProcessor(uint id_listener,uint id_talker);
  //! Subscribe the named listener to id_talker's output.
  /*! \param name the name of the EventProcessor who is requesting updates.
      \param id_talker the id of the EventProcessor producing updates
      \return the EventProcessor of the talker
  */
  EventProcessor *listenEventProcessor(std::string name,uint id_talker)
  {
    return listenEventProcessor(getEventProcessorId(name),id_talker);
  }
  //! Subscribe the named listener to id_talker's output.
  /*! \param name the name of the EventProcessor who is requesting updates.
      \param id_talker the id of the EventProcessor producing updates
      \return the EventProcessor of the talker
  */
  EventProcessor *listenEventProcessor(const char *name,uint id_talker)
  {
    return listenEventProcessor(std::string(name),id_talker);
  }

  //! Externally mark an EventProcessor as updated.
  /*! This function is used to mark the nodes at the starting edge of the graph
      as being updated to start the propagation.
      \param id_updated the EventProcessor id to mark as updated
  */
  void injectEvent(uint id_updated);
  //! Propagate all pending events through all EventProcessors who have expressed interest.
  /*! \param The timestamp at which this propagation is to be considered to be happening.
             Timestamps must be monotonically increasing across separate updates.
   */
  void propagateEvents(ulong time);
};

//! Utility class to register EventProcessors used by REGISTER_EVENT_PROCESSOR
class EventProcessorRegisteringClass {
public:
  EventProcessorRegisteringClass(const char *event_processor_name,EventProcessor::EventProcessorGenerator event_proc_gen) {
    EventManager *event_mgr;

    event_mgr = EventManager::getManager();
    event_mgr->addEventProcessor(std::string(event_processor_name),event_proc_gen);
  }

  EventProcessorRegisteringClass(std::string event_processor_name,EventProcessor::EventProcessorGenerator event_proc_gen) {
    EventManager *event_mgr;

    event_mgr = EventManager::getManager();
    event_mgr->addEventProcessor(event_processor_name,event_proc_gen);
  }
};

//! A macro to register the availability of an EventProcessor.
/*! This macro is used to register the availability of an EventProcessor.  If you
    try to use an EventProcessor from run.cfg or elsewhere without registering it,
    the access will fail.  In the case of access from run.cfg, the robot will ignore
    the unregistered behavior.
    \param class_name A unique name for this class of EventProcessor (must be unique, use the class name)
    \param name A std::string of const char * which has the name of the EventProcessor being registered
    \param generator An EventProcessor::EventProcessorGenerator to use to generate an instance of this EventProcessor
 */
#define REGISTER_EVENT_PROCESSOR(class_name,name,generator) EventProcessorRegisteringClass EPRC##class_name(name,generator);

#endif
