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

function getPath($regionStart, $regionEnd, $onLand) {
	global $list;
    
    $list = [];
    $regionTaxes = [ //currently unused
        $regionStart => 0,
        $regionEnd => 0
    ];
    
	include("serverConnect.php");

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

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

    $result = [
    	"possible" => false,
        "time" => 0,
        "taxes" => 0,
    	"path" => []
    ];

    $done = false;

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

    foreach ($startPoints as $id) {
    	$list[$id] = [
    		"done" => false,
    		"badTerrain" => false,
    		"previous" => 0,
    		"g" => 0,
            "gTaxes" => 0,
    		"f" => minDistance($id, $endPoints)
    	];

    	insertNode($id, $openSet);
    }

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

    	$current = $openSet->dequeue();
		$list[$current]["done"] = true;

		foreach ($endPoints as $end) {
			if ($end == $current) {
				$result = createPath($end);
				return $result; // path found
			}
		}
		

		$nei = getNeighbourgs($current);

		foreach ($nei as $id) {
            $newG = $list[$current]["g"] + 1;
            $newGTaxes = 0;
            
            if (getRegionFromTerritory($current) != getRegionFromTerritory($id)) {
                $req2 = $bdd->prepare('SELECT cUsers.taxes FROM cRegions JOIN cUsers ON cRegions.owner = cUsers.id WHERE cRegions.id = ?');
				$req2->execute(array(getRegionFromTerritory($id)));
                if ($data2 = $req2->fetch()) {
                    $newGTaxes = $data2["taxes"];
                }
            }
            
			if (!array_key_exists($id, $list)) {
				$req = $bdd->prepare('SELECT cTerritories.type FROM cTerritories WHERE cTerritories.id = ?');
				$req->execute(array($id));

				if ($data = $req->fetch()) { //maybe no nei
                    if ($onLand) {
                        $badTerrain = $terrains[$data['type']]['type'] == "water" || $terrains[$data['type']]['type'] == "mountain";
                    }
                    else {
                        $badTerrain = $terrains[$data['type']]['type'] != "water";
                    }
				}
				else {
					$badTerrain = true;
				}
                
                if (!$onLand) {
                    foreach ($endPoints as $end) {
                        if ($end == $id) {
                            $badTerrain = false;
                        }
                    }
                }
                

				if ($badTerrain) {
					$list[$id] = [ // dummy insert
			    	];
				}
				else {
					$list[$id] = [
			    		"done" => false,
			    		"badTerrain" => false,
			    		"previous" => $current,
			    		"g" => $newG,
                        "gTaxes" => $newGTaxes,
			    		"f" => minDistance($id, $endPoints)
			    	];

			    	insertNode($id, $openSet);
				}
			}
			else if (!$list[$id]["done"] && $list[$id]["g"] > $newG){ //node already in list
				$list[$id]["previous"] = $current;
				$list[$id]["g"] = $newG;
				$list[$id]["gTaxes"] = $newGTaxes;

				//Remove old value

				foreach ($openSet as $index => $n) {
					if ($n == $id) {
						$openSet->offsetUnset($index);
					}
				}

				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) {
		if ($list[$n]["g"] + $list[$n]["f"] > $list[$node]["g"] + $list[$node]["f"]) {
			$openSet->add($index, $node);
			return;
		}
	}

	$openSet->push($node);
}

function createPath($end) {
	global $list;

	$result = [
    	"possible" => true,
        "time" => $list[$end]["g"],
        "taxes" => 0,
    	"path" => []
    ];

	$done = false;

	$current = $end;

	while (!$done) {

		$result["path"][] = $current;
        
        $result["taxes"] += $list[$current]["gTaxes"];

		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");
}
?>