<?
$list = []; //all nodes

function getPath($regionStart, $regionEnd, $onLand, $timeRatio) {
	global $list;
    
    $list = [];
    
	include("serverConnect.php");

	$terrains = getTerrainsList();
    
    if ($onLand) {
        $keyTrade = "landTrade";
    }
    else {
        $keyTrade = "seaTrade";
    }

    $startPoints = getTradePosts($regionStart, $keyTrade);
    $endPoints = getTradePosts($regionEnd, $keyTrade);
    
    $startOwner = getRegionOwner($regionStart);
    $endOwner = getRegionOwner($regionEnd);

    $result = [
    	"possible" => false,
        "time" => 0,
        "taxes" => 0,
    	"path" => []
    ];
    
    if (count($endPoints) == 0) {
        return $result;
    }

    $done = false;

    $openSet = new SplQueue(); //all ids of the non evaluated yet nodes

    foreach ($startPoints as $id) {
    	$list[$id] = [
            "goodTerrain" => true,
    		"previous" => 0,
            "owner" => $startOwner,
            "taxes" => 0,
    		"g" => 0,
            "gTime" => 0,
            "gTaxes" => 0,
    		"f" => minDistance($id, $endPoints)
    	];

    	insertNode($id, $openSet);
    }
    
    foreach ($endPoints as $id) {
    	$list[$id] = [
            "goodTerrain" => true,
    		"previous" => 0,
            "owner" => $endOwner,
            "taxes" => 0,
    		"g" => INF,
            "gTime" => INF,
            "gTaxes" => INF,
    		"f" => 0
    	];
    }

    while (!$done) {
    	if ($openSet->count() == 0) {
    		return $result; // no path
    	}

    	$current = $openSet->dequeue();
        $list[$current]["inQueue"] = false;
        
        foreach ($endPoints as $end) {
            if ($end == $current) {
                $result = createPath($end, $startOwner, $endOwner);
                return $result; // path found
            }
        }
        
        $nei = getNeighbourgs($current);
            
        foreach ($nei as $id) {
            
            $newGTime = $list[$current]["gTime"] + 1;
            $newGTaxes = $list[$current]["gTaxes"];
            
            $removeOldValue = true;
                
            if (!array_key_exists($id, $list)) {
                
                $regionId = getRegionFromTerritory($id);
                
                $req = $bdd->prepare('SELECT cRegions.owner, cUsers.taxes FROM cRegions LEFT JOIN cUsers ON cRegions.owner = cUsers.id WHERE cRegions.id = ?');
                $req->execute(array($regionId));
                $data = $req->fetch();
                
                $owner = $data['owner'];
                $taxes = nullIszero($data['taxes']);
                
                $req = $bdd->prepare('SELECT cTerritories.id, cTerritories.type FROM cTerritories WHERE cTerritories.id >= ? AND cTerritories.id <= ?');
                $req->execute(array(getMinTerritoryId($regionId), getMaxTerritoryId($regionId)));
                
                while ($data = $req->fetch()) {
                    $id2 = $data['id'];
                    $type2 = $data['type'];
                    
                    if ($onLand) {
                        $badTerrain = $terrains[$type2]['type'] == "water" || $terrains[$type2]['type'] == "mountain";
                    }
                    else {
                        $badTerrain = $terrains[$type2]['type'] != "water";
                    }
                    
                    if (!array_key_exists($id2, $list)) { //only exists if start/end point
                        $list[$id2] = [
                            "inQueue" => false,
                            "goodTerrain" => !$badTerrain,
                            "previous" => 0,
                            "owner" => $owner,
                            "taxes" => $taxes,
                            "g" => INF,
                            "gTime" => INF,
                            "gTaxes" => INF,
                            "f" => minDistance($id, $endPoints)
                        ];
                    }
                }
                
                $removeOldValue = false;
            }
            
            
            if ($list[$id]["goodTerrain"]) {
                if ($list[$current]["owner"] != $list[$id]["owner"] && $list[$id]["owner"] != $startOwner && $list[$id]["owner"] != $endOwner) {
                    $newGTaxes += $list[$id]["taxes"];
                }
                
                $newG = (1 - $timeRatio) * $newGTime + $timeRatio * $newGTaxes;
                
                if ($list[$id]["g"] > $newG) {
                    $list[$id]["previous"] = $current;
                    $list[$id]["gTime"] = $newGTime;
                    $list[$id]["gTaxes"] = $newGTaxes;
                    $list[$id]["g"] = $newG;

                    //Remove old value

                    if ($list[$id]["inQueue"]) {
                        foreach ($openSet as $index => $n) {
                            if ($n == $id) {
                                $openSet->offsetUnset($index);
                            }
                        }
                    }
                    
                    $list[$id]["inQueue"] = true;

                    insertNode($id, $openSet);
                }
            }
        }	
    }

    return $result;
}

function getTradePosts($regionId, $keyTrade) {
    include("serverConnect.php");

    $a = [];
    
    $buildings = getBuildingsList();
    
    $req = $bdd->prepare('SELECT * FROM cBuildings WHERE territory >= ? AND territory <= ?');
    $req->execute(array(getMinTerritoryId($regionId), getMaxTerritoryId($regionId)));
    
    while ($data = $req->fetch()) {
        if (array_key_exists($keyTrade, $buildings[$data['type']])) { //transport on right terrain
    		$a[] = $data['territory'];
        }
    }

    return $a;
}

function minDistance($current, $goals) {
	$dist = INF;

	foreach ($goals as $goal) {
		$dist = min($dist, distance($current, $goal));
	}
    
    return $dist;
}

function distance($current, $goal) {
	$x1 = getTerritoryX($current);
	$y1 = getTerritoryY($current);
	$x2 = getTerritoryX($goal);
	$y2 = getTerritoryY($goal);

	return sqrt(($x1-$x2) * ($x1-$x2) + ($y1-$y2) * ($y1-$y2));
}

function insertNode($node, $openSet) {
	global $list;

	foreach ($openSet as $index => $n) {
        $nC = $list[$n]["g"] + $list[$n]["f"];
        $nodeC = $list[$node]["g"] + $list[$node]["f"];
        
		if ($nC > $nodeC) {
			$openSet->add($index, $node);
			return;
		}
	}

	$openSet->push($node);
}

function createPath($end, $startOwner, $endOwner) {
	global $list;

	$result = [
    	"possible" => true,
        "time" => $list[$end]["gTime"],
        "taxes" => $list[$end]["gTaxes"],
        "userTaxes" => [],
    	"path" => []
    ];

	$done = false;

	$current = $end;
    $currentOwner = 0;

	while (!$done) {

		$result["path"][] = $current;
        
        if ($list[$current]['owner'] != $currentOwner) {
            $currentOwner = $list[$current]['owner'];
            
            $result["userTaxes"][$currentOwner] += $list[$current]['taxes'];
        }

		if ($list[$current]["previous"] == 0) {
			$done = true;
		}
		else {
			$current = $list[$current]["previous"];
		}
	}

	return $result;
}

function createPathImage($end) {
	global $list;

	$image = imagecreatefrompng("resources/global.png");
	$hexaRed = imagecreatefrompng("resources/small-territories/hexaMask.png");
	$hexaWidth = 25;
	$hexaHalfWidth = 19;
	$hexaHeight = 22;
	$hexaHalfHeight = 10;

	$done = false;

	$current = $end;

	while (!$done) {

		$baseX = getTerritoryX($current) * $hexaHalfWidth;
        $baseY = getTerritoryY($current) * ($hexaHeight - 1);

        if (getTerritoryX($current) % 2 == 1) {
            $baseY += $hexaHalfHeight;
        }

		imagecopy($image, $hexaRed, $baseX, $baseY, 0, 0, 25, 22);

		if ($list[$current]["previous"] == 0) {
			$done = true;
		}
		else {
			$current = $list[$current]["previous"];
		}
	}

	imagepng($image, "tmpPath.png");
}
?>