W42270362 - TimeSlot Lookup Class (binary search)

<?php // http://stackoverflow.com/questions/42270362/optimal-algorithm-to-get-the-next-available-time-slot-in-an-associative-array-co


class TimeRanges {

  /**
   * need this for binary search
   */
  private $startTimes = array();
  private $lastSlotIdx = 0;

  // outputs so you don't need to run the search again

  private $timeNow = 0;
  private $outSlots = array();

  private $dateWhen = null; // used to convert seconds to different formats

  /**
   * @param array The timeSlots that will be searched
   */
  public function __construct(array $timeSlots) {
      $this->buildAllstartTimes($timeSlots);
      $this->dateWhen = new \DateTime();
  }

  /**
   * Create a list of real and 'virtual' timeslots.
   * i.e. All gaps between the real timeslots we treat as a timeslot
   *      when searching for a matching timeslot
   */
  protected function buildAllStartTimes($timeSlots) {

      $this->startTimes = array();

      $iter = new ArrayIterator($timeSlots);

      $prvEndTime = PHP_INT_MAX; // needed to identify 'gaps'

      while ($iter->valid()) {

          $curStartTime = $this->asSeconds($iter->key());   // seconds
          $curEndTime = $this->asSeconds($iter->current()); // so is easy to check

          if ($curStartTime > $prvEndTime) { // make a 'gap' timeslot
              $this->startTimes[]  = ['s' => $prvEndTime + 1,
                                      'e' => $curStartTime,
                                      'real' => false];
              $prvEndTime = $curStartTime;

          } else { // is real
              $this->startTimes[] = ['s' => $curStartTime,
                                     'e' => $curEndTime,
                                     'real' => true];
              $prvEndTime = $curEndTime;
              $iter->next();
          }
      }
      $this->lastSlotIdx = count($this->startTimes) - 1;
  }

  /**
   *  Search the array using a modifield binary search
   *
   *  This can return zero, one or two 'real' timeslots:
   *
   *  o timeNow before first timeslot -- return first timeslot
   *  o timeNow after last timeslot   -- return empty array
   *  o timeNow on a 'gap'            -- return one timeslot (the next one)
   *
   * @param string current time
   */
  public function findTimeSlots($timeNow) {
      $this->timeNow = $this->asSeconds($timeNow);
      $startSlotIdx = $this->searchStartTimes($this->timeNow, 0, $this->lastSlotIdx);


      $returnedSlots = 1;
      if ($startSlotIdx > $this->lastSlotIdx ) {
          $returnedSlots = 0;

      } elseif (    isset($this->startTimes[$startSlotIdx])
                 && $this->startTimes[$startSlotIdx]['real']) {

          $returnedSlots = 2;
      }


      $out = array();  // need current and next real timeslots in the array
      for ($numSlots = $returnedSlots; $numSlots > 0; $numSlots--, $startSlotIdx++) {

          $startSlotIdx = $this->getNextRealTimeSlotIdx($startSlotIdx);

          if (    isset($this->startTimes[$startSlotIdx])
               && $this->startTimes[$startSlotIdx]['real']) { // valid timeslot

              $out[] = ['s' => $this->asHHMMSS($this->startTimes[$startSlotIdx]['s']),
                        'e' => $this->asHHMMSS($this->startTimes[$startSlotIdx]['e'])];
          }
      }
      $this->outSlots = $out;
      return $out;
  }

  /**
   * find required timeslot using a nodified binary search on $startTimes
   *
   * This can be used to find the next valid timeslot so we need to return
   * various conditions:
   *
   *  o  -1           -- timeNow is before the first valid timeslot
   *  o  0 .. n       -- timeslot (real or not) that is within the array
   *  o  PHP_MAX_INT  -- timeNow is after the end of the array
   *
   * @param string   current time
   * @param integer  startRange  to  timeslots to search
   * @param integer  endRange  of timeslots  to search
   * @return integer index
   */
  protected function searchStartTimes($timeNow, $rangeStart, $rangeEnd) {

//      \Kint::dump(__METHOD__.__LINE__, $timeNow, $this->asHHMMSS($timeNow), $rangeStart, $rangeEnd);

      while ($rangeStart <= $rangeEnd) {

          // mid point of the range
          $currentIdx = (int) ($rangeStart + ($rangeEnd - $rangeStart) / 2); // see floor()

          if ($timeNow >= $this->startTimes[$currentIdx]['s']) { // possible start key

              // check is within the end of the timeSlot
              if ($timeNow <= $this->startTimes[$currentIdx]['e']) { // found it
                  return $currentIdx; // finished
              }

              // not found correct time slot yet - search upper range
              if ($timeNow >= $this->startTimes[$currentIdx]['s']) {
                  $rangeStart = $currentIdx + 1;
              }

          } else {
            // timeNow is after current StartTime  - go find a lower range
              $rangeEnd = $currentIdx - 1;
          }
      } // endwhile

      return $rangeEnd < 0 ? -1 : PHP_INT_MAX; // not in the array
  }

  /**
   * Find the next 'real' timeSlot in the array
   *
   *  The input can be:
   *     o Before the first time in the array
   *     o On a timeSlot in the array
   *     o On a 'gap' in the array
   *
   *  PHP_INT_MAX indicates not in the array.
   *
   * @param  integer Current timeslot position
   * @return integer
   */
  protected function getNextRealTimeSlotIdx($startSlotIdx) {

      while (    $startSlotIdx < 0
             || ( isset($this->startTimes[$startSlotIdx])
                  && !$this->startTimes[$startSlotIdx]['real'])) {

          $startSlotIdx++;
      }

      if (!isset($this->startTimes[$startSlotIdx])) {
          $startSlotIdx = PHP_INT_MAX;
      }

      return $startSlotIdx;
  }

  /**
   *  get any information from the class. It is maintained correctly
   */
  public function __get($name) {
     if (property_exists($this, $name)) {
        return $this->$name;
     }
     return null;
  }

  public function asSeconds($hhmmss) {
      return strtotime($hhmmss);
  }

  public function asHHMMSS($seconds) {
      $this->dateWhen->setTimestamp($seconds);
      return $this->dateWhen->format('H:i:s');
  }

} // end class