skiplist/skiplist.py at master · pctablet505/skiplist · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
from random import randint


class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.top = None
        self.bottom = None
        self.data = data


class Skiplist:
    def __init__(self):
        self.left_top = Node(float('-inf'))
        self.right_top = Node(float('inf'))
        self.left_top.right = self.right_top
        self.right_top.left = self.left_top

    def search(self, data):
        curr = self.left_top
        while True:
            while curr.right.data < data:
                curr = curr.right
            if curr.bottom is None:
                break
            curr = curr.bottom

        if curr.right.data == data:
            return curr.right
        return None

    def insert(self, data):
        stack = []
        curr = self.left_top
        while True:
            while curr.right.data < data:
                curr = curr.right
            if curr.bottom is None:
                break
            stack.append(curr)

            curr = curr.bottom
        if curr.right.data == data:
            return

        new_node = Node(data)
        new_node.right = curr.right
        new_node.right.left = new_node
        new_node.left = curr
        curr.right = new_node
        curr = new_node

        while randint(0, 1) == 1:

            if stack:
                prev = stack.pop()
                new_node = Node(data)
                curr.top = new_node
                new_node.bottom = curr
                curr = new_node
                curr.left = prev
                curr.right = prev.right
                prev.right = curr
                curr.right.left = curr
            else:
                new_node = Node(data)
                curr.top = new_node
                curr.top.bottom = curr
                curr = new_node
                curr.right = Node(float('inf'))
                curr.right.left = curr
                curr.left = Node(float('-inf'))
                curr.left.right = curr
                curr.left.bottom = self.left_top
                self.left_top.top = curr.left
                self.left_top = curr.left
                curr.right.bottom = self.right_top
                self.right_top.top = curr.right
                self.right_top = curr.right

    def remove(self, data):
        curr = self.search(data)
        if curr is None:
            return
        while curr:
            curr.left.right = curr.right
            curr.right.left = curr.left
            curr = curr.top
            if curr:
                del (curr.bottom)

    def __str__(self):
        s = ''
        lmost = self.left_top

        while lmost:
            curr = lmost
            while curr:
                s += str(curr.data) + '  '
                curr = curr.right
            s += '\n'
            lmost = lmost.bottom
        return s

t = Skiplist()
for i in range(10):
    t.insert(i)