class SkipListNode: def __init__(self, key, value, successors): self.key = key self.value = value self.successors = successors import random ## possible goals: ## - improve our testing ## - more serious augmentation: order statistics ## - probabilistic analysis of efficiency class SkipList: def __init__(self): self.end = SkipListNode(None, None, None) self.start = SkipListNode(None, None, [self.end]) # only level 0 self.length = 0 #level 0 is direct links, higher levels bypass progressively more nodes def __len__(self): return self.length def find(self, k): """Returns a list with one entry per level of the last node with key = k""" predecessors = self.find(k) immediatePredecessor = predecessors[0] return immediatePredecessor.successors[0] def __setitem__(self, k, v): p = self.find(k) n = p[0].successors[0] if n.key == k: n.value = v else: self.length += 1 levels = 1 while random.randint(0, 1) == 0: levels += 1 while levels > len(p): p.append(self.start) self.start.successors.append(self.end) # now we know the skip list is ready for our number of levels successors = [p[level].successors[level] for level in range(levels)] n = SkipListNode(k, v, successors) for level in range(levels): p[level].successors[level] = n def __getitem__(self, k): n = self.findNode(k) if n.key == k: return n.value else: raise KeyError(k) def __iter__(self): n = self.start.successors[0] while n != self.end: yield n.key n = n.successors[0] def __delitem__(self, k): p = self.find(k) n = p[0].successors[0] if n.key != k: raise KeyError(k) else: self.length -= 1 for level in range(len(n.successors)): p[level].successors[level] = n.successors[level] for level in reversed(range(1,len(self.start.successors))): if self.start.successors[level] == self.end: self.start.successors.pop() else: break def clear(self): self.start = SkipListNode(None, None, [self.end]) # only level 0 self.length = 0 def min(self): """Returns the minimum key with its value, or raises a ValueError""" n =self.start.successors[0] if n == self.end: raise ValueError("min of an empty SkipList") return (n.key, n.value) def __contains__(self, k): n = self.findNode(k) return n.key == k def successor (self, k): n = self.findNode(k) if n.key == k: returnValue = n.successors[0].key else: returnValue = n.key if returnValue == None: raise KeyError(k) return returnValue def predecessor(self, k): predecessors = self.find(k) predecessorKey = predecessors[0].key if predecessorKey == None: raise KeyError(k) return predecessorKey def max(self): """Returns the maximum key with its value, or raises a ValueError""" levels = len(self.start.successors) left = self.start for level in reversed(range(levels)): # do a search with left finger following right finger right = left.successors[level] while right != self.end: left, right = right, right.successors[level] if left == self.start: raise ValueError("max of an empty SkipList") return (left.key, left.value) ##s = SkipList() ##for i in range(100000): ## s[i] = i*10