from random import *
import psyco
psyco.full()
#chord simulator

#input format
# join n - node n joins the system. The node contacted by n is chosen randomly.
# leave n - node n leaves the system
# fail n - node n fails
# insert n id - insert document id; the operation is initiated by node n
# find n id - find document id; the operation is initiated by node n
# exit - terminate simulation 

#for each node: membership in bytes
#               # of messages in
#               # of messages out
#for each search: success/not
#                # of hops

#calculates the distance around the chord ring from id1 to id2
def distance(id1, id2):
    if (id1 == id2):
        return 0
    elif(id1 < id2):
        return id2-id1
    else:
        return (2**160-id1)+id2

def isSuccessor(vid, successor):
    #if the predecessor of the successor is larger than the successor
    #then this is the special case where the range of the successor contains 0
    #print "id: "+repr(vid)
    #print "successor: "+repr(successor)
    predecessor = vnodes[successor].predecessor
    #print "predecessor: "+repr(predecessor)
    if (predecessor >= successor):
        #print "special case "+repr((vid > predecessor) or (vid <= successor))
        return (vid > predecessor) or (vid <= successor)
    else:
        return (vid > predecessor) and (vid <= successor)

def randVID(id):
    return id*(2**32)+randint(0,2**32-1)

nodes = {}
vnodes = {}
msgInPerNode = {}
msgOutPerNode = {}
hopsPerSearch = []

k = 5

routingType = "k"

def countMsg(sender, receiver):
    if sender != receiver:
        msgInPerNode[receiver] = msgInPerNode.get(receiver,0)+1
        msgOutPerNode[sender] = msgOutPerNode.get(sender,0)+1
        
class Node:
    def __init__(self, nodeid):
        self.nodeid = nodeid
        self.virtualNodes = []

    def findNextHop(self, id, nodeid):
        global msgInPerNode, msgOutPerNode
        countMsg(nodeid, self.nodeid)
        fingers = []
        for n in self.virtualNodes:
            fingers.append(vnodes[n].findNextHop(id))
        best = min(fingers,
                   key = lambda x: distance(x,id))
        if best == id:
            return vnodes[best].predecessor
        else:
            return best
        
    def addVnode(self, id):
        self.virtualNodes.append(id)

class VirtualNode:
    def __init__(self, nodeid, vid, predecessor, successor):
        self.nodeid = nodeid
        self.vid = vid
        self.predecessor = predecessor
        self.successor = successor
        self.fingers = []
        self.uniqueFingers = set()
        
        if routingType == "chord":
            if successor != vid:
                countMsg(self.nodeid, self.successor)
                self.fingers = list(vnodes[successor].fingers)
                m = 0
                while(2**m <= distance(vid,successor)):
                    self.fingers[m] = successor 
                    m = m+1
                self.uniquifyFingers()
            else:
                self.fingers = [-1 for i in range(160)]            
        elif routingType == "k":
            self.fingers = [-1 for i in range(k)]
            if successor != vid:
                suc = self.successor
                i = 0
                while ((suc != self.vid) and (i < k)):
                    countMsg(self.nodeid, vnodes[suc].nodeid) 
                    self.fingers[i] = suc
                    suc = vnodes[suc].successor
                    i = i+1
                self.uniquifyFingers()
               
            
    def findNextHop(self, id):
        if len(self.uniqueFingers) > 0:
            return min(self.uniqueFingers,
                       key = lambda x: distance(x,id))
        else:
            return self.successor
        
    def setSuccessor(self, id, nodeid):
        #print "set successor: "+repr(self.vid)
        global msgInPerNode, msgOutPerNode
        self.successor = id
        countMsg(nodeid, self.nodeid)
        if routingType == "chord":
            m = 0
            while(2**m <= distance(self.vid,self.successor)):
                #print "node "+repr(self.vid)+" setting suc finger "+repr(m)+" = "+repr(self.successor)
                self.fingers[m] = self.successor 
                m = m+1
            self.uniquifyFingers()
        elif routingType == "k":
            self.fingers[0] = self.successor
            self.uniquifyFingers()
            
    def setPredecessor(self, id, nodeid):
        global msgInPerNode, msgOutPerNode
        self.predecessor = id
        countMsg(nodeid, self.nodeid)

    def setFinger(self, m, finger):
        self.fingers[m] = finger

    def uniquifyFingers(self):
        self.uniqueFingers = set(self.fingers)
        if -1 in self.uniqueFingers:
            self.uniqueFingers.remove(-1)
        if (self.vid in self.uniqueFingers):
            self.uniqueFingers.remove(self.vid)
        #print "node "+repr(self.vid)+" fingers: "+repr(self.fingers)
        #print "Node "+repr(self.vid)+" finger table: "+repr(id(self.fingers))
        #print "node "+repr(self.vid)+" fingers "+repr(self.uniqueFingers)

    def totalData(self):
        #count fingers plus successor and predecessor pointers
        return len(self.uniqueFingers) + 2
class Chord:
    def __init__(self, n, v):
        global nodes,vnodes
        nodes = n
        vnodes = v
        seed()
        global msgInPerNode, msgOutPerNode, hopsPerSearch
        msgInPerNode = {}
        msgOutPerNode = {}
        hopsPerSearch = []

    def join(self, nodeid):
        #print "Node "+ repr(nodeid) + " joined"
        nodes[nodeid] = Node(nodeid)
        return 1

    def findSuccessor(self, id, nodeid):
        if len(nodes[nodeid].virtualNodes) > 0:
            pred = self.findPredecessor(id, nodeid)
            return vnodes[pred].successor
        else:
            return -1

    def findPredecessor(self, id, nodeid):
        #print "searching for: "+repr(id)
        global hopsPerSearch
        hops = [nodeid]
        nextHopID = nodes[nodeid].findNextHop(id,nodeid)
        nextHop = vnodes[nextHopID]
        hops.append([nextHop.nodeid, nextHopID])
        numHops = 0
        while (not isSuccessor(id,nextHop.successor)):
            nextHopID = nodes[nextHop.nodeid].findNextHop(id,nodeid)
            #print "next hop: "+repr(nextHopID)
            nextHop = vnodes[nextHopID]
            #print "searching for "+repr(id)
            #print "available fingers: "+repr(nextHop.uniqueFingers)
            #print "vnodes: "+repr(vnodes.keys())
            #print "fingers "+repr(nextHop.uniqueFingers)
            if hops[len(hops)-1] != nextHopID:
                numHops = numHops+1
            hops.append([nextHop.nodeid,nextHopID])
        #print "Node "+repr(nodeid)+" found predecessor of "+repr(id)+" in "+repr(numHops)+" hops"
        #print "Path: "+repr(hops)
        hopsPerSearch.append(numHops)
        return nextHopID

    def insert(self, id, nodeid):
        #print "Node "+ repr(nodeid) + " inserted " + repr(id)
        if len(nodes[nodeid].virtualNodes) > 0:
            return self.insertN(id, nodeid, nodeid)
        elif len(vnodes.keys()) > 0:
            keys = nodes.keys()
            shuffle(keys)
            for k in keys:
                if len(nodes[k].virtualNodes) > 0:
                    return self.insertN(id, nodeid, k)
        else:
            vnodes[id] = VirtualNode(nodeid, id, id, id)
            nodes[nodeid].addVnode(id)
        return 1

    def insertN(self, id, nodeid, othernodeid):
        global msgInPerNode, msgOutPerNode
        countMsg(nodeid, othernodeid)
        successor = self.findSuccessor(id, othernodeid)
        if successor == id:
            return 0
        else:
            predecessor = vnodes[successor].predecessor
            #print "insert successor: "+repr(successor)+" predecessor"+repr(predecessor)
            vnodes[id] = VirtualNode(nodeid, id, predecessor, successor)
            nodes[nodeid].addVnode(id)
            vnodes[successor].setPredecessor(id, nodeid)
            vnodes[predecessor].setSuccessor(id, nodeid)            
        return 1
    
    def stabilize(self):
        if routingType == "chord":
            self.chordStabilize()
        elif routingType == "k":
            self.kStabilize()
        
    def chordStabilize(self):
        #print "stabilize ------"
        global vnodes
        for n in nodes.values():
            if len(n.virtualNodes) > 0:
                v = vnodes[choice(n.virtualNodes)]
                #send message to successor node
                countMsg(v.nodeid,vnodes[v.successor].nodeid)
                #pick random finger to check
                m = randint(0,159)
                start = (v.vid+2**(m-1))%(2**160)
                finger = self.findSuccessor(start,v.nodeid)
                #print "finger: "+repr(finger)
                while(2**m <= distance(v.vid,finger)):
                    #print "node "+repr(n.vid)+" setting finger "+repr(m)+" = "+repr(finger)
                    v.setFinger(m,finger)
                    m = m+1
                    v.uniquifyFingers()
                #print "done stabilizing ------"
        
    def kStabilize(self):
        global vnodes
        if len(vnodes) > 1:
            for n in vnodes.values():
                suc = n.successor
                i = 0
                while ((suc != n.vid) and (i < k)):
                    countMsg(n.nodeid, vnodes[suc].nodeid) 
                    n.setFinger(i, suc)
                    suc = vnodes[suc].successor
                    i = i+1                                        
                n.uniquifyFingers()
                
    def getNodes(self):
        return nodes

    def getVnodes(self):
        return vnodes

    def getMsgInPerNode(self):
        return msgInPerNode

    def getMsgOutPerNode(self):
        return msgOutPerNode

    def getHopsPerSearch(self):
        return hopsPerSearch

    def getRoutingDataPerNode(self):
        r = []
        for n in nodes.values():
            data = 0
            for i in n.virtualNodes:
                data = data + vnodes[i].totalData()
            r.append(data)
        return r

    def clearStats(self):
        global msgInPerNode, msgOutPerNode, hopsPerSearch
        msgInPerNode = {}
        msgOutPerNode = {}
        hopsPerSearch = []