/*                                              -*- mode:C++; fill-column:100 -*-
  SFBAlarm.h - Support for time-based events
  Copyright (C) 2009 The Regents of the University of New Mexico.  All rights reserved.

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
  USA
*/

/**
  \file SFBAlarm.h Support for time-based events.
  \author David H. Ackley.  
  \date (C) 2009 All rights reserved.
  \lgpl
 */
#ifndef SFBALARM_H_
#define SFBALARM_H_

#include "SFBTypes.h"
#include "SFBWiring.h"  /* for millis() */

/**
   A function pointer type that can be called when an alarm is triggered.  This is the simpler of
   the such funtion pointer types; see SFBAlarmArgHandler for the more complicated type.
 */
typedef void (*SFBAlarmHandler)(u32 when);

/**
   A function pointer type that can be called when an alarm is triggered.  This is the more powerful
   of the such funtion pointer types; see SFBAlarmArgHandler for the more limited type.
 */
typedef void (*SFBAlarmArgHandler)(u32 when, void *arg);

#ifndef SFBALARM_QUEUE_SIZE
#define SFBALARM_QUEUE_SIZE 51  ///< The maximum number of alarms.  The RAM footprint of an SFBAlarm
                                ///  grows (at least) as (14 bytes * SFBALARM_QUEUE_SIZE).
#endif

#if SFBALARM_QUEUE_SIZE < 256
typedef u8 SFBAlarmIndexType;   ///< The type of an alarm index.  u8 suffices unless SFBALARM_QUEUE_SIZE exceeds 255
#else
#if SFBALARM_QUEUE_SIZE < 65536
typedef u16 SFBAlarmIndexType;
#else
typedef u32 SFBAlarmIndexType;
#endif
#endif

/**
 * Manage "alarm clock"-style settable timers.  For working code samples, see \ref alarm1.cpp, \ref
 * alarm2.cpp, and \ref alarm3.cpp; the rest of this description discusses internals of the system.
 *
 * \section AlarmTheoryOfOperation Theory of operation
 *
 * The primary, somewhat incompatible, goals of this implementation are:
 * -# Fast, high resolution alarm scheduling, accurate to the millisecond barring load
 * -# Integrate tightly with the core so that alarm triggering is automatic
 * -# Easy-to-use API involving no interrupt level code and a minimum of pointers
 * -# Internal data structures are incorruptible by API calls regardless of arguments
 * -# Complete freedom to set and cancel alarms without caring if they were previously set
 * -# Support dozens of alarms reasonably compactly, without dynamic allocation
 *
 * The most consequential design decision is to refer to alarms by a non-zero 'alarm number' rather
 * than via pointer, primarily in support of goals (3) and (4).  In addition, to reduce risk of
 * confusion, there is no support for destroying alarm numbers once they are created (although
 * #update(u32 alarmNumber, SFBAlarmHandler handler) can be used to achieve the effect of an alarm
 * number destruction and immediate reallocation).
 *
 * The result is a conventional heap-based priority queue implementation, using an indirect index
 * array 'slots' to reorder elements without copying the element info, and a reverse array 'idxs' to
 * find the current priority queue position of an element, to support deletion and priority changes.
 *
 * <pre>
 *  used      alarms
 *    +----+    +----+
 *    |  3 |    |  4 |
 *    +----+    +----+
 *             alarm
 *     slots   Number idxs     times      handlers     args
 *     +----+        +----+ +---------+ +---------+ +---------+
 *  0  | xx |     0  | 0  | |   --    | |   --    | |   --    |
 *     +----+        +----+ +---------+ +---------+ +---------+
 *  1  | 3  |     1  | 2  | |     210 | | MyAlarm | |   0     |
 *     +----+        +----+ +---------+ +---------+ +---------+
 *  2  | 1  |     2  | 3  | |     309 | |  Serial | |&SerPort1|
 *     +----+        +----+ +---------+ +---------+ +---------+
 *  3  | 2  |     3  | 1  | |     123 | |  Serial | |&SerPort0|
 *     +----+        +----+ +---------+ +---------+ +---------+
 *  4  | 4  |     4  | 0  | |    ??   | |    ??   | |    ??   |
 *     +----+        +----+ +---------+ +---------+ +---------+
 * </pre>
 *
 * Mapping invariants:
 * - (i >= 1 && i <= used) => idxs[slots[i]] == i
 *
 * - (used <= alarms)   - You can't have more events scheduled than are defined..
 *
 * - (There's also the priority queue invariant, of course..)
 *
 * Alarms RAM usage (allocated in bodyram) is 14*#SFBALARM_QUEUE_SIZE+4, currently a total of 720
 * bytes after alignment.
 *
 */
class SFBAlarm {
  enum { MAX_EVENTS = SFBALARM_QUEUE_SIZE };
 public: 

  SFBAlarm() ;

  /**
     Create a new alarm, return its corresponding alarm number.  Note this method blinks
     #E_API_NO_MORE_ALARMS if no more alarms are available; if a sketch needs to survive running out
     of alarms it must call #canCreate() to ascertain that another alarm is available before calling
     this method.

     This is the simpler method of the two methods of creating an alarm; see also
     #create(SFBAlarmArgHandler, void *) for a more advanced mechanism that provides additional
     flexibility.

     @param handler function to call whenever this alarm goes off

     @return a non-zero \c alarmNumber to use to refer to this alarm in the future

     @blinks #E_API_NO_MORE_ALARMS if the alarm system is full so a new alarm could not be created.
  */ 
  u32 create(SFBAlarmHandler handler) ;  

  /**
     Create a new alarm, return its corresponding alarm number.  This is the 'more advanced' alarm
     creation method, providing an additional \a arg agument for use by the alarm handlers; see \ref
     alarm3.cpp for a usage example.  For the simpler 'basic alarm' creation mechanism see
     #create(SFBAlarmHandler).
     
     Note this method blinks #E_API_NO_MORE_ALARMS if no more alarms are available; if a sketch
     needs to survive running out of alarms it must call #canCreate() to ascertain that another
     alarm is available before calling this method.

     @param handler function to call whenever this alarm goes off

     @param arg an arbitrary pointer value to associate with this alarm, which will be provided as
     the second argument to \a handler whenever the alarm goes off.

     @return a non-zero \c alarmNumber to use to refer to this alarm in the future

     @blinks #E_API_NO_MORE_ALARMS if the alarm system is full so a new alarm could not be created.
  */ 
  u32 create(SFBAlarmArgHandler handler, void * arg) ; /* Create a new alarm object, return alarm number > 0 or 0 if full */ 

  /**
     Alter the handler of an existing alarm.  The existing alarm may be set or unset, or even
     currently running; in all cases the new \a handler value will take effect the \e next time the
     alarm is triggered.  See also #update(u32,SFBAlarmArgHandler,void *).

     \param alarmNumber The number of an existing alarm, whose handler should be changed.

     \param handler Non-null pointer to the alarm handler function (the one-argument
     #SFBAlarmHandler kind) that should become the handler for \a alarmNumber

     \blinks #E_API_BAD_ALARM if \a alarmNumber is not the number of an existing alarm.

     \blinks #E_API_NULL_HANDLER if \a handler is null
  */ 
  void update(u32 alarmNumber, SFBAlarmHandler handler) { 
    update(alarmNumber,(SFBAlarmArgHandler) handler, (void*) 0);
  }

  /**
     Alter the handler and/or the extra argument of an existing alarm.  The existing alarm may be
     set or unset, or even currently running; in all cases the new \a handler value and/or \a arg
     value will take effect the \e next time the alarm is triggered.  See also
     #update(u32,SFBAlarmHandler).

     \param alarmNumber The number of an existing alarm, whose handler should be changed.

     \param handler Non-null pointer to the alarm handler function (the two-argument
     #SFBAlarmArgHandler kind) that should become the handler for \a alarmNumber

     \param arg an arbitrary pointer value to associate with \a alarmNumber, which will be provided
      to \a handler whenever alarm \a alarmNumber is triggered

     \blinks #E_API_BAD_ALARM if \a alarmNumber is not the number of an existing alarm.

     \blinks #E_API_NULL_HANDLER if \a handler is null
  */ 
  void update(u32 alarmNumber, SFBAlarmArgHandler handler, void * arg); /* Alter the handler and/or arg of an existing alarm */ 

  /**
     If alarm \a alarmNumber is set, access the alarm time.  If \a alarmNumber is \e not set,
     returns the \e most \e recent \e previous alarm time; if \a alarmNumber has never been set,
     return 0.

     @param alarmNumber The alarm to access

     @return the current or most-recent alarm setting, or zero

     @blinks #E_API_BAD_ALARM if \a alarmNumber is not an alarm number previously returned by
     #create(SFBAlarmHandler) or #create(SFBAlarmArgHandler,void*)

     @since 0.9.5
  */

  u32 get(u32 alarmNumber) ;

  /**
     Set (or reset) alarm \a alarmNumber to go off at \a when.  If \a when is in the past relative
     to #millis() (in the sense of #IS_EARLIER), the alarm will go off at its soonest possible
     opportunity.

     @param alarmNumber The alarm to set

     @return \c true if the alarm was currently set, \c false if not.

     @blinks #E_API_BAD_ALARM if \a alarmNumber is not an alarm number previously returned by
     #create(SFBAlarmHandler) or #create(SFBAlarmArgHandler,void*)
  */
  bool set(u32 alarmNumber, u32 when) ;

  /**
     Cancel any pending alarm for alarm \a alarmNumber.

     @param alarmNumber The alarm to cancel

     @return \c true if the alarm had been currently set, \c false if not.

     @blinks #E_API_BAD_ALARM if \a alarmNumber is not an alarm number previously returned by
     #create(SFBAlarmHandler) or #create(SFBAlarmArgHandler,void*)
  */
  bool cancel(u32 alarmNumber) ;   

  /**
     Find out what alarm number is currently active.  This method should be called only during a
     callback to an alarm handler; its return value is not defined elsewhere.

    \return The alarm number that triggered the current alarm handler callback, or an unspecified
     value if no alarm handler is currently running.
  */
  u32 currentAlarmNumber() { return currentAlarmIndex; }

  int runDueEvents(int maxEvents, u32 deadline) ; ///< [Intended for core use only]

  int runPriorityEvents(int maxEvents, u32 priorityAtLeast) ; ///< [Intended for core use only]

  /**
     Determine if it is possible to create another alarm.  The alarm creating functions
     #create(SFBAlarmHandler) and #create(SFBAlarmArgHandler,void*) die blinking if they are called
     when there's no more room to create an additional alarm.  To avoid that risk, a sketch may call
     this function first.

     @return \c true if at least one more alarm can be created, \c false otherwise.

   */
  bool canCreate() ;

  /**
     Return the number of alarms have been created.
  */
  u32 created() { 
    return alarms; 
  }

  bool canAdd() ; /**< [Intended for core use] \c true iff the internal alarm queue isn't full */

  bool canRemove() { return used > 0; } /**< Return \c true if #count() is greater than zero, else
                                           \c false */

  u32 count() { return used; } /**< Return the number of currently #set() alarms */

  /** \c true iff \a alarmIndex is a legal, currently scheduled alarm number. */
  bool inUse(u32 alarmIndex) {     
    return alarmIndex <= alarms
      && idxs[alarmIndex] > 0;
  }

  /**
   * Get the earliest time in the queue.  Only valid when #canRemove() returns true.
   */
  u32 getTopTime() {
    return times[slots[1]];
  }

 private:

  int getUsed() {
    return used;
  }

  /**
   * Remove the topmost element and run it.  Only valid when canRemove() returns true.
   */
  void removeAndRunTop() ;

  void deleteElt(int eltIdx);              /* eltIdx must currently be in pq! */

  u32 times[MAX_EVENTS];                   /* when this event goes off */
  SFBAlarmArgHandler handlers[MAX_EVENTS]; /* who to call when it does */
  void * args[MAX_EVENTS];                 /* argument to pass back to them */
  SFBAlarmIndexType slots[MAX_EVENTS];     /* priority queue map slot idx->elt idx */
  SFBAlarmIndexType idxs[MAX_EVENTS];      /* reverse map elt idx->slot idx */
  SFBAlarmIndexType used;
  SFBAlarmIndexType alarms;
  SFBAlarmIndexType currentAlarmIndex;

  void bubbleUp(int fromIndex);
  void bubbleDown(int fromIndex);

#ifdef TEST_SFBALARM
  friend void heapcheck(int) ;
  friend void runRandoms() ;
#endif

};

/**
   The object controlling all #SFBAlarm functions.
 */
extern SFBAlarm Alarms;

#endif /*SFBALARM_H_*/
