public class ShortestPath
{

    /**
     * Instance variable that represents the city map upon which the program will
     * try to find a shortest path from starting cell to destination cell
     */
    CityMap cityMap;

    /**
     * Constructor for the class that receives input of a reference to a CityMap object representing the city map
     * @param theMap
     */
    public ShortestPath (CityMap theMap)
    {
        cityMap = theMap;
    }

    /**
     *
     */
    public void findShortestPath()
    {
        OrderedCircularArray pathList = new OrderedCircularArray();
        MapCell current = cityMap.getStart();

        int distance = 0;
        pathList.insert(current, distance);
        current.markInList();

        boolean destinationFound = false;
        while (!pathList.isEmpty() && destinationFound == false) // while list is not empty and destination has not been reached
        {
            MapCell smallest = (MapCell) pathList.getSmallest(); // cast type MapCell
            smallest.markOutList(); // initially marks starting destination cell out of list

            if (current.isDestination())
            {
                break;
            }


            // inserts all possible next cell paths into pathList in order of index
            for (int i = 0; i < 4; i++) // loops to check each possible cell path given current cell position
            {
                if (nextCell(smallest) == null)
                {
                    continue;
                }

                else
                {
                    int startDist = 1 + distance; // distance from current cell to starting cell

                    if (nextCell(smallest).getDistanceToStart() > startDist)
                    {
                        startDist = nextCell(smallest).getDistanceToStart();
                        nextCell(smallest).setPredecessor(smallest); // sets current cell to be predecessor of neighbouring cell
                    }


                    int currDist = nextCell(smallest).getDistanceToStart(); // distance from current neighbouring cell to starting cell
                    if (nextCell(smallest).isMarked() && currDist < pathList.getValue(smallest))
                    {
                        pathList.changeValue(nextCell(smallest), currDist);
                    }

                    if (!nextCell(smallest).isMarked())
                    {
                        pathList.insert(nextCell(smallest), currDist); // adds current neighbour to the ordered list
                        nextCell(smallest).markInList(); // marks neighbouring cell that is shortest distance from start cell in the list
                    }
                }
            }
        }
    }


    /**
     * Method that returns the first unmarked neighbouring map cell that is viable for continuing the path given the current cell
     * @param cell
     * @return value of the next viable cell
     */
    private MapCell nextCell(MapCell cell)
    {
        MapCell returnValue = null;

        if (cell.isNorthRoad())
        {
            if (cell.getNeighbour(0) != null && !cell.getNeighbour(0).isMarked()) // ensures neighbour cell is not null or marked
            {
                if (cell.getNeighbour(0).isNorthRoad() ||    // another North road is a viable cell path
                    cell.getNeighbour(0).isIntersection() || // an intersection is a viable cell path
                    cell.getNeighbour(0).isDestination())    // the destination cell is a viable cell path
                {
                    returnValue = cell.getNeighbour(0); // returns cell value if found
                }
            }
        }

        else if (cell.isEastRoad())
        {
            if (cell.getNeighbour(1) != null && !cell.getNeighbour(1).isMarked())
            {
                if (cell.getNeighbour(1).isEastRoad() ||
                    cell.getNeighbour(1).isIntersection() ||
                    cell.getNeighbour(1).isDestination())
                {
                    returnValue = cell.getNeighbour(1);
                }
            }
        }

        else if (cell.isSouthRoad())
        {
            if (cell.getNeighbour(2) != null && !cell.getNeighbour(2).isMarked())
            {
                if (cell.getNeighbour(2).isSouthRoad() ||
                    cell.getNeighbour(2).isIntersection() ||
                    cell.getNeighbour(2).isDestination())
                {
                    returnValue = cell.getNeighbour(2);
                }
            }
        }

        else if (cell.isWestRoad())
        {
            if (cell.getNeighbour(3) != null && !cell.getNeighbour(3).isMarked())
            {
                if (cell.getNeighbour(3).isWestRoad() ||
                    cell.getNeighbour(3).isIntersection() ||
                    cell.getNeighbour(3).isDestination())
                {
                    returnValue = cell.getNeighbour(3);
                }
            }
        }

        /**
         * Evaluates the case where cell is an intersection or starting cell and reviews if neighbouring cells are either a North, East, South, or West road
         */
        else if (cell.isIntersection() || cell.isStart())
        {

            if (cell.getNeighbour(0) != null &&
               !cell.getNeighbour(0).isMarked() && !cell.getNeighbour(0).isBlock())
            {
                if (cell.getNeighbour(0).isNorthRoad() || cell.getNeighbour(0).isIntersection())
                {
                    returnValue = cell.getNeighbour(0); // returns cell value if found
                }
            }

            else if (cell.getNeighbour(1) != null &&
                    !cell.getNeighbour(1).isMarked() && !cell.getNeighbour(1).isBlock())
            {
                if (cell.getNeighbour(1).isEastRoad() || cell.getNeighbour(1).isIntersection())
                {
                    returnValue = cell.getNeighbour(1); // returns cell value if found
                }
            }

            else if (cell.getNeighbour(2) != null &&
                    !cell.getNeighbour(2).isMarked() && !cell.getNeighbour(2).isBlock())
            {
                if (cell.getNeighbour(2).isSouthRoad() || cell.getNeighbour(2).isIntersection())
                {
                    returnValue = cell.getNeighbour(2); // returns cell value if found
                }
            }

            else if (cell.getNeighbour(3) != null &&
                    !cell.getNeighbour(3).isMarked() && !cell.getNeighbour(3).isBlock())
            {
                if (cell.getNeighbour(3).isWestRoad() || cell.getNeighbour(3).isIntersection())
                {
                    returnValue = cell.getNeighbour(3); // returns cell value if found
                }
            }
        }
        return returnValue;

    }
}