Online PHP editor | rfc for VpOHL

<?php /* // TODO: this structure class Slot { public $index; } */ class Show { private $possibleSlots; function __construct(array $possibleSlots) { $this->possibleSlots = $possibleSlots; } function getNextSlot() { return $this->possibleSlots.next(); } } class Schedule { public $matchings; function __construct(array $matchings) { $this->matchings = $matchings; } function slotAvalible($slot) { return array_key_exists($slot, $matchings); } function getShowAt($slot) { return $matchings[$slot]; } // simple recursive bipartite matching // applies the new matching or returns false if no possible matching function insertShow(Show $newShow) { // store the alternate matching so we can detect loops static $newMatching; // iterate over all possible slots $nextSlot = $newShow->getNextSlot(); if ($nextSlot) { // add to alternate matching $newMatching[$newShow] = $newSlot; // if there is no show set, we are done if ($this->slotAvalible($newSlot)) { $matchings[$newSlot] = $newMatching[$newSlot]; // clean up so we can reuse unset($newMatchings[$newSlot]); return true; } else { // trace path back $nextShow = $this->getShowAt($nextSlot); if (array_key_exists($nextShow, $newMatching)) { // this matching has already been considered so we would enter a loop unset($newMatching[$newShow]); return false; } // find alternate path from the next node in our alternate path $this->insertShow($nextShow); } } else { // no more slots were found for this show return false; } } } // everything below this line is a test $show1 = new Show(array(0,1,2)); $show2 = new Show(array(1)); $show3 = new Show(array(1,2)); $show4 = new Show(array(3)); // TODO: array cannot have objects as keys $initialMatching = array($show1=>1, $show3=>2, $show4=>3); $sched = new Schedule($initialMatching); $sched->insertShow($show2); print_r($sched->matchings); ?>

3v4l.org

Active branches

Archived branches