import random

class Node:
    def __init__(self, my_record, key):
        self.forward = None
        self.back = None
        self.record = my_record
        self.key = key
    def __repr__(self):
        return "Node: {}, forward {} ({}, back {} ({}), key {}, record {}".format(id(self),
                                                                                  id(self.forward),
                                                                                  self.forward.key,
                                                                                  id(self.backward),
                                                                                  self.backward.key,
                                                                                  self.key,
                                                                                  self.record)                                                                                

class OLL:
    """implements an ordered list of double linked nodes """
    def __init__(self):
        self.head = None
        
    def insert_before_after(new_node, left, right):
        left.forward = new_node
        new_node.back = left
        new_node.forward = right
        right.back = new_node
        
    def insert(self, my_record, my_key):
        new_node = Node(my_record, my_key)
        if self.head:
            current_node = self.head
            if current_node.key < self.head.key:
                OLL.insert_before_after(new_node, self.head, self.head.forward)
                self.head = new_node
            while current_node.forward.key < my_key and current_node.forward != self.head:
                current_node = current_node.forward
            #current_node now points to the left of the insertion point
            OLL.insert_before_after(new_node, current_node, current_node.forward)
        else:
            self.head = new_node
            new_node.forward = new_node
            new_node.back = new_node

    def delete_node(self, current_node):
        if self.head == current_node:
            self.head = current_node.forward
        left = current_node.back
        right = current_node.forward
        left.forward = right
        right.back = left

    def delete(self, key):
        current_node = self.head
        if current_node.forward == current_node:
            # there is only one node left
            self.head = None
        while True:
            if current_node.key == key:
                self.delete_node(current_node)
                return
            else:
                current_node = current_node.forward
                if current_node == self.head:
                    return 
                
    def show(self):
        if not self.head:
            print('empty')
            return
        print(self.head.key, self.head.record, sep=': ')
        current_node = self.head.forward
        while current_node != self.head:
            print(current_node.key, current_node.record, sep= ': ')
            current_node = current_node.forward

if __name__ == '__main__':
    oll = OLL()
    oll.insert('z',1)
    oll.insert('a', 100000)
    oll.insert('d', 2)
    oll.insert('e', 3)
    for _ in range(10):
        x = random.getrandbits(16)
        print(x)
        oll.insert( 3*str(x),x )
    oll.show()