'''
Created on Jan 19, 2012
Modified on June 28, 2012
@author: Dilum Bandara
@version: 0.2
@copyright: Copyright(c) 2012, Dilum Bandara
@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 Histo import Histo
import copy
import Config as Config
import Distance as Distance
import math


class ResourceIndex(object):
    '''
    Resource index class.
    '''

    def __init__(self):
        '''
        Constructor
        '''
        self._idx = {}
        self._idxSorted = {} #Sorted version of Index
        self._idxHisto = Histo() #Histogram for entries in index
        self._idxHistoValid = False #Is histogram valid 
        self._queStartInHisto = Histo() #Histogram for start key of In queries
        self._queEndOutHisto = Histo() #Histogram for end key of Out queries
        self._numQueFwdPrede = 0 #No of queries forwarded by predecessor
        self._numQueFwdSucce = 0 #No of Forward queries forwarded to successor

    def __del__(self):
        '''
        Destructor
        '''
        self._idx = {}
        self._idxSorted = {}
        self._idxHisto = None
        self._queStartInHisto = None
        self._queEndOutHisto = None


    def reset(self, everything = False):
        '''
        Reset index & histograms. No need to reset index size counter
        @param both: Reset both index & histograms  
        '''
        self._queStartInHisto.reset()
        self._queEndOutHisto.reset()
        self._numQueFwdPrede = 0
        self._numQueFwdSucce = 0
        if everything == True: 
            self._idx = {}
            self._idxSorted = {}
            self._idxHisto.reset()
            self._idxHistoValid = False


    def resetPartOfHist(self, newKey, condition, oldKey):
        '''
        Remove entries in histograms corresponding to keys that were removed
        @param newKey: New key of node
        @param condition: '<=', '<', '>' or '>='
        @param oldKey: Old key of node 
        '''
        self._queStartInHisto.removeConditioned(newKey, condition, oldKey)
        self._queEndOutHisto.removeConditioned(newKey, condition, oldKey)


    def add(self, key, attributeName, ress, source):
        '''
        Add given resource to index. Update if already exists
        @param key: Key use for indexing
        @param attributeName: Attribute name used to index resource  
        @param ress: List of resource attribute values. Given as a list of lists
        @param source: Resource ID        
        '''
        if source.NID in self._idx:  #Relying on if change, first REM then ADD 
            self._idx[source.NID][0].append([key, attributeName])
        else: self._idx[source.NID] = [[[key, attributeName]], \
                                    copy.deepcopy(ress), copy.deepcopy(source)]
        self._idxHistoValid = False #Mark histogram as invalid
        
        if attributeName in self._idxSorted: #Add to sorted index
            for i in range(len(self._idxSorted[attributeName])):
                if self._idxSorted[attributeName][i][0] >= key:
                    self._idxSorted[attributeName].insert(i, [key, source.NID])
                    return
            self._idxSorted[attributeName].append([key, source.NID])
        else: self._idxSorted[attributeName] = [[key, source.NID]] #1st one


    def remove(self, key, resourceType, source):
        '''
        Remove from index
        @param key: Key use for indexing
        @param resourceType: Resource type used to index resource   
        @param source: Node ID
        @return: Success or failure
        '''
        if source.NID not in self._idx: return False #Not in index
        #remove an entry completely only if all it's keys are removed
        for i in range(len(self._idx[source.NID][0])):
            if (key == self._idx[source.NID][0][i][0]) and \
                                resourceType == self._idx[source.NID][0][i][1]:
                del self._idx[source.NID][0][i]
                self._idxHistoValid = False #Mark histogram as invalid
                if len(self._idx[source.NID][0]) == 0: #All empty
                    del self._idx[source.NID] #Remove entry
                #remove from sorted index
                for i in range(len(self._idxSorted[resourceType])):
                    if (self._idxSorted[resourceType][i][0] == key) and \
                            (self._idxSorted[resourceType][i][1] == source.NID):
                        del self._idxSorted[resourceType][i]
                        if len(self._idxSorted[resourceType]) == 0: #empty
                            del self._idxSorted[resourceType]
                        return True
        return False


    def query(self, n, attToQue, resQuery, currentResources, minKey, maxKey, \
              myKey, lastNode = False):
        '''
        Find list of entries that satisfy given resource query
        @param n: How many resources required
        @param attToQue: Attribute use to issue query (in SADQ or sub-query)
        @param resQuery: actual resource query
        @param currentResources: List of resources that are already selected
        @param minKey: Minimum key query specified (set only if IN query-direct)
        @param maxKey: Maximum key query specified
        @param myKey: Global key of this node 
        @param lastNode: This will be the last node query will reach  
        @return: List of resources   
        '''
        results = []
        numResults = 0
        if minKey > -1: self._queStartInHisto.put(minKey) #IN/direct query
        else: self._numQueFwdPrede += 1 #FWD query by predecessor
        if attToQue not in self._idxSorted:
            if lastNode == False: self._numQueFwdSucce += 1 #FWD to successor
            else: self._queEndOutHisto.put(maxKey) #should be included in OUT load 
            return results
        
        for entry in self._idxSorted[attToQue]: #Check sorted entries
            if not(Distance.inRangeLR(maxKey, entry[0], myKey)) and \
                                        (lastNode == True): #Reached max key
#            if (entry[0] > maxKey) and (lastNode == True): #Reached max key                
                self._queEndOutHisto.put(maxKey)#Track end key as query terminate
                return results
            #Skip same resource if already selected at a previous node
            nID = entry[1]
            if nID in currentResources: continue
            
            #Assume that queries have only the attributes that are used to index
            attribsMatch = False
            for j in range(len(resQuery)): #Check each attribute in query
                for k in range(len(self._idx[nID][1])):#each attribute in entry
                    if resQuery[j][0] == self._idx[nID][1][k][0]: #Att match
                        if (resQuery[j][1] <= self._idx[nID][1][k][1] <= \
                                                                resQuery[j][2]):
                            attribsMatch = True #Match
                        else: attribsMatch = False #At least 1 attribute mismatch
                        break
                if attribsMatch == False: break #Break outer loop as well
            if attribsMatch == True: #If all required attributes match
                results.append(entry[1])
                numResults += 1
                if numResults == n: #Query answered. Track matched key
                    self._queEndOutHisto.put(entry[0])
                    return results #found enough resources                
        if lastNode == True: self._queEndOutHisto.put(myKey)#Last node to reach
        else: self._numQueFwdSucce += 1
        return results


    def get(self, keys, uniqueOnly = False):
        '''
        Get index entries for given/all keys. This returns duplicates if same 
        node is present multiple times unless uniqueOnly is set
        @param keys: List of keys to get entries for
        @param uniqueOnly: Send only unique nodes 
        @return: List of [key, attributeName, resource, source] 
        '''
        entries = []
        nodes = []
        for nid in self._idx:
            for j in range(len(self._idx[nid][0])): #Try all keys used to index
                if (len(keys) == 0) or (self._idx[nid][0][j][0] in keys):
                    if (uniqueOnly == True) and (self._idx[nid][2].NID in nodes):
                        continue #This node already added
                    entries.append([self._idx[nid][0][j][0], \
                                    self._idx[nid][0][j][1], self._idx[nid][1],\
                                    self._idx[nid][2]])
                    nodes.append(self._idx[nid][2].NID)
        return entries


    def getTotalLoad(self, loadType, keys, needEWMA = False):
        '''
        Get index size & query load of all/subset keys that node is tracking
        @param loadType: Type of load
        @param keys: List of keys
        @return: Load 
        '''
        if loadType == 'FwdPrede': 
            assert(len(keys) == 0), 'Keys cannot be specified'
            return self._numQueFwdPrede
        elif loadType == 'FwdSucce':
            assert(len(keys) == 0), 'Keys cannot be specified' 
            return self._numQueFwdSucce
        elif loadType == 'In': #Queries send directly to me 
            return self._queStartInHisto.getTotalBucketCount(keys)
        elif loadType == 'Out': #Queries send directly to me 
            return self._queEndOutHisto.getTotalBucketCount(keys)
        elif loadType == 'Idx': 
            if len(keys) == 0: return len(self._idx) #Index size
            else: return self._idxToBeRemoved(keys)
        elif loadType == 'Que': #total Que load = IN + FWD load
            assert(len(keys) == 0), 'Keys cannot be specified'
            return (self._queStartInHisto.getTotalBucketCount([]) + \
                                                        self._numQueFwdPrede)
        elif loadType == 'InFwdPrede': #IN + FwdPrede load
            return (self._queStartInHisto.getTotalBucketCount(keys) + \
                                                        self._numQueFwdPrede)
        elif loadType == 'OutFwdSucce': #OUT + FwdSucce load
            return (self._queEndOutHisto.getTotalBucketCount(keys) + \
                                                        self._numQueFwdSucce)
        else: assert(False), 'Unknown load type ' + loadType


    def getLoadKeys(self, keys):
        '''
        Find index size, IN load, & OUT load for each given key
        @param keys: List of keys 
        @return: {key:[idx, IN load, OUT load]}
        '''
        assert(len(keys) > 0), 'Empty key list'        
        results = {}
        if self._idxHistoValid == False: self._rebuildIdxHisto()
        for i in keys:
            idx = self._idxHisto.getBuckets([i])
            if len(idx) == 0: results[i] = [0]
            else: results[i] = [idx[i]]            
            queIn = self._queStartInHisto.getBuckets([i])
            if len(queIn) == 0: results[i].append(0)
            else: results[i].append(queIn[i])            
            queOut = self._queEndOutHisto.getBuckets([i])
            if len(queOut) == 0: results[i].append(0)
            else: results[i].append(queOut[i])            
        return results


    def _idxToBeRemoved(self, keys):
        '''
        If given list of keys are to be removed from index how much index size
        will actually reduce/free.
        @param keys: List of keys to remove
        @return: How much of index will actually be free 
        '''
        count = 0
        for i in self._idx: #For each resource
            canRemove = True
            for j in range(len(self._idx[i][0])): #Each key of the resource
                if self._idx[i][0][j][0] not in keys: #A key can't be removed
                    canRemove = False
                    break
            if canRemove == True: count += 1
        return count


    def shedLoad(self, loadTarget, loadType, towardsPrede, nodeKey):
        '''
        Identify list of keys to remove so that required amount of load is 
        reduced. Content is not removed.
        @param loadTarget: At least reduce this much of load
        @param loadType: Type of load to be shed
        @param towardsPrede: Is keys being send to predecessor 
        @param nodeKey: Key of the node calling this function  
        @return: [keys to remove to shed load]
        ''' 
        if loadType == 'Idx': #Shed from index
            if self._idxHistoValid == False: self._rebuildIdxHisto()
            #Get approximate idea
            tmpKeys = self._idxHisto.shedLoad(loadTarget, towardsPrede, nodeKey)
            if len(tmpKeys) == 0: return tmpKeys #Can't remove any
            while True:
                count = self._idxToBeRemoved(tmpKeys)
                if count >= loadTarget: return tmpKeys
                nextKey = self._idxHisto.previousValue(tmpKeys, towardsPrede, \
                                                                    nodeKey)
                if nextKey == -1: return [] #No more keys to try. Can't remove
                tmpKeys.append(nextKey)
        elif loadType == 'In': #Shed from IN queries
            return self._queStartInHisto.shedLoad(loadTarget, towardsPrede, \
                                                  nodeKey)
        elif loadType == 'Out': 
            return self._queEndOutHisto.shedLoad(loadTarget, towardsPrede, \
                                                 nodeKey)
        else: assert(False), 'Unknown load type ' + loadType


    def getConditioned(self, histo, key, condition, nodeKey):
        '''
        Get list of keys from the given histogram that satisfy the given condition
        @param histo: Which histogram to use
        @param key: Key to apply condition for 
        @param condition: Condition to use
        @param nodeKey: Key of the node calling function 
        @return: List of keys   
        '''
        if histo == 'Idx': 
            if self._idxHistoValid == False: self._rebuildIdxHisto()            
            return self._idxHisto.getBucketsConditioned(key, condition, nodeKey)
        elif histo == 'In':
            return self._queStartInHisto.getBucketsConditioned(key, condition,\
                                                                nodeKey)
        elif histo == 'Out':
            return self._queEndOutHisto.getBucketsConditioned(key, condition, \
                                                              nodeKey)
        else: assert(False), 'Unknown histogram ' + histo


    def fragmentHalf(self, startKey = -1, endKey = -1):
        '''
        Get a random half of the keys in index or if range of keys are given 
        find entries between [min, max]
        @param startKey: Start of range
        @param endKey: End of range
        @return: List of [[[key, att]], resource, source]
        '''
        results = []
        count = 0
        target = len(self._idx)/2
        for i in self._idx:
            if startKey == -1: #Key not given                            
                results.append(self._idx[i])
                count += 1
                if count >= target: break
            else:
                #Here the key is not the attribute value but hash of resource ID
                if Distance.inRangeLR(self._idx[i][2].NIDHash, startKey, \
                                                       endKey) == True:
                    results.append(self._idx[i])
        return results


    def maxKey(self, nodeKey):
        '''
        Find maximum key in index
        @param nodeKey: Key of the node calling this function 
        @return: Maximum key in index
        '''
        if self._idxHistoValid == False: self._rebuildIdxHisto()
        return self._idxHisto.maxBucketValue(nodeKey)


    def _rebuildIdxHisto(self):
        '''
        Rebuild histogram for resource index 
        '''
        self._idxHisto.reset() #Reset
        for i in self._idx:
            for j in range(len(self._idx[i][0])): 
                self._idxHisto.put(self._idx[i][0][j][0]) #rebuild
        self._idxHistoValid = True #Mark as valid


    def numMsgs(self, keys):
        '''
        Number of messages required to transfer given list of keys. Assume all
        resources have same no of attributes
        @param keys: List of keys
        @return: number of messages 
        '''
        nodes = []
        numIdxKeys = 0 #No of keys resource is indexed under
        for nid in self._idx: #For each resource
            for j in range(len(self._idx[nid][0])): #Try all keys used to index
                if (len(keys) == 0) or (self._idx[nid][0][j][0] in keys):
                    numIdxKeys += 1
                    if self._idx[nid][2].NID in nodes: 
                        continue #This resource already added
                    nodes.append(self._idx[nid][2].NID)
        totalBytes = len(nodes) * (Config.IP_PORT_SIZE + Config.NUM_ATTRIBS * \
                                    Config.ATT_VALUE_SIZE) + numIdxKeys * \
                                    math.ceil(Config.KEY_LENGTH/8.0)
        return int(math.ceil(totalBytes/Config.MAX_PACKET_SIZE))


    def getStat(self):
        '''
        Get stat
        @return: [index size, In query load, Out query load, Fwd query load]
        '''
        return [len(self._idx), self._queStartInHisto.getTotalBucketCount(), \
                self._queEndOutHisto.getTotalBucketCount(), \
                self._numQueFwdPrede, self._numQueFwdSucce]