TimeSlotRange (SO Question 40505794)

/* ---------------------------------------------------------------------------------
 * Process One range of TimeSlots
 */

/*
 *  Requirements:
 *
 *    Input:
 *        1) One date range that will contain the optimal list of timeslots
 *        2) list of 'required' dates    - these are fixed and will always be in the final list
 *        3) A list of 'candidate' dates - fit as many of these in as we can.
 *
 *    Output:
 *      1) A 'final list of 'none-overlapping' dates
 *         Where:
 *           a) will contain all the 'required dates'
 *           b) as many candidates as will fit
 *           c) No timeslot will have overlapping dates.
 *
 *    Note: There is no validation done in this class.
 *          see TimeSlotList for validation / filtering of the range
 */

class TimeSlotRange
{
    /**
    *  All the candidate timeslots that don't overlap with any 'required' date
    *
    * @var array $candidates
    */
    private $candidates = array();

    /**
    * Any timeslot record we didn't use.
    *
    * @var array $unused
    */
    private $unused = array();

    /**
    * List of dates that must be included in the 'final' list.
    * There must not be any overlapping ranges
    *
    * @var array $required
    */
    private $required = array();

    /**
    * Timeslot range all dates must be between
    *
    * @var array $ranges
    */
    private $range = null;

    /**
    * Ordered list of 'none overlapping' dates from the Required and candidates
    *
    * @var array $final
    */
    private $final = array();


    /**
    * Current List of paths with associated score
    *
    * The top one is the current best one
    */
    private $currentPath = array();


    /**
    * Check if candidate overlaps any of the dates in the list
    *
    * @param array $candidate
    * @param array $whenList  -- list of non-overlapping dates
    *
    * @return boolean  true if overlaps
    */
    public static function isOverlapAny(ITimeSlot $candidate, $whenList)
    {
        foreach ((array) $whenList as $when) {
            if ($candidate->isOverlap($when)) { // ignore it
               return true;
            }
        }
        return false;
    }


    /**
    * These are the date lists.
    * They will NOT be filtered or validated. see TimeSlotList for that
    *
    * @range ITimeSlot $range
    * @param array     $requiredDates
    * @param array     $candidateDates
    * @return void
    */
    public function __construct(ITimeSlot $range,
                                array $requiredDates = array(),
                                array $candidateDates = array())
    {
        if (!empty($range)) {
            $this->setRange($range);
        }

        if (!empty($requiredDates)) {
            $this->setRequired($requiredDates);
        }

        if (!empty($candidateDates)) {
            $this->setCandidates($candidateDates);
        }
    }

    /**
    * Add the candidates to the final list
    *
    *   Known conditions:
    *     o  Both lists are in start date order
    *     o  No candidates overlap with any Required date
    *     o  The candidates may overlap with each other - Hmm... need to check...
    *
    *  Note: The '$this->isOverlapsAny' method - as it is used a lot will be expensive (O(n^2))
    *        I can think of ways to reduce that - will happen when it is  refactored ;-/
    *
    *        This version uses the 'brute force'path search.
    *
    * @return array
    */
    public function generateList()
    {
        $whenList = $this->bestFitDates($this->range,
                                        $this->required,
                                        $this->candidates);


        // sort final by start times - makes it easy to reason about
        $this->sortStartTime($whenList);

        $this->final = $whenList;

//        $this->unused = array_diff($this->final, $this->candidates);

        // sort final by start times - makes it easy to reason about
//        $this->sortStartTime($this->unused);

        return $this->final;
    }

    /**
    * Build and walk a 'decision tree'. This will be 'interesting' ;-/
    *
    * @return array list of timeslots that will fit in the range
    */
    public function bestFitDates(ITimeSlot $range,
                                 array $required,
                                 array $candidates)
    {
          $rangeDuration = $range['duration'];

          $totalRequiredDuration = 0;
          foreach ($required as $when) {
              $totalRequiredDuration += $when['duration'];
          }

          $this->currentPath = array();

          $bestPath = array('path' => $required, 'score' => $totalRequiredDuration);
          array_push($this->currentPath, $bestPath);

          $this->maxDuration($required,
                             $candidates,
                             count($candidates) - 1,
                             $rangeDuration - $totalRequiredDuration,
                             $totalRequiredDuration);


          return array_pop($this->currentPath)['path']; // best path
    }

    /**
    * The algorithn creates and walks a 'binary decision tree' using 'unused' and 'used' branches
    * for the current timeslot.
    *
    * The method is to
    *     o create a list of the timeslots by adding and removing one of the candiates
    *       at a time.
    *
    *     o Keep a score for the list which is just the sum of all the durations of all the
    *       current timeslots in the list
    *
    *     o if the current score is higher than any found so far then record this as the 'best' list
    *        see: $this->currentPath
    *
    *
    *
    * @param array     $currentWhenList    The current complete list of timeslots we are checking
    * @param array     $candidates         The complate list of candidate timeslots to use
    * @param integer   $candidateIdx       The index of the current candidate we are checking
    * @param integer   $availableDuration  The total amount of time that is available top use
    * @param integer   $totalDuration      The total duration of the path so far (score)
    * @param string    $whichPath          Debugging - show which node branch currently being processed
    *
    * @return boolean  True when reached a leaf node, false when 'cannot continue'
    */
    public function maxDuration($currentWhenList,
                                $candidates,
                                $candidateIdx,
                                $availableDuration,
                                $totalDuration,
                                $whichPath = '')
    {
        // check whether current path has higher score than current
        $topPath = end($this->currentPath);
        if ($totalDuration > $topPath['score']) { // save it

            $bestPath = array('path' => $currentWhenList, 'score' => $totalDuration);
            array_push($this->currentPath, $bestPath);
        }

        if ($candidateIdx < 0) { // no more candidates
           return true;
        }


        /*
         * Unused path  - don't add the current 'candidate' timeslot
         *
         *                Always check the 'unused' branch first
         */
        $this->maxDuration($currentWhenList,
                           $candidates,
                           $candidateIdx - 1,
                           $availableDuration,
                           $totalDuration,
                           'unused');

        /*
         * Used path  - add the current candidate timeslot...
         *
         *              o It may take us over the limit of duration
         *              o It may overlap with others already in the list!
         */

        // assume we are going to use it:
        // Calculate all the new stuff as we are going to use the candidate
        $newAvailableDuration = $availableDuration - $candidates[$candidateIdx]['duration'];
        $newTotalDuration  = $totalDuration + $candidates[$candidateIdx]['duration'];

        if ($newAvailableDuration < 0) { // it will not fit
            return false;
        }

        // will it overlap with any existing timeslots already in the list?
        if ($this->isOverlapAny($candidates[$candidateIdx], $currentWhenList)) {
            return false;
        }


        // add it to the current candidate list and recurse to check the other candidates

        $key = $candidates[$candidateIdx]->getKey();
        $currentWhenList[$key] = $candidates[$candidateIdx]; // add to list

        $this->maxDuration($currentWhenList,       // list of candidates being tried
                           $candidates,
                           $candidateIdx - 1,      // ensure we check the next candidate !important
                           $newAvailableDuration,
                           $newTotalDuration,
                           'used ');

        unset($currentWhenList[$key]); // remove it from the list!

        return true;
    }


    /**
    * Used to check if a timeslot will completely fit in this range
    *
    * @param ITimeSlot $when
    *
    * @return boolean true when inside
    */
    public function isInsideRange(ITimeSlot $when)
    {
        return $this->range->isInside($when);
    }

    /**
    * date range
    *
    * @param array $range
    */
    public function setRange(ITimeSlot $range)
    {
        $this->range = $range;
    }


    /**
    * date range and sort them
    *
    * @param array $requiredDates
    */
    public function setRequired(array $dates)
    {
        foreach ($dates as $date) {
            $date->setIsRequired();
            $this->required[] = $date;
        }

        // sort final by start times - makes it easy to reason about
        $this->sortStartTime($dates);
        $this->required = $dates;
    }

    /**
    * setter for candidates
    *
    * @param array $candidateDates
    *
    * @return void;
    */
    public function setCandidates(array $dates)
    {
        $this->sortStartTime($dates);

        $this->candidates = $dates;

    }

    public function sortEndTime(&$timeSlots)
    {
        // sort by end times - makes it easy to reason about
        usort($timeSlots,
              function ($when1, $when2) {
                    $order = $when1['endTime'] - $when2['endTime'];
                    if ($order === 0) { // want the largest first
                        return $when2['duration'] - $when1['duration'];
                    }
                    return $order;
              });

        return;
    }

    public function sortStartTime(&$timeSlots)
    {
        // sort by end times - makes it easy to reason about
        usort($timeSlots,
              function ($when1, $when2) {
                    $order = $when1['startTime'] - $when2['startTime'];
                    if ($order === 0) { // want the largest first
                        return $when2['duration'] - $when1['duration'];
                    }
                    return $order;
              });

        return;
    }

    /*
     *  `Getters` so you can see what happened
     */
    public function getRequired()   { return $this->required; }
    public function getRange()      { return $this->range; }
    public function getUnused()     { return $this->unused; }
    public function getCandidates() { return $this->candidates; }
    public function getFinal()      { return $this->final; }

    /**
    * properties - for those of us that like them
    */
    public function __get($name)
    {
        if (property_exists($this, $name)) {
            return $this->$name;
        }
        return null;
    }
}