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:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
|
# A program to implement a skip list.
# TODO: implement the `getNode` function, which is a prerequisite for __getitem__ and __setitem__
# TODO: implement the `length`
import random
import math as np
index_s = None
class Node:
"""
An item in the skip list holding the data itself and pointers to
the successors of the item at all levels.
"""
def __init__(self, data, max_lvl):
self.data = data
self.successors = [None] * (max_lvl + 1)
# By convention, the width is 0 if no successor is present.
# Otherwise it specifies the deviation of the indices between
# this item and the succeeding item in a level.
self.widths = [0] * (max_lvl + 1)
def __str__(self):
return f'Node(data={self.data}, \
successors={list(map(lambda n: n.data if n else None, self.successors))}, \
widths={self.widths})'
class SkipList:
"""
A class modelling a skip list and providing common list operations.
"""
def __init__(self, max_lvl, p):
self.max_lvl = max_lvl
self.head = None
self.p = p
self.self_length = 0
def insert(self, data, index = None):
"""
Insert a new element into the list.
If index isn't specified, or the index exceeds the highest index
in the list, the item is inserted at the tail of the list.
"""
if self.head == None:
self.head = Node(data, self.max_lvl)
return self.head
else:
n = Node(data, self.max_lvl)
if index is not None and index < 1:
# item will be inserted before current head
n.successors = [self.head] * (self.max_lvl + 1)
n.widths = [1] * (self.max_lvl + 1)
self.head = n
else:
current = self.head
# find the item in each level that will preceed the newly inserted item
to_update = [[None, 0]] * (self.max_lvl + 1)
i = 0
for level in range(self.max_lvl, -1, -1):
while current.successors[level] and \
(index == None or current.widths[level] + i < index):
i = i + current.widths[level]
current = current.successors[level]
to_update[level] = (current, i)
# choose the max level in that a pointer to the new item should be added
max_lvl = 0
while random.random() < self.p and max_lvl < self.max_lvl:
max_lvl = max_lvl + 1
# insert the new item and update its predecessors
for level in range(self.max_lvl + 1):
pred, pred_index = to_update[level]
if level <= max_lvl:
n.successors[level] = pred.successors[level]
new_pred_width = i - pred_index + 1
if pred.successors[level]:
n.widths[level] = pred.widths[level] - new_pred_width + 1
pred.widths[level] = new_pred_width
pred.successors[level] = n
else:
pred.widths[level] = pred.widths[level] + 1
index_s = index
self.self_length += 1
return n
def get_node(self, k):
"""
x = self.head
pos = 0
for i in range(self.max_lvl, -1, -1):
while pos + x.widths[i] < k:
pos = pos + x.widths[i]
x = x.successors[i]
if x == None:
return None
else:
return x
"""
node = self.head
k += 1
for level in reversed(range(self.max_lvl)):
while node.widths[level] <= k:
k -= node.widths[level]
node = node.successors[level]
return node
"""
Returns the node of this skip list at the given index or None if no
item exist for this index.
"""
# TODO your code here
def __getitem__(self, index):
"""Overwrites reading with the array operator `list[i]`."""
n = self.get_node(index)
if n:
return n.data
else:
raise IndexError
def __setitem__(self, index, value):
"""Overwrites writing with the array operator `list[i]`."""
n = self.get_node(index)
if n:
n.data = value
else:
raise IndexError
def updateList(self, elem):
update = [None]*self.max_lvl
x = self.head
for i in reversed(range(self.max_lvl)):
while x.successors[i] != None and x.successors[i].data < elem:
x = x.successors[i]
update[i] = x
return update
def __len__(self):
"""Return the amount of items in this list."""
# TODO your code here
return self.self_length
def __str__(self):
result = ""
if self.head:
for i in range(self.max_lvl, -1, -1):
str = f"lvl {i}: {self.head.data}"
current = self.head
while current.successors[i]:
str += f" -{current.widths[i]}> {current.successors[i].data}"
current = current.successors[i]
if result != "":
result += "\n"
result += str
return result
if __name__ == 'builtins' or __name__ == '__main__':
l = SkipList(4, .5)
l.insert(15)
l.insert(4)
l.insert(2)
l.insert(5)
l.insert(10)
l.insert(11)
l.insert(56)
l.insert(200, 0)
l.insert(400, 7)
print("Skip List structure:")
print(l) |