'''
Created on Jan 9, 2012
Modified on July 17, 2012
@author: Dilum Bandara
@version: 0.1
@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 AdvMsg import AdvMsg
from OverlayMsg import OverlayMsg
from ResourceIndex import ResourceIndex
from PeerID import PeerID
import Distance as Distance
import Config
import copy
import PeerManager as PM
import random


class DHT(object):
    '''
    Distributed hash table (DHT) class. Maintain resource index, load stat & 
    responsible for load balancing.
    '''
    def __init__(self, PID, cMembers):
        '''
        @param PID: DHT's peer ID
        @param cMembers: List of nodes in cluster 
        '''
        self.PID = PID #This should be in sink with overlay & resource PID
        #Cluster members - index by local key. Replicas as a list
        self._cMembers = cMembers
        self._numCMembers = 0  #Number of cluster members
        for i in self._cMembers: self._numCMembers += len(self._cMembers[i])
        self._idx = ResourceIndex() #Index
        self._idxSizeEWMA = 0 #Exponentially weight moving average
        self._queryInEWMA = 0 #Queries directed towards keys in index
        self._queryFwdPredeEWMA = 0 #Queries received from predecessor
        self._queryFwdSucceEWMA = 0 #Queries forward to successor
        self._queryFwdCMemberEWMA = 0 #Queries forward to cluster member        
        self._queryOutEWMA = 0 #Queries being forwarded & answered
        self._numFwdCMember = 0 #No of queries forwarded to cluster members
        self._queLoadReceived = 0 #Load received due to transfered keys
        self._numUpdatesRec = 0 #No of resource updates
        self._numQueFwd = 0
        self._numQueAns = 0
        self._queryInTime = [] #time that queries were received. Sliding window
        self._adsInTime = [] #time that Ads were received. Sliding window
        self._isLeaving = False
        self._firstRound = True #No action during 1st load check round 
        if self._numCMembers > 0:
            self._sendToCMembers(OverlayMsg('NewCMember', self.PID))
        #Set load check timer
        intTime = random.randint(1, Config.LOAD_CHECK_INTERVAL - 1)
        PM.EVENTS.addEvent(PM.EVENTS.now + intTime, 'LOADCHECK', PID.NID)


    def __del__(self):
        '''
        Destructor
        '''
        self._idx.reset(True)
        self._cMembers = {}
        self._queryInTime = []
        self._adsInTime = []


    def checkLoad(self):
        '''
        Time to check load over last time period
        '''
        if self._firstRound == False: #Has enough stat to take a decision
            #Calculate exponentially weighted moving average of loads
            a = Config.WEIGHTING_FACTOR #Alpha
            load = self._idx.getTotalLoad('Idx', [])
            if self._idxSizeEWMA == 0: self._idxSizeEWMA = load #1st time 
            else: self._idxSizeEWMA = a * load  + (1 - a) * self._idxSizeEWMA
            load = self._idx.getTotalLoad('In', [])
            if self._queryInEWMA == 0: self._queryInEWMA = load
            else: self._queryInEWMA = a * load + (1 - a) * self._queryInEWMA
        
            load = self._idx.getTotalLoad('FwdPrede', [])
            if self._queryFwdPredeEWMA == 0: self._queryFwdPredeEWMA = load
            else: self._queryFwdPredeEWMA = a * load + \
                                            (1 - a) * self._queryFwdPredeEWMA 
            load = self._idx.getTotalLoad('FwdSucce', [])
            if self._queryFwdSucceEWMA == 0: self._queryFwdSucceEWMA = load
            else: self._queryFwdSucceEWMA = a * load + \
                                            (1 - a) * self._queryFwdSucceEWMA
            load = self._idx.getTotalLoad('Out', [])
            if self._queryOutEWMA == 0: self._queryOutEWMA = load
            else: self._queryOutEWMA = a * load + (1 - a) * self._queryOutEWMA
        
            if self._queryFwdCMemberEWMA == 0: 
                self._queryFwdCMemberEWMA = self._numFwdCMember
            else: self._queryFwdCMemberEWMA = a * self._numFwdCMember + \
                                            (1 - a) * self._queryFwdCMemberEWMA
        
            #If not answering enough queries. Try to leave overlay. If there's a 
            #transferred query load consider that before leaving.
            #If query load is high or index size is large try to move load or 
            #add another node to handle load 
            #if Load due to forwarding is high add another node to handle load
            if (((self._queryOutEWMA + self._queLoadReceived) < \
                    Config.THRES_MIN_QUE_LOAD) or (self._idxSizeEWMA == 0))\
                    and Config.SIMULATION_TYPE != 'Chord+Split':
                self._leaveOverlay()
            elif (self._queryInEWMA + self._queryFwdPredeEWMA > \
                                Config.THRES_MAX_QUE_LOAD)\
                                or (self._idxSizeEWMA > Config.THRES_IDX_SIZE):
                self._movePartOfIdx()
        
        if self._isLeaving == True: return #Node is leaving. Keep stat intact
        #Node not leaving so prepare for next round
        self._idx.reset() #Reset load counters
        self._numFwdCMember = 0
        self._queLoadReceived = 0
        self._firstRound = False
        PM.EVENTS.addEvent(PM.EVENTS.now + Config.LOAD_CHECK_INTERVAL, \
                                    'LOADCHECK', self.PID.NID)#Set timer again             


    def getCMembers(self, fragmentsOnly = False, skipMyFragment = False, \
                    sort = False):
        '''
        Get the list of cluster members (all or only the fragments) except this
        node
        @param fragmentsOnly: Fragments only 
        @param skipMyFragment: Skip this node's fragment
        @param sort: Sort cMembers based on local key 
        @return: List of Peer IDs of cluster members (other than this node)
        '''
        result = []
        lKeys = self._cMembers.keys()
        if sort == True: lKeys = sorted(lKeys) #Sort according to local key
        for i in lKeys: #For each local key
            if skipMyFragment == True:
                if i == self.PID.lKey: continue
            if fragmentsOnly == False: #All nodes
                for j in range(len(self._cMembers[i])):
                    result.append(self._cMembers[i][j])
            else: #Only the fragments - pick 1 node from each fragment
                idx = random.randint(0, len(self._cMembers[i]) - 1)
                result.append(self._cMembers[i][idx])
        return result


    def getLSucce(self, key):
        '''
        Get one of the local successors of given key (within this cluster) 
        @param key: Key
        @return: Peer ID of successor
        '''
        if Distance.inRangeLR(key, self.PID.lStartKey, self.PID.lKey):
            return self.PID #Within my range
        for i in self._cMembers: #Find closest key to my local key
            if i == self.PID.lKey: continue #Skip same local key as mine
            if Distance.inRangeLR(key, self._cMembers[i][0].lStartKey, i):
                #Pick a node randomly
                return self._cMembers[i][random.randint(0, \
                                                    len(self._cMembers[i]) - 1)]
        return None


    def recMsg(self, msg):
        '''
        Receive message from overlay. Handle accordingly
        @param msg: Message
        @return: Corresponding reply 
        '''
        if (msg.msgType == 'Put') or (msg.msgType == 'PutReplica'):
            return self._addToIndex(msg)
        elif msg.msgType == 'ReceiveKeys':
            return self._handleReceiveKeys(msg)
        elif (msg.msgType == 'Remove') or (msg.msgType == 'ReplicaRemove'):
            return self._removeFromIndex(msg)
        elif msg.msgType == 'Query': return self._queryIndex(msg)
        elif msg.msgType == 'NewCMember': self._updateCMember(msg.source, True)        
        elif msg.msgType == 'LeaveCMember':
            self._updateCMember(msg.source, False)
        elif msg.msgType == 'CMemberUpdate':
            self._updateCMembers(msg.payload[0]) #Update cluster members
            self._transferKeys([], msg.payload[1], True) #Move relevant keys
        elif msg.msgType == 'ChangeGKey': #Change my global key
            self._handleChangeGKeyMsg(msg)
        elif msg.msgType == 'GetLoad':
            load = []
            for i in range(len(msg.payload[1])): #2nd entry is load types
                if (msg.payload[2] == False) or (msg.payload[1][i] == 'Idx'):
                    load.append(self._idx.getTotalLoad(msg.payload[1][i], \
                                                   msg.payload[0]))
                else: #Use values from EWMA counters, except for index
                    if msg.payload[1][i] == 'Que':
                        load.append(self._queryInEWMA + self._queryFwdPredeEWMA)
                    else: assert(False), 'Unknown laod type' + msg.payload[1][i]
            return OverlayMsg('GetLoadReply', self.PID, -1, load)
        elif msg.msgType == 'GetLoadKeys':
            [key, condition] = msg.payload
            #Find individual lists of keys
            tmpKeys = self._idx.getConditioned('Idx', key, condition, \
                                                        self.PID.gKey) #Index
            tmpKeys += self._idx.getConditioned('In', key, condition, \
                                                        self.PID.gKey) #In
            tmpKeys += self._idx.getConditioned('Out', key, condition, \
                                                        self.PID.gKey) #InOut
            keys = list(set(tmpKeys)) #Remove duplicates
            if len(keys) > 0:
                return OverlayMsg('GetLoadKeysReply', self.PID, -1, \
                                            self._idx.getLoadKeys(keys))
            else: return OverlayMsg('GetLoadKeysReply', self.PID, -1, {})
        elif msg.msgType == 'GetLoadKey':
            [key, loadTypes, condition] = msg.payload
            tmpKeys = []
            for i in loadTypes: #Find list of keys
                tmpKeys += self._idx.getConditioned(i, key, condition, \
                                                        self.PID.gKey) #InOut
            keys = list(set(tmpKeys)) #Remove duplicates
            load = []
            for i in loadTypes:
                load.append(self._idx.getTotalLoad(i, keys))
            return OverlayMsg('GetLoadKeyReply', self.PID, -1, load)
        elif msg.msgType == 'CanHandleLoad':
            return self._handleCanHandleLoadMsg(msg)
        elif msg.msgType == 'MoveKeys': self._handleMoveKeysMsg(msg)
        elif msg.msgType == 'Leave':
            if msg.payload:
                PM.OVERLAY[self.PID.NID].leaveOverlay(False, True, True)
            else: PM.OVERLAY[self.PID.NID].leaveOverlay(False, True, False, True)
            self._isLeaving = True #Mark as leaving
        else: assert(False), 'Wrong message type ' + msg.msgType


    def _addCMemberFragment(self):
        '''
        Fragment index & assign to a new node. If there is a replica convert 
        it to a fragment. Otherwise add new cluster member & move keys
        '''
        if Config.SIMULATION_TYPE != 'Chord+RDSim': return #Not supported
        convertedNode = None
        newNID = -1
        newNodeLKeys = {} #New local keys
        moveKeys = True
        if Config.FRAGMENT_METHOD == 'Half':
            #If node has a replica convert that to avoid key movement
            if self.PID.lKey in self._cMembers:
                convertedNode = self._cMembers[self.PID.lKey][0]
                del self._cMembers[self.PID.lKey][0]
                if len(self._cMembers[self.PID.lKey]) == 0:
                    del self._cMembers[self.PID.lKey]
                moveKeys = False #No need to move keys
            else: #Pick any replica as they don't have any of my keys
                for i in self._cMembers:
                    if len(self._cMembers[i]) > 1: #Has replicas
                        convertedNode = self._cMembers[i][1]
                        del self._cMembers[i][1]
                        break
            if convertedNode is not None: #Find new node ranges/keys
                newNodeLKeys = self._fragmentHalf(convertedNode.NID)
            else: #No converted node. Add new node 
                newNID = self._findNewNode()
                newNodeLKeys = self._fragmentHalf(newNID)#New ranges
            [self.PID.lStartKey, self.PID.lKey] = newNodeLKeys[self.PID.NID]
        elif Config.FRAGMENT_METHOD == 'Uniform': #Local range for new fragments
            [newNodeStart, newNodeEnd, newNodeLKeys] = self._fragmentUniform()
            #If replicas, find node with max overlap to reduce no of keys to move
            largestCoverage = -1
            idx = -1
            for lKey in self._cMembers:
                startJ = 0
                if self.PID.lKey != lKey: startJ = 1 #Skip 1st entry
                for j in range(startJ, len(self._cMembers[lKey])):
                    coverage = Distance.coverage(newNodeStart, newNodeEnd\
                                        , self._cMembers[lKey][j].lStartKey, \
                                        self._cMembers[lKey][j].lKey)
                    if coverage[0] > largestCoverage:
                        largestCoverage = coverage[0]
                        convertedNode = self._cMembers[lKey][j]
                        idx = j
            for i in newNodeLKeys: #Find my new local keys
                if i == self.PID.NID: 
                    [self.PID.lStartKey, self.PID.lKey] = newNodeLKeys[i]
                    break
            if convertedNode: #Remove it being a further candidate
                del self._cMembers[convertedNode.lKey][idx]
                if len(self._cMembers[convertedNode.lKey]) == 0:
                    del self._cMembers[convertedNode.lKey]
                newNodeLKeys[convertedNode.NID] = [newNodeStart, newNodeEnd]
            else: #Find a new node
                newNID = self._findNewNode()
                newNodeLKeys[newNID] = [newNodeStart, newNodeEnd]
        else: assert(False), 'Unknown fragmentation method ' + \
                                                Config.FRAGMENT_METHOD
        #If new node is needed add a node to overlay. Added node will inform all
        # other nodes as a cluster member (atomic task). Then transfer keys &
        #Finally join that node to overlay
        if newNID > -1:
            cMembersToSnd = copy.deepcopy(self._cMembers)
            if self.PID.lKey in cMembersToSnd: #Add this node
                cMembersToSnd[self.PID.lKey].append(copy.deepcopy(self.PID))
            else: cMembersToSnd[self.PID.lKey] = [copy.deepcopy(self.PID)] 
            PM.OVERLAY[self.PID.NID].addNewNode(newNID, True, self.PID.gKey,\
                    newNodeLKeys[newNID][0], newNodeLKeys[newNID][1], \
                    self.PID.gKey, cMembersToSnd, None)
            PM.STAT_CHECK_LOAD.append(1)#Cost
        #Inform all nodes about changes in ranges. If adding a new node it need
        #to be in the network to receive any keys that may be moved
        #Following conversion can/should be done at receiving cMember but this 
        #makes simulation fast
        updatedCMembers = self._constructCMembers(newNodeLKeys)
        self._updateCMembers(updatedCMembers) #Update my own list of cMembers
        newMsg = OverlayMsg('CMemberUpdate', self.PID, -1, [updatedCMembers, \
                                                            newNodeLKeys])
        numMsg = self._sendToCMembers(newMsg) #add to cMember key update cost
        PM.STAT_CHECK_LOAD.append(numMsg)       
        #Move keys, if required
        if ((Config.FRAGMENT_METHOD == 'Half') and moveKeys == True) or \
            Config.FRAGMENT_METHOD == 'Uniform': 
                numMsg = self._transferKeys([], newNodeLKeys, True)
                PM.STAT_CHECK_LOAD.append(numMsg)
#        self._updateCMembers(updatedCMembers) #Update my own list of cMembers

        if newNID > -1: #Added a new node. So ask it to join overlay
            newMsg = OverlayMsg('JoinOverlay', self.PID, -1, \
                                [[self.PID.gKey, [PM.OVERLAY[newNID].PID], []]])
            PM.OVERLAY[self.PID.NID].sendMsg(newMsg, newNID)
        PM.STAT.trackStat('AddFrag', [self.PID.NID, convertedNode, newNID, \
                                                            self.PID.gKey])


    def _addCMemberReplicate(self):
        '''
        Add new node to cluster. Replicate index. Then ask node to join overlay
        '''
        if Config.SIMULATION_TYPE != 'Chord+RDSim': return #Not supported
        newNID = self._findNewNode()
        cMembersToSend = copy.deepcopy(self._cMembers)
        if self.PID.lKey in cMembersToSend: #Add this node
            cMembersToSend[self.PID.lKey].append(copy.deepcopy(self.PID))
        else:cMembersToSend[self.PID.lKey] = [copy.deepcopy(self.PID)]
        #Create a new node
        PM.OVERLAY[self.PID.NID].addNewNode(newNID, True, self.PID.gKey, \
            self.PID.lKey, self.PID.lStartKey, self.PID.gKey, cMembersToSend, \
            None)
        #Transfer keys
        numMsg = self._transferKeys([], newNID, False, False)
        PM.STAT_CHECK_LOAD.append(numMsg + 1)#Cost add new node & send replica
        #Ask it to join overlay
        newMsg = OverlayMsg('JoinOverlay', self.PID, -1, \
                            [[self.PID.gKey, [PM.OVERLAY[newNID].PID], []]])
        PM.OVERLAY[self.PID.NID].sendMsg(newMsg, newNID)
        PM.STAT.trackStat('AddRep', [self.PID.NID, newNID, self.PID.gKey])


    def _addNodeBetween(self, excessIdxSize, excessQueLoad, succeKeys, \
                        succeLoad, predeKeys, predeLoad):
        '''
        Balance node's load by recruiting a new node(s) to handle transfered keys.
        Place node between me & my predecessor. If there are multiple nodes 
        in a cluster aggregate & move from all fragments. If 1 node can't handle 
        try adding series of nodes. If a node can't be added between me & my 
        successor/predecessor (no key space) then fragment or replicate
        @param excessIdxSize: Index size to reduce
        @param excessQueLoad: Query load to reduce
        @param succeKeys: List of keys to be transfered to successors to cut
         down desired load
        @param succeLoad: Load for keys to be transfered to successors [Idx, que]
        @param predeKeys: List of keys to be transfered to predecessor
        @param predeLoad: Load for keys to be transfered to predecessor     
        '''
        if (Config.SIMULATION_TYPE == 'Chord') or (Config.SIMULATION_TYPE ==
                                        'Chord+Split'): 
            return #Not supported
        
        addSucce = True if (len(succeKeys) > 1) else False #Can add successor?
        addPrede = True if (len(predeKeys) > 1) else False #Can add predecessor?

        gPredeKey = PM.OVERLAY[self.PID.NID].getPrede()[0].gKey
        minKey = -1
        if addSucce == True: #Still possible check availability of key range
            minKey = Distance.mini(succeKeys, self.PID.gKey)
            newGKey = (minKey - 1) % (Config.MAX_KEY + 1)
            if newGKey == gPredeKey: addSucce = False
            else:
                assert(Distance.inRange(newGKey, gPredeKey, self.PID.gKey)), \
                'newGKey not between this node & predecessor'
        if addSucce == True:
            #Will load be insignificant after adding new node(s) & transfered 
            #Load exceed capacity of new node. if so no point in adding new node
            loadFwdSucce = self._idx.getTotalLoad('FwdSucce', [])            
            queLoadKeys = self._idx.getConditioned('In', minKey, '>=', \
                                                                self.PID.NID)
            queLoadReduced = self._idx.getTotalLoad('In', queLoadKeys)
            queLoadTrans = loadFwdSucce + succeLoad[1]
            queLoadRemain = self._idx.getTotalLoad('In', []) + \
                        self._idx.getTotalLoad('FwdPrede', []) - queLoadReduced
            idxLoadTrans = len(self._idx.get(succeKeys, True))
            idxLoadRemain = self._idx.getTotalLoad('Idx', []) - \
                                        self._idx.getTotalLoad('Idx', succeKeys)
            if (queLoadRemain < Config.THRES_MIN_QUE_LOAD) and \
                ((Config.THRES_MAX_QUE_LOAD - queLoadTrans) > queLoadRemain) \
                and ((Config.THRES_IDX_SIZE - idxLoadTrans) > idxLoadRemain):
                addSucce = False
        if addSucce == True:
            result = self._addNodeBetweenSucce(succeKeys, gPredeKey, minKey)
            if result[0] == True:
                return #Some keys transfered no need to handle any remaining keys
            addSucce = False #Failed

        #Successor can't be added, try adding predecessor
        if addPrede == True: #Try adding predecessor(s). Key space available?
            maxKey = Distance.maxi(predeKeys, self.PID.gKey)
            if maxKey == self.PID.gKey: addPrede = False
            else:
                assert(Distance.inRange(maxKey, gPredeKey, self.PID.gKey)), \
                'maxKey not between this node & predecessor'
            if addPrede == True:
                #Will load on this node be insignificant after adding new node?
                loadFwdPrede = self._idx.getTotalLoad('FwdPrede', [])
                queLoadKeys = self._idx.getConditioned('Out', maxKey, '<=', \
                                                                self.PID.NID)
                queLoadReduced = self._idx.getTotalLoad('Out', queLoadKeys)
                queLoadTrans = loadFwdPrede + predeLoad[1]
                queLoadRemain = self._idx.getTotalLoad('In', []) + \
                        self._idx.getTotalLoad('FwdPrede', []) - queLoadReduced
                idxLoadTrans = len(self._idx.get(predeKeys, True))
                idxLoadRemain = self._idx.getTotalLoad('Idx', []) - \
                                        self._idx.getTotalLoad('Idx', predeKeys)

                if (queLoadRemain < Config.THRES_MIN_QUE_LOAD) and \
                    ((Config.THRES_MAX_QUE_LOAD - queLoadTrans) > queLoadRemain)\
                    and ((Config.THRES_IDX_SIZE - idxLoadTrans) > idxLoadRemain):
                    addPrede = False

            if addPrede == True:
                result = self._addNodeBetweenPrede(predeKeys, maxKey)
                if result[0] == True: 
                    return #Some keys transfered no need to handle any remaining
                addPrede = False #Failed
                
        #If that also fails try to either replicate or fragment. Give preference
        #to fragmentation as a large index can't be replicated but fragments 
        #can still reduce query load 
        if (addSucce == False) and (addPrede == False):
            if excessIdxSize > 0: self._addCMemberFragment()#Fragment large Idx 
            elif excessQueLoad > 0: self._addCMemberReplicate() #replicate


    def _addNodeBetweenSucce(self, keys, gPredeKey, minKey):
        '''
        Check whether a node(s) between this node & its successor can be added
        If so, add a node(s) & transfer keys
        @param keys: List of keys to be transfered to successors
        @param gPredeKey: Global key of predecessor
        @param minKey: Minimum key  
        @return: [Success or failure, keys moved]     
        '''
        keyRanges = self._splitSeriesOfKeys(minKey)
        if len(keyRanges) == 0: return [False, []] #can't split

        newGKey = -1
        for i in reversed(range(len(keyRanges))):#Start checking with closet range
            tmpGKey = (keyRanges[i][0] - 1) % (Config.MAX_KEY + 1)
            if tmpGKey != gPredeKey:
                newGKey = tmpGKey
                break
        #Can key be moved without violating global key of this node?
        if newGKey == -1: return [False, []]
        assert(Distance.inRange(newGKey, gPredeKey, self.PID.gKey)), \
                'newGKey not between this node & predecessor'
        if newGKey == self.PID.gKey:
            print keyRanges, self._idx._idx
            assert(False), 'New & old key is same' 

        keyRanges[0][1] = self.PID.gKey#make sure 1st new node comes to my place
        preKey = self.PID.gKey
        self.PID.gKey = newGKey
        self._updateCMemberGKey(newGKey)
        #Me & my cluster members will become the predecessor(s)
        tmpCMembers = copy.deepcopy(self.getCMembers())
        tmpCMembers.append(copy.deepcopy(self.PID)) #Add this node
        disNewGKeyToOld = Distance.distance(newGKey, preKey)        
        allKeysTrans = [] #All keys transfered
        for i in range(len(keyRanges)): #Find new successor node & add it
            if Distance.distance(keyRanges[i][0], preKey) >= \
                    disNewGKeyToOld: #>= is considered because tmpGKey is 1 less 
                break
            newNID = self._findNewNode() #Find new node
            PM.OVERLAY[self.PID.NID].addNewNode(newNID, False, keyRanges[i][1],\
                        Config.MAX_KEY, 0, newGKey, tmpCMembers, True) #Add new
            PM.STAT_CHECK_LOAD.append(1) #Cost to add new node
            keyRanges[i].append(newNID) #Add new node to key ranges

            #Transfer my keys if required - check based on global keys
            keysToSend = []
            for key in keys:
                if keyRanges[i][0] == keyRanges[i][1]: #Only if same key
                    if key == keyRanges[i][0]: keysToSend.append(key)
                else:
                    if Distance.inRangeLR(key, keyRanges[i][0], keyRanges[i][1]\
                                          , True):
                        keysToSend.append(key)
            if len(keysToSend) > 0:
                numMsg = self._transferKeys(keysToSend, newNID, True, False, \
                                            False)
                PM.STAT_CHECK_LOAD.append(numMsg)
                allKeysTrans += keysToSend
            
        #Inform cMembers to update global key & move index. No need to notify
        if self._numCMembers > 0:
            msg = OverlayMsg('ChangeGKey', self.PID, -1, [newGKey, keyRanges])
            numMsg = self._sendToCMembers(msg) #add to cMember key update cost
            PM.STAT_CHECK_LOAD.append(numMsg)

        #Join each new node to overlay. Add reverse order to update succe/prede
        for i in reversed(range(len(keyRanges))): 
            if len(keyRanges[i]) == 2: continue #No node added
            newMsg = OverlayMsg('JoinOverlay', self.PID, -1, \
                    [[keyRanges[i][1], [PM.OVERLAY[keyRanges[i][2]].PID], []]])
            #Use node that comes to current gKey to notify gKey change to others
            if keyRanges[i][1] == preKey: newMsg.payload[0][2] = tmpCMembers 
            PM.OVERLAY[self.PID.NID].sendMsg(newMsg, keyRanges[i][2])            
            PM.STAT.trackStat('AddSuce', [self.PID.NID, keyRanges[i][2], \
                        keyRanges[i][0], keyRanges[i][1], newGKey]) #Succe added

        #Set this node's new global key & inform overlay layer not to send
        #notification for departure.
        PM.OVERLAY[self.PID.NID].changeGKey(newGKey, \
                                    [[newGKey, tmpCMembers, []]], False, True)
        return [True, allKeysTrans]


    def _addNodeBetweenPrede(self, keys, maxKey):
        '''
        Check whether a node between this node & its predecessor can be added. 
        If so add a node(s)
        @param keys: List of keys to be transfered to predecessor
        @param maxKey: Maximum key
        @return: [Success or failure, key moved]        
        '''
        keyRanges = self._splitSeriesOfKeys(maxKey, False)
        if len(keyRanges) == 0: return [False, []]

        tmpGKey = -1
        for i in reversed(range(len(keyRanges))):#Has enough key space for prede
            if Distance.distance(keyRanges[i][1], self.PID.gKey) > 0: 
                tmpGKey = keyRanges[i][1]
                break
        #Can key be moved without violating global key of this node?
        if tmpGKey == -1: return [False, []]
        assert(Distance.inRange(tmpGKey, \
            PM.OVERLAY[self.PID.NID].getPrede()[0].gKey, self.PID.gKey)), \
            'tmpGKey not between this node & predecessor'

        allKeysTrans = []
        disTmpGKeyToOld = Distance.distance(tmpGKey, self.PID.gKey)
        #Me & my cluster members will become the successor(s)
        tmpCMembers = copy.deepcopy(self.getCMembers())
        tmpCMembers.append(copy.deepcopy(self.PID)) #Add this node
        for i in range(len(keyRanges)): #Add new predecessor(s)
            if Distance.distance(keyRanges[i][1], self.PID.gKey) < \
                                disTmpGKeyToOld: 
                break
            newNID = self._findNewNode() #Find a new node & just add it
            PM.OVERLAY[self.PID.NID].addNewNode(newNID, False, keyRanges[i][1],\
                        Config.MAX_KEY, 0, self.PID.gKey, tmpCMembers, False)
            PM.STAT_CHECK_LOAD.append(1) #Cost to add new node
            keyRanges[i].append(newNID) #Add new node to selected key ranges

            #Transfer relevant keys to new node(s) - check based on global key
            keysToSend = []
            for key in keys:
                if keyRanges[i][0] == keyRanges[i][1]: #Only if same key
                    if key == keyRanges[i][0]: keysToSend.append(key)
                else:
                    if Distance.inRangeLR(key, keyRanges[i][0], keyRanges[i][1]\
                                          , True):
                        keysToSend.append(key)
            if len(keysToSend) > 0:
                numMsg = self._transferKeys(keysToSend, newNID, True, False, \
                                            False)
                PM.STAT_CHECK_LOAD.append(numMsg)
                allKeysTrans += keysToSend
        
        #Inform cMembers to move index to nodes given in keyRanges
        if self._numCMembers > 0:
            startKey = keyRanges[len(keyRanges) - 1][1]#Key to start transfer <=
            msg = OverlayMsg('MoveKeys', self.PID, -1, [startKey, keyRanges])
            numMsg = self._sendToCMembers(msg) #add to cMember key update cost
            PM.STAT_CHECK_LOAD.append(numMsg)

        #Join each new node to overlay
        for i in reversed(range(len(keyRanges))):
            if len(keyRanges[i]) == 2: continue
            newMsg = OverlayMsg('JoinOverlay', self.PID, -1, \
                    [[keyRanges[i][1], [PM.OVERLAY[keyRanges[i][2]].PID], []]])
            PM.OVERLAY[self.PID.NID].sendMsg(newMsg, keyRanges[i][2])
            PM.STAT.trackStat('AddPred', [self.PID.NID, keyRanges[i][2], \
                            keyRanges[i][1], -1]) #Prede added - no gKey change

        return [True, allKeysTrans]


    def _addToIndex(self, msg):
        '''
        Add given resource to index. If from a resource also inform to replicas.
        If from global predecessor first fragment & then inform replicas. If 
        from a cluster member just add - as cluster member is responsible for
        fragmentation & replication
        @param msg: Message
        @return: Reply message (if relevant)
        '''        
        if msg.msgType == 'Put':
            self._idx.add(msg.key, msg.payload[0], msg.payload[1], msg.payload[2])        
            if msg.source.NID != self.PID.NID: self._numUpdatesRec += 1
            numMsgs = 0
            if self.PID.lKey in self._cMembers: #Inform to my replicas
                newMsg = OverlayMsg('PutReplica', self.PID, -1, \
                    [[[msg.key, msg.payload[0], msg.payload[1], msg.payload[2]]]])
                numMsgs = self._sendToCMembers(newMsg, True)
            return AdvMsg(self.PID, True, 'PutReply', numMsgs)
        elif msg.msgType == 'PutReplica': #Support bulk transfer
            for i in msg.payload[0]:
                self._idx.add(i[0], i[1], i[2], i[3])
            if msg.source.NID != self.PID.NID: self._numUpdatesRec += 1


    def _handleReceiveKeys(self, msg):
        '''
        Handle Keys transfered from another node. Change gKey if needed & 
        inform other nodes
        @param msg: Message
        '''
        if msg.source.NID != self.PID.NID: self._numUpdatesRec += 1
        #If new gKey is given, change this node's & cluster Member's gKey
        if msg.payload[2] > -1: #Has a valid GKey
            if self._numCMembers > 0: #Inform cMembers to update global key
                newMsg = OverlayMsg('ChangeGKey', self.PID, -1, [msg.payload[2]])                    
                numMsg = self._sendToCMembers(newMsg) #track cost
                PM.STAT_CHECK_LOAD.append(numMsg)

            preGKey = self.PID.gKey #Current key
            self.PID.gKey = msg.payload[2] #Set my new key
            self._updateCMemberGKey(msg.payload[2]) #Update all cluster members
            tmpCMembers = copy.deepcopy(self.getCMembers()) #List of cMembers
            tmpCMembers.append(copy.deepcopy(self.PID))
            departedNodes = []
            if msg.payload[3] == True: departedNodes.append(msg.source)
            toNotify = [[msg.payload[2], tmpCMembers,  departedNodes]] #New loc
            toNotify.append([preGKey, [], tmpCMembers]) #Old location
            PM.OVERLAY[self.PID.NID].changeGKey(msg.payload[2], toNotify)
    
        keys = msg.payload[0]
        self._queLoadReceived += msg.payload[1] #Show that query load not 0 
        #If there are fragments divide incoming list of entries among cMembers
        fragments = {}
        tmpCMembers = copy.deepcopy(self._cMembers)
        if self.PID.lKey not in tmpCMembers: 
            tmpCMembers[self.PID.lKey] = [self.PID]           
        for entry in keys:
            for j in tmpCMembers: #Assign based on node/resource hash
                if Distance.inRangeLR(entry[3].NIDHash, \
                        tmpCMembers[j][0].lStartKey, tmpCMembers[j][0].lKey):
                    if j in fragments: fragments[j].append(entry)
                    else: fragments[j] = [entry]
                    break
        #Send fragments to appropriate cluster members
        numMsg = 0
        for k in self._cMembers: #for each fragment
            if k not in fragments: continue
            newMsg = OverlayMsg('PutReplica', self.PID, -1, [fragments[k]])
            for l in range(len(self._cMembers[k])):#Each replica in fragment
                PM.OVERLAY[self.PID.NID].sendMsg(newMsg, self._cMembers[k][l].NID)
                numMsg += 1
        PM.STAT_CHECK_LOAD.append(numMsg) #Cost
            
        if self.PID.lKey in fragments: #Add keys that should be in my index
            for l in fragments[self.PID.lKey]: 
                self._idx.add(l[0], l[1], l[2], l[3])


    def _canCMembersHandleLoad(self, idxLoad, queLoad):
        '''
        Can cluster members (other than this node) handle load
        @param idxSize: Index size trying to transfer
        @param queLoad: Query load trying to transfer 
        @return: True or False
        '''
        resLoad = self._residualLoadOnCluster(True) #Residual load on cluster
        #Is my load higher than residual load?
        if (idxLoad > resLoad[0]) or (queLoad > resLoad[1]): return False
        return True


    def _canGlobalHandleLoad(self, idxSize, queLoad, gSucce = True):
        '''
        Check whether global successor(s)/predecessors can handle load
        @param idxSize: Index size trying to transfer
        @param queLoad: Query load trying to transfer 
        @param gSucce: Try global successor 
        @result: [True or false, node to send if True] 
        '''
        newMsg = OverlayMsg('CanHandleLoad', self.PID, -1, [idxSize, queLoad, \
                                                gSucce], Config.TTL_LOAD_SPLIT)
        replyMsg = PM.OVERLAY[self.PID.NID].sendMsg(newMsg)
        assert(replyMsg.msgType == 'CanHandleLoadReply'), \
            'Wrong message type' + replyMsg.msgType
        PM.STAT_CHECK_LOAD.append(replyMsg.hops)
        return replyMsg.payload


    def _canLSucceHandleLoad(self, idxSize, queLoad):
        '''
        Can local successor(s) among cluster members handle my load
        @param idxSize: Index size trying to transfer
        @param queLoad: Query load trying to transfer 
        @return: True or False
        '''
        lSucce = self.getLSucce((self.PID.lKey + 1) % (Config.MAX_KEY + 1))
        msg = OverlayMsg('GetLoad', self.PID, -1, [[], ['Idx', 'Que'], False])
        replyMsg = PM.OVERLAY[self.PID.NID].sendMsg(msg, lSucce.NID)
        assert(replyMsg.msgType == 'GetLoadReply'), 'wrong message type'
        PM.STAT_CHECK_LOAD.append(1)
        #Can't accept 1 of the loads
        if ((idxSize + replyMsg.payload[0]) > Config.THRES_IDX_SIZE) or \
            ((queLoad + replyMsg.payload[1]) > Config.THRES_MAX_QUE_LOAD):
            return False
        return True


    def _constructCMembers(self, ranges):
        '''
        Construct cluster member list using given ranges
        @param ranges: Dictionary of ranges {NID:[start, end]}
        @return: Dictionary of cluster members {localKey: [PeerID]}  
        '''
        cMembers = {}
        for i in ranges: #for each entry
            if ranges[i][1] in cMembers: #lKey already in
                cMembers[ranges[i][1]].append(PeerID(i, self.PID.gKey, \
                                                    ranges[i][1], ranges[i][0]))
            else: #New one
                cMembers[ranges[i][1]] = [PeerID(i, self.PID.gKey, \
                                                 ranges[i][1], ranges[i][0])]
        return cMembers
        

    def _findNewNode(self):
        '''
        Find a new node to add into overlay to balance load. We keep a list of
        candidates. In practice this can also be done by sending a 
        multi-attribute query to find a node with given set of resources
        @return: Node ID of new node (not the Peer ID, just NID)  
        '''
        assert(len(PM.RESOURCEFUL_PEERS) > 0), 'No resourceful peers'
        tmpIdx = random.randint(0, len(PM.RESOURCEFUL_PEERS) -1)
        nID = PM.RESOURCEFUL_PEERS[tmpIdx]
        del PM.RESOURCEFUL_PEERS[tmpIdx] #Remove from list of resourceful peers
        return nID


    def _fragmentHalf(self, newNode):
        '''
        Find local range of node to be given 1/2 of the index
        @param newNode: New nodes node ID
        @return: [start range for new node, end range for new node, dictionary 
        of {node ID: [start Key, end key], ...]} for all nodes
        '''
        fragments = {}
        middle = (self.PID.lStartKey + Distance.distance(self.PID.lStartKey, \
                 self.PID.lKey)/2) %(Config.MAX_KEY + 1)
        myRange = [(middle + 1) % (Config.MAX_KEY + 1), self.PID.lKey]
        for i in self._cMembers:                
            for j in range(len(self._cMembers[i])):
                if i == self.PID.lKey:
                    fragments[self._cMembers[i][j].NID] = myRange
                else: #Other's are not affected
                    fragments[self._cMembers[i][j].NID] = \
                        [self._cMembers[i][j].lStartKey, \
                         self._cMembers[i][j].lKey]
        #Add new one - if it's already there it'll be updated
        fragments[newNode] = [self.PID.lStartKey, middle]
        fragments[self.PID.NID] = myRange #Add my new key
        return fragments


    def _fragmentUniform(self):
        '''
        Find new list of ranges when index is uniformly fragmented by adding a 
        new node.
        @return: [start range for new node, end range for new node, dictionary 
        of {node ID: [start Key, end key], ...]} for all nodes
        ''' 
        fragments = copy.deepcopy(self._cMembers)
        if self.PID.lKey not in fragments: #Add this node
            fragments[self.PID.lKey] = [self.PID]
        else: fragments[self.PID.lKey].append(self.PID)
        newFrags = {}
        numFrags = len(fragments) + 1 #After adding me & new one
        fragRange = (Config.MAX_KEY + 1)/float(numFrags)
        fragCovered = [False] * numFrags
        maxIdx = -1
        #Find maximum overlapping node for each fragment
        for i in fragments: #For each candidate what's the best coverage
            maxCover = [-1, -1, -1]
            for j in range(numFrags):
                if fragCovered[j] == True: continue #don't check covered frags
                startRange = int(round(j * fragRange)) #New range start
                endRange = int(round((j + 1) * fragRange)) - 1 #New range end            
                cover = Distance.coverage(startRange, endRange, \
                                fragments[i][0].lStartKey, fragments[i][0].lKey)
                if cover[0] > maxCover[0]:  #Largest coverage
                    maxCover[0] = cover[0]
                    maxCover[1] = startRange
                    maxCover[2] = endRange
                    maxIdx = j
            for k in range(len(fragments[i])):
                newFrags[fragments[i][k].NID] = [maxCover[1], maxCover[2]]
            fragCovered[maxIdx] = True
        #Find which fragment is not covered by a node
        for i in range(len(fragCovered)):
            if fragCovered[i] == False:
                startRange = int(round(i * fragRange)) #New range start
                endRange = int(round((i + 1) * fragRange)) - 1 #New range end
                return [startRange, endRange, newFrags]


    def _handleCanHandleLoadMsg(self, msg):
        '''
        Can this node (& its cluster members) handle what predecessor(s)/
        successor(s) is requesting. Need to find list of keys to move to 
        successor/predecessor to support wave-like key movement (not implemented) 
        @param msg: Message
        @return: Modified message indicating remaining load & this node's (or 
        this cluster's) contribution
        '''
        [idxCapacity, queCapacity] = self._residualLoadOnCluster()
        result = [idxCapacity, queCapacity, [], self.PID.NID]#Keys to move empty
        msg.payload[0] -= idxCapacity #Reduce load can accommodate
        msg.payload[1] -= queCapacity
        if msg.payload[0] < 0: msg.payload[0] = 0
        if msg.payload[1] < 0: msg.payload[1] = 0
        #To support wave like load moving through multiple nodes list to keys
        #to move to next successor needs to be determined - not implemented
        msg.payload.append(result)
        return msg
            

    def _handleChangeGKeyMsg(self, msg):
        '''
        Change global key. Also transfer relevant keys to given node(s)
        @param msg: Message
        '''
        assert(msg.payload[0] > -1), 'Key not set'
        #First determine what keys to move before changing global key
        if len(msg.payload) > 1: #Has set of destinations to transfer keys
            #Find keys greater than given global key
            allKeysToTrans = self._idx.getConditioned('Idx', msg.payload[0], \
                                                      '>', self.PID.gKey)
            if len(allKeysToTrans) > 0:
                if type(msg.payload[1]).__name__ == 'int': #Specific destination
                    numMsg = self._transferKeys(allKeysToTrans, msg.payload[1],\
                                                True, True, False)
                    PM.STAT_CHECK_LOAD.append(numMsg)
                else: #List of nodes with ranges are given
                    for i in msg.payload[1]:
                        if len(i) == 2: continue #No node given
                        keysToTrans = []
                        for j in allKeysToTrans: #Find matching keys
                            if Distance.inRangeLR(j, i[0], i[1], True): 
                                keysToTrans.append(j)
                        if len(keysToTrans) > 0:
                            numMsg = self._transferKeys(keysToTrans, i[2], \
                                                        True, True, False)
                            PM.STAT_CHECK_LOAD.append(numMsg)
        self._idx.resetPartOfHist(msg.payload[0], '>', self.PID.gKey)
        self._updateCMemberGKey(msg.payload[0]) #Update all cluster members
        self.PID.gKey = msg.payload[0] #Change global key        
        PM.OVERLAY[self.PID.NID].changeGKey(msg.payload[0], [])


    def _handleMoveKeysMsg(self, msg):
        '''
        Move keys to predecessor(s)
        @param msg: Message. Pay load has the form [[min, max, NID]]
        '''
        #Find keys <= to given global key then transfer
        assert(msg.payload[0] > -1), 'Key not set'
        allKeysToTrans = self._idx.getConditioned('Idx', msg.payload[0], '<=',\
                                                   self.PID.gKey)
        if len(allKeysToTrans) == 0: return
        if type(msg.payload[1]).__name__ == 'int': #Specific destination
            numMsg = self._transferKeys(allKeysToTrans, msg.payload[1], True,\
                                         True, False)
            PM.STAT_CHECK_LOAD.append(numMsg)
            return
        #List of nodes with ranges are given
        for i in msg.payload[1]:
            if len(i) == 2: continue #No node given
            keysToTrans = []
            for j in allKeysToTrans: #Find matching keys
                if Distance.inRangeLR(j, i[0], i[1], True): 
                    keysToTrans.append(j)
            if len(keysToTrans) > 0:
                numMsg = self._transferKeys(keysToTrans, i[2], True, True, False)
                PM.STAT_CHECK_LOAD.append(numMsg)


    def _leaveOverlay(self):
        '''
        Leave overlay. If node is a replica leave after informing cluster 
        members. If node in a cluster with fragments check whether they can 
        handle load. If node is the only node in cluster check global  
        successor(s) are willing to accept the load, else try global 
        predecessor(s) If so, transfer keys, inform cluster members, also send 
        new gKey if receiver's gKey will change
        '''
        if Config.SIMULATION_TYPE != 'Chord+RDSim': return #Not supported
        newGKey = -1 #If sending to predecessor its gKey will change
        #Am I a fragment? No other replica of my index?        
        if self.PID.lKey not in self._cMembers: #No replicas
            idxLoad = self._idx.getTotalLoad('Idx', [])#current Index size
            if self._numCMembers > 0: #There are cluster members
                #Query load that'll be sending to cluster members
                queLoad = self._idx.getTotalLoad('In', []) + \
                        self._idx.getTotalLoad('FwdPrede', []) \
                        - self._numFwdCMember
                newNodeKeys = {}
                if Config.FRAGMENT_METHOD == 'Half':
                    #Can local successor handle load?
                    if self._canLSucceHandleLoad(idxLoad, queLoad) == False:
                        #can't leave see whether we need to move part of index
                        self._movePartOfIdx()
                        return
                    newNodeKeys = self._mergeHalf() #New key ranges
                elif Config.FRAGMENT_METHOD == 'Uniform':
                    #Can cluster members handle my load?
                    if self._canCMembersHandleLoad(idxLoad, queLoad) == False:
                        #can't leave see whether we need to move part of index
                        self._movePartOfIdx()
                        return
                    newNodeKeys = self._mergeUniform()
                else: assert(False), 'Unknown fragmentation method' + \
                                                Config.FRAGMENT_METHOD

                #Inform cluster members about local key change
                #As this node's information is not there it imply node left 
                updatedCMembers = self._constructCMembers(newNodeKeys)
                newMsg = OverlayMsg('CMemberUpdate', self.PID, -1, \
                                                [updatedCMembers, newNodeKeys])
                numMsg = self._sendToCMembers(newMsg)
                PM.STAT_CHECK_LOAD.append(numMsg)
                numMsg = self._transferKeys([], newNodeKeys, False)
                PM.STAT_CHECK_LOAD.append(numMsg)
            else: #No cluster members so try global successor(s)
                queLoad = self._idx.getTotalLoad('Out', [])
                result = self._canGlobalHandleLoad(idxLoad, queLoad)
                if result[0] == False:#Can't handle load. Try global predecessor
                    queLoad = self._idx.getTotalLoad('In', [])
                    result = self._canGlobalHandleLoad(idxLoad, queLoad, False)
                    if result[0] == False: #Both succe & prede can't handle load
                        self._movePartOfIdx()#can't leave see whether we need to
                        return
                    newGKey = self.PID.gKey #Predecessor gets my key
                #Departing node should not empty index as we need stat
                if newGKey == -1: #To successor. No global key change
                    numMsg = self._transferKeys([], result[1], False, True, \
                                                False)
                else: #Predecessor(s) global key change
                    numMsg = self._transferKeys([], result[1], False, True, \
                                                False, newGKey, True)
                PM.STAT_CHECK_LOAD.append(numMsg)
                PM.STAT.trackStat('Leave', [self.PID.NID, self.PID.gKey, \
                                                    newGKey, idxLoad, queLoad])
        else: #Has replica. Inform cluster members that node is leaving
            numMsg = self._sendToCMembers(OverlayMsg('LeaveCMember', self.PID, \
                                                                            -1))
            PM.STAT_CHECK_LOAD.append(numMsg)
            PM.STAT.trackStat('Leave', [self.PID.NID, self.PID.gKey, 0, 0]) 
        #If no CMembers change predecessor & successor pointers Else remove 
        #from my entry from finger table of predecessor & successor
        self._isLeaving = True #Mark as leaving 
        if self._numCMembers > 0: PM.OVERLAY[self.PID.NID].leaveOverlay(True)
        else: #No cluster members. Do we need to notify gKey change
            if newGKey == -1: PM.OVERLAY[self.PID.NID].leaveOverlay(False)
            else: #Predecessor will handle departure notification
                PM.OVERLAY[self.PID.NID].leaveOverlay(False, False, True)


    def _mergeHalf(self):
        '''
        Find local range of node when a node leave (which was created initially
        by fragmenting the address space by 1/2)
        @return: Dictionary {node ID: [start Key, end key], ..]} for all nodes
        '''
        assert(self.PID.lKey not in self._cMembers), \
            'There are replicas. This function should not be called'
        fragments = {}
        lSucce = self.getLSucce((self.PID.lKey + 1) % (Config.MAX_KEY + 1))
        
        succeRange = [self.PID.lStartKey, lSucce.lKey]
        for i in self._cMembers:                
            for j in range(len(self._cMembers[i])):
                if i == lSucce.lKey:
                    fragments[self._cMembers[i][j].NID] = succeRange
                else:
                    fragments[self._cMembers[i][j].NID] = \
                        [self._cMembers[i][j].lStartKey, \
                         self._cMembers[i][j].lKey]
        return fragments


    def _mergeUniform(self):
        '''
        Merge 2 fragments as this node is going to leave cluster. This should
        be called by the last node for a given fragment (i.e., no replicas for
        that fragment)
        @return: {node ID: [start Key, end key], ...]} for all existing nodes
        '''
        assert(self.PID.lKey not in self._cMembers), \
            'There are replicas this function should not be called'
        newFrags = {}
        numFrags = len(self._cMembers) #After removing this node
        fragRange = (Config.MAX_KEY + 1)/float(numFrags)
        fragCovered = [False] * numFrags
        maxIdx = -1

        #Find maximum overlapping node for each fragment
        for i in self._cMembers: #For each candidate what's the best coverage
            maxCover = [-1, -1, -1]
            for j in range(numFrags):
                if fragCovered[j] == True: continue #don't check covered frags
                startRange = int(round(j * fragRange)) #New range start
                endRange = int(round((j + 1) * fragRange)) - 1#New range end          
                cover = Distance.coverage(startRange, endRange, \
                    self._cMembers[i][0].lStartKey, self._cMembers[i][0].lKey)
                if cover[0] > maxCover[0]:  #Largest coverage
                    maxCover[0] = cover
                    maxCover[1] = startRange
                    maxCover[2] = endRange
                    maxIdx = j
            for k in range(len(self._cMembers[i])):
                newFrags[self._cMembers[i][k].NID] = [maxCover[1], maxCover[2]]
            fragCovered[maxIdx] = True
        return newFrags


    def _movePartOfIdx(self):
        '''
        Balance node's load by transferring keys to successor(s). If there are 
        multiple nodes in cluster aggregate & move from all fragments.
        '''
        if Config.SIMULATION_TYPE == 'Chord': return #Not supported
        #How much of index and/or query load to remove
        excessIdxSize = self._idx.getTotalLoad('Idx', [])- Config.THRES_IDX_SIZE
        if excessIdxSize < 0: excessIdxSize = 0
        inLoad = self._idx.getTotalLoad('In', [])
        excessQueLoad =  inLoad + self._idx.getTotalLoad('FwdPrede', []) - \
                                                    Config.THRES_MAX_QUE_LOAD
        if excessQueLoad < 0: excessQueLoad = 0
        if (excessIdxSize == 0) and (excessQueLoad == 0): return #Not overloaded
        
        resultSucce = [False, [], []]
        #Try successor(s) if index is too large or too much query load. Query 
        #load can be reduced only if IN load >= excess load. Give priority to que  
        if inLoad >= excessQueLoad:
            resultSucce = self._movePartOfIdxSucce(excessIdxSize, excessQueLoad)
            if resultSucce[0] == True:  #Successful 
                PM.STAT.trackStat('TranSuce', [self.PID.NID, resultSucce[1],\
                                         resultSucce[2]])#Transfer to succe 
                return

        #Try predecessor(s) if successor failed
        resultPrede = self._movePartOfIdxPrede(excessIdxSize, excessQueLoad)
        if resultPrede[0] == True: #Success
            PM.STAT.trackStat('TranPred', [self.PID.NID, resultPrede[1], \
                                            resultPrede[2]]) #Transfer to Prede 
            return
        #Unable to transfer keys. Add new node & move keys
        self._addNodeBetween(excessIdxSize, excessQueLoad, resultSucce[1], \
                             resultSucce[2], resultPrede[1], resultPrede[2])


    def _movePartOfIdxSucce(self, excessIdxSize, excessQueLoad):
        '''
        Try to move part of index to successor. Will change this node's gKey. If
        no space is left after moving keys this node need to be removed
        @param excessIdxSize: Excess index size 
        @param excessQueLoad: Excess query load
        @return: [Success or failure, keys to move, total load for those keys]
        '''
        idxKeysToMove = [] #Keys to remove from large index
        queKeysToMove = [] #Keys to remove from index
        if excessIdxSize > 0: #If removing due to large index
            idxKeysToMove = self._idx.shedLoad(excessIdxSize, 'Idx', False, \
                                                                self.PID.gKey)
            if len(idxKeysToMove) == 0: return [False, [], []] #Can't move keys
        if excessQueLoad > 0: #If removing due to large query load
            queKeysToMove = self._idx.shedLoad(excessQueLoad, 'In', False, \
                                                                self.PID.gKey)
            if len(queKeysToMove) == 0: return [False, [], []] #Can't move keys

        #Not yet decided to fragment or replicate. Find all keys to move
        tmpKeysToMove = idxKeysToMove + queKeysToMove #Combine 2 lists
        minKey = Distance.mini(tmpKeysToMove, self.PID.gKey)
        allKeysToMove = self._idx.getConditioned('Idx', minKey, '>=', \
                                self.PID.gKey) #All keys >= minKey will be moved            
        allKeysToMove += self._idx.getConditioned('Out', minKey, '>=', \
                                self.PID.gKey) #All keys >= minKey will be moved            
        allKeysToMove = list(set(allKeysToMove)) #Remove any duplicates
        
        #Find actual index size & query load for selected keys. If there are
        #cluster members find their load as well
        totalLoad = self._totalLoadOnClusterCondi(['Idx', 'Out'], minKey, '>=')
        #Are my successor(s) willing to accept total load?
        result = self._canGlobalHandleLoad(totalLoad[0], totalLoad[1])
        if result[0] == False: return [False, allKeysToMove, totalLoad]#No

        #Transfer all keys & update keys on local ring to go up
        #New key is 1 less than smallest moving key. But this can't be done if
        #new key is same as predecessors key 
        newGKey = (minKey - 1) % (Config.MAX_KEY + 1)
        #Inform cluster members to update global key & move index. They don't 
        #need send notify messages as this node will take care for it
        if self._numCMembers > 0: #Has cluster members
            msg = OverlayMsg('ChangeGKey', self.PID, -1, [newGKey, result[1]])                    
            numMsg = self._sendToCMembers(msg) #track cost
            PM.STAT_CHECK_LOAD.append( numMsg)
        
        if len(allKeysToMove) > 0:
            numMsg = self._transferKeys(allKeysToMove, result[1], True, True, \
                                                                        False)
            PM.STAT_CHECK_LOAD.append(numMsg)
        if newGKey != PM.OVERLAY[self.PID.NID].getPrede()[0].gKey:
            #Notify 1st arrival to new key then departure from previous key
            preGKey = self.PID.gKey
            self.PID.gKey = newGKey #Set my new gKey
            self._updateCMemberGKey(newGKey)  #Update cMember global key
            tmpCMembers = copy.deepcopy(self.getCMembers()) #List of cMembers
            tmpCMembers.append(copy.deepcopy(self.PID))
            toNotify = [[newGKey, tmpCMembers, []]] 
            toNotify.append([preGKey, [], tmpCMembers])
            PM.OVERLAY[self.PID.NID].changeGKey(newGKey, toNotify)
        else: #No key space left & successor accepting all load. Remove node
            if self._numCMembers > 0: #Has cluster members. Inform them to leave
                msg = OverlayMsg('Leave', self.PID, -1, False)                    
                numMsg = self._sendToCMembers(msg) #track cost
                PM.STAT_CHECK_LOAD.append(numMsg)
#                assert(False), 'No key space after moving to succe & has cluster'
            self._isLeaving = True #Mark as leaving
            PM.OVERLAY[self.PID.NID].leaveOverlay(False)
        
        return [True, allKeysToMove, totalLoad]
        

    def _movePartOfIdxPrede(self, excessIdxSize, excessQueLoad):
        '''
        Try to move part of index to predecessor. If no key space is left after 
        moving keys remove this node.
        @param excessIdxSize: Excess index size 
        @param excessQueLoad: Excess query load
        @return: [Success or failure, keys to move, total load for those keys] 
        '''
        idxKeysToMove = [] #Keys to remove from large index
        queKeysToMove = [] #Keys to remove from index
        if excessIdxSize > 0: #If removing due to large index
            idxKeysToMove = self._idx.shedLoad(excessIdxSize, 'Idx', True, \
                                                                self.PID.gKey)
            if len(idxKeysToMove) == 0: return [False, [], []] #Keys can't move 
        if excessQueLoad > 0: #If removing due to large query load
            queKeysToMove = self._idx.shedLoad(excessQueLoad, 'Out', True, \
                                                                self.PID.gKey)
            if len(queKeysToMove) == 0: return [False, [], []] #Keys can't move

        #Not yet decided to fragment or replicate
        tmpKeysToMove = idxKeysToMove + queKeysToMove #Combine 2 lists
        maxKey = Distance.maxi(tmpKeysToMove, self.PID.gKey)
        allKeysToMove = self._idx.getConditioned('Idx', maxKey, '<=', \
                                self.PID.gKey) #All keys >= minKey will be moved            
        allKeysToMove += self._idx.getConditioned('In', maxKey, '<=', \
                                self.PID.gKey) #All keys >= minKey will be moved
        allKeysToMove = list(set(allKeysToMove)) #Remove any duplicates

        #Find actual index size & query load for selected keys. If there are
        #cluster members find their load as well
        totalLoad = self._totalLoadOnClusterCondi(['Idx', 'In'], maxKey, '<=')
        #Are my predecessor(s) willing to accept total load?
        result = self._canGlobalHandleLoad(totalLoad[0], totalLoad[1], False)
        if result[0] == False: return [False, allKeysToMove, totalLoad] #No
        #Inform cluster members to move keys to predecessor
        if self._numCMembers > 0: #Has cluster members
            msg = OverlayMsg('MoveKeys', self.PID, -1, [maxKey, result[1]])                    
            numMsg = self._sendToCMembers(msg) #track cost
            PM.STAT_CHECK_LOAD.append(numMsg)

        if len(allKeysToMove) > 0: #Transfer all keys to predecessor
            numMsg = self._transferKeys(allKeysToMove, result[1], True, True, \
                            False, maxKey, maxKey == self.PID.gKey)
            PM.STAT_CHECK_LOAD.append(numMsg)
        if maxKey == self.PID.gKey: #Predecessor comes to my position so leave
            if self._numCMembers > 0: #Has cMembers inform them to leave
                msg = OverlayMsg('Leave', self.PID, -1, True)
                numMsg = self._sendToCMembers(msg) #track cost
                PM.STAT_CHECK_LOAD.append(numMsg)                
#                assert(False), 'No key space after moving to prede & has cluster'
            self._isLeaving = True #Mark as leaving 
            PM.OVERLAY[self.PID.NID].leaveOverlay(False, False, True)
        return [True, allKeysToMove, totalLoad]


    def _queryIndex(self, msg):
        '''
        Check whether index has what is needed to satisfy query
        @param msg: Query message
        @return: Modified query message
        '''
        n = msg.n - msg.numResFound #How many resources required
        predeGKey = PM.OVERLAY[self.PID.NID].getPrede()[0].gKey 
        inQueryKey = msg.minKey if (Distance.inRangeR(msg.minKey, predeGKey, \
                    self.PID.gKey) == True) else -1 #Is this a direct/IN query
        lastNode = True if (Distance.inRangeR(msg.maxKey, predeGKey, \
            self.PID.gKey) == True) else False #Is last node query will reach?
        results = self._idx.query(n, msg.attToQue, msg.query, msg.resources, 
                                inQueryKey, msg.maxKey, self.PID.gKey, lastNode)        
        numRes = len(results)
        if numRes > 0:
            msg.resources += results
            msg.numResFound += numRes
            self._numQueAns += 1
        if msg.foundEnoughResources() == False:
            if msg.hasFragmentsToTry() == False: #1st node in cluster
                msg.setFragmentsToTry(copy.deepcopy(self.getCMembers(True, True)))
            else: msg.popFragment() #Remove my entry
            if msg.hasFragmentsToTry() == True: #Need to try other fragments
                self._numFwdCMember += 1
        self._queryInTime.append(PM.EVENTS.now) #Track query arrival time 
        return msg


    def _removeFromIndex(self, msg):
        '''
        Remove given entry from index   
        @param msg: Message
        @return: Message indicating success/failure
        '''
        if msg.msgType == 'ReplicaRemove':
            self._idx.remove(msg.payload[0], msg.payload[1], msg.payload[2])
#            self._idx.remove(msg.payload[0], msg.payload[1], msg.payload[2], \
#                             msg.payload[3])            
            return
        #if 'Remove' message, then inform replicas (if available)
        numSend = 0
        result = self._idx.remove(msg.key, msg.payload[0], msg.payload[2])        
#        result = self._idx.remove(msg.key, msg.payload[0], msg.payload[1], \
#                                  msg.payload[2])        
        if self.PID.lKey in self._cMembers: #Has replica
            newMsg = OverlayMsg('ReplicaRemove', self.PID, -1, \
                    [msg.key, msg.payload[0], msg.payload[2]])
#            newMsg = OverlayMsg('ReplicaRemove', self.PID, -1, \
#                    [msg.key, msg.payload[0], msg.payload[1], msg.payload[2]])
            numSend = self._sendToCMembers(newMsg, True)
        return OverlayMsg('RemoveReply', self.PID, -1, result, 0, numSend)


    def _residualLoadOnCluster(self, skipMe = False):
        '''
        Find amount of residual load on cluster.
        @param skipMe: Skip this node   
        @return: [index size, query load]
        '''
        #Find load based on EWMA not from counters (not applicable for Index)
        totalLoad = self._totalLoadOnCluster(['Idx', 'Que'], skipMe, [], True)
        numFragments = len(self._cMembers)
        totalCMembers = self._numCMembers
        if skipMe == True: #Skip this node
            if self.PID.lKey in self._cMembers: numFragments -= 1
        else:
            if self.PID.lKey not in self._cMembers: numFragments += 1
            totalCMembers = self._numCMembers + 1
        resIdxSize = Config.THRES_IDX_SIZE * numFragments - totalLoad[0]
        resQueLoad = Config.THRES_MAX_QUE_LOAD * totalCMembers - totalLoad[1]
        if resIdxSize < 0: resIdxSize = 0
        if resQueLoad < 0: resQueLoad = 0
        return [resIdxSize, resQueLoad]


    def _sendToCMembers(self, msg, replicasOnly = False): 
        '''
        Send given message to all or subset of cluster members
        @param msg: Message
        @param replicasOnly: Send only to replicas
        @return: Number of messages send  
        '''
        numSend = 0
        if replicasOnly == False: #Send to all
            for i in self._cMembers: #For each local key
                for member in self._cMembers[i]:
                    PM.OVERLAY[self.PID.NID].sendMsg(msg, member.NID)
                    numSend += 1
        else: #only to replicas
            if self.PID.lKey not in self._cMembers: return numSend #No replica
            for replica in self._cMembers[self.PID.lKey]:
                PM.OVERLAY[self.PID.NID].sendMsg(msg, replica.NID)
                numSend += 1
        return numSend


    def _totalLoadOnCluster(self, loadTypes, skipMe = False, keys = None, \
                            useEWMA = False):
        '''
        Find total load on a given set of keys. For queries consider all nodes
        for index consider only the distinct fragments.
        @param loadTypes: List of Types of load(s) 
        @param skipMe: Skip this node 
        @param keys: List of keys. If not given - find all keys in cluster
        @param useEWMA: Use EWMA counters to answer load query (except for index) 
        @return: [index size, query load]
        '''
        if keys == None: keys = [] 
        loads = [0] * len(loadTypes) #[0, 0 , ...]
        hops = 0
        for lKey in self._cMembers: #Check each member
            resultMsg = None
            for member in self._cMembers[lKey]:
                payload = [keys, loadTypes, useEWMA]
                newMsg = OverlayMsg('GetLoad', self.PID, -1, payload)
                resultMsg = PM.OVERLAY[self.PID.NID].sendMsg(newMsg, member.NID)
                assert(resultMsg.msgType == 'GetLoadReply'),'Wrong message type'
                hops += 1
                for k in range(len(loadTypes)):
                    if loadTypes[k] == 'Idx': continue
                    loads[k] += resultMsg.payload[k]
            #Pick distinct fragments
            if self.PID.lKey != lKey: 
                for k in range(len(loadTypes)):
                    if loadTypes[k] == 'Idx': 
                        loads[k] += resultMsg.payload[k]
                        break

        if skipMe == False: #Consider my load as well
            for k in range(len(loadTypes)):
                loads[k] += self._idx.getTotalLoad(loadTypes[k], keys)
        PM.STAT_CHECK_LOAD.append(hops)
        return loads


    def _totalLoadOnClusterCondi(self, loadTypes, key, condition, \
                                 skipMe = False):
        '''
        Find total load on a keys satisfying given condition. For queries 
        consider all nodes for index consider only the distinct fragments.
        @param loadTypes: List of Types of load(s) 
        @param key: Key
        @param condition: Condition on key range to apply 
        @return: [index size, query load]        
        @param skipMe: Skip this node
        '''
        loads = [0] * len(loadTypes) #[0, 0 , ...]
        hops = 0
        for lKey in self._cMembers: #Check each member
            resultMsg = None
            for member in self._cMembers[lKey]:
                payload = [key, loadTypes, condition]
                newMsg = OverlayMsg('GetLoadKey', self.PID, -1, payload)
                resultMsg = PM.OVERLAY[self.PID.NID].sendMsg(newMsg, member.NID)
                assert(resultMsg.msgType == 'GetLoadKeyReply'),'Wrong msg type'
                hops += 1
                for k in range(len(loadTypes)):
                    if loadTypes[k] == 'Idx': continue
                    loads[k] += resultMsg.payload[k]
            #Pick distinct fragments
            if self.PID.lKey != lKey: 
                for k in range(len(loadTypes)):
                    if loadTypes[k] == 'Idx': 
                        loads[k] += resultMsg.payload[k]
                        break

        if skipMe == False: #Consider my load as well
            tmpKeys = []
            for k in loadTypes:
                tmpKeys += self._idx.getConditioned(k, key, condition, \
                                                    self.PID.gKey)
            keys = list(set(tmpKeys)) #Remove duplicates
            for k in range(len(loadTypes)):
                loads[k] += self._idx.getTotalLoad(loadTypes[k], keys)
                
        PM.STAT_CHECK_LOAD.append(hops)
        return loads


    def _loadOnClusterKeys(self, key, condition, skipMe = False):
        '''
        Find load on given range of keys from cluster members. For queries 
        consider all nodes & for index consider only the distinct fragments.
        @param key: Key
        @param condition: Condition 
        @param skipMe: Skip this node 
        @return: {{key:[index size, IN query load, out query load]}}
        '''
        totalLoad = {}
        hops = 0
        for lKey in self._cMembers: #For each local key
            resultMsg = None
            for member in self._cMembers[lKey]: #Check each member
                newMsg = OverlayMsg('GetLoadKeys', self.PID, -1, \
                                    [key, condition])
                resultMsg = PM.OVERLAY[self.PID.NID].sendMsg(newMsg, member.NID)
                assert(resultMsg.msgType == 'GetLoadKeysReply'),'Wrong msg type'
                hops += 1
                for i in resultMsg.payload:
                    entry = resultMsg.payload[i]
                    if i in totalLoad:
                        totalLoad[i][1] += entry[1] 
                        totalLoad[i][2] += entry[2] 
                    else: #Don't add index yet
                        totalLoad[i]= [0, entry[1], entry[2]] 
                
            if self.PID.lKey != lKey: #Pick distinct fragments
                for i in resultMsg.payload:
                    totalLoad[i][0] += resultMsg.payload[i][0] 
        if skipMe == False: #Consider my load as well
            tmpKeys = self._idx.getConditioned('Idx', key, condition, \
                                              self.PID.gKey) #Index
            tmpKeys += self._idx.getConditioned('In', key, condition, \
                                              self.PID.gKey) #In
            tmpKeys += self._idx.getConditioned('Out', key, condition, \
                                              self.PID.gKey) #InOut
            keys = list(set(tmpKeys)) #Remove duplicates
            result = self._idx.getLoadKeys(keys) #Index            
            for i in result:
                entry = result[i]
                if i in totalLoad:
                    totalLoad[i][0] += entry[0]
                    totalLoad[i][1] += entry[1] 
                    totalLoad[i][2] += entry[2] 
                else: totalLoad[i]= [entry[0], entry[1], entry[2]] 
        PM.STAT_CHECK_LOAD.append(hops)
        return totalLoad


    def _transferKeys(self, keys, dest, delete, receiverFragment = False, \
                      useLKeys = True, newGKey = -1, notifyDeparture = False):
        '''
        Copy/move given list of keys to given node(s). Also send transfered load
        information so that receiving node can better estimate its load
        @param keys: List of keys
        @param dest: Destination node or list of destinations with [start, end]  
        @param delete: Should those keys be removed from my index
        @param receiverFragment: Receiver is responsible for fragmentation
        @param useLKeys: Use local keys to check range
        @param newGKey: New global key if current key need to change
        @param notifyDeparture: Notify departure of this node   
        @return: Cost of transferring keys
        '''
        hops = 0
        toTransfer = [self._idx.get(keys)]
        toRemove = []
        if type(dest).__name__ == 'int': #specific destination
            if dest == self.PID.NID: return 0 #from me to me
            #Send query load (effective contribution) for these keys. Don't need
            #to be correct value. Mainly use to prevent new/received node from 
            #leaving next stat check round 
            #[keys, load, newGKey, notify departure]
            toTransfer.append(self._idx.getTotalLoad('Out', keys))
            toTransfer.append(newGKey)
            toTransfer.append(notifyDeparture)
            newMsg = OverlayMsg('PutReplica', self.PID, -1, toTransfer)
            if receiverFragment == True: newMsg.setMsgType('ReceiveKeys')
            PM.OVERLAY[self.PID.NID].sendMsg(newMsg, dest)
            if Config.MAX_PACKET_SIZE == 0: hops += 1#Packet size doesn't matter 
            else: hops += self._idx.numMsgs(keys) #Size matter - No of messages 
            if delete: toRemove = toTransfer[0]
        else: #Dictionary of destinations given
            assert(notifyDeparture == False), 'Can\'t send to multiple nodes'
            assert(newGKey == -1), \
                            'Can\'t inform to multiple nodes about key change'
            toSend = {} #{NID:[entries]}
            myMinKey = -1 #Find my key range
            myMaxKey = -1
            for j in dest:
                if j == self.PID.NID:
                    myMinKey = dest[j][0]
                    myMaxKey = dest[j][1]
                    break
            for entry in toTransfer[0]: #Each key to transfer
                for j in dest: #Which cluster member(s) should receive key
                    if j == self.PID.NID: continue #from me to me
                    send = self._isReplicaResponsible() #Should I send keys
                    #Use either global or local keys 
                    key = entry[3].NIDHash if (useLKeys == True) else entry[0]
                    handleStartEqualEnd = False if (useLKeys == True) else True
                    
                    #Is this key in range of node (either lKey or gKey based)
                    if Distance.inRangeLR(key, dest[j][0], dest[j][1], \
                                          handleStartEqualEnd) == True:
                        #If there are replicas only the node with lowest ID 
                        #among them need to transfer key(s) other replicas just
                        #remove those keys from index (if required)
                        if send == True: #Append entries to {dest}
                            if j in toSend: toSend[j].append(entry)
                            else: toSend[j] = [entry]
                        #Delete only if key doesn't mapped to my index
                        if (delete == True) and (myMinKey != -1) and \
                            (myMaxKey != -1) and (Distance.inRangeLR(key, \
                                myMinKey, myMaxKey, handleStartEqualEnd) \
                                                  == False): #Not in my range
                            toRemove.append(entry) #Remove from my index
                        break
            for j in toSend: #All cluster members
                #Send query load (effective contribution) for these keys. This's
                #not accurate but some estimation to prevent receiver from 
                #immediately leaving the Overlay is sufficient   
                keysToSend = []
                for entry in toSend[j]: keysToSend.append(entry[0])
                payload = [toSend[j], self._idx.getTotalLoad('Out', keysToSend)\
                           , newGKey, notifyDeparture]
                newMsg = OverlayMsg('PutReplica', self.PID, -1, payload)
                if receiverFragment == True: newMsg.setMsgType('ReceiveKeys')
                PM.OVERLAY[self.PID.NID].sendMsg(newMsg, j)
                if Config.MAX_PACKET_SIZE == 0: hops += 1#Don't care packet size 
                else: hops += self._idx.numMsgs(keysToSend) #Size matter
        for i in range(len(toRemove)): #Remove these keys from my index
            self._idx.remove(toRemove[i][0], toRemove[i][1], toRemove[i][3])
        return hops


    def _isReplicaResponsible(self):
        '''
        When it comes to copy/move keys is this node the one to actually send 
        message to receiver. Node with lowest ID should be selected
        @return: True or False
        '''
        if self.PID.lKey not in self._cMembers: return True #No replicas
        minNID = self.PID.NID
        for member in self._cMembers[self.PID.lKey]:
            if minNID > member.NID: return False
        return True


    def _updateCMember(self, PID, join = True):
        '''
        Update cluster member information. If present update. Else add or remove
        @param PID: Peer ID
        @param jojn: Cluster member of joining (or leaving)  
        '''
        #Is node already in cMember list?
        result = [-1, -1]
        for i in self._cMembers:
            for j in range(len(self._cMembers[i])):
                if self._cMembers[i][j].NID == PID.NID:
                    result = [i, j]
                    break
        if (result[0] > -1) and (result[1] > -1): #Already in. Remove it
            del self._cMembers[result[0]][result[1]]
            if len(self._cMembers[result[0]]) == 0: 
                del self._cMembers[result[0]]
            self._numCMembers -= 1
        if join == False: return #Remove request
        if PID.lKey not in self._cMembers: #Join request
            self._cMembers[PID.lKey] = [copy.deepcopy(PID)]
        else: self._cMembers[PID.lKey].append(copy.deepcopy(PID))
        self._numCMembers += 1


    def _updateCMembers(self, members):
        '''
        Update current list of cluster members
        @param members: Dictionary of cluster members {localKey: [PeerID]}  
        '''
        self._cMembers = {} #Reset
        self._numCMembers = 0
        for i in members:
            for j in range(len(members[i])):
                if members[i][j].NID == self.PID.NID: #My new local keys
                    self.PID.lKey = members[i][j].lKey
                    self.PID.lStartKey = members[i][j].lStartKey
                else:
                    if i in self._cMembers:
                        self._cMembers[i].append(copy.deepcopy(members[i][j]))
                    else: self._cMembers[i] = [copy.deepcopy(members[i][j])]
                    self._numCMembers += 1


    def _splitSeriesOfKeys(self, key, addSucce = True):
        '''
        Split given list of keys to series of new successor/predecessor nodes
        @param key: Min or max key among given list of keys 
        @param addSucce: Trying to add 1 or more successors   
        @return: Range of keys for each new node [[min, max], [min, max]]
        '''
        results = []
        #Find load for each key from cluster members {key:idx, in, out}
        condition = '>=' if (addSucce == True) else '<=' 
        loadOnCMembers = self._loadOnClusterKeys(key, condition)
        tmpKeys = Distance.sortKeys(loadOnCMembers.keys(), self.PID.gKey)
        if addSucce: tmpKeys.reverse() #Add a successor
        totalQueLoad = 0
        totalIdxLoad = 0
        allocatedTotal = 0 #Load that has being allocated so far (succe or prede)
        #If adding new successor it'll get FwdSucce else it'll get FwdPrede
        if addSucce: allocatedTotal = self._totalLoadOnCluster(['FwdSucce'])[0]
        else: allocatedTotal = self._totalLoadOnCluster(['FwdPrede'])[0]
        
        inTotalForAllocated = 0 #Or OUT
        selectedKeys = []
        for i in tmpKeys: #For each key
            idxLoad = loadOnCMembers[i][0]
            #Succe get part of current OUT load & prede get part of IN load
            queLoad = loadOnCMembers[i][2] if (addSucce == True) else \
                                                        loadOnCMembers[i][1]
            #Too much query load or index size for one node
            #What a node receive as queries depends on FwdLoad to current 
            #successor & newly added nodes -what those nodes will receive directly
            carriedLoad = allocatedTotal - inTotalForAllocated
            if carriedLoad < 0: carriedLoad = 0
            if ((totalQueLoad + queLoad + carriedLoad) > \
                    Config.THRES_MAX_QUE_LOAD) or ((totalIdxLoad + idxLoad)\
                     > Config.THRES_IDX_SIZE):
                #No key has being selected yet, so can't split any more
#                if len(selectedKeys) == 0: return results
                if len(selectedKeys) > 0: 
                    minKey = Distance.mini(selectedKeys, self.PID.gKey)
                    maxKey = Distance.maxi(selectedKeys, self.PID.gKey)
                    results.append([minKey, maxKey]) #Range for node
                    if addSucce: #IN load that'll reduce for next node
                        disMinKey = Distance.distance(minKey, self.PID.gKey)
                        for j in selectedKeys:
                            if Distance.distance(j, self.PID.gKey) <= disMinKey:
                                inTotalForAllocated += loadOnCMembers[j][1]
                    else: #OUT load
                        disMaxKey = Distance.distance(maxKey, self.PID.gKey)
                        for j in selectedKeys:
                            if Distance.distance(j, self.PID.gKey) >= disMaxKey:
                                inTotalForAllocated += loadOnCMembers[j][2]

                    allocatedTotal += totalQueLoad
#                if (allocatedTotal - inTotalForAllocated) > \
#                                                    Config.THRES_MAX_QUE_LOAD:
#                    return results
                #Can single node handle load for selected key
                if (queLoad <= Config.THRES_MAX_QUE_LOAD) and (idxLoad <= \
                                                        Config.THRES_IDX_SIZE): 
                    selectedKeys = [i] #Reset with this key
                    totalQueLoad = queLoad #Reset
                    totalIdxLoad = idxLoad
                else: #It can't
                    results.append([i, i]) #Range for node
                    if addSucce: #IN load that'll reduce for next node
                        inTotalForAllocated += loadOnCMembers[i][1]
                    else: inTotalForAllocated += loadOnCMembers[i][2] #OUT load
                    allocatedTotal += queLoad
                    selectedKeys = [] #Reset 
                    totalQueLoad = 0 #Reset
                    totalIdxLoad = 0
#                    break
            else: #just increment counters
                totalQueLoad += queLoad
                totalIdxLoad += idxLoad
                selectedKeys.append(i)
        if len(selectedKeys) > 0: #Add any remaining keys 
            results.append([Distance.mini(selectedKeys, self.PID.gKey), \
                            Distance.maxi(selectedKeys, self.PID.gKey)])
        return results


    def _updateCMemberGKey(self, newGKey):
        '''
        Update cluster members global key
        @param newKey: 
        '''
        for lKey in self._cMembers: #Each fragment
            for j in range(len(self._cMembers[lKey])): #Each replica
                self._cMembers[lKey][j].gKey = newGKey     


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

        for i in range(len(self._adsInTime)):
            if self._adsInTime[i] >= threshold:
                self._adsInTime = self._adsInTime[i:] #remove old ones
                break
            if i == (len(self._adsInTime) - 1): #No new ones 
                self._adsInTime = []

        tmpStat = [self.PID.NID, self._numQueAns, self._numQueFwd, \
                   self._numUpdatesRec, self._numCMembers, self._idxSizeEWMA,\
                   self._queryInEWMA, self._queryFwdPredeEWMA, \
                   self._queryFwdSucceEWMA, self._queryFwdCMemberEWMA, \
                   self._queryOutEWMA, self._idx.getTotalLoad('Idx', []), \
                   self._idx.getTotalLoad('In', []), \
                   self._idx.getTotalLoad('Out', []), \
                   self._idx.getTotalLoad('FwdPrede', []), \
                   self._idx.getTotalLoad('FwdSucce', []), self._numFwdCMember,\
                   len(self._queryInTime), len(self._adsInTime)]
        return tmpStat