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"""
        levels = len(self.start.successors)
        result = [None]*levels
        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 and right.key < k:
                left, right = right, right.successors[level]
            result[level] = left
        return result

    def findNode(self, k):
        """Returns the first SkipListNode 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