skiplist.py

## More infromation about SkipList data structure one can find:
## on Wikipedia http://en.wikipedia.org/wiki/Skip_list
## on Stackoverflow http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree

from math import log
from random import randint, random

class SkipNode(object):
    __slots__ = "value", "next"

    def __init__(self, value, height):
        self.value = value
        self.next = [None] * height

    def __str__(self):
        return str(self.value)

class SkipList(object):

    def __init__(self, expected_size=100):
        self.maxlevel = int(1 + log(expected_size, 2.0))
        self.head = SkipNode("HEAD", self.maxlevel)

    def __iter__(self):
        cur = self.head 
        while cur is not None:
            yield cur.value 
            cur = cur.next[0]

    def _prepare_links(self, el):
        cur, links = self.head, [None] * self.maxlevel
        for level in reversed(range(self.maxlevel)):
            while cur.next[level] is not None \
                and cur.next[level].value < el:
                cur = cur.next[level]

            links[level] = cur

        return links

    def find(self, el, links=None):
        links = links or self._prepare_links(el) 
        last = links[0].next[0]
        if last is not None and last.value == el:
            return last 
        return None

    def insert(self, el):
        links = self._prepare_links(el)
        if self.find(el, links) is None:
            node = SkipNode(el, self.maxlevel)
            height = min(self.maxlevel, int(1 - log(random(), 2.0)))
            for level in range(height):
                node.next[level] = links[level].next[level]
                links[level].next[level] = node

    def remove(self, el):
        pass

sl = SkipList()
map(sl.insert, [randint(1, 100) for _ in range(10)])
print list(sl)

# node = SkipNode(10, sl.maxlevel)
# sl.head.next[0] = node
# print sl.find(10)