/* author D3Q; may 2009 */

package astar;


import base;



/* this interface will transform nodes in the n-dim model to pathnodes 
   used in the A* algorithm */
interface IMapPathNodes
	operation getStartNode(): PathNode;
	operation getEndNodes(): PathNodeSet;
	/* getAdjacentNodes will return the adjacent nodes of node. It also
	   will set the id, the parent, and costFromStart of the returned nodes.
	   Parent and costFromStart can be written during the life of the node
	   in the open set of AStar */
	operation getAdjacentNodes(node : PathNode) : PathNodeSet;
end;

class PathNode
	attribute id: Integer;
	attribute parent: PathNode;
	attribute costFromStart: Real;
	attribute costHeuristic: Real;
	operation equals(node: PathNode): Boolean;
end;

class PathNodeList specializes Sequence<PathNode>
end;

class PathNodeSet specializes Collection<PathNode>
	operation inSet(node: PathNode): Boolean;
	operation add(node: PathNode): Boolean;
	operation subtract(node: PathNode): Boolean;
end;


class AStar
	operation AStar(map: IMapPathNodes);
	begin
		self.map := map;
	end;
	abstract operation heuristic(node: PathNode): Real;
	private attribute open: PathNodeSet;
	private attribute closed: PathNodeSet;
	private reference map: IMapPathNodes;
	
	/* findPath returns a linear list of 
       subclass AStar using a good heuristic function */
	operation findPath(): PathNodeList;
	begin
		var startN: PathNode, endNs: PathNodeSet, nextN: PathNode, adjNs: PathNodeSet;
		startN := self.map.getStartNode();		
		endNs := self.map.getEndNodes();
		self.open.add(startN);
		nextN := startN;
		while (nextN) do 
		begin
		    /* expand nextN */
			adjNs := self.map.getAdjacentNodes(nextN);

			adjNs.asSet().forEach ((x : PathNode) { self.open.add(x);}); 
			/* werkt niet: adjNs.forEach ((an : PathNode) { self.open.add(an);}); */

			/* stoppen nu nextN expanded is en nextN een eindpunt is */
			if (endNs.inSet(nextN)) then begin
				return self.makePath(nextN);
			end
			else begin
				self.closed.add(nextN);
				self.open.subtract(nextN);
				nextN := self.bestNextNode(self.open);
			end;
		end;
		return;
	end; 

	private operation makePath(node: PathNode): PathNodeList;
	
	/* bepaal node met minimum geschatte weglengte: 
	   de cost van de node + minimale afstand tot endnodes, geschat via heuristiek */
	private operation bestNextNode(openSet: PathNodeSet): PathNode;
	begin
	end;

end;

end.