import math
import loader
import cellOpening

cellList = []

class Cell(object):
    posY = -1
    posX = -1
    valueFinal = -1 # value of cell in the f(x) + heuristic *g(x) map

    def __init__(self, posY, posX, valueFinal):
        self.posY = posY
        self.posX = posX
        self.valueFinal = valueFinal

# check if new pos is a wall in the file, if the pos
#is already visited and if the end was already found
def checkNewPos(distMap, aStarMap, inputMap, posY, posX, done):
    if done:
        return False
    if distMap[posY][posX] != -2:
        return False
    if aStarMap[posY][posX] != -2:
        return False
    if inputMap[posY][posX] == 1:
        return False
    return True

# opens surrounding cell of current position
def cellOpening(cell, inputMap, manhattanMap, distMap, aStarMap, heuristic):
    cellNextValue = distMap[cell.posY][cell.posX] + 1
    done = False

    done = openingUp(cell.posX, cell.posY, inputMap, manhattanMap, distMap, aStarMap, cellNextValue, heuristic, done)
    done = openingLeft(cell.posX, cell.posY, inputMap, manhattanMap, distMap, aStarMap, cellNextValue, heuristic, done)
    done = openingRight(cell.posX, cell.posY, inputMap, manhattanMap, distMap, aStarMap, cellNextValue, heuristic, done)
    done = openingDown(cell.posX, cell.posY, inputMap, manhattanMap, distMap, aStarMap, cellNextValue, heuristic, done)

    aStarMap[cell.posY][cell.posX] = -1 #"X"
    if done:
        return True
    # sort by value of f(x) + heuristic * g(x) matrice then Y then X
    cellList.sort(key = lambda l: (l.valueFinal, l.posY, l.posX))
    return False

# initialize the content of the f(x) matrice and of the f(x) + heuristic *g(x) matrice
#for the pos at the north of current pos
def openingUp(posX, posY, inputMap, manhattanMap, distMap, aStarMap, value, heuristic, done):
    if posY > 0 \
    and checkNewPos(distMap, aStarMap, inputMap,posY -1, posX, done):
        distMap[posY - 1][posX] = value
        aStarMap[posY - 1][posX] = value + heuristic * manhattanMap[posY -1][posX]
        if inputMap[posY -1][posX] == 3:
            done = True
        cellList.append(Cell(posY -1, posX, aStarMap[posY - 1][posX]))
    return done

def openingLeft(posX, posY, inputMap, manhattanMap, distMap, aStarMap, value, heuristic, done):
    if posX > 0 \
    and checkNewPos(distMap, aStarMap, inputMap,posY, posX - 1, done):
        distMap[posY][posX - 1] = value
        aStarMap[posY][posX - 1] = value + heuristic * manhattanMap[posY][posX - 1]
        if inputMap[posY][posX - 1] == 3:
            done = True
        cellList.append(Cell(posY, posX - 1, aStarMap[posY][posX - 1]))
    return done

def openingRight(posX, posY, inputMap, manhattanMap, distMap, aStarMap, value, heuristic, done):
    if posX < len(inputMap[posY]) -1 \
    and checkNewPos(distMap, aStarMap, inputMap,posY, posX + 1, done):
        distMap[posY][posX + 1] = value
        aStarMap[posY][posX + 1] = value + heuristic * manhattanMap[posY][posX + 1]
        if inputMap[posY][posX + 1] == 3:
            done = True
        cellList.append(Cell(posY, posX + 1, aStarMap[posY][posX + 1]))
    return done

def openingDown(posX, posY, inputMap, manhattanMap, distMap, aStarMap, value, heuristic, done):
    if posY < len(inputMap) - 1 \
    and checkNewPos(distMap, aStarMap, inputMap,posY + 1, posX, done):
        distMap[posY + 1][posX] = value
        aStarMap[posY + 1][posX] = value + heuristic * manhattanMap[posY + 1][posX]
        if inputMap[posY + 1][posX] == 3:
            done = True
        cellList.append(Cell(posY + 1, posX, aStarMap[posY + 1][posX]))
    return done

# fill the f(x)  and f(x) + heuristic * g(x) matrices
def aStarMapCreation(inputMap, manhattanMap, heuristic, destY, destX):
    posY = -1
    posX = -1
    distMap = [[-2 for char in line] for line in inputMap]
    aStarMap = [[-2 for char in line] for line in inputMap]
    done = False

    # Seek starting position
    for line in inputMap:
        posY += 1
        try:
            posX = line.index(2)
            break
        except ValueError:
            continue

    distMap[posY][posX] = 0
    aStarMap[posY][posX] = 0 + heuristic * manhattanMap[posY][posX]
    cellList.append(Cell(posY, posX, aStarMap[posY][posX]))
    iteration = 1
    while cellList and done == False:
        # Select the cell with the smallest value
        newPos = cellList.pop(0)
        iteration += 1
        # Open the cells next to the cell selected
        done = cellOpening(newPos, inputMap, manhattanMap, distMap, aStarMap, heuristic)
    return endAlgo(iteration, done, destY, destX, inputMap, distMap)

# verify and save the result of the execution
def endAlgo(iteration, done, destY, destX, inputMap, distMap):
    if done == False:
        return -1, "IMPOSSIBLE"
    pos = []
    # Generate a path from the destination to the starting point
    while inputMap[destY][destX] != 2 :
        compass = backTrack(destY, destX, distMap)
        if compass == 1:
            destY -= 1
            pos.append("N")
        elif compass == 2:
            destX -= 1
            pos.append("O")
        elif compass == 3:
            destX += 1
            pos.append("E")
        elif compass == 4:
            destY += 1
            pos.append("S")
    # nested ternary in list manipulation <3
    # Reverse the generated path to end up with a path start to dest
    return iteration, ["S" if elem == "N" else ("O" if elem == "E" else ("E" if elem == "O" else "N")) for elem in reversed(pos)]

# trace the execution of the algorithm in the matrice
def backTrack(posY, posX, distMap):
    current = distMap[posY][posX]
    mini = current
    compass = -1 # 1 = N | 2 = O | 3 = E | 4 = S

# Weight based priority
# if it doesn't go inside any of the 4 if, we reached the destination

    if posY > 0 and distMap[posY - 1][posX] < mini and distMap[posY - 1][posX] >= 0:
        mini = distMap[posY - 1][posX]
        compass = 1
    if posX > 0 and distMap[posY][posX - 1] < mini and distMap[posY][posX - 1] >= 0:
        mini = distMap[posY][posX - 1]
        compass = 2
    if posX < len(distMap[0]) - 1 and distMap[posY][posX + 1] < mini and distMap[posY][posX +1] >= 0:
        mini = distMap[posY][posX + 1]
        compass = 3
    if posY < len(distMap) - 1 and distMap[posY + 1][posX] < mini and distMap[posY + 1][posX] >= 0:
        mini = distMap[posY + 1][posX]
        compass = 4
    return compass

def manhattan(inputMap):
    destY = -1
    destX = -1

    # Seek destination
    for line in Map:
        destY +=1
        try:
            destX = line.index(3)
            break
        except ValueError:
            continue

    # Manhattan Map creation and filling using list manipulation
    manhattanMap = [[int(math.fabs(line - destY) + math.fabs(column - destX)) for column in range(0,len(inputMap[line]))] for line in range(0,len(inputMap))]

    # return the manhattanMap filled and the position of the cell to reach
    return manhattanMap, destY, destX

def astar(fileSelected, fileNumber):
    inputMap = readFile(fileSelected)
    # load map from file

    heuristic = getHeuristic(fileNumber)
    # get heuristic depend on file number

    manhattanMap, destY, destX = manhattan(inputMap)
    # target identification and creation of a manhattan map

    iteration, path = aStarMapCreation(inputMap, manhattanMap, heuristic, destY, destX)
    # Generate the solution for the fileSelected

    fd = open("./Resultat"+ str(fileNumber) + ".txt", "w")
    if iteration == -1: # impossible to find a path
        print(path, file = fd)
        pass
    else:
        print("".join(path), file= fd)
        print(iteration, file = fd)
        pass

def readFile(fileSelected):
    linesFiles = fileSelected.readlines()
    fileSelected.close()
    linesMatrice = []
    for line in linesFiles:
        tmp = line.replace("\r", "")
        linesMatrice.append(list(tmp.replace("\n", "")))
    return [[int(char) for char in line] for line in linesMatrice]

def getHeuristic(fileNumber):
    if fileNumber >= 1 and fileNumber <= 6: return 1
    elif fileNumber == 7 or fileNumber == 8: return 0.5
    elif fileNumber == 9: return 5


def main():
    for fileNumber in range(1,10):
        fileSelected = open("./Exercice"+ str(fileNumber) + ".txt", "r")
        cellList = []
        astar(fileSelected, fileNumber)

if __name__ == "__main__":
    main()
