/*
 * Copyright 2010 Aalto University, ComNet
 * Released under GPLv3. See LICENSE.txt for details.
 */
package movement;

import input.WKTMapReader;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Vector;

import movement.map.MapNode;
import movement.map.SimMap;
import core.Coord;
import core.Settings;
import core.SettingsError;
import core.SimError;

/**
 * Map based movement model which gives out Paths that use the
 * roads of a SimMap.
 */
public class MapBasedMovement extends MovementModel implements SwitchableMovement {
	/** sim map for the model */
	private SimMap map = null;
	/** node where the last path ended or node next to initial placement */
	protected MapNode lastMapNode;
	/**  max nrof map nodes to travel/path */
	protected int maxPathLength = 100;
	/**  min nrof map nodes to travel/path */
	protected int minPathLength = 10;
	/** May a node choose to move back the same way it came at a crossing */
	protected boolean backAllowed;
	/** map based movement model's settings namespace ({@value})*/
	public static final String MAP_BASE_MOVEMENT_NS = "MapBasedMovement";
	/** number of map files -setting id ({@value})*/
	public static final String NROF_FILES_S = "nrofMapFiles";
	/** map file -setting id ({@value})*/
	public static final String FILE_S = "mapFile";

	/**
	 * Per node group setting for selecting map node types that are OK for
	 * this node group to traverse trough. Value must be a comma separated list
	 * of integers in range of [1,31]. Values reference to map file indexes
	 * (see {@link #FILE_S}). If setting is not defined, all map nodes are
	 * considered OK.
	 */
	public static final String MAP_SELECT_S = "okMaps";

	/** the indexes of the OK map files or null if all maps are OK */
	private int [] okMapNodeTypes;

	/** how many map files are read */
	private int nrofMapFilesRead = 0;
	/** map cache -- in case last mm read the same map, use it without loading*/
	private static SimMap cachedMap = null;
	/** names of the previously cached map's files (for hit comparison) */
	private static List<String> cachedMapFiles = null;

	/**
	 * Creates a new MapBasedMovement based on a Settings object's settings.
	 * @param settings The Settings object where the settings are read from
	 */
	public MapBasedMovement(Settings settings) {
		super(settings);
		map = readMap();
		readOkMapNodeTypes(settings);
		maxPathLength = 100;
		minPathLength = 10;
		backAllowed = false;
	}

	/**
	 * Creates a new MapBasedMovement based on a Settings object's settings
	 * but with different SimMap
	 * @param settings The Settings object where the settings are read from
	 * @param newMap The SimMap to use
	 * @param nrofMaps How many map "files" are in the map
	 */
	public MapBasedMovement(Settings settings, SimMap newMap, int nrofMaps) {
		super(settings);
		map = newMap;
		this.nrofMapFilesRead = nrofMaps;
		readOkMapNodeTypes(settings);
		maxPathLength = 100;
		minPathLength = 10;
		backAllowed = false;
	}

	/**
	 * Reads the OK map node types from settings
	 * @param settings The settings where the types are read
	 */
	private void readOkMapNodeTypes(Settings settings) {
		if (settings.contains(MAP_SELECT_S)) {
			this.okMapNodeTypes = settings.getCsvInts(MAP_SELECT_S);
			for (int i : okMapNodeTypes) {
				if (i < MapNode.MIN_TYPE || i > MapNode.MAX_TYPE) {
					throw new SettingsError("Map type selection '" + i +
							"' is out of range for setting " +
							settings.getFullPropertyName(MAP_SELECT_S));
				}
				if (i > nrofMapFilesRead) {
					throw new SettingsError("Can't use map type selection '" + i
							+ "' for setting " +
							settings.getFullPropertyName(MAP_SELECT_S)
							+ " because only " + nrofMapFilesRead +
							" map files are read");
				}
			}
		}
		else {
			this.okMapNodeTypes = null;
		}
	}

	/**
	 * Copyconstructor.
	 * @param mbm The MapBasedMovement object to base the new object to
	 */
	protected MapBasedMovement(MapBasedMovement mbm) {
		super(mbm);
		this.okMapNodeTypes = mbm.okMapNodeTypes;
		this.map = mbm.map;
		this.minPathLength = mbm.minPathLength;
		this.maxPathLength = mbm.maxPathLength;
		this.backAllowed = mbm.backAllowed;
	}

	/**
	 * Returns a (random) coordinate that is between two adjacent MapNodes
	 */
	@Override
	public Coord getInitialLocation() {
		List<MapNode> nodes = map.getNodes();
		MapNode n,n2;
		Coord n2Location, nLocation, placement;
		double dx, dy;
		double rnd = rng.nextDouble();

		// choose a random node (from OK types if such are defined)
		do {
			n = nodes.get(rng.nextInt(nodes.size()));
		} while (okMapNodeTypes != null && !n.isType(okMapNodeTypes));

		// choose a random neighbor of the selected node
		n2 = n.getNeighbors().get(rng.nextInt(n.getNeighbors().size()));

		nLocation = n.getLocation();
		n2Location = n2.getLocation();

		placement = n.getLocation().clone();

		dx = rnd * (n2Location.getX() - nLocation.getX());
		dy = rnd * (n2Location.getY() - nLocation.getY());

		placement.translate(dx, dy); // move coord from n towards n2

		this.lastMapNode = n;
		return placement;
	}

	/**
	 * Returns map node types that are OK for this movement model in an array
	 * or null if all values are considered ok
	 * @return map node types that are OK for this movement model in an array
	 */
	protected int[] getOkMapNodeTypes() {
		return okMapNodeTypes;
	}

	@Override
	public Path getPath() {
		Path p = new Path(generateSpeed());
		MapNode curNode = lastMapNode;
		MapNode prevNode = lastMapNode;
		MapNode nextNode = null;
		List<MapNode> neighbors;
		Coord nextCoord;

		assert lastMapNode != null: "Tried to get a path before placement";

		// start paths from current node
		p.addWaypoint(curNode.getLocation());

		int pathLength = rng.nextInt(maxPathLength-minPathLength) +
			minPathLength;

		for (int i=0; i<pathLength; i++) {
			neighbors = curNode.getNeighbors();
			Vector<MapNode> n2 = new Vector<MapNode>(neighbors);
			if (!this.backAllowed) {
				n2.remove(prevNode); // to prevent going back
			}

			if (okMapNodeTypes != null) { //remove neighbor nodes that aren't ok
				for (int j=0; j < n2.size(); ){
					if (!n2.get(j).isType(okMapNodeTypes)) {
						n2.remove(j);
					}
					else {
						j++;
					}
				}
			}

			if (n2.size() == 0) { // only option is to go back
				nextNode = prevNode;
			}
			else { // choose a random node from remaining neighbors
				nextNode = n2.get(rng.nextInt(n2.size()));
			}

			prevNode = curNode;

			nextCoord = nextNode.getLocation();
			curNode = nextNode;

			p.addWaypoint(nextCoord);
		}

		lastMapNode = curNode;

		return p;
	}

	/**
	 * Selects and returns a random node that is OK from a list of nodes.
	 * Whether node is OK, is determined by the okMapNodeTypes list.
	 * If okMapNodeTypes are defined, the given list <strong>must</strong>
	 * contain at least one OK node to prevent infinite looping.
	 * @param nodes The list of nodes to choose from.
	 * @return A random node from the list (that is OK if ok list is defined)
	 */
	protected MapNode selectRandomOkNode(List<MapNode> nodes) {
		MapNode n;
		do {
			n = nodes.get(rng.nextInt(nodes.size()));
		} while (okMapNodeTypes != null && !n.isType(okMapNodeTypes));

		return n;
	}

	/**
	 * Returns the SimMap this movement model uses
	 * @return The SimMap this movement model uses
	 */
	public SimMap getMap() {
		return map;
	}

	/**
	 * Reads a sim map from location set to the settings, mirrors the map and
	 * moves its upper left corner to origo.
	 * @return A new SimMap based on the settings
	 */
	private SimMap readMap() {
		SimMap simMap;
		Settings settings = new Settings(MAP_BASE_MOVEMENT_NS);
		WKTMapReader r = new WKTMapReader(true);

		if (cachedMap == null) {
			cachedMapFiles = new ArrayList<String>(); // no cache present
		}
		else { // something in cache
			// check out if previously asked map was asked again
			SimMap cached = checkCache(settings);
			if (cached != null) {
				nrofMapFilesRead = cachedMapFiles.size();
				return cached; // we had right map cached -> return it
			}
			else { // no hit -> reset cache
				cachedMapFiles = new ArrayList<String>();
				cachedMap = null;
			}
		}

		try {
			int nrofMapFiles = settings.getInt(NROF_FILES_S);

			for (int i = 1; i <= nrofMapFiles; i++ ) {
				String pathFile = settings.getSetting(FILE_S + i);
				cachedMapFiles.add(pathFile);
				r.addPaths(new File(pathFile), i);
			}

			nrofMapFilesRead = nrofMapFiles;
		} catch (IOException e) {
			throw new SimError(e.toString(),e);
		}

		simMap = r.getMap();
		checkMapConnectedness(simMap.getNodes());
		// mirrors the map (y' = -y) and moves its upper left corner to origo
		simMap.mirror();
		Coord offset = simMap.getMinBound().clone();
		simMap.translate(-offset.getX(), -offset.getY());
		checkCoordValidity(simMap.getNodes());

		cachedMap = simMap;
		return simMap;
	}

	/**
	 * Checks that all map nodes can be reached from all other map nodes
	 * @param nodes The list of nodes to check
	 * @throws SettingsError if all map nodes are not connected
	 */
	private void checkMapConnectedness(List<MapNode> nodes) {
		Set<MapNode> visited = new HashSet<MapNode>();
		Queue<MapNode> unvisited = new LinkedList<MapNode>();
		MapNode firstNode;
		MapNode next = null;

		if (nodes.size() == 0) {
			throw new SimError("No map nodes in the given map");
		}

		firstNode = nodes.get(0);

		visited.add(firstNode);
		unvisited.addAll(firstNode.getNeighbors());

		while ((next = unvisited.poll()) != null) {
			visited.add(next);
			for (MapNode n: next.getNeighbors()) {
				if (!visited.contains(n) && ! unvisited.contains(n)) {
					unvisited.add(n);
				}
			}
		}

		if (visited.size() != nodes.size()) { // some node couldn't be reached
			MapNode disconnected = null;
			for (MapNode n : nodes) { // find an example node
				if (!visited.contains(n)) {
					disconnected = n;
					break;
				}
			}
			throw new SettingsError("SimMap is not fully connected. Only " +
					visited.size() + " out of " + nodes.size() + " map nodes " +
					"can be reached from " + firstNode + ". E.g. " +
					disconnected + " can't be reached");
		}
	}

	/**
	 * Checks that all coordinates of map nodes are within the min&max limits
	 * of the movement model
	 * @param nodes The list of nodes to check
	 * @throws SettingsError if some map node is out of bounds
	 */
	private void checkCoordValidity(List<MapNode> nodes) {
		 // Check that all map nodes are within world limits
		for (MapNode n : nodes) {
			double x = n.getLocation().getX();
			double y = n.getLocation().getY();
			if (x < 0 || x > getMaxX() || y < 0 || y > getMaxY()) {
				throw new SettingsError("Map node " + n.getLocation() +
						" is out of world  bounds "+
						"(x: 0..." + getMaxX() + " y: 0..." + getMaxY() + ")");
			}
		}
	}

	/**
	 * Checks map cache if the requested map file(s) match to the cached
	 * sim map
	 * @param settings The Settings where map file names are found
	 * @return A cached map or null if the cached map didn't match
	 */
	private SimMap checkCache(Settings settings) {
		int nrofMapFiles = settings.getInt(NROF_FILES_S);

		if (nrofMapFiles != cachedMapFiles.size() || cachedMap == null) {
			return null; // wrong number of files
		}

		for (int i = 1; i <= nrofMapFiles; i++ ) {
			String pathFile = settings.getSetting(FILE_S + i);
			if (!pathFile.equals(cachedMapFiles.get(i-1))) {
				return null;	// found wrong file name
			}
		}

		// all files matched -> return cached map
		return cachedMap;
	}

	@Override
	public MapBasedMovement replicate() {
		return new MapBasedMovement(this);
	}

	public Coord getLastLocation() {
		if (lastMapNode != null) {
			return lastMapNode.getLocation();
		} else {
			return null;
		}
	}

	public void setLocation(Coord lastWaypoint) {
		// TODO: This should be optimized
		MapNode nearest = null;
		double minDistance = Double.MAX_VALUE;
		Iterator<MapNode> iterator = getMap().getNodes().iterator();
		while (iterator.hasNext()) {
			MapNode temp = iterator.next();
			double distance = temp.getLocation().distance(lastWaypoint);
			if (distance < minDistance) {
				minDistance = distance;
				nearest = temp;
			}
		}
		lastMapNode = nearest;
	}

	public boolean isReady() {
		return true;
	}

}
