'''
Created on Jan 4, 2012
Modified on Apr 8, 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.
'''

import copy
import random
import Config as Config
import Distance as Distance


class FingerTable(object):
    '''
    Finger table class
    '''

    def __init__(self):
        '''
        Constructor
        '''
        self._FT = [] #list of [finger, [nodes], use this node next]
        self._numFingerUpdates = 0


    def __del__(self):
        '''
        Destructor
        '''
        self._FT = []


    def put(self, finger, key, node):
        '''
        Add to finger table. Add multiple entries if they have the same global
        key. If key is different remove existing ones. Maintain from largest to
        smallest finger to speed up
        @param finger: Finger number
        @param key: Key used to advertise
        @param node: NodeID  
        '''
        assert(-1 < finger < Config.KEY_LENGTH), 'Wrong finger ' + str(finger)
        self._numFingerUpdates += 1

        nodeCopy = copy.deepcopy(node)
        nodeCopy.gKey = key
        for i in range(len(self._FT)):
            if self._FT[i][0] == finger: #Exact finger
                if key == self._FT[i][1][0].gKey: #same global key
                    for j in range(len(self._FT[i][1])): #No duplicates 
                        if node.NID == self._FT[i][1][j].NID: return
                    self._FT[i][1].append(nodeCopy) #Add to current list
                else: self._FT[i][1] = [nodeCopy] #Add as a new list
                return
            if self._FT[i][0] < finger: #Next one is larger
                self._FT.insert(i, [finger, [nodeCopy], 0]) #insert
                return
        self._FT.insert(0, [finger, [nodeCopy], 0])#Add as no entry


    def remove(self, finger, key, node):
        '''
        Remove given finger from table
        @param finger: Finger number
        @param key: Key used to advertise        
        @param node: NodeID          
        '''
        assert(-1 < finger < Config.KEY_LENGTH), 'Wrong finger ' + str(finger)
        self._numFingerUpdates += 1

        for i in range(len(self._FT)):
            #Exact finger & node
            if self._FT[i][0] == finger:
                for j in range(len(self._FT[i][1])):
                    if (self._FT[i][1][j].NID == node.NID) and \
                                (self._FT[i][1][j].gKey == key): #Same node with key
                        del self._FT[i][1][j]
                        if len(self._FT[i][1]) == 0: del self._FT[i]
                        return


    def getPrede(self, key, myKey, needAll = False):
        '''
        Get predecessor of given key. Also consider exact match. Use either 
        round robin or random selection when multiple entries are there
        @param key: Key we are looking for
        @param myKey: Key of this node 
        @param needAll: Need list of all the nodes
        @return: [List of nodes. If not found return None, finger that matched]   
        '''
        for i in self._FT:
            #Find 1st finger between me & givn key
            if Distance.inRangeR(i[1][0].gKey, myKey, key):
                if (len(i[1]) == 1) or (needAll == True): 
                    return [i[1], i[0]] #all entries
                numEntries = len(i[1])
                if Config.NEXT_HOP_SELECTION == 'RoundRobin':                    
                    idx = i[2] % numEntries  #effective if an entry is removed
                    i[2] = (i[2] + 1) % numEntries #Next chance
                    return [[i[1][idx]], i[0]]
                elif Config.NEXT_HOP_SELECTION == 'Random':
                    return [[i[1][random.randint(0, numEntries - 1)]], i[0]]
                else: assert(False), 'Unknown next hop selection policy' + \
                    Config.NEXT_HOP_SELECTION
        return [None, -1]


    def getFinger(self, finger):
        '''
        Get node responsible for given finger
        @param finger: Finger ID
        @return: List of node IDs or None if not found 
        '''
        for i in range(len(self._FT)):
            if self._FT[i][0] == finger: #Exact finger
                return self._FT[i][1]
        return None


    def isFTEmpty(self):
        '''
        Is finger table empty?
        @return: True or False
        '''
        if len(self._FT) == 0: return True
        return False


    def getStat(self):
        '''
        Dump node statistics
        @return: [No of distinct entries in finger table, No finger updates]
        '''
        nodes = []
        for i in range(len(self._FT)):
            for node in self._FT[i][1]:
                if node.NID not in nodes: nodes.append(node.NID) #Distinct ones
        return [len(nodes), self._numFingerUpdates]