'''
Created on Jan 23, 2011
Modified on July 9, 2012
@author: Dilum Bandara
@version: 1.0
@license: Apache License v2.0

   Copyright 2012 H. M. N. Dilum Bandara and Anura P. Jayasumana, Colorado State
   University

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
'''

from BaseHash import BaseHash
from DHT import DHT
from FingerTable import FingerTable
from OverlayMsg import OverlayMsg
from PeerID import PeerID
import PeerManager as PM
import Distance as Distance
import Config
import copy
import math
import random


class Overlay(object):
    '''
    Chord overlay class. 
    '''
    def __init__(self, PID, gSucce = None, gPrede = None, fingerTable = None):
        '''
        Constructor
        @param NID: Node ID 
        @param gSucce: List of global successors
        @param gPrede: List of global predecessors
        @param fingerTable: Finger table if available   
        '''        
        self.PID = PID
        self._gSucce = [gSucce, 0]
        self._gPrede = [gPrede, 0]
        self._FT = FingerTable() if fingerTable is None else fingerTable 
        self._fingerUpdateCost = 0
        self._infoNotAPrede = None #Nodes to inform if this node is not a prede
        self._numMsgRec = 0 #No of messages received by this node (any msg)
        self._numMsgRecInt = 0 #No of msgs received within stat collect interval
        self._msgInEWMA = 0 #Messages arriving at this node
        self._msgInTime = [] #Time that messages were received. Sliding window
        self._firstRound = True #No action during 1st load check round 
        #Set finger table update timers
        self._hashFun = BaseHash(Config.MAX_KEY)
        intTime = random.randint(Config.FIX_FINGER_INTERVAL/2, \
                                 Config.FIX_FINGER_INTERVAL)#Next fixFinger time
        PM.EVENTS.addEvent(PM.EVENTS.now + intTime, 'FIXFINGER', PID.NID)
        PM.STAT.trackStat('AddN', [PID.NID, PID.gKey])


    def __del__(self):
        '''
        Destructor
        '''
        self._gSucce = []
        self._gPrede = []
        self._FT = None
        self._msgInTime = []


    def join(self, joinNode = None, whatToNotify = None):
        '''
        Join overlay
        @param joinNode: Node to use for boostraping (Peer ID)
        @param nodeList: Node list to be used with notify messages 
        '''
        if whatToNotify == None: whatToNotify = []
        if joinNode is None: #Probably 1st node
            if self._gPrede[0] is None: #No predecessor
                self._gPrede = [[copy.deepcopy(self.PID)], 0]
                self._gSucce = [[copy.deepcopy(self.PID)], 0]
                return
        #More nodes so initialize finger table & notify nodes that point to me
        self._initFT(joinNode)
        self._fingerUpdateCost += self._notify(whatToNotify)


    def leaveOverlay(self, hasCMembers = False, sendNotification = True, \
                                        infoRemMe = False, notifyOnly = False):
        '''
        Leave overlay. Inform global predecessors & successors that node is 
        leaving. Change their fingers if this is the only node at this global 
        keys. Then Leave. Keys should have been already moved. Called by DHT
        @param hasCMembers: Are there other cluster members
        @param sendNotification: Send a notification message indicating departure
        @param infoRemMe: Inform predecessor & successor that this node left
        @param notifyOnly: Send only a notification message   
        '''
        #Set my successors' predecessor(s) to my predecessor. My predecessors' 
        #successor(s) to my successor
        #If there are no other cluster member change predecessor & successor
        if sendNotification: #1st notify my departure then change succe & prede
            msgCost = self._notify([[self.PID.gKey, [], [self.PID]]])
            PM.STAT_CHECK_LOAD.append(msgCost)

        #No cMembers, change prede & successor pointers
        if (hasCMembers == False) and (notifyOnly == False):
            newMsg = OverlayMsg('NewPrede', self.PID, -1, self._gPrede[0])
            for i in range(len(self._gSucce[0])): #Send to all nodes
                PM.OVERLAY[self._gSucce[0][i].NID].recMsg(newMsg, self.PID.NID)
                PM.STAT_CHECK_LOAD.append(1)
            newMsg = OverlayMsg('NewSucce', self.PID, -1, self._gSucce[0])
            for i in range(len(self._gPrede[0])): #Send to all nodes
                PM.OVERLAY[self._gPrede[0][i].NID].recMsg(newMsg, self.PID.NID)
                PM.STAT_CHECK_LOAD.append(1)
        #Ask predecessor & successor to remove this node
        if ((hasCMembers == True) or (infoRemMe == True)) and \
                                                        (notifyOnly == False):
            newMsg = OverlayMsg('RemPrede', self.PID, -1, [self.PID])
            for i in range(len(self._gSucce[0])): #Send to all nodes
                PM.OVERLAY[self._gSucce[0][i].NID].recMsg(newMsg, self.PID.NID)
                PM.STAT_CHECK_LOAD.append(1)
            newMsg = OverlayMsg('RemSucce', self.PID, -1, [self.PID])
            for i in range(len(self._gPrede[0])): #Send to all nodes
                PM.OVERLAY[self._gPrede[0][i].NID].recMsg(newMsg, self.PID.NID)
                PM.STAT_CHECK_LOAD.append(1)
        
        PM.RESOURCEFUL_PEERS.append(self.PID.NID) #Node is ready to be reselected 
        PM.REMOVE_FROM_OVERLAY.append(self.PID.NID) #Mark for removeal


    def addNewNode(self, newNID, isCMember, newGKey, newLKey, newLStartKey, \
                   myGKey, cMembers, isSucce):
        '''
        Add new node to overlay & DHT layers. It will not join the overlay at
        this point. Will be done separately after transferring keys 
        @param newNID: New node NID 
        @param isMember: Is new node cluster member or not
        @param newGKey: New node's global key
        @param newLKey: New node's local key
        @param newLStartKey: New node's start key for local range
        @param myGKey: My new global key (if changed)
        @param cMembers: List of cluster members
        @param isSucce: Will new node be a successor or predecessor
        '''
        peerPID = PeerID(newNID, newGKey, newLKey, newLStartKey)
        FT = copy.deepcopy(self._FT) #Copy my finger table

        if isCMember == True: #Add as a cluster member
            gPrede = copy.deepcopy(self._gPrede[0]) #My predecessor is its prede
            gSucce = copy.deepcopy(self._gSucce[0]) #My successor is its succe
            PM.OVERLAY[newNID] = Overlay(peerPID, gSucce, gPrede, FT)
            PM.DHT[newNID] = DHT(peerPID, cMembers)
            return
        
        #New node will be added between me & my successor/predecessor        
        if isSucce == True: #Adding a successor. It comes to current location    
            gPrede = cMembers
            gSucce = copy.deepcopy(self._gSucce[0]) #My successor is its succe
            if self._gSucce[0][0].NID == self.PID.NID: #Only 1 node in overlay
                gSucce[0].gKey = myGKey
            #Need to inform current successor that this node is no longer 
            #predecessor. If adding series of successors do this only once
            if self._infoNotAPrede is None: #Empty
                self._infoNotAPrede = copy.deepcopy(self._gSucce[0])
            self._gSucce = [[copy.deepcopy(peerPID)], 0] #Update my successor
            PM.OVERLAY[newNID] = Overlay(peerPID, gSucce, gPrede, FT)
        else: #Adding a predecessor
            gPrede = copy.deepcopy(self._gPrede[0])#My prede is its prede
            gSucce = cMembers #cMembers are succe of new one
            self._gPrede = [[copy.deepcopy(peerPID)], 0] #Update my successor
            PM.OVERLAY[newNID] = Overlay(peerPID, gSucce, gPrede, FT) #No FT        
        PM.DHT[newNID] = DHT(peerPID, {})


    def changeGKey(self, newGKey, whatToNotify, updatePrede = True, \
                                                        updateSucce = True):
        '''
        Change global key & notify. Informed by DHT layer
        @param newGKey: New global key
        @param whatToNotify: List of keys & nodes to send notifications for
        @param updatePrede: Inform predecessor change to successor
        @param updateSucce: Inform successor change to predecessor 
        Expect to contain new GKey  
        '''
        self.PID.gKey = newGKey #Set my key
        for entry in whatToNotify:
            if entry[0] == newGKey: #Inform key change to succe(s) & prede(s)
                if updatePrede:
                    newMsg = OverlayMsg('UpdatePrede', self.PID, -1, entry[1])
                    for i in range(len(self._gSucce[0])):#Send to all successors
                        PM.OVERLAY[self._gSucce[0][i].NID].recMsg(newMsg, \
                                                                  self.PID.NID)
                        PM.STAT_CHECK_LOAD.append(1)
                if updateSucce:
                    newMsg = OverlayMsg('UpdateSucce', self.PID, -1, entry[1])
                    for i in range(len(self._gPrede[0])): #Send to all nodes
                        PM.OVERLAY[self._gPrede[0][i].NID].recMsg(newMsg, \
                                                                  self.PID.NID)
                        PM.STAT_CHECK_LOAD.append(1)
                #Inform if there's a node(s) that this node is no longer a prede
                if self._infoNotAPrede is not None:
                    newMsg = OverlayMsg('RemPrede', self.PID, -1, entry[1])
                    for i in range(len(self._infoNotAPrede)): #Send to all nodes
                        PM.OVERLAY[self._infoNotAPrede[i].NID].recMsg(newMsg, \
                                                                self.PID.NID)
                        PM.STAT_CHECK_LOAD.append(1)
                    self._infoNotAPrede= None #Reset
        #Also notify other relevant nodes
        msgCost = self._notify(whatToNotify)
        PM.STAT_CHECK_LOAD.append(msgCost)
        self.fixFingers()


    def recMsg(self, msg, source):
        '''
        Receive message from overlay neighbor
        @param msg: Message
        @param source: Source node ID
        @return: Response message  
        '''
        self._numMsgRecInt += 1
        self._msgInTime.append(PM.EVENTS.now)
        if (msg.msgType == 'Put') or (msg.msgType == 'Remove'):
            #I'm I the successor of key?
            inRange = Distance.inRangeR(msg.key, self._gPrede[0][0].gKey, \
                                     self.PID.gKey)
            assert(inRange == True), \
                'Put/Remove msg send to a node that is not a global successor'
            lSucce = PM.DHT[self.PID.NID].getLSucce(msg.source.NIDHash)
            if lSucce.NID == self.PID.NID: #This node is responsible
                return PM.DHT[self.PID.NID].recMsg(msg)
            msg.setNextHop(lSucce.NID)
            return msg
        elif (msg.msgType == 'Query') or (msg.msgType == 'PutReplica') or \
                (msg.msgType == 'ReceiveKeys') or \
                (msg.msgType == 'ReplicaRemove') or \
                (msg.msgType == 'NewCMember') or (msg.msgType == 'LeaveCMember')\
                or (msg.msgType == 'CMemberUpdate') or \
                (msg.msgType == 'ChangeGKey') or (msg.msgType == 'GetLoad') or \
                (msg.msgType == 'CanHandleLoad') or \
                (msg.msgType == 'GetLoadKey') or (msg.msgType == 'GetLoadKeys')\
                or (msg.msgType == 'MoveKeys') or (msg.msgType == 'Leave'):
            return PM.DHT[self.PID.NID].recMsg(msg)
        elif msg.msgType == 'UpdateFT':
            self._updateFT(msg.payload[0], msg.payload[1], msg.payload[2], \
                                                msg.payload[3])
        elif msg.msgType == 'NewSucce': #New successor
            if self._gSucce[0][0].gKey == msg.payload[0].gKey: #Same global key
                for i in msg.payload: #Make sure no duplicates
                    alreadyIn = False 
                    for j in self._gSucce[0]:
                        if i.NID == j.NID: #same node
                            alreadyIn = True
                            break   
                    if alreadyIn == False: 
                        self._gSucce[0].append(copy.deepcopy(i))
            else: self._gSucce[0] = copy.deepcopy(msg.payload) #Different key
        elif msg.msgType == 'NewPrede': #New predecessor
            if self._gPrede[0][0].gKey == msg.payload[0].gKey: #Same global key
                for i in msg.payload: #Check for duplicates
                    alreadyIn = False 
                    for j in self._gPrede[0]:
                        if i.NID == j.NID: #same node
                            alreadyIn = True
                            break   
                    if alreadyIn == False: 
                        self._gPrede[0].append(copy.deepcopy(i))
            else: self._gPrede[0] = copy.deepcopy(msg.payload)
        elif msg.msgType == 'UpdateSucce': #Update successor
            for node in msg.payload:
                for i in range(len(self._gSucce[0])):
                    if self._gSucce[0][i].NID == node.NID:
                        self._gSucce[0][i] = copy.deepcopy(node)
                        break
        elif msg.msgType == 'UpdatePrede': #Update predecessor
            for node in msg.payload:
                for i in range(len(self._gPrede[0])):
                    if self._gPrede[0][i].NID == node.NID:
                        self._gPrede[0][i] = copy.deepcopy(node)
                        break                
        elif msg.msgType == 'GetGSucce': #Get my global successor
            result = self._gSucce[0] if (msg.payload == True) else \
                                                [self._pickNextNode('Succe')]
            newMsg = OverlayMsg('GetGSucceReply', self.PID, msg.key, result)
            if msg.source.NID != self.PID.NID: newMsg.setHops(1)
            return newMsg
        elif msg.msgType == 'GetGPrede': #Get global predecessor
            result = self._gPrede[0] if (msg.payload == True) else \
                                                [self._pickNextNode('Prede')]
            newMsg = OverlayMsg('GetGPredeReply', self.PID, msg.key, result)
            if msg.source.NID != self.PID.NID: newMsg.setHops(1) 
            return newMsg
        elif msg.msgType == 'FindGSucce': #find global successor for given key
            succe = self._findGSucce(msg.key, msg.payload)
            return OverlayMsg('FindGSucceReply', self.PID, msg.key, succe[0], \
                              -1, succe[1])
        elif msg.msgType == 'CloseGPrede': 
            return self._closestGPreceNode(msg.key, msg.payload)       
        elif msg.msgType == 'RemSucce':
            for node in msg.payload:
                for i in range(len(self._gSucce[0])):
                    if node.NID == self._gSucce[0][i].NID:
                        del self._gSucce[0][i]
                        break
            if len(self._gSucce[0]) == 0: #No one. Set myself
                self._gSucce[0].append(copy.deepcopy(self.PID))
        elif msg.msgType == 'RemPrede':
            for node in msg.payload:
                for i in range(len(self._gPrede[0])):
                    if node.NID == self._gPrede[0][i].NID:
                        del self._gPrede[0][i]
                        break
            if len(self._gPrede[0]) == 0: #No one. Set myself
                self._gPrede[0].append(copy.deepcopy(self.PID))
        elif msg.msgType == 'JoinOverlay': self.join(None, msg.payload)
        else: assert(False), 'Overlay::recMsg Unknown msg type ' + msg.msgType


    def sendMsg(self, msg, dest = -1):
        '''
        Send message. Send directly if destination is given. Expected to be 
        called by DHT & resource layers
        @param msg: Message 
        @param dest: Destination node ID (not peer ID)
        '''
        assert(type(dest).__name__ == 'int'), 'Wrong destination type ' + \
            str(type(dest))
        if dest >= 0: #Destination given, send directly
            return PM.OVERLAY[dest].recMsg(msg, self.PID.NID)
        #ELse, treat according to message type
        if (msg.msgType == 'Put') or (msg.msgType == 'Remove'):
            return self._handleAdsMsg(msg)        
        elif msg.msgType == 'Query':
            return self._handleQueryMsg(msg)
        elif msg.msgType == 'CanHandleLoad': 
            return self._handleCanHandleLoadMsg(msg)
        else: assert(False), 'Unknown message type ' + msg.msgType


    def _handleCanHandleLoadMsg(self, msg):
        '''
        Send message to a global successor/predecessor & check whether it 
        can handle desired query load & index size. If so, move keys between 
        nodes. Implement focus on speed up rather than passing actual messages.
        Wave like moving load through multiple nodes is not implemented. To 
        implement it modify _handleCanHandleLoadMsg() in DHT.
        @param msg: Message
        @return: Reply message 
        '''        
        assert(msg.ttl == 1), 'TTL > 1 Not implemented'
        succe = self._getSucce()[0] if (msg.payload[2] == True) else \
                                                            self.getPrede()[0]
        nextNode = succe
        if nextNode.NID == self.PID.NID: #Only 1 node in network
            return OverlayMsg('CanHandleLoadReply', self.PID, -1, [False, -1])
        currentNode = self.PID
        hops = 0
        #i = 1
        while msg.ttl > 0: #TTL not expired
            msg.reduceTTL()
            msg = PM.OVERLAY[nextNode.NID].recMsg(msg, currentNode.NID)
            assert(msg.msgType == 'CanHandleLoad'), 'Wrong message type'
            if nextNode.NID != self.PID.NID: hops += 1
            #Update message should have [idx size to move, que load to move, 
            #list of keys to move, node ID]
            #Do we need to more load down further?
            break
            #if (msg.payload[i][0] == 0) and (msg.payload[i][1] == 0): break
            #currentNode = nextNode
            #nextNode = self._getSucce(nextNode)
            #i += 1
        #More load is remaining
        if (msg.payload[0] > 0) or (msg.payload[1] > 0):
            return OverlayMsg('CanHandleLoadReply', self.PID, -1, \
                                                    [False, succe.NID], 0, hops)
        #Move keys starting from last node. Simulate message returning back
        #for i in reversed(range(i - 1)):
        #    #Move keys from predecessor to successor
        #    newMsg = OverlayMsg('ChangeGKey', msg.payload[i + 1][3], -1, \
        #                        [msg.payload[i + 1][2], msg.payload[i + 2][3]])
        #    PM.OVERLAY[nextNode.NID].recMsg(newMsg, msg.payload[i + 2][3])
        return OverlayMsg('CanHandleLoadReply', self.PID, -1, [True, succe.NID]\
                                                                    , 0, hops)


    def _closestGPreceNode(self, key, needAll = False):
        '''
        Find globally closest preceding node for given key
        @param key: Key to route to
        @param needAll: Need list of all the nodes 
        @return: List of Peer IDs
        '''
        if self._gSucce[0][0].gKey == key: #Know exact key
            if needAll == True: return self._gSucce[0] #Successor(s)
            else: return [self._pickNextNode('Succe')] #pick 1
        #Is my global successor responsible for this key. Then I'm predecessor 
        if Distance.inRangeR(key, self.PID.gKey, self._gSucce[0][0].gKey):
            if needAll == True:
                cMembers = copy.deepcopy(PM.DHT[self.PID.NID].getCMembers())
                cMembers.append(copy.deepcopy(self.PID))
                return cMembers
            else: return [copy.deepcopy(self.PID)]
        while True: #Try finger table Pick a node that's in the network
            [prede, finger] = self._FT.getPrede(key, self.PID.gKey, needAll)
            #No where to go or found entry is close than successor (can't be true)
            #Successor is always correct. So send to successor
            if (prede == None) or (Distance.inRange(prede[0].gKey, \
                            self.PID.gKey, self._gSucce[0][0].gKey) == True): 
                if needAll == True: return self._gSucce[0] #Succe must be valid
                else: return [self._pickNextNode('Succe')] #pick 1
            if (prede[0].NID in PM.OVERLAY) and \
                        (PM.OVERLAY[prede[0].NID].PID.gKey == prede[0].gKey): 
                return prede #Valid node
            self._FT.remove(finger, prede[0].gKey, prede[0])#Invalid, remove it


    def fixFingers(self, joinNode = None):
        '''
        Update current finger table. Keep entries even if they point to same 
        node to simplify implementation. Don't set timer here as it's called
        both synchroniously & asynchroniously
        @param joinNode: Node to bootstrap 
        '''
        distToSucc = Distance.distance(self.PID.gKey, self._gSucce[0][0].gKey)
        for i in range(Config.KEY_LENGTH):
            offset = long(math.pow(2, i))
            if offset <= distToSucc: continue #Skip obvious fingers
            lookupKey = (self.PID.gKey + offset) % (Config.MAX_KEY + 1)
            succe = []
            hops = -1
            if joinNode is None: #I have a finger table use it
                [succe, hops] = self._findGSucce(lookupKey)
            else: #No finger table given
                newMsg = OverlayMsg('FindGSucce', self.PID, lookupKey, True)
                replyMsg = PM.OVERLAY[joinNode.NID].recMsg(newMsg, self.PID.NID)
                assert(replyMsg.msgType == 'FindGSucceReply'), \
                        'Unable to find successor of key. Wrong message'
                assert(replyMsg.payload), 'Finger update failed at ' + \
                        str(self.PID.NID)
                succe = replyMsg.payload
                hops = replyMsg.hops
            for j in succe: self._FT.put(i, j.gKey, j)
            self._fingerUpdateCost += hops


    def _findGSucce(self, key, needAll = False):
        '''
        find global successor of given key
        @param key: Key to route to
        @param needAll: Need list of all the nodes 
        @return: [PeerID of successor, hop count] 
        '''
        #This is node the successor
        if Distance.inRangeR(key, self._gPrede[0][0].gKey, self.PID.gKey):
            if needAll: 
                cMembers = copy.deepcopy(PM.DHT[self.PID.NID].getCMembers())
                cMembers.append(copy.deepcopy(self.PID))
                return [cMembers, 0] 
            else: return [[self.PID], 0]

        prede = self._findGPrede(key, needAll) #Find predecessor
        if prede[0][0].gKey == key: return prede #Know path to exact node 
        if prede[0][0].NID == self.PID.NID: #Back to me
            if needAll: return [self._gSucce[0], prede[1]] 
            else: return [[self._pickNextNode('Succe')], prede[1]]
        else:
            msg = OverlayMsg('GetGSucce', self.PID, key, needAll)
            replyMsg = PM.OVERLAY[prede[0][0].NID].recMsg(msg, self.PID.NID)
            assert(replyMsg.msgType == 'GetGSucceReply'), 'Wrong message type'
            return [replyMsg.payload, prede[1] + 1]


    def _findGPrede(self, key, needAll = False):
        '''
        Find global predecessor of key. Use iterative routing
        @param key: Key to route to
        @param needAll: Need list of all the nodes
        @return: [[PeerIDs of predecessors], hop count to reach that node] 
        '''
        numHops = 0
        prede = [self.PID]
        while True: #Find closestPreceNode
            if prede[0].gKey == key: return [prede, numHops] #Exact match
            succe = None
            if prede[0].NID == self.PID.NID: #This node is selected as prede 
                succe = self._gSucce[0]
            else: #Find its successor
                msg = OverlayMsg('GetGSucce', self.PID, key, needAll)
                replyMsg = PM.OVERLAY[prede[0].NID].recMsg(msg, self.PID.NID)
                assert(replyMsg.msgType == 'GetGSucceReply'), 'Wrong msg type'
                succe = replyMsg.payload
                #This step doesn't increase hops as this part of code should
                #be executed in selected predecessor in actual an implementation
            #if between them
            if succe[0].gKey == key: return [succe, numHops + 1]#Exact successor
            if Distance.inRangeR(key, prede[0].gKey, succe[0].gKey):
                return [prede, numHops]
            if self.PID.NID == prede[0].NID: #1st time
                prede = self._closestGPreceNode(key, needAll)
            else:
                msg = OverlayMsg('CloseGPrede', self.PID, key, needAll)
                prede = PM.OVERLAY[prede[0].NID].recMsg(msg, self.PID.NID)
            numHops += 1


    def _getSucce(self, currentNode = None, needAll = False):
        '''
        Get one of my or given node's global successors
        @param currentNode: Find global successor of this node
        @param needAll: Need all the successors   
        @return: [Successor's peer ID or list of IDs, hops]
        '''
        if currentNode is None:
            if needAll: return [self._gSucce[0], 0] 
            else: return [self._pickNextNode('Succe'), 0]
        else:
            msg = OverlayMsg('GetGSucce', self.PID, -1, needAll) 
            replyMsg = PM.OVERLAY[currentNode.NID].recMsg(msg, self.PID.NID)
            assert(replyMsg.msgType == 'GetGSucceReply'), 'Wrong msg type'
            return [replyMsg.payload, replyMsg.hops]            


    def getPrede(self, currentNode = None, needAll = False):
        '''
        Get one of my or given node's global predecessor
        @param currentNode: Find global successor of this node  
        @param needAll: Need all the predecessors   
        @return: [Predecessor's peer ID or list of IDs, hops]
        '''
        if currentNode is None: 
            if needAll: return [self._gPrede[0], 0]
            else: return [self._pickNextNode('Prede'), 0]
        else:
            msg = OverlayMsg('GetGPrede', self.PID, -1, needAll) 
            replyMsg = PM.OVERLAY[currentNode.NID].recMsg(msg, self.PID.NID)
            assert(replyMsg.msgType == 'GetGPredeReply'), 'Wrong msg type'
            return [replyMsg.payload, replyMsg.hops]


    def _handleAdsMsg(self, msg):
        '''
        Route resource ads to given destination & return no of overlay hops.
        Send all attributes in list
        @param msg: Message  
        @return: [No of hops]
        '''
        hops = []
        for i in range(len(msg.resource)): #For each attribute
            key = self._hashFun.ULPHash(msg.resource[i])  #Get hash
            result = self._findGSucce(key)
            assert(result), 'No successor for given key'
            succe = result[0][0]
            tmpHops = result[1] #Collect hops
            if msg.msgType == 'Put': 
                newMsg = OverlayMsg('Put', self.PID, key, \
                                [msg.resource[i][0], msg.resource, msg.source])
                replyMsg = PM.OVERLAY[succe.NID].recMsg(newMsg, self.PID.NID)
                if replyMsg.msgType == 'PutReply': tmpHops += replyMsg.hops
                elif replyMsg.msgType == 'Put': #Send to proper cluster member
                    tmpHops += 1
                    replyMsg = PM.OVERLAY[replyMsg.nextHop].recMsg(newMsg, \
                                                                   self.PID.NID)
                    if replyMsg.msgType == 'PutReply': tmpHops += replyMsg.hops
                    else: assert(False), 'Wrong message type' + replyMsg.msgType
                else: assert(False), 'Wrong message type' + replyMsg.msgType
            elif msg.msgType == 'Remove':
                #Route when multiple cluster members are there 
                newMsg = OverlayMsg('Remove', self.PID, key, \
                                [msg.resource[i][0], msg.resource, msg.source])
                replyMsg = PM.OVERLAY[succe.NID].recMsg(newMsg, self.PID.NID)
                if replyMsg.msgType == 'RemoveReply': tmpHops += replyMsg.hops
                elif replyMsg.msgType == 'Remove': #Try a different fragment
                    tmpHops += 1
                    replyMsg = PM.OVERLAY[replyMsg.nextHop].recMsg(newMsg, \
                                                                   self.PID.NID)
                    if replyMsg.msgType == 'RemoveReply': 
                        tmpHops += replyMsg.hops
                    else: assert(False), 'Wrong message type' + replyMsg.msgType
                else: assert(False), 'Wrong message type' + replyMsg.msgType
            else: assert(False), 'Unknown message type ' + msg.msgType
            hops.append(tmpHops)
        return hops


    def _handleQueryMsg(self, msg):
        '''
        Route query to given destination & return no of overlay hops. Use single
        attribute dominated queries (SADQ)  
        @param msg: Query message
        @return: Modified query message
        '''
        #Pick the most selective attribute
        minRange = Config.MAX_KEY + 1
        minI = -1
        for i in range(len(msg.query)): #For each attribute
            #Fin min & max hash values
            minKey = self._hashFun.ULPHash([msg.query[i][0], msg.query[i][1]])
            maxKey = self._hashFun.ULPHash([msg.query[i][0], msg.query[i][2]])
            #No need to worry about address range wrapping
            tmpRange = maxKey - minKey
            assert(tmpRange >= 0), 'minKey > maxKey'
            if tmpRange <= minRange:
                minRange = tmpRange
                minI = i
        atts = [msg.query[minI]] #most selective attribute to query
        msg.attToQue = atts[0][0] #Most selective attribute
        
        for i in range(len(atts)): #For each attribute selected to query
            minKey = self._hashFun.ULPHash([atts[i][0], atts[i][1]]) #MIN hash
            maxKey = self._hashFun.ULPHash([atts[i][0], atts[i][2]]) #MAX hash
            msg.minKey = minKey
            msg.maxKey = maxKey
            result = self._findGSucce(minKey) #find 1 successor
            assert(result), 'No successor for given key'
            succe = result[0][0]
            msg = PM.OVERLAY[succe.NID].recMsg(msg, self.PID.NID)
            assert(msg.msgType == 'Query'), 'Wrong message type ' + msg.msgType
            msg.setHops(result[1]) #Collect hops
            if msg.success == True: return msg
            #If not enough resources first check other fragments (if available).
            #Else check successors. Skip for categorical data           
            #Destination node. This is a hack to simplify simulation
            maxNodeGKey = self._findGSucce(maxKey)[0][0].gKey
            last = succe
            startKey = succe.gKey
            disMinToStart = Distance.distance(minKey, startKey)
            disMinToMax = Distance.distance(minKey, maxKey)
            while True:
                succe = msg.getFragmentToTry() #Try local fragment                    
                if succe is None: #Try next global successor, no fragments
                    if disMinToMax <= disMinToStart: break
                    
                    newMsg = OverlayMsg('GetGSucce', self.PID, -1) #Find succe
                    replyMsg = PM.OVERLAY[last.NID].recMsg(newMsg, self.PID.NID)
                    assert(replyMsg.msgType == 'GetGSucceReply'), \
                            'Wrong message type'
                    succe = replyMsg.payload[0]
                    #Keep moving if succe is in range or same node revisited
                    if succe.gKey == last.gKey: break #Only 1 node
                    if disMinToMax > disMinToStart:
                        if startKey == succe.gKey: break
                    if Distance.inRangeR(succe.gKey, minKey, maxNodeGKey) \
                                                                    == False:
                        break
                #Query next node
                msg = PM.OVERLAY[succe.NID].recMsg(msg, self.PID.NID)
                assert(msg.msgType == 'Query'), \
                    'Wrong message type' + msg.msgType
                msg.incrementHops() #Increment hops
                if msg.success == True: return msg
                last = succe
            return msg


    def _initFT(self, joinNode, infoAsPrede = True, infoAsSucce = True):
        '''
        Initialize finger table using given node
        @param joinNode: Node to use for bootstraping
        @param infoAsPrede: Inform to successor as a predecessor
        @param infoAsSucce: Inform to predecessor as a successor  
        '''
        if joinNode: #Initialize my finger table using join node
            newMsg = OverlayMsg('FindGSucce', self.PID, self.PID.gKey, True)
            replyMsg = PM.OVERLAY[joinNode.NID].recMsg(newMsg, self.PID.NID)
            assert(replyMsg.msgType == 'FindGSucceReply'), \
                'No successor. Wrong message type'
            self._gSucce[0] = copy.deepcopy(replyMsg.payload) #May return a list
            self._fingerUpdateCost += replyMsg.hops

            newMsg = OverlayMsg('GetGPrede', self.PID, self.PID.gKey, True)
            replyMsg = PM.OVERLAY[self._gSucce[0][0].NID].recMsg(newMsg, \
                                                                  self.PID.NID)
            assert(replyMsg.msgType == 'GetGPredeReply'), \
                'No predecessor. Wrong message'
            self._gPrede[0] = copy.deepcopy(replyMsg.payload) #May return a list
            self._fingerUpdateCost += replyMsg.hops
       
        #Inform presence to predecessors & successors. This is redundant to the
        #node that added new node (as it know new node is its prede/succe. But
        #its cluster members don't know
        newMsg = OverlayMsg('NewPrede', self.PID, -1, [self.PID])
        for i in range(len(self._gSucce[0])):
            PM.OVERLAY[self._gSucce[0][i].NID].recMsg(newMsg, self.PID.NID)
            self._fingerUpdateCost += 1
        newMsg = OverlayMsg('NewSucce', self.PID, -1, [self.PID])
        for i in range(len(self._gPrede[0])):
            PM.OVERLAY[self._gPrede[0][i].NID].recMsg(newMsg, self.PID.NID)
            self._fingerUpdateCost += 1
        if joinNode: self.fixFingers(joinNode)#Has join node-use it to fix fingers


    def _notify(self, whatToSend):
        '''
        Notify my arrival/departure to other nodes that may keep a finger to me
        Also inform if another node that was in the same position needs to be 
        removed from receivers FT
        @param whatToSend: List of notifications to send [[key, [arrival nodes],\
         [departure nodes]]] 
        @return: Cost to send notify messages 
        '''        
        hops = 0
        for entry in whatToSend:
            hops += self._sendNotification(entry[0], entry[1], entry[2])
        return hops


    def _sendNotification(self, refKey, arrivingNodes, departingNodes):
        '''
        Send notification messages
        @param refKey: Key to use as reference when calculating other addresses 
        @param arrivingNodes: Nodes arriving/joining
        @param departingNodes: Nodes leaving/departing
        @return: No of hops
        '''
        for finger in range(Config.KEY_LENGTH):
            newKey = (refKey - long(math.pow(2, finger))) % (Config.MAX_KEY + 1)
            nodes = self._findGPrede(newKey, True) #may be multiple nodes
            PM.FT_NOTIFY_COST.append(nodes[1])
            for node in nodes[0]:
                if node.NID == self.PID.NID:
                    self._updateFT(finger, refKey, arrivingNodes, \
                                                                departingNodes)
                else:
                    if node.NID in PM.OVERLAY:
                        newMsg = OverlayMsg('UpdateFT', self.PID, -1, [finger, \
                                        refKey, arrivingNodes, departingNodes])
                        PM.OVERLAY[node.NID].recMsg(newMsg, self.PID.NID)
                        PM.FT_NOTIFY_COST.append(1)
        totalHops = sum(PM.FT_NOTIFY_COST)
        PM.FT_NOTIFY_COST = []
        return totalHops


    def _pickNextNode(self, whichList):
        '''
        Pick the next node from successor or predecessor list based on the given
        load balancing policy
        @param whichList: From whichList - Successors or predecessors
        @return: Peer ID  
        '''
        if whichList == 'Succe':
            numEntries = len(self._gSucce[0])
            if Config.NEXT_HOP_SELECTION == 'Random':
                return self._gSucce[0][random.randint(0, numEntries - 1)]
            elif Config.NEXT_HOP_SELECTION == 'RoundRobin':
                idx = self._gSucce[1] % numEntries #effective if entry removed
                self._gSucce[1] = (self._gSucce[1] + 1) % numEntries #Next chance
                return self._gSucce[0][idx]                
            else: assert(False), 'Wrong load balancing policy ' + \
                Config.NEXT_HOP_SELECTION
        elif whichList == 'Prede':
            numEntries = len(self._gPrede[0])
            if Config.NEXT_HOP_SELECTION == 'Random':    
                return self._gPrede[0][random.randint(0, numEntries - 1)]
            elif Config.NEXT_HOP_SELECTION == 'RoundRobin':
                idx = self._gPrede[1] % numEntries #effective if entry removed
                self._gPrede[1] = (self._gPrede[1] + 1) % numEntries #Next chance
                return self._gPrede[0][idx]
            else: assert(False), 'Wrong load balancing policy ' + \
                Config.NEXT_HOP_SELECTION
        else: assert(False), 'Wrong list ' + whichList        


    def _updateFT(self, finger, advKey, arrivingNodes, departingNodes):
        '''
        Update finger table using given information. PID may have changed 
        depending on when updateMsg was generated so use advKey
        @param finger: finger number
        @param advKey: Key use to indicate arrival or departure 
        @param arrivingNodes: Nodes arriving/joining
        @param departingNodes: Nodes leaving/departing
        '''
        currentNodes = self._FT.getFinger(finger) #Is there a current finger?
        if currentNodes is None: currentNodes = self._gSucce[0] #No finger entry

        #Is new node better than what I know already know? Equal to current node
        #is fine as we can add multiple nodes
        if Distance.inRangeLR(advKey, self.PID.gKey, currentNodes[0].gKey):
            if len(arrivingNodes) > 0:#Arrival. Better/same (cMember) as current
                if advKey != self._gSucce[0][0].gKey: #Don't add succes
                    distToNode = Distance.distance(self.PID.gKey, advKey)
                    if advKey == self.PID.gKey: 
                        distToNode = Config.MAX_KEY + 1
                    distToCurrent = Distance.distance(self.PID.gKey, \
                                                    self._gSucce[0][0].gKey)
                    if distToCurrent < distToNode:
                        return #Valid node but successor is more closer
                    for node in arrivingNodes: 
                        self._FT.put(finger, advKey, node) #Add it
            #departure nodes. Is given node in finger table
            inFT = False
            for node in currentNodes:
                for nodeRem in departingNodes:
                    if (node.NID == nodeRem.NID) and (node.gKey == advKey):#Has it 
                        self._FT.remove(finger, advKey, nodeRem)
                        inFT = True
                        break
            #Is departing node in FT? If not, it may not be in predecessors
            #If arriving node is useful still keep forwarding to predecessors
            if ((inFT == False) and (len(departingNodes) > 0)) or \
                                                    (len(arrivingNodes) > 0): 
                return
        else: return #Not useful
        #Useful to me may be useful to my predecessor(s)
        for node in arrivingNodes:
            if node.NID == self.PID.NID: return #don't forward my own
        if len(arrivingNodes) == 0: #If only a departure message
            for node in departingNodes:
                if node.NID == self.PID.NID: return #don't forward my own            
        newMsg = OverlayMsg('UpdateFT', self.PID, -1, [finger, advKey, \
                                                arrivingNodes, departingNodes])            
        for i in range(len(self._gPrede[0])):
            PM.OVERLAY[self._gPrede[0][i].NID].recMsg(newMsg, self.PID.NID)#update
            PM.FT_NOTIFY_COST.append(1)


    def checkLoad(self):
        '''
        Time to check load over last time period
        '''
        self._numMsgRec += self._numMsgRecInt #Increment total count
        if self._firstRound == False:
            a = Config.WEIGHTING_FACTOR #Alpha
            if self._msgInEWMA == 0: self._msgInEWMA = self._numMsgRecInt #1st time 
            else: self._msgInEWMA = a * self._numMsgRecInt  + (1 - a) * \
                                                                self._msgInEWMA
        self._numMsgRecInt = 0 #Reset
        self._firstRound = False


    def getStat(self):
        '''
        Dump node statistics
        @return: Stat
        '''
        #Consider only the messages arrived within last stat collection window
        threshold = PM.EVENTS.now - Config.LOAD_CHECK_INTERVAL
        for i in range(len(self._msgInTime)):
            if self._msgInTime[i] >= threshold:
                self._msgInTime = self._msgInTime[i:] #remove old ones
                break
            if i == (len(self._msgInTime) - 1): #No new ones 
                self._msgInTime = []

        result = [self.PID.NID, self._numMsgRec, self._msgInEWMA, \
                  len(self._msgInTime), self._fingerUpdateCost, \
                  len(self._gSucce[0]), len(self._gPrede[0])] + \
                                                        self._FT.getStat()
        return result