class Node:  # Node has only PARENT_NODE, STATE, DEPTH
    def __init__(self, state, parent=None, depth=0, heuristic=0, cost=0):
        self.STATE = state
        self.PARENT_NODE = parent
        self.DEPTH = depth
        self.COST = cost
        self.HEURISTIC = heuristic
        self.HEURICOST = heuristic + cost

    def path(self):  # Create a list of nodes from the root to this node.
        current_node = self
        path = [self]
        while current_node.PARENT_NODE:  # while current node has parent
            current_node = current_node.PARENT_NODE  # make parent the current node
            path.append(current_node)   # add current node to path
        return path

    def display(self):
        print(self)

    def __repr__(self):
        return 'State: ' + str(self.STATE) + ' - Depth: ' + str(self.DEPTH) + ' - Cost: ' + str(self.COST) + ' - Heuristic: ' + str(self.HEURISTIC) + ' - Heuricost: ' + str(self.HEURICOST)

#Takes a list and finds the lowest note
def FIND_LOWEST_COST(open):
    lowestNode = Node(INITIAL_STATE)
    lowestNode.COST = 0
    lowestNode.HEURISTIC = 0
    lowestNode.HEURICOST = 1000
    iterableNode = Node(INITIAL_STATE)

    for node in open:
        iterableNode = node
        iterableNode = POPULATE_NODE(iterableNode)
#        print("<LOWEST_COST> Iterable node: " + iterableNode.__str__())
        if int(iterableNode.HEURICOST) <= int(lowestNode.HEURICOST):
            lowestNode = iterableNode
    return lowestNode


#based on a state, it will populate the node
def POPULATE_NODE(node):
#    print("<POPULATE_NODE> node recieved is: " + node.__str__())
    a, b, c = node
#    print("<POPULATE_NODE> A from state: " + a.__str__())
#    print("<POPULATE_NODE> B from state: " + b.__str__())
#    print("<POPULATE_NODE> C from state: " + c.__str__())
    node = Node(node)
    node.HEURISTIC = c
#    print("<FIND_COST> Node Heuristic after set: " + node.HEURISTIC.__str__())
    node.COST = b
#        print("<FIND_COST> Node Cost after set: " + node.COST.__str__())
    node.HEURICOST = int(b) + int(c)
#    print("<FIND_COST> Node Heuricost after set: " + node.HEURICOST.__str__())
    return node


def DISTANCE_TO_CHILD(mother, child):
    mother = int(mother)
    child = int(child)
    distance = 0
    distance = child - mother
    return distance


def FINAL_PATH(cameFrom, current):
#    print("<FINAL_PATH> cameFrom at start " + cameFrom.__str__())
#    print("<FINAL_PATH> current at start " + current.__str__())
    total_path = current.STATE

    check = current.STATE
    while check in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path


def ASTAR_SEARCH():
    closedSet = []
    openSet=[]
    firstNode = POPULATE_NODE(INITIAL_STATE)
    cameFrom = {}
    INSERT(firstNode.STATE, openSet)
    while openSet is not None:
        current = FIND_LOWEST_COST(openSet)
        print("<A STAR> current  " + current.__str__())
#        print("<A STAR> lowest " + current.__str__())
        if current.STATE in GOAL_STATE:
            return FINAL_PATH(cameFrom, current)

        INSERT(current.STATE, closedSet)
        openSet.remove(current.STATE)
#        print("<A STAR> open " + openSet.__str__())

        for succesor in successor_fn(current.STATE):
            if succesor in closedSet:
                continue
            if succesor not in openSet:
                INSERT(succesor, openSet)
                continue
            succesor = POPULATE_NODE(succesor)
#            distance = DISTANCE_TO_CHILD(current.COST, succesor.COST)
#            tempCost = int(current.COST)
            tempCost = succesor.COST + succesor.HEURISTIC

#            tempPathCost = tempCost + distance
            if int(succesor.COST) >= int(succesor.COST):
                continue
            print("<A STAR> succesor  " + succesor.__str__())
            print("<A STAR> current  " + current.__str__())
            print("<A STAR> succesor " + succesor.__str__())
            cameFrom[succesor.STATE] = current.STATE
            succesor.COST = tempCost
            succesor.HEURISTIC = str(succesor.HEURISTIC) + str(succesor.COST)

    return print("Error, Open List is empty")


'''
Insert node in to the queue (fringe).
'''
def INSERT(node, queue):
    #queue.insert(0, node)  # DFS
    queue.append(node)      # BFS
    return queue


'''
Insert list of nodes into the fringe
'''
def INSERT_ALL(list, queue):
    for node in list:
        INSERT(node, queue)
    return queue


'''
Remove first element from fringe
'''
def REMOVE_FIRST(queue):
    if len(queue) != 0:
        return queue.pop(0)
    return []


'''
Successor function, mapping the nodes to its successors
'''
def successor_fn(state):  # Lookup list of successor states
    return STATE_SPACE[state]  # successor_fn( 'C' ) returns ['F', 'G']


#initial state, path count of 0, cost = heuristic
INITIAL_STATE = ('A', '0', '6')

#Initial State A - end point is either K or L
#Current state, path, cost
GOAL_STATE = [('L', '11', '0'),('L', '13', '0'),('L', '10', '0'),('K', '13', '0'),('K', '11', '0'),('K', '12', '0'),('K', '14', '0')]
#GOAL_STATE = ('L', '11', '0')
#GOAL_STATE2 = ('K', '13', '0')

'''
Complete state space including loops back to current state
'''
#                  Current State - Actions:
STATE_SPACE = {('A', '0', '6'): [('B', '1', '5'), ('C', '2', '5'), ('D', '4', '2')],
               ('B', '1', '5'): [('F', '6', '5'), ('E', '5', '4')],
               ('C', '2', '5'): [('E', '3', '4')],
               ('D', '4', '2'): [('J', '6', '1'), ('I', '8', '2'), ('H', '5', '1')],

               ('F', '6', '5'): [('G', '7', '4')],

               ('E', '3', '4'): [('G', '5', '4'), ('H', '6', '1')],
               ('E', '5', '4'): [('G', '7', '4'), ('H', '8', '1')],
               ('I', '8', '2'): [('L', '11', '0')],
               ('J', '6', '1'): [],

               ('G', '7', '4'): [('K', '13', '0')],
               ('G', '5', '4'): [('A', '15', '0')],

               ('H', '6', '1'): [('L', '11', '0'), ('K', '12', '0')],
               ('H', '8', '1'): [('L', '13', '0'), ('K', '14', '0')],
               ('H', '5', '1'): [('L', '10', '0'), ('K', '11', '0')],

               ('L', '11', '0'): [],
               ('L', '13', '0'): [],
               ('L', '10', '0'): [],

               ('K', '13', '0'): [],
               ('K', '11', '0'): [],
               ('K', '12', '0'): [],
               ('K', '14', '0'): []
               }

'''
Run Astar and display the nodes in the path to goal node
'''
def run():
    path = ASTAR_SEARCH()





if __name__ == '__main__':
    run()