import sys, os
from sets import Set
from math import log

NODECOLOR = "blue"
KEYCOLOR = "green"

def log2int(x):
    return int(log(x) / log(2))

MAXID = 360

nodePositions = [12, 30, 52, 68, 87, 125, 135, 161, 182, 220, 245, 289, 305, 327, 353]

def findKeySuccessor(key, nodes):
    s = nodes[0]
    for x in nodes:
        if x.id >= key:
            s = x
            break
    return s

def getLocation(key):
    if key < 23:
        return "top"
    elif key < (45+23):
        return "urt"
    elif key < (90+23):
        return "rt"
    elif key < (135+23):
        return "lrt"
    elif key < (180+23):
        return "bot"
    elif key < (225+23):
        return "llft"
    elif key < (270+23):
        return "lft"
    elif key < (315+23):
        return "ulft"
    else:
        return "top"

class Node:
    def __init__(self, id, isKey):
        self.id = int(id * 256 / 360)
        self.pos = id
        self.fingers = Set()
        self.successor = 0
        if isKey:
            self.isKey = 1
            self.color = KEYCOLOR
        else:
            self.isKey = 0
            self.color = NODECOLOR

    def findSuccessor(self, nodes):
        self.successor = findKeySuccessor(self.id+1, nodes)
        
    def findFingers(self, nodes):
        for i in range(log2int(MAXID)):
            d = 2**i
            key = (self.id + d) % MAXID
            self.fingers.add(findKeySuccessor(key, nodes))

    def drawNode(self, file):
        file.write("node(%d, nodes[%d], %d, %s, %s, \"%s\");\n" %
                   (self.isKey,
                    self.id, self.pos, self.color,
                    getLocation(self.pos),
                    ((((self.isKey == 0) and "N" or "K")) + str(self.id))))

    def drawSuccessor(self, file):
        if self.isKey == 0:
            file.write("connect(1,  nodes[%d], nodes[%d]);\n" %
                       (self.id, self.successor.id))
        else:
            file.write("directconnect(nodes[%d], nodes[%d]);\n" %
                       (self.id, self.successor.id))
            

    def drawFingers(self, file):
        for x in self.fingers:
            file.write("connect(0, nodes[%d], nodes[%d]);\n" %
                       (self.id, x.id))


nodes = []

def initMP(file):
    file.write("input chord;\n")
    file.write("beginfig(-1);\n")
    file.write("verbatimtex\n")
    file.write("\\documentclass[12pt]{article}\n")
    file.write("\\usepackage{times}\n")
    file.write("\\begin{document}\n")
    file.write("etex;\n")
    file.write("init_chord;\n")
    file.write("path nodes[];\n")

def endMP(file):
    file.write("endfig;\n")
    file.write("verbatimtex\n")
    file.write("\\end{document}\n")
    file.write("etex\n")
    file.write("end\n")

def runMP(filename):
    os.system("mpost " + filename)

def makeNodes(positions, nodes):
    for x in positions:
        nodes.append(Node(x, False))
    for n in nodes:
        n.findSuccessor(nodes)
        n.findFingers(nodes)

def drawNodes(nodes, file):
    for n in nodes:
        n.drawNode(file)

def drawSuccessors(nodes, file):
    for n in nodes:
        n.drawSuccessor(file)

makeNodes(nodePositions, nodes)
key = Node(270, True)
key.findSuccessor(nodes)


f = file("chash1.mp", "w")
initMP(f)
drawNodes(nodes, f)
endMP(f)

f = file("chash2.mp", "w")
initMP(f)
drawNodes(nodes, f)
key.drawNode(f)
key.drawSuccessor(f)
endMP(f)

f = file("successors.mp", "w")
initMP(f)
drawNodes(nodes, f)
key.drawNode(f)
key.drawSuccessor(f)
drawSuccessors(nodes, f)
endMP(f)

f = file("fingers1.mp", "w")
initMP(f)
drawNodes(nodes, f)
key.drawNode(f)
key.drawSuccessor(f)
#drawSuccessors(nodes, f)
nodes[0].drawFingers(f)
endMP(f)

f = file("fingers2.mp", "w")
initMP(f)
drawNodes(nodes, f)
key.drawNode(f)
key.drawSuccessor(f)
#drawSuccessors(nodes, f)
nodes[9].drawFingers(f)
endMP(f)


# filename = "foo.mp"
# f = file(filename, "w")
# initMP(f)
# drawNodes(nodes, f)
# drawSuccessors(nodes, f)
# nodes[0].drawFingers(f)
# nodes[9].drawFingers(f)
# key.drawNode(f)
# key.drawSuccessor(f)
# endMP(f)
#runMP(filename)