yatt · April 6, 2012 10:50 · Apr 6, 2012 · Apr 6, 2012
diff --git a/skiplist.py b/skiplist.py
@@ -19,13 +19,13 @@
 
 class ListNode(object):
     """skip list node
-       +-----+-----+                         
+       +-----------+                         
  --->  |  link[3]  | ----------------------------------------->
-       +-----+-----+                         +-----+-----+
+       +-----------+                         +-----------+
  --->  |  link[2]  | ----------------------> |  link[2]  | --->
-       +-----+-----+      +-----+-----+      +-----+-----+ 
+       +-----------+      +-----------+      +-----------+ 
  --->  |  link[1]  | ---> |  link[1]  | ---> |  link[1]  | --->
-       +-----+-----+      +-----+-----+      +-----+-----+ 
+       +-----------+      +-----------+      +-----------+ 
  --->  |  link[0]  | ---> |  link[0]  | ---> |  link[0]  | --->
        +-----+-----+      +-----+-----+      +-----+-----+ 
        |     |     |      |     |     |      |     |     | 

diff --git a/skiplist.py b/skiplist.py
@@ -0,0 +1,110 @@
+#! /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)