import random
def random_level(max_level):
    num = random.randint(1, 2**max_level - 1)
    lognum = math.log(num, 2)
    level = int(floor(lognum))
    return max_level - level

print random_level(8)
print random_level(8)
print random_level(8)
print random_level(8)
print random_level(8)
print random_level(8)

class Node(object):
    def __init__(self, value, level=0):
        self.value = value
        self.next = [None] * level
    
    def __str__(self):
        return "Node(%s,%s)" % (self.value, len(self.next))
    __repr__ = __str__
    
class SkipList(object):
    def __init__(self, max_level=8):
        self.max_level = max_level
        n = Node(None, max_level)
        self.head = n
        self.verbose = False
    
    def update_list(self, value):
        update = [None] * (self.max_level)
        n = self.head
        
        self._n_traverse = 0
        
        level = self.max_level - 1
        while level >= 0:
            if self.verbose and \
                n.next[level] != None and n.next[level].value >= value:
                print 'DROP down from level', level + 1
            while n.next[level] != None and n.next[level].value < value:
                self._n_traverse += 1
                if self.verbose:
                    print 'AT level', level, 'value', n.next[level].value
                n = n.next[level]
            update[level] = n
            level -= 1

        return update
    
    def find(self, value, update=None):
        if update is None:
            update = self.update_list(value)
                        
        if len(update) > 0:
            candidate = update[0].next[0]
            if candidate != None and candidate.value == value:
                return candidate
        return None
    
    def insert_node(self, value, level=None):
        if level is None:
            level = random_level(self.max_level)
            
        node = Node(value, level)
        
        update = self.update_list(value)
        if self.find(value, update) == None:
            for i in range(level):
                node.next[i] = update[i].next[i]
                update[i].next[i] = node
    
def print_level(sl, level):
    print 'level %d:' % level,
    node = sl.head.next[level]
    while node:
        print node.value, '=>',
        node = node.next[level]
    print 'END'
        

# create and load a skiplist with max level of 4
x = SkipList(4)
for i in range(0, 20, 2):
    x.insert_node(i)

# print out the data structure
print_level(x, 0)
print_level(x, 1)
print_level(x, 2)

# verbalize the insertion process for '11'
x.verbose = True
print 'INSERT', 11
x.insert_node(11)
print 'DONE;', x._n_traverse, 'traversals'

# print out the updated data structure
print_level(x, 0)
print_level(x, 1)
print_level(x, 2)

# do a random simulation to evaluate how many traversals need to be done to reach
# the last element in the list
def skiplist_traverse_mc(max_level, max_count, n=100):
    z = []
    for _ in range(n):
        x = SkipList(max_level)
        for i in reversed(range(max_count)):
            x.insert_node(i)
        
        x.find(254)
        z.append(x._n_traverse)

    return z


avgs = []
for i in range(1, 10):
    z = skiplist_traverse_mc(i, 200)
    avgs.append((i, average(z)))

avgs = numpy.array(avgs)

# graph average to traverse to last of 200 elements
plot(avgs[:,0], avgs[:,1])
axis(ymin=0, xmin=0)
xlabel('skiplist max level')
ylabel('time to traverse to last of 200 elements')