q40505794 - Generate optimal list of non-overlapping dates

<?php // http://stackoverflow.com/questions/40505794/how-to-push-the-next-date-time-to-array-which-fits-around-current-date-times-in

// see Dynamic programming: http://stackoverflow.com/questions/3243234/algorithm-to-find-the-maximum-sum-in-a-sequence-of-overlapping-intervals

// include __DIR__ .'/__bootstrap__.php'; // all my stuff :)

/*
 * I tend to:
 *   1) break things down to small functions so it looks like a lot of code.
 *
 *   2) use intermediate variables to store partial results so I can easily use them
 *      in later conditions. Is just easier to read when developing the code
 *
 *   3) Sort lists / Arrays so I can reason about them easier.
 *      It also tends to reduce the number of passes but you have the cost of the sort.
 *
 *   4) If there are more than a couple of 'helper' functions then I will use a 'class'
 *      It is just easier to reason about and saves having to pass data structures about.
 *
 *   5) I will refactor the code later to remove all the redundancy. ;-/
 *      First, get something that works and is easy to understand?
 */

/*
 *  Requirements:
 *
 *    Input:
 *        1) given a list of 'chosen' dates
 *        2) A list of 'candidate' dates
 *
 *    Output:
 *      1) A 'final list of 'none-overlapping' dates
 *
 *         Where:
 *           a) All the chosen dates are in the final list.  !important
 *
 *           b) NO Date ranges can Overlap.                  !important
 *
 *       !!  c) The 'Maximum amount of time' between the chosen dates
 *              MUST be utilised.                            !important
 *
 *              i.e. if there is a gap of 15 minutes between chosen dates and
 *                   1) There is a date range of 10 numisted that will fit
 *
 *                   OR
 *
 *                   2) Two data ranges that total 15 minutes that fit then
 *                      we must find the two date ranges
 *
 *
 *           d) The first (least start time) 'chosen' data is a 'start' date
 *              i.e. All candidate dates must be on or after this date.
 *
 *           e) The last chosen date (max end date) is the 'end date'
 *
 *           f) There can be any number of none-ovelapping chosen dates between the
 *              chosen start and chosen end.
 *
 *  Nice to have: run in some reasonable amount of time... more on this later...
 */

/* ---------------------------------------------------------------------------------
 * Class that does all the work...
 */

/*
 *  Requirements:
 *
 *    Input:
 *        1) given a list of 'chosen' dates
 *        2) A list of 'candidate' dates
 *
 *    Output:
 *      1) A 'final list of 'none-overlapping' dates
 *
 *         Where:
 *           a) The first 'chosen' data is a 'start' date
 *              i.e. All candidate dates must be on or after this date.
 *
 *           b) No date ranges must ovevlap.
 */

class ScheduleList
{
    /**
    * A list of all the dates that:
    *   1) After the 'chosen' start date
    *   2) Do not overlap with any 'chosen' date
    *
    * @var array $candidates
    */
    private $candidates = array();

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

    /**
    * List of dates that must be included in the 'final' list.
    * The earliest date is assumed to be a start date and everything must be later.
    *
    * @var array $chosen
    */
    private $chosen = array();

    /**
    * List of dates ranges that candidate dates must be between
    *
    * @var array $ranges
    */
    private $ranges = array();

    /**
    * Ordered list of `none overlapping' dates from the chosen 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();

    /**
    * These are the date lists.
    * They will be converted, sorted and filters as required.
    *
    * @param array $chosenDates
    * @param array $candidateDates
    * @return void
    */
    public function __construct(array $chosenDates = array(),
                                array $candidateDates = array(),
                                array $ranges = array())
    {
        if (!empty($ranges)) {
            $this->setRanges($ranges);
        }

        if (!empty($chosenDates)) {
            $this->setChosen($chosenDates);
        }

        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 chosen 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 ;-/
    *
    * @return array
    */
    public function generateList()
    {
        $bestList = array();
        foreach ($this->ranges as $range) {

            $availableList = $this->getAllDatesWithinRange($range);

            $whenList = $this->bestFitDates($range,
                        $availableList['chosen'],
                        $availableList['candidates']);

            $bestList = array_merge($bestList, $whenList);
        }


        // sort final by start times - makes it easy to reason about
        usort($bestList,
              function ($when1, $when2) {
                    return $when1['startTime'] - $when2['startTime'];
              });

        $this->final = $bestList;

        return $bestList;
    }


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

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

          $this->currentPath = array();

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

          $this->maxDuration($chosen,
                             $candidates,
                             count($candidates) - 1,
                             $rangeDuration - $totalChosenDuration,
                             $totalChosenDuration);

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


    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
         */
        $this->maxDuration($currentWhenList,
                           $candidates,
                           $candidateIdx - 1,
                           $availableDuration,
                           $totalDuration,
                           'unused');


        /*
         * Used path
         */

        if ($this->isOverlapAny($candidates[$candidateIdx], $currentWhenList)) {
            return false;
        }

        // 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) {
            $key = $candidates[$candidateIdx]['key'];
            $currentWhenList[$key] = $candidates[$candidateIdx]; // add to list

            $this->maxDuration($currentWhenList,
                               $candidates,
                               $candidateIdx - 1,
                               $availableDuration,
                               $newTotalDuration,
                               'used ');

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

        } else {
            $usedPath = $currentWhenList;
        }

        return true;
    }

    /**
    * Convert ranges to date range and sort them
    *
    * @param array $chosenDates
    */
    public function setRanges(array $dates)
    {
        $this->ranges = $this->convertDateList($dates);
    }

    /**
    * Convert chosen dates to date range and sort them
    *
    * @param array $chosenDates
    */
    public function setChosen(array $dates)
    {
        $this->chosen = $this->convertDateList($dates, true);
    }

    /**
    * setter for candidates - will convert to date range
    *
    * @param array $candidateDates
    *
    * @return void;
    */
    public function setCandidates(array $dates)
    {
        $dateList = $this->convertDateList($dates);

        // filter the candidates
        $this->filterCandidates($dateList);
    }


   /*
    * Convert each date to a dateRange that is easier to check and display
    *
    * o Check each candidate date for ovelapping with any of the 'chosen dates'
    * o Check if before first chosen start data.
    */
    protected function filterCandidates(array $candidates)
    {
        $startTime = $this->ranges[0]['startTime'];
        foreach ($candidates as $candidate) {

            // overlaps with any chosen then ignore it
            if ($this->isOverlapAny($candidate, $this->chosen)) { // ignore it
                $candidate['fail'] = 'overlap chosen';
                $this->unused[] = $candidate;  // record failed ones so easy to check
                continue;
            }

            // ignore if before start time
            if ($candidate['startTime'] <=  $startTime) {
                $candidate['fail'] = 'before start';
                $this->unused[] = $candidate;   // record failed ones so easy to check
                continue;
            }

            if (!$this->insideRangeAny($candidate, $this->ranges)) { // ignore it
                $candidate['fail'] = 'overlap range';
                $this->unused[] = $candidate;  // record failed ones so easy to check
                continue;
            }


            $this->candidates[] = $candidate;
        }
    }


    public function getAllDatesWithinRange(array $range)
    {
        $whenList = array('chosen' => array(), 'candidates' => array());

        foreach ($this->chosen as $when) {
            if ($this->insideRange($when, $range)) {
                $whenList['chosen'][] = $when;
            }
        }

        foreach ($this->candidates as $when) {
            if ($this->insideRange($when, $range)) {
                $whenList['candidates'][] = $when;
            }
        }

        return $whenList;
    }


    /**
     * if start is after other end OR end is before other start then they don't overlap
     *
     * Easiest way is to check that they don't overlap and reverse the result
     */
    public function isOverlap($when1, $when2)
    {
        return ! (    $when1['endTime'] <= $when2['startTime']
                   || $when1['startTime'] >= $when2['endTime']);
    }

    /**
    * 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
    */
    function isOverlapAny(array $candidate, array $whenList)
    {
        foreach ($whenList as $when) {
            if ($this->isOverlap($when, $candidate)) { // ignore it
               return true;
            }
        }
        return false;
    }

    /**
     *
     */
    public function insideRange(array $when, array $range)
    {
        return   (    $when['startTime'] >= $range['startTime']
                   && $when['endTime'] <= $range['endTime']);
    }

    public function insideRangeAny(array $when, array $ranges)
    {
        foreach ($ranges as $range) {
            if ($this->insideRange($when, $range)) {
               return true;
            }
        }
        return false;
    }

    public function convertDateList(array $dates, $isChosen = false)
    {
        $list = array();

        // convert and sort
        foreach ($dates as $when) {
            $dtRange = $this->makeDateRange($when, $isChosen);
            $list[] = $dtRange;
        }

        if (count($list) > 1) { // sort them so we can easily compare against them
            usort($list,
                  function ($when1, $when2) {
                       return $when1['startTime'] - $when2['startTime'];
                  });
        }

        return $list;
    }

    /**
     * Convert to UNIX timestamp as seconds will make the calculations easier
     *
     * The result has:
     *   1) the time as a date object - I can do calculations / format it whatever
     *   2) startTime as epoch seconds
     *   3) endTime as epoch seconds
     *
     * @param array $when
     *
     * @return array
     */
    public function makeDateRange(array $when, $isChosen = false)
    {
        $dt = \DateTime::createFromFormat('Y-m-d H:i:s', $when['date']);
        $result = array();
        $result['when']   = $dt;
        $result['duration'] = (int) $when['duration'];
        $result['startTime']  = (int) $dt->format('U');
        $result['endTime']  = (int) $result['startTime'] + $when['duration'];
        $result['key'] = $result['startTime'] .'|'. $result['endTime'];
        $result['isChosen'] = $isChosen;

        return $result;
    }

    public function displayWhenList(array $whenList, $title = 'whenList', $sort = true)
    {
        if ($sort) {
            usort($whenList,
                  function ($when1, $when2) {
                    return $when1['startTime'] - $when2['startTime'];
                  });
        }

        echo PHP_EOL, PHP_EOL, $title;

        foreach ($whenList as $when) {
            $this->displayWhen($when);
        }
        echo '<pre>';
    }

    /**
    * Show a date formatted for debugging purposes
    *
    * @param array $when
    * @return void
    */
    public function displayWhen(array $when)
    {
        echo PHP_EOL, 'date: ',   $when['when']->format('Y-m-d H:i:s'),
                      ' len: ',   sprintf('%4d', $when['duration']),
                      ' end: ',   date('Y-m-d H:i:s', $when['endTime']),
                      ' start: ',  $when['startTime'],
                      ' end: ',    $when['endTime'],
                      ' chosen? ', ($when['isChosen'] ? 'true' : 'false'),

                      (!empty($when['fail'])
                         ? ' fail: ' . $when['fail'] : '');
    }


    /*
     *  `Getters` so you can see what happened
     */
    public function getChosen()     { return $this->chosen; }
    public function getRanges()     { return $this->ranges; }
    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;
    }
}