'''
Created on Jan 16, 2012
Modified on May 31, 2012
@author: Dilum Bandara
@version: 1.0
@license: Apache License v2.0

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

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

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

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

import Distance as Dis

class Histo(object):
    '''
    Histogram class
    '''


    def __init__(self):
        '''
        Constructor
        '''
        self._buckets = {}
        self._total = 0 #total count of elements in buckets


    def __del__(self):
        '''
        Destructor
        '''
        self._buckets = {}


    def put(self, value):
        '''
        Add to histogram
        @param valude: Value to add 
        '''
        self._total += 1
        if value in self._buckets: self._buckets[value] += 1
        else: self._buckets[value] = 1


    def remove(self, value):
        '''
        Remove bucket related to given value
        @param value: Value to remove  
        '''
        self._buckets[value] -= 1
        if self._buckets[value] == 0: del self._buckets[value]
        self._total -= 1


    def maxBucketCount(self):
        '''
        Find bucket with the largest no of entries in bucket
        @return: [value, fraction of load]
        '''
        maxValue = -1
        maxCount = -1
        for i in self._buckets:
            if self._buckets[i] > maxCount:
                maxValue = i 
                maxCount = self._buckets[i]
        return [maxValue, maxCount/float(self._total)]


    def maxBucketValue(self, nodeValue):
        '''
        Find bucket with largest value with respect to the given node value
        (not the count). Aware of address range wrapping
        @param nodeValde: Key of the node calling this function 
        @return: Largest bucket value
        '''
        tmpValues = Dis.sortKeys(self._buckets.keys(), nodeValue)
        return tmpValues[-1]


    def shedLoad(self, target, towardsPrede, nodeValue):
        '''
        Find set of buckets that have the target total count. Start with largest
        bucket value while considering address range can wrap around
        @param target: At least reduce this much of load
        @param towardsPrede: Load is moved towards predecessor or successor
        @param nodeValde: Key of the node calling this function 
        @return: List of bucket values to remove to shed load
        '''
        if target > self._total: return [] #too much
        values = Dis.sortKeys(self._buckets.keys(), nodeValue) 
        if towardsPrede == False: values.reverse() #Add a successor
        tmpTotal = 0
        idx = -1
        for i in range(len(values)):
            tmpTotal += self._buckets[values[i]]
            if tmpTotal >= target:
                idx = i
                break
        if idx > -1: return values[:idx + 1] #range works with a +1
        return []


    def getBuckets(self, values):
        '''
        Get all buckets or given list of buckets. Useful when asking for 
        specific bucket values
        @param values: List of values to find the load
        @return: Dictionary of buckets {value:count}
        '''
        if len(values) == 0: return self._buckets
        results = {}
        for i in self._buckets:
            if i in values: results[i] = self._buckets[i]            
        return results


    def getBucketsConditioned(self, key, condition, nodeValue):
        '''
        Get all buckets that satisfy the given condition. Useful when 
        transferring keys to successor or predecessor & removing stat for keys
        that are already moved before next load balacning cycle
        @param key: Given key 
        @param condition: Condition for keys
        @param nodeValue: Key of the node calling this function
        @return: List of bucket values
        '''
        values = Dis.sortKeys(self._buckets.keys(), nodeValue)
        disKeyToValue = Dis.distance(key, nodeValue)
        result = []
        for i in range(len(values)):
            disIToValue = Dis.distance(values[i], nodeValue)
            if condition == '>=':
                if disIToValue <= disKeyToValue: return values[i:]
            elif condition == '>':
                if disIToValue < disKeyToValue: return values[i:]
            elif condition == '<=':
                if disIToValue >= disKeyToValue: result.append(values[i])
                else: break
            elif condition == '<':
                if disIToValue > disKeyToValue: result.append(values[i])
                else: break
            else: assert(False), 'Unknown condition ' + condition
        return result


    def removeConditioned(self, value, condition, nodeValue): 
        '''
        Remove buckets that belongs to the keys that were moved
        @param key: Given key 
        @param condition: Condition for keys
        @param nodeValue: Key of the node calling this function
        '''
        values = self.getBucketsConditioned(value, condition, nodeValue)
        for value in values: #Remove
            self._total -= self._buckets[value]
            del self._buckets[value]


    def getTotalBucketCount(self, values):
        '''
        Get total number of entries in buckets or given list of buckets
        @param values: List of values to find the load
        @return: Total count
        '''
        if len(values) == 0: return self._total
        tmpTotal = 0
        for i in self._buckets:
            if i in values: tmpTotal += self._buckets[i]        
        return tmpTotal


    def reset(self):
        '''
        Reset histogram buckets
        '''
        self._buckets= {}
        self._total = 0
    
    
    def previousValue(self, keys, towardsPrede, nodeValue):
        '''
        Find largest/smallest bucket value less/larger than the given list of 
        bucket values
        @param keys: List of keys given
        @param towardsPrede: Load is moved towards predecessor or successor
        @param nodeValde: Key of the node calling this function
        @return: Previous key or -1 if no such keys   
        '''
        #Pick key to compare. If successor pick MAX distant key else pick MIN key
        keyToCheck = Dis.maxi(keys, nodeValue) if (towardsPrede == True) else \
                                                    Dis.mini(keys, nodeValue)
        disCheckToNode = Dis.distance(keyToCheck, nodeValue)
        values = Dis.sortKeys(self._buckets.keys(), nodeValue)
        
        for i in range(len(values)):
            disValueToNode = Dis.distance(values[i], nodeValue)
            if towardsPrede == True:
                if disValueToNode < disCheckToNode: return values[i]                
            else: #Towards successor
                if disValueToNode <= disCheckToNode:
                    if i == 0: return -1
                    else: return values[i - 1]
        return -1