<?php
/**
 * @author Andy Thompson
 * @copyright Copyright (c) 2010 Andy Thompson
 * @license http://www.webtatic.com/license/new-bsd     New BSD License
 */
$start = array('Ibuildings Office in London', deg2rad(51.58701), deg2rad(-0.23029));
$end = array('Dutch PHP Conference', deg2rad(52.34139), deg2rad(4.88833));

if (file_exists($_SERVER['argv'][1]) && ($csvHandle = fopen($_SERVER['argv'][1], 'r')) !== false) {
    $landmarks = array($start, $end);
    $edges = $edgeCounts = array();

    fgetcsv($csvHandle);
    $landmarkCount = 2;
    while (($landmark = fgetcsv($csvHandle)) !== false) {
        $landmark[1] = deg2rad($landmark[1]);
        $landmark[2] = deg2rad($landmark[2]);
        foreach ($landmarks as $key => $landmarkB) {
            $edges[] = array($key, $landmarkCount, distanceBetweenLandmarks($landmark, $landmarkB));
        }
        $landmarks[] = $landmark;
        $landmarkCount++;
    }
    fclose($csvHandle);
}

$root = (object) array(
    'edges' => $edges,
    'include' => array(),
    'exclude' => array_fill_keys(range(0, $landmarkCount-1), $landmarkCount - 3),
    'clusters' => array(),
    'lowerBound' => null,
);

lowerBound($root, $landmarks);
$stack = array($root);
$bestTour = null;

while ($next = array_pop($stack)) {
    if (count($next->edges) == 0) {
        if ($bestTour == null || $next->lowerBound < $bestTour->lowerBound) {
            $bestTour = $next;
        }
    } else if ($bestTour == null || $bestTour->lowerBound > $next->lowerBound) {
        $nodes = array(clone $next, clone $next);

        $nodes[0]->include[] = $n = array_shift($nodes[0]->edges);
        $nodes[0]->clusters = addToClusters($nodes[0]->clusters, $n, $landmarkCount);

        $n = array_shift($nodes[1]->edges);
        $nodes[1]->exclude[$n[0]]--;
        $nodes[1]->exclude[$n[1]]--;

        foreach ($nodes as $key => $node) {
            if (improveConstraints($node, $landmarkCount)) {
                lowerBound($node, $landmarks);
            } else {
                unset($nodes[$key]);
            }
        }
        usort($nodes, function($a, $b) {
            return $b->lowerBound - $a->lowerBound;
        });
        array_splice($stack, count($stack)-1, 0, $nodes);
    }
}

if ($bestTour !== null) {
    $landmark = 0;
    $tourEdges = $bestTour->include;
    echo $landmarks[$landmark][0] . PHP_EOL;
    while (count($tourEdges) > 0) {
        foreach ($tourEdges as $key => $edge) {
            if ($edge[0] == $landmark && ($landmark = $edge[1])
                    || $edge[1] == $landmark && ($landmark = $edge[0])) {
                echo $landmarks[$landmark][0] . PHP_EOL;
                unset($tourEdges[$key]);
                break;
            }
        }
    }
}

function addToClusters($clusters, $edge, $nodeCount) {
    $clusterA = $clusterB = null;
    foreach ($clusters as $key => $cluster) {
        if (array_key_exists($edge[0], $cluster)) {
            $clusterA = $key;
        }
        if (array_key_exists($edge[1], $cluster)) {
            $clusterB = $key;
        }
    }
    if ($clusterA === null) {
        if ($clusterB === null) {
            $clusters[] = array($edge[0] => 1, $edge[1] => 1);
            return $clusters;
        } else {
            $clusterA = $clusterB;
        }
    } else if ($clusterB !== null && $clusterA != $clusterB) {
        $clusters[$clusterA] += $clusters[$clusterB];
        unset($clusters[$clusterB]);
    }

    if (isset($clusters[$clusterA][$edge[0]])) {
        $clusters[$clusterA][$edge[0]]++;
    } else {
        $clusters[$clusterA][$edge[0]] = 1;
    }

    if (isset($clusters[$clusterA][$edge[1]])) {
        $clusters[$clusterA][$edge[1]]++;
    } else {
        $clusters[$clusterA][$edge[1]] = 1;
    }

    $clusterNonTour = checkCluster($clusters[$clusterA]);

    if ($clusterNonTour == -1 || ($clusterNonTour == 1 && (count($clusters) != 1 || count(current($clusters)) < $nodeCount))) {
        return null;
    } else {
        return $clusters;
    }
}

function checkCluster($cluster) {
    $d = false;
    foreach ($cluster as $node => $count) {
        $max = $node < 2 ? 1 : 2;
        if ($count > $max) {
            return -1;
        } else if ($count < $max) {
            $d = true;
        }
    }
    return $d ? 0 : 1;
}

function improveConstraints($node, $landmarkCount) {
    $node->lowerBound = null;
    $search = true;
    while ($search) {
        $search = false;
        foreach ($node->edges as $key => $edge) {
            $clusters = addToClusters($node->clusters, $edge, $landmarkCount);
            $include = $node->exclude[$edge[0]] == 0
                || $node->exclude[$edge[1]] == 0;
            $exclude = $clusters == null;

            if ($include && $exclude) {
                return false;
            } else if ($include) {
                $node->include[] = $edge;
                unset($node->edges[$key]);
                $node->clusters = $clusters;
                $search = true;
                break;
            } else if ($exclude) {
                unset($node->edges[$key]);
                $node->exclude[$edge[0]]--;
                $node->exclude[$edge[1]]--;
                $search = true;
                break;
            }
        }
    } ;

    return true;
}

function filterEdges($edges, $landmark) {
    $include = array();
    foreach ($edges as $edge) {
        if ($landmark == $edge[0] || $landmark == $edge[1]) {
            $include[] = $edge[2];
        }
    }
    return $include;
}

function lowerBound($node, $landmarks) {
    $count = 0;
    foreach ($landmarks as $landmark => $null) {
        $countEdges = $landmark < 2 ? 1 : 2;
        $include = filterEdges($node->include, $landmark);

        if (count($include) == $countEdges) {
            $edges = $include;
        } else {
            $other = filterEdges($node->edges, $landmark);
            sort($other);
            $edges = array_slice(array_merge($include, $other), 0, $countEdges);
        }
        $count += array_sum($edges);
    }
    $node->lowerBound = $count / 2;
}

function distanceBetweenLandmarks($landmarkA, $landmarkB)
{
    $a = pow(sin(($landmarkA[1] - $landmarkB[1]) / 2), 2)
        + cos($landmarkA[1]) * cos($landmarkB[1])
        * pow(sin(($landmarkA[2] - $landmarkB[2]) / 2), 2);
    return 2 * atan2(sqrt($a), sqrt(1 - $a));
}