'''
Created on Sep 3, 2012
@author: Dilum Bandara
@email: dilumb@engr.colostate.edu
@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 math
import random
import Config as Config

class LPHash(object):
    '''
    Locality preserving has implementation. Also implement mapping from a point
    or area to Hilbert space filling curve 
    '''


    def __init__(self, attOrder, numDim, numBits, sizeTorus, SFCMapFile):
        '''
        Constructor
        @param attOrder: Order of attributes (types of sensor readings)
        @param numDim: Number of dimensions of d-torus
        @param numBits: Number of bits per axis (define self._SPCresolution along axis) 
        @param sizeTorus: Size of d-Torus 
        @param SFCMapFile: Space Filling Curve (SFC) map file which contains 
        mapping form coordinates (x, y, z, ...) to a Hilbert SFC (integer)
        '''
        self._attOrder = sorted(attOrder) #Sort alphabetically
        self._numDim = numDim
        self._numBits = numBits
        self._sizeTorus = sizeTorus
        self._SPCMap = {} #Indexed by string representation of coordinates
        self._deltas = [] #Resolution along each axis
        self._attNames = [] #Tuples of attribute names based on dimensions

        #Build SFC mapping table
        gridSize = math.pow(2, numBits)
        for i in range(self._numDim): 
            self._deltas.append(self._sizeTorus[i]/gridSize)

        #Groups attributes based on dimensions
        numTuples = int(math.ceil(len(self._attOrder)/float(numDim)))
        for i in range(numTuples):
            start = i * self._numDim
            end = start + self._numDim
            if end > len(self._attOrder): end = len(self._attOrder)
            self._attNames.append(self._attOrder[start:end])

        fdIn = open(SFCMapFile, 'r') 
        for line in fdIn:
            tmpLine = line.split('\t')
            entry = [int(tmpLine[-1]), [], []]
            strCoordinate = ''
            for j in range(self._numDim):
                strCoordinate += tmpLine[j] + '_'
                idx = int(tmpLine[j])
                entry[1].append(idx * self._deltas[j]) #Lower left
                entry[2].append((idx + 1) * self._deltas[j]) #Upper right
            self._SPCMap[strCoordinate] = entry
        fdIn.close()


    def __del__(self):
        '''
        Destructor
        '''
        self._SPCMap = None
        self._attOrder = None
        self._deltas = None


    def val2Points(self, values):
        '''
        Calculate mapping from given attribute values to point(s) in d-torus. 
        Attribute values are scaled along each dimension using locality 
        preserved hashing. LPH_hash[i] = (value[i] - min[i])/(max[i] - min[i]).
        If particular attribute is missing substitute a random value
        @param values: List of attribute values as [[att_name, value], [.., ..]]
        @return: List of mappings for pairs of attributes. If values had n 
        entries result will contain ceil(n/2) values. [point1, point2, ...]
        '''
        #Make sure attributes are in the order defined in attOrder
        tmpValues = copy.deepcopy(values)
#        tmpValues = sorted(tmpValues, key=lambda att: att[0])
        tmpNames = []
        for i in values: tmpNames.append(i[0]) #Given attributes
            
        scaledValues = self._scale(tmpValues) #Scale attribute values based on LPH

        idxs = []
        for i in range(len(self._attNames)): #Which tuples to use
            for name in self._attNames[i]:
                if name in tmpNames:
                    idxs.append(i)
                    break

        #If 1 or more attributes in a tuple is missing, add a random value
        #Add a random value also if no of attributes in a tuple is < numDim 
        hashValues = []
        count = 0
        for i in idxs: #Each selected tuple
            tmpValues = []
            for name in self._attNames[i]: #Each attribute in selected tuple
                idx = -1
                for j in range(len(tmpNames)):
                    if tmpNames[j] == name:
                        idx = j
                        break
                if idx == -1: #No such attribute so add random value
                    tmpValues.append(random.random() * \
                                      self._sizeTorus[count % self._numDim])
                else:
                    tmpValues.append(scaledValues[idx][1] * \
                                     self._sizeTorus[count % self._numDim])
                count += 1
            #Add if size of a tuple is not same at no of dimensions
            for k in range(self._numDim - len(self._attNames[i])):
                tmpValues.append(random.random() * \
                                 self._sizeTorus[count % self._numDim])
                count += 1
            hashValues.append(tmpValues)
        return hashValues


    def que2Area(self, query):
        '''
        Calculate mapping from given multi-attribute range query to the minimum
        area/volume in d-torus that need to be searched. 
        Attribute values are scaled along each dimension using locality 
        preserved hashing. LPH_hash[i] = (value[i] - min[i])/(max[i] - min[i])
        @param queries: List of attribute values as [[att_name, min_value, 
        max_value], [..., ..., ...]]
        @return: Lower left & upper right coordinates of the area to search. 
        No of coordinates depends on the the dimensions of the d-torus. [[min_x,
        min_y, min_x, ...], [max_x, max_y, max_y, ...]]         
        '''
        #Fist find index of attributes as they are ordered.
        idx = []
        tmpQuery = copy.deepcopy(query) #Sort based on attribute names
        tmpQuery = self._scale(tmpQuery) #Scale attribute ranges
        tmpQuery = sorted(tmpQuery, key=lambda att: att[0])
        for i in range(len(tmpQuery)):
            for j in range(len(self._attOrder)):
                if query[i][0] == self._attOrder[j]: idx.append(j)

        #Find other attributes that goes with the given attributes
        modifiedRanges = [] #Modified ranges after adding missing attributes
        usedIdx = []
        numHashes = int(math.ceil(len(self._attOrder)/float(self._numDim)))
        for i in idx:
            for j in range(numHashes):
                start = j * self._numDim
                end = start + self._numDim
                if (start <= i < end) and i not in usedIdx: #Range it belongs to
                    tmpIdx = range(start, end)
                    usedIdx += tmpIdx
                    tmpRanges = []
                    for k in tmpIdx:
                        #If len(attOrder) is odd, attribute may not be in
                        attName = self._attOrder[k] if len(self._attOrder) \
                                    != k else 'RND'
                        if k in idx: #Attribute in
                            for l in tmpQuery: #Find range of attributes
                                if l[0] == attName: 
                                    tmpRanges.append(l)
                                    break
                        else: tmpRanges.append([attName, 0.0, 1.0]) #Added RND
                    modifiedRanges.append(tmpRanges)
        #Identify attribute pair that leads to lowest query area/volume
        minArea = 1.1 #At unit scale can't exceed 1.0
        minIdx = -1
        for i in range(len(modifiedRanges)):
            area = 1
            for j in modifiedRanges[i]:
                area *= j[2]- j[1] #(max - min)
            if area < minArea:
                minIdx = i
                minArea = area
        
        #Lower left & upper right corners of minimum query area. Scale back to 
        #size of d-torus
        queryArea = [[], []]
        for i in range(self._numDim):
            mini = modifiedRanges[minIdx][i][1] * self._sizeTorus[i]
            maxi = modifiedRanges[minIdx][i][2] * self._sizeTorus[i]
            queryArea[0].append(mini) #1st entry is name    
            queryArea[1].append(maxi) 

        return queryArea


    def area2SFC(self, area, sorting):
        '''
        Find list of SFCs that overlap with given area
        @param area: Query area [[min_x, min_y, ...], [max_x, max_y, ...]]
        @param ascending: How to sort list of points in 'None' sorting, 
        'ascending' order, or 'descending' order. 
        @return: List of SFC points as [[integer, [lower left], [upper right]]]
        '''
        #What range of grid points are covered by given area
        gridMin = []
        gridMax = []
        for i in range(self._numDim):
            gridMin.append(int(math.floor(area[0][i]/self._deltas[i])))
            gridMax.append(int(math.ceil(area[1][i]/self._deltas[i])))
        #Find what grid cells need to be searched
        grids = []
        for i in range(self._numDim):
            if i == 0:
                tmpGrids = [] 
                for j in range(gridMin[i], gridMax[i]):
                    tmpGrids.append([j])
                grids.append(tmpGrids)
            else:
                tmpGrids = []
                for j in grids[i - 1]:
                    for k in range(gridMin[i], gridMax[i]):
                        tmpGrids.append(j + [k])
                grids.append(tmpGrids)        
        #Find indexes using last list of grid entries which contain all dims
        idxs = []
        for i in grids[self._numDim - 1]:
            strCoordinate = ''
            for j in i: #Find string representation of coordinates 
                strCoordinate += str(j) + '_'
            entry = self._SPCMap[strCoordinate] #Get entry
            #Find actual area that need to be searched as a grid cell may be
            #larger than the area specified in query
            for k in range(self._numDim):
                entry[1][k] = max(area[0][k], entry[1][k])  
                entry[2][k] = min(area[1][k], entry[2][k])
            idxs.append(entry)
        if sorting == 'ascending':
            return sorted(idxs, key=lambda att: att[0])
        elif sorting == 'descending':
            return sorted(idxs, key=lambda att: att[0], reverse=True)
        elif sorting == 'None': return idxs
        else: assert(False), 'Unknown sorting type ' + sorting


    def _scale(self, values):
        '''
        Scale given list of attributes
        @param values: List of attribute vales [[att_name, value1, value2], []]
        value 2 is optional
        @requires: Scaled list of attributes 
        '''
        hasV2 = True if len(values[0]) == 3 else False #No of values
        
        for i in range(len(values)):
            v1 = values[i][1]
            v2 = -1 if hasV2 == False else values[i][2]  
            if values[i][0] == 'X': #X location
                max_min = float(Config.SIZE_TORUS[0])
                values[i][1] = v1/max_min
                if hasV2:
                    values[i][2] = v2/max_min
            elif values[i][0] == 'Y': #X location
                max_min = float(Config.SIZE_TORUS[1])
                values[i][1] = v1/max_min
                if hasV2:
                    values[i][2] = v2/max_min
            elif values[i][0] == 'ELEV': #Elevation
                max_min = float(Config.MAX_ELEV - Config.MIN_ELEV)
                values[i][1] = (v1 - Config.MIN_ELEV) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_ELEV) / max_min
            elif values[i][0] == 'DD': #Wind direction
                max_min = float(Config.MAX_DD - Config.MIN_DD)
                values[i][1] = (v1 - Config.MIN_DD) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_DD) / max_min
            elif values[i][0] == 'FF': #Wind speed
                max_min = float(Config.MAX_FF - Config.MIN_FF)
                values[i][1] = (v1 - Config.MIN_FF) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_FF) / max_min
            elif values[i][0] == 'FFGUST': #Wind gust
                max_min = float(Config.MAX_FFGUST - Config.MIN_FFGUST)
                values[i][1] = (v1 - Config.MIN_FFGUST) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_FFGUST) / max_min
            elif values[i][0] == 'P': #Station pressure
                max_min = float(Config.MAX_P - Config.MIN_P)
                values[i][1] = (v1 - Config.MIN_P) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_P) / max_min
            elif values[i][0] == 'PCP1H': #Accumulated precipitation 1 Hour
                max_min = float(Config.MAX_PCP1H - Config.MIN_PCP1H)
                values[i][1] = (v1 - Config.MIN_PCP1H) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCP1H) / max_min                
            elif values[i][0] == 'PCP5M': #Accumulated precipitation 5 min
                max_min = float(Config.MAX_PCP5M - Config.MIN_PCP5M)
                values[i][1] = (v1 - Config.MIN_PCP5M) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCP5M) / max_min                    
            elif values[i][0] == 'PCP15M': #Accumulated precipitation 15 min
                max_min = float(Config.MAX_PCP15M - Config.MIN_PCP15M)
                values[i][1] = (v1 - Config.MIN_PCP15M) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCP15M) / max_min
            elif values[i][0] == 'PCPRATE': #Precipitation rate
                max_min = float(Config.MAX_PCPRATE - Config.MIN_PCPRATE)
                values[i][1] = (v1 - Config.MIN_PCPRATE) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCPRATE) / max_min
            elif values[i][0] == 'PCPINT': #Precipitation intensity
                max_min = float(Config.MAX_PCPINT - Config.MIN_PCPINT)
                values[i][1] = (v1 - Config.MIN_PCPINT) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCPINT) / max_min
            elif values[i][0] == 'PCPTYPE': #Precipitation type
                max_min = float(Config.MAX_PCPTYPE - Config.MIN_PCPTYPE)
                values[i][1] = (v1 - Config.MIN_PCPTYPE) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_PCPTYPE) / max_min
            elif values[i][0] == 'T': #Air temperature
                max_min = float(Config.MAX_T - Config.MIN_T)
                values[i][1] = (v1 - Config.MIN_T) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_T) / max_min
            elif values[i][0] == 'RH': #Relative humidity
                max_min = float(Config.MAX_RH - Config.MIN_RH)
                values[i][1] = (v1 - Config.MIN_RH) / max_min
                if hasV2:
                    values[i][2] = (v2 - Config.MIN_RH) / max_min
            else: assert(False), 'Unknown attribute ' + values[i][0]
        return values