"""A linked list implementation of priority queue."""
class PriorityQueue:

    def __init__( self ):
        """Constructor to create an empty queue."""
        self.head = None
        self.tail = None
        self.count = 0

    def is_empty( self ):
        """Check to see if the queue is empty."""
        return self.count == 0

    def __len__( self ):
        """Return the length of the queue."""
        return self.count

    def enqueue( self, item, priority ):
        """Insert the new node with item and priority into the queue."""
        # Make a new node
        entry = PriorityEntry( item, priority )
        node = PriorityNode( entry )

        if self.tail == None:   # an empty queue
            self.head = node
            self.tail = node
        else:                   # find a proper location to insert
            cur = self.head
            pre = None
            while cur != None and cur.data.priority < priority:
                pre = cur
                cur = cur.next

            if cur == None:     # insert after the tail
                self.tail.next = node
                self.tail = node
            elif pre == None:   # insert before the head
                node.next = self.head
                self.head = node
            else:               # insert between pre and cur
                pre.next = node
                node.next = cur

        self.count += 1

    def dequeue( self ):
        """Remove an item at the front."""
        assert not self.is_empty(), "Cannot dequeue from an empty queue."
        item = self.head
        self.head = self.head.next
        if self.head == None:   # now an empty queue
            self.tail = None
        self.count -= 1
        return item.data

    def peek( self ):
        """Examine the value of the first node."""
        assert not self.is_empty(), "Cannot peek from an empty queue."
        node = self.head
        return node.data

class PriorityNode:
    """The node contains a piece of data and a 'next' link."""
    def __init__( self, data ):
        self.data = data
        self.next = None

class PriorityEntry:
    """A priority entry contains a piece of data and a priority."""
    def __init__( self, item, priority ):
        self.item = item
        self.priority = priority

    def __str__( self ):
        """Return a string form of the node for printing."""
        value = 'Priority : ' + str( self.priority ) + \
            ' data: ' + str( self.item )
        return value