import sys
from Queue import Queue, PriorityQueue
from sets import Set


# Take in a node, then return the neighbours of the node
def getNeighbours(g, id, rows, cols):
    (i, j) = id
    # In the order UP, DOWN, LEFT, RIGHT
    possibleNodes = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    results = []
    # print(possibleNodes)
    for possibleNode in possibleNodes:
        if valid(g,possibleNode, rows, cols):
            # print(possibleNode)
            results.append(possibleNode)
    # print('Current Node', id)
    # print('Results from GetNeighbours: ', results)
    # results = filter(valid(g,currentNode), possibleNodes)
    print('Neighbours',results)
    # *** MIGHT NOT NEED TO REVERSE ***
    # results = reversed(results)
    return results

def valid(g, node, rows, cols):
    (i, j) = node
    if 0 <= i  <= rows and 0 <= j <= cols:
        if g[i][j] != 'X':
            return True
    else:
        return False

def drawGrid(g,explored, start, currentNode):
    t = False
    res = currentNode
    g[8][0] = 'A'
    while not t:
        if res == start:
            t = True
        (i,j) = res
        g[i][j] = '*'
        res = explored[res]
    # **Printing the Map**
    for i in range(0, len(g)):
        for j in range(0,len(g[0])):
            print(g[i][j]),
        print('')

def nextCost(g, current, next):
    (i,j) = current
    (x,y) = next
    currentVal = int(g[i][j])
    nextVal = int(g[x][y])

    # print('CurrVal,NextVal: ',currentVal, nextVal)
    # Return 1 if staying 'level' or going 'downhill'
    if nextVal <= currentVal:
        return 1
    # Return 1 + Difference of points if going 'uphill'
    elif nextVal > currentVal:
        cost = 1 + (nextVal - currentVal)
        return cost


    # if int(g[x][y] )
    return 1

def bfs(g, start, end, rows, cols): # Returns a solution, or a failure
    # print('---BFS started---')
    # initialise the fringe/fringe - A list of nodes we know about but have not visited yet
    fringe = Queue()
    fringe.put(start)
    cost = 0
    # initialise the explored list
    explored = {}
    explored[start] = None
    # loop
    while not fringe.empty():
        # print('---WHILE loop---')
        currentNode = fringe.get()
        # print(currentNode)
        # print(fringe.queue)
        if currentNode == end:
            # print('FOUND IT', currentNode)
            # print(cost)
            drawGrid(g, explored, start, currentNode)
            break
        # if
        for nextNode in getNeighbours(g, currentNode, rows, cols):
            if nextNode not in explored:
                fringe.put(nextNode)
                explored[nextNode] = currentNode
                cost += 1
                # print('Current:', currentNode)
                # print('Next:', nextNode)




def ucs(g, start, end, rows, cols):
    # print('---UCS started---')
    # initialise the fringe - A list of nodes we know about but have not visited yet
    # different to the Queue used in BFS, a PriorityQueue is used for this algorithm
    fringe = PriorityQueue()
    count = 0
    fringe.put(start, 0, count)
    # initialise the explored list
    explored = {}
    explored[start] = None
    # initialise the cost list
    costList = {}
    costList[start] = 0
    # loop
    while not fringe.empty():
        # print('---WHILE loop---')
        print('Frontier', fringe.queue)
        currentNode = fringe.get()
        print('Queue Chooses:', currentNode)
        if currentNode == end:
            print('FOUND IT', currentNode)
            # print(cost)
            break

        for nextNode in getNeighbours(g, currentNode, rows, cols):
            nextNodeCost = nextCost(g, currentNode, nextNode)
            cost = costList[currentNode] + nextNodeCost
            print(cost)
            if nextNode not in costList or cost < costList[nextNode]:
                count += 1
                costList[nextNode] = cost
                explored[nextNode] = currentNode
                nodePriority = cost
                fringe.put(nextNode, count, nodePriority)
                print(fringe.queue)
                print('Just Explored:', currentNode)
                print('Count: ', count)
                print('Added to Fringe:', nextNode)
                print('')
                print(' ')
    drawGrid(g, explored, start, currentNode)

def astar(g, start, end, rows, cols, heuristic):
    pass

def main():
    args = ['null'] * 3
    # Placing arguments in a list
    # FORMAT: args[0] = map, args[1] = bfs/ucs/astar, args[2] = heuristic
    for i in range(1,4):
       try:
           args[i - 1] = sys.argv[i]
       except IndexError:
           pass

    # Opening file and storing input
    with open(args[0]) as f:
        lines = [line.split() for line in f]

    # print(lines)

    # Rows(R) and Columns(C)
    R = int(lines[0][0])-1
    C = int(lines[0][1])-1

    # Start Point and End Point
    start = (int(lines[1][0])-1, int(lines[1][1])-1)
    end = (int(lines[2][0])-1, int(lines[2][1])-1)
    # print(start, end)
    # c = Maze(R,C)
    # print(c)
    # Storing the map
    g = []
    for i in range(3, R+4):
        g.append(lines[i])

    if args[1] == 'astar':
        if args[2] == 'euclidian':
            pass
        elif args[2] == 'manhattan':
            pass
    elif args[1] == 'bfs':
        bfs(g,start, end, R, C)
    elif args[1] == 'ucs':
        ucs(g,start, end, R, C)

if __name__ == '__main__':
    main()