package com.brackeen.javagamebook.path;

import java.util.*;

/**
    Klasa AStarSearch class wraz z klasą AStarNode, implementują ogólny
    algorytm przeszukiwania A*. Aby umożliwić wykonanie konkretnego
    przeszukiwania, klasa AStarSearch powinna zostać podklasowana.
*/
public class AStarSearch {


    /**
        Prosta lista priorytetów, zwana również kolejką priorytetów.
        Obiekty na tej liście są porządkowane według ich priorytetów,
        ustalanych za pomocą interfejsu Comparable obiektu.
        Element o najwyższym priorytecie znajdzie się na początku listy.
    */
    public static class PriorityList extends LinkedList {

        public void add(Comparable object) {
            for (int i=0; i<size(); i++) {
                if (object.compareTo(get(i)) <= 0) {
                    add(i, object);
                    return;
                }
            }
            addLast(object);
        }
    }


    /**
        Skonstruuj ścieżkę, bez węzła startowego.
    */
    protected List constructPath(AStarNode node) {
        LinkedList path = new LinkedList();
        while (node.pathParent != null) {
            path.addFirst(node);
            node = node.pathParent;
        }
        return path;
    }


    /**
        Znajdź ścieżkę od węzła startowego do węzła końcowego. Zwracana
        jest lista węzłów AStarNode lub wartość null, jeśli nie uda się 
        odnaleźć ścieżki.
    */
    public List findPath(AStarNode startNode, AStarNode goalNode) {

        PriorityList openList = new PriorityList();
        LinkedList closedList = new LinkedList();

        startNode.costFromStart = 0;
        startNode.estimatedCostToGoal =
            startNode.getEstimatedCost(goalNode);
        startNode.pathParent = null;
        openList.add(startNode);

        while (!openList.isEmpty()) {
            AStarNode node = (AStarNode)openList.removeFirst();
            if (node == goalNode) {
                // skonstruuj ścieżkę od startu do celu
                return constructPath(goalNode);
            }

            List neighbors = node.getNeighbors();
            for (int i=0; i<neighbors.size(); i++) {
                AStarNode neighborNode =
                    (AStarNode)neighbors.get(i);
                boolean isOpen = openList.contains(neighborNode);
                boolean isClosed =
                    closedList.contains(neighborNode);
                float costFromStart = node.costFromStart +
                    node.getCost(neighborNode);

                // sprawdź, czy węzeł sąsiadujący nie był już
                // trawersowany lub czy nie została  właśnie 
                // znaleziona krótsza ścieżka do niego.
                if ((!isOpen && !isClosed) ||
                    costFromStart < neighborNode.costFromStart)
                {
                    neighborNode.pathParent = node;
                    neighborNode.costFromStart = costFromStart;
                    neighborNode.estimatedCostToGoal =
                        neighborNode.getEstimatedCost(goalNode);
                    if (isClosed) {
                        closedList.remove(neighborNode);
                    }
                    if (!isOpen) {
                        openList.add(neighborNode);
                    }
                }
            }
            closedList.add(node);
        }

        // nie znaleziono ścieżki
        return null;
    }

}