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

'''SI 486D Spring 2013
   This is a skeleton for a skip list class that only supports
   insertion of height-1 nodes.
 
   Nodes are stored in "towers" which contain a list of forward-facing
   links ("flinks"), as well as a key and a value.
 
   To demo on a small random example, run 'python3 skiplist.py"
'''
 
import random
 
class SkipList:
    class Tower:
        def __init__(self, h, key, value=None):
            self.key = key
            self.value = value
            self.flinks = [None] * (h+1)
 
    def __init__(self):
        self.start = self.Tower(0, float('-inf'))
        self.end = self.Tower(0, float('+inf'))
        self.start.flinks[0] = self.end
        self.size = 0
 
    def height(self):
        return len(self.start.flinks) - 1
 
    def __len__(self):
        return self.size
 
    def insert(self, key, value=None):
        h = 1 # TODO: choose height randomly!
        newTower = self.Tower(h, key, value)
 
        # Grow height of start/end as needed
        while h >= self.height():
            self.start.flinks.append(self.end)
            self.end.flinks.append(None)
 
        currentTower = self.start
        level = len(currentTower.flinks)-1
        while level >= 0:
            if key > currentTower.flinks[level].key:
                # Move right if we can on this level
                currentTower = currentTower.flinks[level]
            else:
                # Otherwise go down a level
                if level <= h:
                    # Insert the new tower on this level
                    newTower.flinks[level] = currentTower.flinks[level]
                    currentTower.flinks[level] = newTower
                level -= 1
        
        self.size += 1
 
    def __str__(self):
        '''Returns a nice pretty representation of the skip list'''
        toret = ""
        for level in reversed(range(self.height()+1)):
            currentTower = self.start
            while currentTower is not self.end:
                rep = '({})'.format(currentTower.key)
                if level >= len(currentTower.flinks):
                    rep = '-' * len(rep)
                toret = toret + rep + '--'
                currentTower = currentTower.flinks[0]
            toret = toret + '({})\n'.format(currentTower.key)
        return toret
 
if __name__ == '__main__':
    # Randomly insert 10 numbers and print the resulting skip list
    S = SkipList()
    for i in range(10):
        S.insert(random.randrange(100), 'this is the value')
    print(S)