# sentinel_DLL.py
# CS 1 class example for a circular, doubly linked list with a sentinel.
# by db, thc

# Class for a node in a circular, doubly linked list with a sentinel.
class Node:
    def __init__(self, data):
        self.data = data  # instance variable to store the data
        self.next = None  # instance variable with address of next node
        self.prev = None  # instance variable with address of previous node

    # Return the data in the Node.
    def get_data(self):
        return self.data

# Class for a circular, doubly linked list with a sentinel.
class Sentinel_DLL:
    # Create the sentinel node, which is before the first node
    # and after the last node.
    def __init__(self):
        self.sentinel = Node(None)
        self.sentinel.next = self.sentinel
        self.sentinel.prev = self.sentinel

    # Return a reference to the first node in the list, if there is one.
    # If the list is empty, return None.
    def first_node(self):
        if self.sentinel.next == self.sentinel:
            return None
        else:
            return self.sentinel.next

    # Insert a new node with data after node x.
    def insert_after(self, x, data):
        y = Node(data)   # make a new Node object.

        # Fix up the links in the new node.
        y.prev = x
        y.next = x.next

        # The new node follows x.
        x.next = y

        # And it's the previous node of its next node.
        y.next.prev = y

    # Insert a new node at the end of the list.
    def append(self, data):
        last_node = self.sentinel.prev
        self.insert_after(last_node, data)

    # Insert a new node at the start of the list.
    def prepend(self, data):
        self.insert_after(self.sentinel, data)

    # Delete node x from the list.
    def delete(self, x):
        # Splice out node x by making its next and previous
        # reference each other.
        x.prev.next = x.next
        x.next.prev = x.prev

    # Find a node containing data, and return a reference to it.
    # If no node contains data, return None.
    def find(self, data):
        # Trick: Store a copy of the data in the sentinel,
        # so that the data is always found.
        self.sentinel.data = data

        x = self.first_node()
        while x.data != data:
            x = x.next

        # Restore the sentinel's data.
        self.sentinel.data = None

        # Why did we drop out of the while-loop?
        # If we found the data in the sentinel, then it wasn't
        # anywhere else in the list.
        if x == self.sentinel:
            return None     # data wasn't really in the list
        else:
            return x        # we found it in x, in the list

    #  Return the string representation of a circular, doubly linked
    #  list with a sentinel, just as if it were a Python list.
    def __str__(self):
        s = "["

        x = self.sentinel.next
        while x != self.sentinel:  # look at each node in the list
            if type(x.data) == str:
                s += "'"
            s += str(x.data)        # concatenate this node's data
            if type(x.data) == str:
                s += "'"
            if x.next != self.sentinel:
                s += ", "   # if not the last node, add the comma and space
            x = x.next

        s += "]"
        return s