# Doubly-linked list routines
# Useful for, e.g., equivalence "sets"
# Note that several routines take as argument (or return as result)
# a DNode instead of a datum.  This facilitates middle-of-list
# insertion and removal.

class DNode:
    def __init__(self, initdata):
        self.data = initdata
        self.next = self    # circular linking simplifies list manipulation
        self.prev = self
    def isSingleton(self):
        return self.next == self
    def insertBefore(self, other):
        assert other.isSingleton()
        other.prev = self.prev
        other.next = self
        self.prev.next = other
        self.prev = other
    def insertAfter(self, other):
        assert other.isSingleton()
        other.prev = self
        other.next = self.next
        self.next.prev = other
        self.next = other
    def remove(self):
        assert not self.isSingleton()
        self.prev.next = self.next
        self.next.prev = self.prev
        self.next = self
        self.prev = self
    def __str__(self):
        return str(self.data)

class DList:
    def __init__(self):
        self.headNode = DNode(None)
    def isEmpty(self):
        return self.headNode.isSingleton()
    def addFront(self, node):               # inserts node, not data
        self.headNode.insertAfter(node)
    def addBack(self, node):                # inserts node, not data
        self.headNode.insertBefore(node)

    def length(self):
        current = self.headNode
        count = 0
        while current.next != self.headNode:
            count = count + 1
            current = current.next
        return count

    def search(self, item):         # returns node, or None if not found
        current = self.headNode.next
        while current != self.headNode:
            if current.data == item:
                return current
            else:
                current = current.next
        return None

    def remove(self, item):         # returns node, or None if not found
        node = self.search(item)
        if node != None:
            node.remove()
            return node
        return node

    def __str__(self):
        rtn = ""
        current = self.headNode.next
        while current != self.headNode:
            rtn += (" " + str(current))
            current = current.next
        return rtn

    def clone(self):
        rtn = DList()
        current = self.headNode.next
        while current != self.headNode:
            rtn.addBack(DNode(current.data))
            current = current.next
        return rtn

    def merge(self, other):         # allows duplicates
        rtn = self.clone()
        current = other.headNode.next
        while current != other.headNode:
            rtn.addBack(DNode(current.data))
            current = current.next
        return rtn

class Deque:
    def __init__(self):
        self.L = DList()
    def insertFront(self, val):
        self.L.addFront(DNode(val))
    def insertBack(self, val):
        self.L.addBack(DNode(val))
    def isEmpty(self):
        return self.L.isEmpty()
    def removeFront(self):
        if self.isEmpty():
            return None
        rtn = self.L.headNode.next
        rtn.remove()
        return rtn.data
    def removeBack(self):
        if self.isEmpty():
            return None
        rtn = self.L.headNode.prev
        rtn.remove()
        return rtn.data
