gistfile1.py

import random
import math

def sort_by_z_order(a,b):
    return a.z_value - b.z_value

def push_zeros(a, n):
    if len(a) < n:
        for i in xrange(n-len(a)):
            a = '0' + a
        return a
        a = '0'*(n-len(a)) + a
    return a

def interleave(a,b):
    ret = ""
    for i in range(len(a)):
        ret = ret + a[i] + b[i]
    return ret

def gen_membership_vector(n):
    n_digit = int(math.ceil(math.log(n,2)))
    ret = ''
    for i in xrange(n_digit):
        ret += str(random.randint(0,1))

    return ret

def print_points(points):
    for p in points:
        print p.z_value

def calc_z_value(x,y, n):
    s1 = format(x, 'b')
    s2 = format(y, 'b')
    s1 = push_zeros(s1, n)
    s2 = push_zeros(s2,n)
    bits = interleave(s1, s2)
    return int(bits, 2), bits



class Point():
    def __init__(self, x, y):
        self.pos = (x,y)
        self.z_value, _ = calc_z_value(x,y,3)

class SkipGraph():
    class Node():
        def __init__(self, key, value):
             self.key = key
             self.value = value
             self.neighbors = []
             self.membership_vectors = None

        def get_prev(self, level):
            return self.neighbors[level][0]

        def set_prev(self, level, val):
            self.neighbors[level][0] = val
            
        def get_next(self, level):
            return self.neighbors[level][1]

        def set_next(self, level, val):
            self.neighbors[level][1] = val

        def show_neighbor(self, level):
            prev =  self.get_prev(level)
            nxt = self.get_next(level)
            s1 = s2 = None
            if prev != None:
                s1 = prev.key
            if nxt != None:
                s2 = nxt.key

            print "Node %d, %s: " % (self.key, self.membership_vectors),
            print (s1, s2)
                

    def __init__(self):
        self.nodes = []
        self.max_level = 0
	self.current_level = 0
        
    def build(self, points):
        points.sort(sort_by_z_order)
        vec_set = set()
        self.max_level = int(math.ceil(math.log(len(points), 2)))
        
	for i, p in enumerate(points):
            n = self.Node(p.z_value, p)
            n.neighbors = [[None, None]] * self.max_level
            while True:
                vec = gen_membership_vector(len(points))
                if not vec in vec_set:
                    n.membership_vectors = vec
                    vec_set.add(vec)
                    break

            self.nodes.append(n)

        ### build level 0 ###
        self.connect(self.nodes, self.current_level)
        
        self.show_nodes(self.current_level)
        
        ### build level 1 and higher ###
        self.current_level += 1
        
        while self.current_level < self.max_level:
            
            prefixes = gen_prefix(self.current_level)
            for prefix in prefixes:
                neighbors = [node for node in self.nodes if node.membership_vectors.startswith(prefix)]
                if len(neighbors) != 0:
                       self.connect(neighbors, self.current_level)
                       
            self.show_nodes(self.current_level)
            self.current_level += 1
            
        for i in range(self.current_level):
            self.show_nodes(i)
            

    def connect(self, nodes, level):
        nodes[0].set_prev(level, None)
        nodes[-1].set_next(level, None)
        for i in range(1, len(nodes)):
            nodes[i].set_prev(level, nodes[i-1])
            nodes[i-1].set_next(level, nodes[i])
        
    def show_nodes(self, level):
        print "### Level %d neighborhood structure ### " % level
        for node in self.nodes:
            node.show_neighbor(level)
        print
            
    def search(self, key):
        cand = self.find_nearest_key(key)
        if cand.key == key:
            print "Found."
            return cand
        else:
            print "Not found."
            return None

    def find_nearest_key(self, key):
            
        current = self.nodes[random.randint(0, len(self.nodes)-1)]
        level = self.current_level-1
        while True:
            print "Level " + str(level) + " : " + " current " + str(current.key)			                        
            if current.key == key:
                return current
            elif current.key < key:
                nxt = current.get_next(level)
                print nxt
                if nxt != None and nxt.key <= key:
                    current = nxt
                else:
                    if level > 0:
                        level -= 1
                    else:
                        ### reached at the level 0. current has the nearest key. ###
                        return current
            else:
                prev = current.get_prev(level)
                if prev != None and prev.key >= key:
                    current = prev
                else:
                    if level > 0:
                        level -= 1
                    else:
                        ### reached at the level 0. current has the nearest key. ###
                        return current
            

            
        


    def range_search(self, key1, key2):
	assert key1 <= key2, "key1 has to be less than key2"
	start_node =  self.find_nearest_key(key1)
	last_node = self.find_nearest_key(key2)
        print "(start, end) : (%d, %d)" % (start_node.key, last_node.key)
	return self._range_search(start_node, last_node, len(self.levels)-1)

    def _range_search(self, start, end,level):
        pass




def gen_membership_vector(n):
    n_digit = int(math.ceil(math.log(n,2)))
    ret = ''
    for i in xrange(n_digit):
        ret += str(random.randint(0,1))

    return ret

def gen_prefix(n):
    return [push_zeros(format(i, 'b'), n) for i in range(2**n)]
    
        
def print_points(points):
    for p in points:
        print (p.pos[0], p.pos[1]),

    print

def gen_points(num):
    c, n = 0,num
    points = []
    used = set()
    while c < n :
        x = random.randint(0,7)
        y = random.randint(x, 7)
        p = Point(x,y)
        if (x,y) not in used:
            points.append(p)
            used.add((x,y))
            c += 1

    return points

def test_nearest():
    points = gen_points(10)
    print "Point being queryed: "
    print_points(points)
    
    print "Building Skip Graph ..."
    skgraph = SkipGraph()
    skgraph.build(points)
    
    print "Skip Graph built."

    while True:
        print "Give me a key:", 
        key = int(raw_input())
        print "Search for a key %d" % key
        cand = skgraph.find_nearest_key(key)
        if cand.key == key:
            print "Found %d." % cand.key
        else:
            print "Nearest key %d. " % cand.key
    
        
def test_range():
    points = gen_points(10)
    print "Point being queryed: "
    print_points(points)
    
    print "Building Skip Graph ..."
    print
    
    skgraph = SkipGraph()
    skgraph.build(points)
    
    # print "Skip Graph built."
    # # skgraph.print_me()

    # print "Give me two keys:",
    # line = raw_input()
    # key1, key2 = line.strip().split()
    # key1, key2 = int(key1), int(key2)
    # print "Range search with %d <= key <= %d " % (key1, key2)
    # skgraph.range_search(key1, key2)

test_nearest()