class Node:

    def __init__(self, data = None, next = None, prev = None):
        self.data = data
        self.next = next
        self.prev = prev

class DLL:

    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.curr = self.tail
        self.size = 0
        self.pos = 0
        self.reversed = False

    def insert(self, value):

        new_node = Node(value)
        if self.reversed:
            if self.curr != self.tail:
                new_node.next = self.curr.next
                new_node.prev = self.curr
                self.curr.next.prev = new_node
                self.curr.next = new_node
                self.curr = new_node
                self.size += 1
                return

        new_node.next = self.curr
        new_node.prev = self.curr.prev
        self.curr.prev.next = new_node
        self.curr.prev = new_node
        self.curr = new_node
        self.size += 1


    def remove(self):

        if self.curr != self.head and self.curr != self.tail:
            self.curr.next.prev = self.curr.prev
            self.curr.prev.next = self.curr.next
            self.size -= 1
            if self.reversed:
                self.curr = self.curr.prev
            else:
                self.curr = self.curr.next

    def get_value(self):

        return self.curr.data

    def move_to_next(self):

        if self.reversed:
            if self.curr.prev != None:
                self.curr = self.curr.prev
                self.pos += 1
        else:
            if self.curr.next != None:
                self.curr = self.curr.next
                self.pos += 1

    def move_to_prev(self):

        if self.reversed:
            if self.curr.next != self.tail:
                self.curr = self.curr.next
                self.pos -= 1
        else:
            if self.curr.prev != self.head:
                self.curr = self.curr.prev
                self.pos -= 1

    def move_to_pos(self, position):

        if position > self.size or position < 0:
            return

        if self.pos == position:
            return

        elif position == self.size:

            if self.reversed:
                self.curr = self.head
                self.pos = 0
            else:
                self.curr = self.tail
                self.pos = self.size

        elif position == 0:

            if self.reversed:
                self.curr = self.tail.prev
                self.pos = self.size - 1
            else:
                self.curr = self.head.next
                self.pos = 0

        else:
            if position > self.pos:
                while self.pos != position:
                    self.move_to_next()

            elif position < self.pos:
                while self.pos != position:
                    self.move_to_prev()

            else:
                return
        '''
        else:
            if position > self.pos:
                if self.reversed:
                    self.pos += 1
                    self.curr = self.curr.next
                else:
                    self.pos += 1
                    self.curr = self.curr.next
                self.move_to_pos(position)

            elif position < self.pos:
                if self.reversed:
                    self.pos -= 1
                    self.curr = self.curr.prev
                else:
                    self.pos -= 1
                    self.curr = self.curr.prev
                self.move_to_pos(position)

            else:
                return
        '''
    def remove_all(self, value):

        if self.reversed:
            iterator = self.tail.prev

            if self.curr.data == value:
                self.curr = self.tail.prev

        else:
            iterator = self.head.next

            if self.curr.data == value:
                self.curr = self.head.next

        while iterator != None:

            if iterator.data == value:
                iterator.prev.next = iterator.next
                iterator.next.prev = iterator.prev
                self.size -= 1

            if self.reversed:
                iterator = iterator.prev
            else:
                iterator = iterator.next

        if self.reversed:

            if self.curr.data == value:
                self.curr = self.tail.prev

        else:

            if self.curr.data == value:
                self.curr = self.head.next

    def reverse(self):

        if self.reversed:
            self.reversed = False
            self.curr = self.head.next
            self.pos = 0

        else:
            self.reversed = True
            self.curr = self.tail.prev
            self.pos = self.size - 1

    def sort(self):

        if self.head.next == self.tail:
            return

        else:
            self.curr = self.head.next

            while self.curr.next != None:
                compare = self.curr.next
                while compare.next != None:
                    if self.curr.data > compare.data:
                        temp = self.curr.data
                        self.curr.data = compare.data
                        compare.data = temp

                    compare = compare.next
                self.curr = self.curr.next

            self.reversed = False
            self.curr = self.head.next
            self.pos = 0

    def __len__(self):

        return self.size

    def __str__(self):

        ret_str = ''

        if self.reversed:
            ret_val = self.tail.prev
            while ret_val.prev != None:
                ret_str += str(ret_val.data) + ' '
                ret_val = ret_val.prev

        else:
            ret_val = self.head.next
            while ret_val.next != None:
                ret_str += str(ret_val.data) + ' '
                ret_val = ret_val.next

        return ret_str

    def getStatus(self):
        return self.reversed

    def getPos(self):
        return self.pos



dll = DLL()
dll.insert(29)
dll.insert(24)
dll.insert(25)
dll.insert(25)
dll.insert(17)
dll.insert(16)
dll.insert(28)
dll.insert(24)
dll.insert(12)
dll.insert(20)
dll.insert(11)
dll.insert(19)
dll.insert(23)
dll.insert(24)
dll.insert(24)
dll.insert(24)
dll.insert(25)
dll.insert(25)
dll.insert(26)
dll.insert(27)
dll.insert(28)
dll.reverse()
print(dll)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.move_to_pos(21)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))