skiplist.py

skiplist.py

#! /usr/bin/python2.6
# coding: utf-8

# ref: http://live-e.naist.jp/sensor_overlay/5/doc/yoshida.pdf
# ref: http://en.wikipedia.org/wiki/Skip_list
# ref: http://msdn.microsoft.com/en-us/library/Aa289151

# 利点
# バランス操作が不要
# lock-free

# TODO: 参考にするべき実装を探す
# ->
# ->
# ->


import random

class ListNode(object):
    """skip list node
       +-----------+                         
 --->  |  link[3]  | ----------------------------------------->
       +-----------+                         +-----------+
 --->  |  link[2]  | ----------------------> |  link[2]  | --->
       +-----------+      +-----------+      +-----------+ 
 --->  |  link[1]  | ---> |  link[1]  | ---> |  link[1]  | --->
       +-----------+      +-----------+      +-----------+ 
 --->  |  link[0]  | ---> |  link[0]  | ---> |  link[0]  | --->
       +-----+-----+      +-----+-----+      +-----+-----+ 
       |     |     |      |     |     |      |     |     | 
       | key | val |      | key | val |      | key | val | 
       |     |     |      |     |     |      |     |     | 
       +-----+-----+      +-----+-----+      +-----+-----+ 
    """
    __slots__ = ['key', 'value', 'link']
    def __init__(self, key, value, link):
        self.key = key
        self.value = value
        self.link = link


class SkipList(object):
    _hidden = ListNode(None, None, [])
    def __init__(self, prop = .5, level = 3):
        self.prop = prop
        self.level = level
        self.tail = ListNode(self._hidden, self._hidden, [])
        self.head = ListNode(self._hidden, self._hidden, [self.tail] * level)

    def findfrom(self, node, key, level, prevlist = None):
        """find node from current node level."""
        #print 'find',key,'at',level,node
        #print node
        #print
        if node.key == key:
            return node
        while True:
            nnode = node.link[level]
            if   nnode.key == key:
                return nnode
            elif nnode.key > key:
                return node
            elif nnode is self.tail:
                return node
            else:
                node = nnode

    def get(self, key, route = None):
        """if parameter 'route' is passed, then route is traced for insertion"""
        node = self.head
        for i in range(self.level):
            node = self.findfrom(node, key, self.level - i - 1)
            if node.key == key:
                #print '**found!'
                return node.value
            if route is not None:
                route.append(node)
        if not route:
            raise IndexError

    def insert(self, key, value):
        """insert new item"""
        node = ListNode(key, value, [])
        
        route = []
        self.get(key, route)

        node.link.append(route[self.level - 1].link[0])
        route[self.level - 1].link[0] = node

        for i in range(1, self.level):
            if random.random() >= self.prop:
                # move link to new item
                link = route[self.level - i - 1].link[i]
                node.link.append(link)
                # link new item from routeious node for level i
                route[self.level - i - 1].link[i] = node
            else:
                break

    def remove(self, key):
        """remove item"""
        pass


    def __getitem__(self, key):
        return self.get(key)
    def __setitem__(self, key, value):
        self.insert(key, value)