<?php

class Location
{

	/** @var ?array */
	private static $flatLocationCache = null;
	/** @var ?array */
	private static $assocLocationCache = null;

	/**
	 * Get a nested array of locations. Each element in the array represents a top-level
	 * location, and locations with have child-nodes will have a 'children' key that again
	 * contains an array of location elements, with 'children' as appropriate, and so on.
	 * If you pass one or more startLocationIds, the tree will be cut down to only contain
	 * the locations given (plus any subtrees they have).
	 * @return array<array{locationid: int, locationname: string, parentlocationd: int, children: array}>
	 */
	public static function getTree(int ...$startLocationId): array
	{
		static $treeCache = null;
		if ($treeCache === null) {
			$treeCache = self::buildTree(self::queryLocations());
		}
		if (empty($startLocationId) || in_array(0, $startLocationId))
			return $treeCache;
		// Subtree, search
		return self::filterTreeByLocations($treeCache, $startLocationId);
	}

	/**
	 * Return a filtered tree that only contains the locations present in $idList, plus their respective
	 * child locations in the 'children' array key, if applicable. Top level elements will only be those
	 * contained in $idList, but not every location given in $idList will be a top level element, as they
	 * might already be present in one of the nested 'children' arrays.
	 * @param array $locationTree part of tree to search in
	 * @param array $idList list of wanted ids
	 * @return array<array{locationid: int, locationname: string, parentlocationd: int, children: array}> filtered tree
	 */
	private static function filterTreeByLocations(array $locationTree, array $idList): array
	{
		$ret = [];
		foreach ($locationTree as $location) {
			if (in_array($location['locationid'], $idList)) {
				$ret[] = $location;
			} elseif (!empty($location['children'])) {
				$ret = array_merge($ret, self::filterTreeByLocations($location['children'], $idList));
			}
		}
		return $ret;
	}

	/**
	 * @return array<array{locationid: int, locationname: string, parentlocationd: int, children: array}>
	 */
	private static function buildTree(array $elements, int $parentId = 0): array
	{
		$branch = array();
		foreach ($elements as $lid => $element) {
			$lid = (int)$lid;
			if ($lid === 0 || $lid === $parentId)
				continue;
			if ($element['parentlocationid'] === $parentId) {
				$children = self::buildTree($elements, $lid);
				if (!empty($children)) {
					$element['children'] = $children;
				}
				$element['locationid'] = $lid;
				$branch[] = $element;
			}
		}
		ArrayUtil::sortByColumn($branch, 'locationname');
		return $branch;
	}

	private static function queryLocations(): array
	{
		static $locationDbCache = null;
		if ($locationDbCache === null) {
			$locationDbCache = Database::queryIndexedList("SELECT locationid, parentlocationid, locationname FROM location");
			foreach ($locationDbCache as &$loc) {
				$loc['parentlocationid'] = (int)$loc['parentlocationid'];
			}
		}
		return $locationDbCache;
	}

	/**
	 * Get all location ids starting from the specified location id.
	 * If $startId is 0, it will return all available location ids.
	 * If $withStart is true, the starting location id will be included in the result.
	 *
	 * @param int $startId The location id to start from (default is 0 to get all location ids).
	 * @param bool $withStart True to include the starting location id in the result (default is false).
	 * @return int[] An array of location ids, including the starting location id if requested.
	 */
	public static function getAllLocationIds(int $startId = 0, bool $withStart = false): array
	{
		if ($startId === 0) {
			$locs = array_keys(self::queryLocations());
		} else {
			$locs = self::getLocationsAssoc();
			if (!isset($locs[$startId]))
				return [];
			$locs = $locs[$startId]['children'] ?? [];
		}
		if ($withStart) {
			$locs[] = $startId;
		}
		return $locs;
	}

	/**
	 * Return row from location table for $locationId.
	 * @return array|bool row from DB, false if not found
	 */
	public static function get(int $locationId)
	{
		return Database::queryFirst("SELECT * FROM location WHERE locationid = :locationId", compact('locationId'));
	}

	/**
	 * Get name of location
	 * @param int $locationId id of location to get name for
	 * @return string|false Name of location, false if locationId doesn't exist
	 */
	public static function getName(int $locationId)
	{
		$locs = self::queryLocations();
		return $locs[$locationId]['locationname'] ?? false;
	}

	/**
	 * Get all the names of the given location and its parents, up
	 * to the root element. Array keys will be locationids, value the names.
	 * @return ?array locations, from furthest to nearest or false if locationId doesn't exist
	 */
	public static function getNameChain(int $locationId): ?array
	{
		$locs = self::queryLocations();
		$ret = [];
		while (isset($locs[$locationId])) {
			$ret[$locationId] = $locs[$locationId]['locationname'];
			$locationId = $locs[$locationId]['parentlocationid'];
		}
		if (empty($ret))
			return null;
		return array_reverse($ret, true);
	}

	/**
	 * Get associative array of locations. Mostly used for working with locations, in contrast to ::getLocations()
	 * @return array<array{locationid: int, locationname: string, parentlocationid: int, parents: int[], children: int[], directchildren: int[], depth: int, isleaf: bool}> All the locations
	 */
	public static function getLocationsAssoc(): array
	{
		if (self::$assocLocationCache === null) {
			self::$assocLocationCache = self::flattenTreeAssoc(self::getTree());
		}
		return self::$assocLocationCache;
	}

	/**
	 * @return array<array{locationid: int, locationname: string, parentlocationid: int, parents: int[], children: int[], directchildren: int[], depth: int, isleaf: bool}> All the locations
	 */
	private static function flattenTreeAssoc(array $tree, array $parents = [], int $depth = 0): array
	{
		$output = [];
		foreach ($tree as $node) {
			$cc = empty($node['children']) ? [] : array_column($node['children'], 'locationid');
			$output[$node['locationid']] = [
				'locationid' => $node['locationid'],
				'parentlocationid' => $node['parentlocationid'],
				'parents' => $parents,
				'children' => $cc,
				'directchildren' => $cc,
				'locationname' => $node['locationname'],
				'depth' => $depth,
				'isleaf' => empty($cc),
			];
			if (!empty($node['children'])) {
				$childNodes = self::flattenTreeAssoc($node['children'], array_merge($parents, [$node['locationid']]), $depth + 1);
				$output[$node['locationid']]['children'] = array_merge($output[$node['locationid']]['children'],
					array_reduce($childNodes, function ($carry, $item) {
						return array_merge($carry, $item['children']);
					}, []));
				$output += $childNodes;
			}
		}
		return $output;
	}

	private static function buildFlatTree(): void
	{
		if (self::$flatLocationCache === null) {
			self::$flatLocationCache = self::flattenTree(self::getTree());
		}
	}

	/**
	 * get locations as flat array - mostly used for rendering a <select>.
	 * @param int|int[] $selected Which locationIDs to mark as selected
	 * @param int $excludeId Which locationID to exclude
	 * @param bool $addNoParent Add entry for "no location" at the top
	 * @param bool $keepArrayKeys Keep location IDs as array index
	 * @return array Locations
	 */
	public static function getLocations($selected = 0, int $excludeId = 0, bool $addNoParent = false, bool $keepArrayKeys = false): array
	{
		self::buildFlatTree();
		$rows = self::$flatLocationCache;
		$del = false;
		unset($row);
		$index = 0;
		foreach ($rows as $key => &$row) {
			if ($del === false && $row['locationid'] == $excludeId) {
				$del = $row['depth'];
			} elseif ($del !== false && $row['depth'] <= $del) {
				$del = false;
			}
			if ($del !== false) {
				unset($rows[$key]);
				continue;
			}
			if ((is_array($selected) && in_array($row['locationid'], $selected)) || $row['locationid'] == $selected) {
				$row['selected'] = true;
				$row['checked'] = 'checked';
			}
			$row['sortIndex'] = $index++;
		}
		if ($addNoParent) {
			$noParent = [
				'locationid' => 0,
				'locationname' => '-----',
				'selected' => $selected === 0,
				'checked' => $selected === 0 || (is_array($selected) && in_array(0, $selected)) ? 'checked' : '',
				'locationpad' => '',
			];
			if ($keepArrayKeys) {
				$rows = array_reverse($rows, true);
				$rows[0] = $noParent;
				$rows = array_reverse($rows, true);
			} else {
				array_unshift($rows, $noParent);
			}
		}
		if ($keepArrayKeys)
			return $rows;
		return array_values($rows);
	}

	private static function flattenTree(array $tree, int $depth = 0): array
	{
		$output = [];
		foreach ($tree as $node) {
			$output[$node['locationid']] = [
				'locationid' => $node['locationid'],
				'parentlocationid' => $node['parentlocationid'],
				'locationname' => $node['locationname'],
				'locationpad' => str_repeat('--', $depth),
				'isleaf'	=> empty($node['children']),
				'depth' => $depth,
			];
			if (!empty($node['children'])) {
				$output += self::flattenTree($node['children'], $depth + 1);
			}
		}
		return $output;
	}

	public static function isLeaf(int $locationid): bool
	{
		if (self::$flatLocationCache !== null)
			return self::$flatLocationCache[$locationid]['isleaf'] ?? false;
		if (self::$assocLocationCache !== null)
			return self::$assocLocationCache[$locationid]['isleaf'] ?? false;
		return empty(self::getAllLocationIds($locationid));
	}

	/**
	 * Get location id for given machine (by uuid)
	 *
	 * @param string $uuid machine uuid
	 * @return ?int locationid, null if no match
	 */
	public static function getFromMachineUuid(string $uuid): ?int
	{
		// Only if we have the statistics module which supplies the machine table
		if (Module::get('statistics') === false)
			return null;
		$ret = Database::queryFirst("SELECT locationid FROM machine WHERE machineuuid = :uuid",
			['uuid' => $uuid]);
		if ($ret === false || !$ret['locationid'])
			return null;
		return (int)$ret['locationid'];
	}

	/**
	 * Get closest location by matching subnets. Deepest match in tree wins.
	 * Ignores any manually assigned locationid (fixedlocationid).
	 *
	 * @param string $ip IP address of client
	 * @param bool $honorRoomPlanner consider a fixed location assigned manually by roomplanner
	 * @return ?int locationid, or null if no match
	 */
	public static function getFromIp(string $ip, bool $honorRoomPlanner = false): ?int
	{
		if (Module::get('statistics') !== false) {
			// Shortcut - try to use subnetlocationid in machine table
			if ($honorRoomPlanner) {
				$ret = Database::queryFirst("SELECT locationid AS loc FROM machine
						WHERE clientip = :ip
						ORDER BY lastseen DESC LIMIT 1", compact('ip'));
			} else {
				$ret = Database::queryFirst("SELECT subnetlocationid AS loc FROM machine
						WHERE clientip = :ip
						ORDER BY lastseen DESC LIMIT 1", compact('ip'));
			}
			if ($ret !== false) {
				if ($ret['loc'] > 0) {
					return (int)$ret['loc'];
				}
				return null;
			}
		}
		return self::mapIpToLocation($ip);
	}

	/**
	 * Combined "intelligent" fetching of locationId by IP and UUID of
	 * client. We can't trust the UUID too much as it is provided by the
	 * client, so if it seems too fishy, the UUID will be ignored.
	 *
	 * @param string $ip IP address of client
	 * @param ?string $uuid System-UUID of client
	 * @return ?int location id, or null if none matches
	 */
	public static function getFromIpAndUuid(string $ip, ?string $uuid): ?int
	{
		$locationId = false;
		$ipLoc = self::getFromIp($ip);
		if ($ipLoc !== null) {
			// Set locationId to ipLoc for now, it will be overwritten later if another case applies.
			$locationId = $ipLoc;
			if ($uuid !== null) {
				// Machine ip maps to a location, and we have a client supplied uuid (which might not be known if the client boots for the first time)
				$uuidLoc = self::getFromMachineUuid($uuid);
				if (self::isFixedLocationValid($uuidLoc, $ipLoc)) {
					$locationId = $uuidLoc;
				}
			}
		}
		return $locationId;
	}

	public static function isFixedLocationValid(?int $uuidLoc, int $ipLoc): bool
	{
		if ($uuidLoc === false)
			return false;
		$uuidLoc = (int)$uuidLoc;
		$ipLoc = (int)$ipLoc;
		if ($uuidLoc === $ipLoc || $uuidLoc === 0)
			return true;
		if ($ipLoc === 0)
			return false; // roomplanner assignment, but no subnet - deny
		// Validate that the location the IP maps to is in the chain we get using the
		// location determined by roomplanner
		$uuidLocations = self::getLocationRootChain($uuidLoc);
		if (!empty(self::$assocLocationCache[$uuidLoc]['children']))
			return false; // roomplanner location isn't actually leaf node, this is not valid
		$idx = array_search($ipLoc, $uuidLocations);
		// If roomplanner loc is max two levels deeper than IP loc, accept
		return $idx !== false && $idx <= 2;
	}

	/**
	 * Get all location IDs from the given location up to the root.
	 *
	 * @return int[] location ids, including $locationId
	 */
	public static function getLocationRootChain(int $locationId): array
	{
		$locs = self::getLocationsAssoc();
		if (!isset($locs[$locationId]))
			return [];
		$chain = $locs[$locationId]['parents'];
		$chain[] = $locationId;
		return array_reverse($chain);
	}

	/**
	 * @return array<array{locationid: int, startaddr: int, endaddr: int}> list of subnets
	 */
	public static function getSubnets(): array
	{
		$res = Database::simpleQuery("SELECT startaddr, endaddr, locationid FROM subnet");
		$subnets = array();
		foreach ($res as $row) {
			settype($row['locationid'], 'int');
			$subnets[] = $row;
		}
		return $subnets;
	}

	/**
	 * @return array<array{locationid: int, subnets: array<array{startaddr:int, endaddr: int}>}> assoc array mapping from locationid to subnets
	 */
	public static function getSubnetsByLocation($recursive = false): array
	{
		$locs = self::getLocationsAssoc();
		$subnets = self::getSubnets();
		// Accumulate - copy up subnet definitions
		foreach ($locs as &$loc) {
			$loc['subnets'] = array();
		}
		unset($loc);
		foreach ($subnets as $subnet) {
			$lid = $subnet['locationid'];
			while (isset($locs[$lid])) {
				$locs[$lid]['subnets'][] = array(
					'startaddr' => $subnet['startaddr'],
					'endaddr' => $subnet['endaddr']
				);
				if (!$recursive)
					break;
				$lid = $locs[$lid]['parentlocationid'];
			}
		}
		return $locs;
	}

	/**
	 * Lookup $ip in subnets, try to find one that matches
	 * and return its locationid.
	 * If two+ subnets match, the one which is nested deeper wins.
	 * If two+ subnets match and have the same depth, the one which
	 * is smaller wins.
	 * If two+ subnets match and have the same depth and size, a
	 * random one will be returned.
	 *
	 * @param string $ip IP to look up
	 * @return ?int locationid ip matches, null = no match
	 */
	public static function mapIpToLocation(string $ip): ?int
	{
		static $subnetMapCache = null;
		if ($subnetMapCache === null) {
			$subnetMapCache = self::getSubnetsByLocation();
		}
		$long = sprintf('%u', ip2long($ip));
		$best = null;
		$bestSize = 0;
		foreach ($subnetMapCache as $lid => $curLocation) {
			if ($best !== null && $curLocation['depth'] < $subnetMapCache[$best]['depth'])
				continue; // Don't even need to take a look
			foreach ($curLocation['subnets'] as $subnet) {
				if ($long < $subnet['startaddr'] || $long > $subnet['endaddr'])
					continue; // Nope
				if ($best !== null // Already have a best candidate
						&& $curLocation['depth'] === $subnetMapCache[$best]['depth'] // Same depth
						&& $bestSize < $subnet['endaddr'] - $subnet['startaddr']) { // Old candidate has smaller subnet
					// So we ignore this one as the old one is more specific
					continue;
				}
				$bestSize = $subnet['endaddr'] - $subnet['startaddr'];
				$best = (int)$lid;
			}
		}
		return $best;
	}

	/**
	 * @return ?int newly determined location
	 */
	public static function updateMapIpToLocation(string $uuid, string $ip): ?int
	{
		$loc = self::mapIpToLocation($ip);
		Database::exec("UPDATE machine SET subnetlocationid = :loc WHERE machineuuid = :uuid",
			['loc' => $loc, 'uuid' => $uuid]);
		return $loc;
	}

}