"""Each ListNode holds a reference to its previous node
as well as its next node in the List."""


class ListNode:
    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

    """Wrap the given value in a ListNode and insert it
    after this node. Note that this node could already
    have a next node it is point to."""
    def insert_after(self, value):
        current_next = self.next
        self.next = ListNode(value, self, current_next)
        if current_next:
            current_next.prev = self.next

    """Wrap the given value in a ListNode and insert it
    before this node. Note that this node could already
    have a previous node it is point to."""
    def insert_before(self, value):
        current_prev = self.prev
        self.prev = ListNode(value, current_prev, self)
        if current_prev:
            current_prev.next = self.prev

    """Rearranges this ListNode's previous and next pointers
    accordingly, effectively deleting this ListNode."""
    def delete(self):
        if self.prev:
            self.prev.next = self.next
        if self.next:
            self.next.prev = self.prev


"""Our doubly-linked list class. It holds references to
the list's head and tail nodes."""


class DoublyLinkedList:
    def __init__(self, node=None):
        self.head = node
        self.tail = node
        self.length = 1 if node is not None else 0

    def __len__(self):
        return self.length

    def add_to_head(self, value):
        # adding to an empty list
        new_node = ListNode(value)
        self.length += 1
        if self.head is None and self.tail is None:
            # create a new node
            self.head = new_node
            self.tail = new_node
        else:
            # adding a new value, to existing list
            # link new_node with current head
            new_node.next = self.head
            self.head.prev = new_node
            # update head
            self.head = new_node

    def remove_from_head(self):
        # if list is empty
        if self.head is None and self.tail is None:
            return "empty"
        val = self.head.value
        # if list has only 1 element
        if self.head == self.tail:
            #unlink the node
            self.head, self.tail = None, None
            self.length = 0
            return val
        else:
            # we have more then one element
            self.head.prev = None
            self.head = self.head.next
            self.length -= 1
            return val

    def add_to_tail(self, value):
        # adding to an empty list
        new_node = ListNode(value)
        self.length += 1
        if self.head is None and self.tail is None:
            # create a new node
            self.head = new_node
            self.tail = new_node
        else:
            # adding a new value, to existing list
            # link new_node with current tail
            new_node.prev = self.tail
            self.tail.next = new_node
            # update tail
            self.tail = new_node

    def remove_from_tail(self):
        # if list is empty
        if self.head is None and self.tail is None:
            return "empty"
        val = self.tail.value
        # if list has only 1 element
        if self.head == self.tail:
            #unlink the node
            self.head, self.tail = None, None
            self.length = 0
            return val
        else:
            # we have more then one element
            prev_tail = self.tail.prev
            prev_tail.next = None
            self.tail.prev = None
            self.tail = prev_tail
            self.length -= 1
            return val

    def move_to_front(self, node):
        val = node.value
        # check if the node is a tail 
        if self.tail is node:
            # reasign the tail to the prev value
            self.tail = self.tail.prev
            self.tail.next = None
        # delete node
        node.delete()
        self.length -= 1
        self.add_to_head(val)

    def move_to_end(self, node):
        val = node.value
        # check if the node is a head 
        if self.head is node:
            # reasign the head to the next value
            self.head = self.head.next
            self.head.prev = None
        # delete node
        node.delete()
        self.length -= 1
        self.add_to_tail(val)

    def delete(self, node):
        # check if the node is a head 
        if self.head is node:
            # check if there's another value in a list
            if self.head.next:
                # reasign the head
                self.head = self.head.next
                self.head.prev = None
            else:
                self.head = None
        # check if the node is a tail 
        if self.tail is node:
            # check if there's another value in a list
            if self.tail.prev:
                # reasign the tail
                self.tail = self.tail.prev
                self.tail.next = None
            else:
                self.tail = None
        # delete the node
        node.delete()
        self.length -= 1

    def get_max(self):
        # if there's no head the doubly list is empty
        if not self.head:
            return -1
        # first value is the max value
        max_ = self.head.value
        # curr is the head (we'll go from head to tail)
        curr = self.head
        # while there's a next value go
        while curr.next:
            # reasign the curr value 
            curr = curr.next
            # reasign the max value in case if current value is bigger then currently stored max value
            if curr.value > max_:
                max_ = curr.value
        return max_
