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:
            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

        else:
            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
        else:
            return

    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
                #print('EKKKI Next REVERSE POS: ', self.pos)

    def move_to_prev(self):

        if self.reversed:
            if self.curr.next != self.tail:
                self.curr = self.curr.next
                self.pos += 1
                print('POS' ,self.pos)

            else:
                return

        else:
            if self.curr.prev != self.head:
                self.curr = self.curr.prev
                self.pos -= 1
                print('POS' ,self.pos)

            else:
                return

    def move_to_pos(self, position):

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

        if self.pos == position:
            return

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


        else:
            if position > self.pos:  #  move next
                while self.pos != position:
                    self.move_to_next()
                #self.move_to_pos(position)

            elif position < self.pos:  #  move prev
                while self.pos != position:
                    self.move_to_prev()
                    #print('PREv')
                    #print(position,':  BIL  :',self.pos)
                #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
            if self.reversed:
                self.pos = self.size
            else:
                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)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.move_to_next()
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.insert(18)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.insert(24)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.insert(24)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.move_to_pos(-1)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.move_to_prev()
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
dll.move_to_pos(2)
print('reversed: ' + str(dll.getStatus()) + ' - pos: ' + str(dll.getPos()))
print('value: ' + str(dll.get_value()) + ' - size: ' + str(len(dll)))
'''