Requirement: Sort a list of boarding passes with route information so that the 'to' and 'from' of adjacent routes are the same. i.e. An ordered list of destinations.
Demonstration: https://eval.in/662878
The approach I use is to:
- Create partial lists of routes that match the rules
- Merge the partial lists each time the opportunity occurs.
To do this we need fast lookup of adjacent routes.
We need:
- A list of routes keyed by 'from'
- A list of routes keyed by 'to'
- Fast access to the 'partial list' the route is currently in.
Processing:
For each route:
- Add it to the from/to lookup lists
- Add it to the appropriate 'partial list'
This is where it get interesting:
We check to see if the adjacent routes are already in the list. there can be various possibilities:
Note: Adjacent Routes are really important and make the sorting 'not as quick' as we would like.
The issue is that there is no obvious way by comparing routes against each other, to decide, which is 'before' or 'after' the other. What we can compare is whether they are 'directly adjacent' to each other. i.e. 'From' of one matches the 'To' of the other. Or the other way around.
So, the idea is to build 'partial paths' and merge them when we can do so.
1) No match - start a new 'partial path'.
2) 'From' or 'To' match - add to the appropriate list.
3) 'From' and 'to' both match. This mean we can join two 'partial lists' together!
At the end of all the merging there will be one path (RoutePath) that all the routes will point to.
The Code:
BuildPath
The class the processes individual routes and decide which RoutePath to process:
class BuildPath {
/**
*
* Generate partially sorted lists of boarding passes
* when adding one at a time to an output list.
*
* Method:
* o Each route will get appended to the approriate partial list as it processed.
*
* o When the route will join two partial lists then that are merged
*
* Needed:
* o Fast lookup of adjacent routes to find out which list to appended to.
*
* o Fast lookup of the partial list
*/
/**
* Initial source array of boarding passes that hold routes
*
* @var array
*/
private $boardingPasses = null;
/**
* stdClass Route object indexed by 'From' keys
*
* @var array
*/
private $keyFrom = array();
/**
* stdClass Route object indexed by 'To' keys
*
* @var array
*/
private $keyTo = array();
/**
* @return void
*/
public function __construct(array $boardingPasses)
{
$this->boardingPasses = $boardingPasses;
foreach ($boardingPasses as $key => $pass) {
$route = current($pass);
$route->passId = $key; // so I can get as the full data later
$this->addRoute($route);
}
}
public function addRoute($route)
{
/*
* Can new route be joined to an existing route?
*/
// Will this route join two partial lists
if ( $this->canAddFrom($route->from)
&& $this->canAddTo($route->to) ) { // join two partial lists together
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
// add to one list first - it doesn't matter which
$this->getAddFromPath($route->from)->add($route);
// merge the two partial paths together
$this->getAddFromPath($route->from)->merge($this->getAddToPath($route->to));
} elseif ($this->canAddFrom($route->from)) { // add to this ;ist
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$this->getAddFromPath($route->from)->add($route);
} elseif ($this->canAddTo($route->to)) { // add to existing path
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$this->getAddToPath($route->to)->add($route);
} else { // start a new path
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$path = new \RoutePath();
$route->path = $path; // the path may change later
$path->add($route);
// $this->routes[] = $route;
return $route;
}
}
/**
* The original array in path order
*
* @return array
*/
public function getSortedRoutes()
{
$out = array();
foreach($this->getPath()->getRoutes() as $route) {
unset($route->path);
$out[] = $this->boardingPasses[$route->passId];
}
return $out;
}
/*
* All routes should point to the same path
*
* Whatever happens: each route will point to the path it is in :)
*
* So, a scan of all the routes for different paths will find all the partial paths :)
*/
public function getPath()
{
reset($this->keyFrom);
return current($this->keyFrom)->path;
}
// helpers
public function canAddFrom($from)
{
return isset($this->keyTo[$from]);
}
public function canAddTo($to)
{
return isset($this->keyFrom[$to]);
}
public function getAddFromPath($from)
{
return $this->keyTo[$from]->path;
}
public function getAddToPath($to)
{
return $this->keyFrom[$to]->path;
}
}
RoutePath
The class that holds the 'partial list' of adjacent routes:
class RoutePath {
private $path = array();
/**
* Add the route to the appropriate end of the list
*
* @param stdClass $route
*
* @return void
*/
public function add($route)
{
$route->path = $this; // ensure it pounts to correct path
if (empty($this->path)) {
array_push($this->path, $route);
} elseif ($this->canAddFrom($route->from)) {
array_push($this->path, $route);
} elseif ($this->canAddTo($route->to)) {
array_unshift($this->path, $route);
} else {
throw new \Exception('Cannot add node: From: '. $route->from . ', To: '. $route->to, 500);
}
}
/**
* Merge two partial lists together
*
* o Decide which list to append to
*
* o Update all the routes to point to rthe merged path
*
* @param RoutePath $path
*
* @return void
*/
public function merge(\RoutePath $path)
{
if ($this->canAddFrom($path->getFrom())) {
$path->updateRoutePath($this);
$this->path = array_merge($this->path, $path->getpath());
} elseif ($this->canAddTo($path->getTo())) {
$path->merge($this);
} else {
throw new \Exception('Cannot merge paths: '
. ' (this): From: '. $this->getFrom() .', To: '. $this->getTo()
. ' (path): From: '. $path->getFrom() .', To: '. $path->getTo()
, 500);
}
}
/**
* Make all the routes point to the correct list
*
* @param RoutePath $path
*
* @return void
*/
public function updateRoutePath(\RoutePath $path)
{
foreach ($this->path as $route) {
$route->path = $path;
}
}
// always check the first entry in the list
public function canAddTo($to)
{
return $this->getFrom() === $to;
}
// alway check last entry in the list
public function canAddFrom($from)
{
return $this->getTo() === $from;
}
public function getFrom()
{
reset($this->path);
return current($this->path)->from;
}
public function getTo()
{
return end($this->path)->to;
}
public function getpath()
{
return $this->path;
}
public function getRoutes()
{
return $this->path;
}
}
Run it and show output:
$path = new BuildPath($passes);
// print output...
echo '<pre>Sorted...', PHP_EOL;
print_r($path->getSortedRoutes());
echo '</pre>';
Sample Output:
Sorted...
Array
(
[0] => Array
(
[planner\boarding\BoardingPasses] => stdClass Object
(
[from] => Madrid
[to] => Barcelona
[passId] => 1
)
)
[1] => Array
(
[planner\boarding\BoardingPasses] => stdClass Object
(
[from] => Barcelona
[to] => Gerona Airport
[passId] => 3
)
)
[2] => Array
(
[planner\boarding\BoardingPasses] => stdClass Object
(
[from] => Gerona Airport
[to] => Stockholm
[passId] => 0
)
)
[3] => Array
(
[planner\boarding\BoardingPasses] => stdClass Object
(
[from] => Stockholm
[to] => New York JFK
[passId] => 2
)
)
)
Test Data:
$passes = Array(
0 => array('planner\boarding\BoardingPasses' =>
(object) array('from' => 'Gerona Airport', 'to' => 'Stockholm')
),
1 => array('planner\boarding\BoardingPasses' =>
(object) array('from' => 'Madrid', 'to' => 'Barcelona')
),
2 => array('planner\boarding\BoardingPasses' =>
(object) array('from' => 'Stockholm', 'to' => 'New York JFK')
),
3 => array('planner\boarding\BoardingPasses' =>
(object) array('from' => 'Barcelona', 'to' => 'Gerona Airport')
),
);
