- print_r: documentation ( source)
- next: documentation ( source)
<?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);
?>