# A PQ is a dictionary mapping nodes to distances.

PQ1 = {}


def addNode1(node,distance):
    """Add node to the PQ with the given distance if the node isn't already present.  Updates the node's distance if it is present."""
    if node in PQ1:
        # Possibly update the node's distance.
        oldDistance = PQ1[node]
        
        #if distance < oldDistance:
        #    PQ1[node] = distance
        PQ1[node] = min(distance,oldDistance)

    else:
        # Add the node and distance.
        PQ1[node] = distance



def getNode1():
    """Returns and deletes from the PQ the node with the lowest distance.  Also returns its distance."""

    # Find the node with lowest distance.
    lowestNode,lowestDistance = PQ1.items()[0]
    for node,distance in PQ1.items()[1:]:
        if distance < lowestDistance:
            lowestNode = node
            lowestDistance = distance

    # Delete the node and return it.
    del PQ1[lowestNode]
    return lowestNode,lowestDistance





def isEmptyPQ1():
    """Returns whether the PQ is empty."""
    return PQ1 == {}

    








# A PQ is a list of pairs of nodes and distances, in ascending sorted order by distance.

PQ2 = []


def addNode2(node,distance):
    """Add node to the PQ with the given distance if the node isn't already present.  Updates the node's distance if it is present."""

    # Is the node in the PQ?
    for index in range(len(PQ2)):
        if node == PQ2[index][0]:
            # Found it!

            # Get distance stored in PQ for this node.
            oldDistance = PQ2[index][1]

            # If distance < old distance, then delete and insert with the new distance.
            if distance < oldDistance:
                del PQ2[index]
                addNode2InsertHelper(node,distance)

            # Don't look for it any more.
            break

    else:
        # node is not in PQ.
        addNode2InsertHelper(node,distance)


def addNode2InsertHelper(node,distance):
    """Add node to the PQ with the given distance.  It is guaranteed not to be in the PQ."""
    # Find where to insert the node.
    for index in range(len(PQ2)):
        if distance < PQ2[index][1]:
            # Insert it where it belongs, before the first item that is bigger.
            PQ2.insert(index,(node,distance))

            # Don't look for it any more.
            break
        
    else:
        # Doesn't belong before some other node.  Belongs at end.
        PQ2.append(   (node,distance)   )



def getNode2():
    """Returns and deletes from the PQ the node with the lowest distance.  Also returns its distance."""
    return PQ2.pop(0)    




def isEmptyPQ2():
    """Returns whether the PQ is empty."""
    return PQ2 == []




################
# Tests
# Each should print True.

##addNode1("a",5)
##addNode1("b",9)
##addNode1("a",3)
##addNode1("c",7)
##addNode1("c",8)
##addNode1("d",1)
##addNode1("e",10)
##
##print ("d",1) == getNode1()
##print ("a",3) == getNode1()
##print ("c",7) == getNode1()
##print ("b",9) == getNode1()
##print ("e",10) == getNode1()
##print isEmptyPQ1()
##
##
##addNode2("a",5)
##addNode2("b",9)
##addNode2("a",3)
##addNode2("c",7)
##addNode2("c",8)
##addNode2("d",1)
##addNode2("e",10)
##
##print ("d",1) == getNode2()
##print ("a",3) == getNode2()
##print ("c",7) == getNode2()
##print ("b",9) == getNode2()
##print ("e",10) == getNode2()
##print isEmptyPQ2()