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 get_next(self, level):
            return self.neighbors[level][1]


    def __init__(self):
        self.nodes = []
	
    def build(self, points):
        points.sort(sort_by_z_order)
	for i, p in enumerate(points):
            n = Node(p.z_value, p)

            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)

        
                  


    def print_me(self):
        pass

    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):
        pass

    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 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."
    skgraph.print_me()

    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 ..."
    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)