'''
Created on Nov 9, 2011
Modified on Jan 10, 2012
@version: 0.2
@author: Dilum Bandara
@email: dilumb@engr.colostate.edu
@copyright: Copyright(c) 2011, Dilum Bandara
@license: GPL
'''

class CS(object):
    '''
    Content store class
    '''


    def __init__(self, maxSize, policy):
        '''
        Constructor
        @param maxSize: Maximum size of content store
        @param policy: Caching policy  
        '''
        self._maxSize = maxSize
        assert(policy == 'oldest' or policy == 'LRU' or policy == 'LFU'), \
            'Wrong caching policy ' + policy
        self.policy = policy
        self._CS = {} #{name: [data, expiration time]} 
        self._sizeCS = 0
        self.numCSHits = 0
        self.numCSChecks = 0
        self.futureRem = []

        
    def put(self, name, dataSize, data, genTime, source, sourceLoc, time):
        '''
        Add to content store. First check its not already in CS
        @param name: Content name without timeout
        @param dataSize: Data size 
        @param data: actual data
        @param genTime: Time that content/data was generated
        @param source: Data source
        @param sourceLoc: Data source location
        @param time: Current time - useful for LRU 
        @return: -1 - Error (object larger than cache), 0 success  
        '''
        #update entries to be removed as they now become fresh content
        thresh = -1
        if self.policy == 'oldest': thresh = genTime
        elif self.policy == 'LFU': thresh = 1
        elif self.policy == 'LRU': thresh = time
        if len(self.futureRem) == 3:
            if (self.futureRem[2][0] == name) or (self.futureRem[2][2] > thresh):
                del self.futureRem[2]
            if (self.futureRem[1][0] == name) or (self.futureRem[1][2] > thresh):
                del self.futureRem[1]
            if (self.futureRem[0][0] == name) or (self.futureRem[0][2] > thresh):
                del self.futureRem[0]
        elif len(self.futureRem) == 2:
            if (self.futureRem[1][0] == name) or (self.futureRem[1][2] > thresh):
                del self.futureRem[1]
            if (self.futureRem[0][0] == name) or (self.futureRem[0][2] > thresh):
                del self.futureRem[0]
        elif len(self.futureRem) == 1:
            if (self.futureRem[0][0] == name) or (self.futureRem[0][2] > thresh):
                del self.futureRem[0]

        if name in self._CS: #Already in
            newSource = True
            for i in range(len(self._CS[name])):
                if self._CS[name][i][0] == source: #Same source
                    self._sizeCS += (dataSize - self._CS[name][i][2]) #New size 
                    self._CS[name][i][1] = sourceLoc
                    self._CS[name][i][2] = dataSize
                    self._CS[name][i][3] = data
                    self._CS[name][i][4] = genTime
                    self._CS[name][i][5] = thresh
                    newSource = False
            if newSource == False: return 0
        if (self._sizeCS + dataSize) > self._maxSize: #Cache size will exceed
            if dataSize > self._maxSize: return -1 #Object larger than cache
            self.cleanUpCache(dataSize)
        if name in self._CS: #Already in & different source
            self._CS[name].append([source, sourceLoc, dataSize, data, genTime, thresh])
        else: #[source node, data size, data, generation time, counter for LFU/LRU]
            self._CS[name] = [[source, sourceLoc, dataSize, data, genTime, thresh]]
        self._sizeCS += dataSize #Increase CS size
        return 0


    def get(self, name, validTime, time):
        '''
        Get from content store.
        @param name: Content name without timeout
        @param validTime: Content should be fresh/new than this time
        @param time: Current time
        @return: [source, data size, data, genTime, counter for LFU/LRU] if in 
        cache, [] else  
        '''
        self.numCSChecks += 1
        results = []
        if name not in self._CS: return results #Not in CS
        if self.policy == 'LFU' or self.policy == 'LRU':
            #update entries to be removed as they now become fresh content
            if len(self.futureRem) == 3:
                if self.futureRem[2][0] == name: del self.futureRem[2]
                if self.futureRem[1][0] == name: del self.futureRem[1]
                if self.futureRem[0][0] == name: del self.futureRem[0]
            if len(self.futureRem) == 2:
                if self.futureRem[1][0] == name: del self.futureRem[1]
                if self.futureRem[0][0] == name: del self.futureRem[0]             
            elif len(self.futureRem) == 1:
                if self.futureRem[0][0] == name: del self.futureRem[0]                

        for i in range(len(self._CS[name])):
            if self._CS[name][i][4] >= validTime: 
                results.append(self._CS[name][i])
                if self.policy == 'LFU': self._CS[name][i][5] += 1
                if self.policy == 'LRU': self._CS[name][i][5] = time 
        if results: self.numCSHits += 1
        return results #return data
        
        
    def cleanUpCache(self, dataSize):
        '''
        Clean up cache according to given policy
        @param dataSize: Size of new data
        '''
        for i in range(len(self.futureRem)) : #Remove any entries found last time
            self._sizeCS -= self._CS[self.futureRem[i][0]][self._CS\
                    [self.futureRem[i][0]].index(self.futureRem[i][1])][2]
            del self._CS[self.futureRem[i][0]][self._CS\
                        [self.futureRem[i][0]].index(self.futureRem[i][1])]
            if len(self._CS[self.futureRem[i][0]]) == 0: 
                del self._CS[self.futureRem[i][0]] 
            if (self._sizeCS + dataSize) <= self._maxSize:
                self.futureRem = self.futureRem[i + 1:] 
                return
        self.futureRem = []
        if self.policy == 'oldest': #Remove oldest cache entry
            while True: #Continue to remove until required capacity
                oldest1 = 999999 #Track multiple entries to speed up
                oldest2 = 999999
                oldest3 = 999999
                oldest4 = 999999
                idxI1 = -1
                idxI2 = -1
                idxI3 = -1
                idxI4 = -1
                idxJ1 = -1
                idxJ2 = -1
                idxJ3 = -1
                idxJ4 = -1
                for i in self._CS:
                    for j in range(len(self._CS[i])):
                        if oldest1 > self._CS[i][j][4]: #Pick oldest entry
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3
                            oldest3 = oldest2
                            idxI3 = idxI2
                            idxJ3 = idxJ2
                            oldest2 = oldest1                            
                            idxI2 = idxI1
                            idxJ2 = idxJ1
                            oldest1 = self._CS[i][j][4]
                            idxI1 = i
                            idxJ1 = self._CS[i][j]
                            continue
                        if oldest2 > self._CS[i][j][4]: #Pick oldest entry
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3                            
                            oldest3 = oldest2
                            idxI3 = idxI2
                            idxJ3 = idxJ2
                            oldest2 = self._CS[i][j][4]                            
                            idxI2 = i
                            idxJ2 = self._CS[i][j]
                            continue
                        if oldest3 > self._CS[i][j][4]: #Pick oldest entry
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3                            
                            oldest3 = self._CS[i][j][4]
                            idxI3 = i
                            idxJ3 = self._CS[i][j]
                            continue
                        if oldest4 > self._CS[i][j][4]: #Pick oldest entry
                            oldest4 = self._CS[i][j][4]
                            idxI4 = i
                            idxJ4 = self._CS[i][j]
                self._sizeCS -= self._CS[idxI1][self._CS[idxI1].index(idxJ1)][2]
                del self._CS[idxI1][self._CS[idxI1].index(idxJ1)] #oldest entry
                if len(self._CS[idxI1]) == 0: del self._CS[idxI1] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    #track for next time
                    if idxI2 >= 0: self.futureRem.append([idxI2, idxJ2, oldest2])
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, oldest3]) 
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4])
                    break #enough                
                self._sizeCS -= self._CS[idxI2][self._CS[idxI2].index(idxJ2)][2]
                del self._CS[idxI2][self._CS[idxI2].index(idxJ2)]
                if len(self._CS[idxI2]) == 0: del self._CS[idxI2] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, oldest3])
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4]) 
                    break #enough
                self._sizeCS -= self._CS[idxI3][self._CS[idxI3].index(idxJ3)][2]
                del self._CS[idxI3][self._CS[idxI3].index(idxJ3)]
                if len(self._CS[idxI3]) == 0: del self._CS[idxI3] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4]) 
                    break #enough
                self._sizeCS -= self._CS[idxI4][self._CS[idxI4].index(idxJ4)][2]
                del self._CS[idxI4][self._CS[idxI4].index(idxJ4)]
                if len(self._CS[idxI4]) == 0: del self._CS[idxI4] 
                if (self._sizeCS + dataSize) <= self._maxSize: break #enough
        elif self.policy == 'LFU':
            while True: #Continue to remove until required capacity
                freq1 = 999999 #Track multiple entries to speed up
                freq2 = 999999
                freq3 = 999999
                freq4 = 999999
                idxI1 = -1
                idxI2 = -1
                idxI3 = -1
                idxI4 = -1
                idxJ1 = -1
                idxJ2 = -1
                idxJ3 = -1
                idxJ4 = -1
                for i in self._CS:
                    for j in range(len(self._CS[i])):
                        if freq1 > self._CS[i][j][5]: #Entry with lowest freq
                            freq4 = freq3
                            idxI4 = idxI3
                            idxJ4 = idxJ3
                            freq3 = freq2
                            idxI3 = idxI2
                            idxJ3 = idxJ2
                            freq2 = freq1
                            idxI2 = idxI1
                            idxJ2 = idxJ1                            
                            freq1 = self._CS[i][j][5]
                            idxI1 = i
                            idxJ1 = self._CS[i][j]
                            continue
                        if freq2 > self._CS[i][j][5]: #Entry with lowest freq
                            freq4 = freq3
                            idxI4 = idxI3
                            idxJ4 = idxJ3
                            freq3 = freq2
                            idxI3 = idxI2
                            idxJ3 = idxJ2                            
                            freq2 = self._CS[i][j][5]
                            idxI2 = i
                            idxJ2 = self._CS[i][j]
                            continue
                        if freq3 > self._CS[i][j][5]: #Entry with lowest freq
                            freq4 = freq3
                            idxI4 = idxI3
                            idxJ4 = idxJ3                            
                            freq3 = self._CS[i][j][5]
                            idxI3 = i
                            idxJ3 = self._CS[i][j]
                            continue
                        if freq4 > self._CS[i][j][5]: #Entry with lowest freq
                            freq4 = self._CS[i][j][5]
                            idxI4 = i
                            idxJ4 = self._CS[i][j]                                                                          
                self._sizeCS -= self._CS[idxI1][self._CS[idxI1].index(idxJ1)][2]
                del self._CS[idxI1][self._CS[idxI1].index(idxJ1)] #oldest entry
                if len(self._CS[idxI1]) == 0: del self._CS[idxI1]
                if (self._sizeCS + dataSize) <= self._maxSize:
                    #track for next time
                    if idxI2 >= 0: self.futureRem.append([idxI2, idxJ2, freq2])
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, freq3]) 
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, freq4])
                    break #enough                
                self._sizeCS -= self._CS[idxI2][self._CS[idxI2].index(idxJ2)][2]
                del self._CS[idxI2][self._CS[idxI2].index(idxJ2)] #remove oldest
                if len(self._CS[idxI2]) == 0: del self._CS[idxI2]
                if (self._sizeCS + dataSize) <= self._maxSize:                
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, freq3]) 
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, freq4])
                    break #enough                
                self._sizeCS -= self._CS[idxI3][self._CS[idxI3].index(idxJ3)][2]
                del self._CS[idxI3][self._CS[idxI3].index(idxJ3)] #remove oldest
                if len(self._CS[idxI3]) == 0: del self._CS[idxI3]
                if (self._sizeCS + dataSize) <= self._maxSize:
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, freq4])
                    break #enough                                
                self._sizeCS -= self._CS[idxI4][self._CS[idxI4].index(idxJ4)][2]
                del self._CS[idxI4][self._CS[idxI4].index(idxJ4)] #remove oldest
                if len(self._CS[idxI4]) == 0: del self._CS[idxI4]
                if (self._sizeCS + dataSize) <= self._maxSize: break #enough                
        elif self.policy == 'LRU':
            while True: #Continue to remove until required capacity
                oldest1 = 999999
                oldest2 = 999999
                oldest3 = 999999                
                oldest4 = 999999
                idxI1 = -1
                idxI2 = -1
                idxI3 = -1
                idxI4 = -1                
                idxJ1 = -1
                idxJ2 = -1
                idxJ3 = -1
                idxJ4 = -1                
                for i in self._CS:
                    for j in range(len(self._CS[i])):
                        if oldest1 > self._CS[i][j][5]: #Entry with lowest time
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3
                            oldest3 = oldest2
                            idxI3 = idxI2
                            idxJ3 = idxJ2
                            oldest2 = oldest1
                            idxI2 = idxI1
                            idxJ2 = idxJ1                            
                            oldest1 = self._CS[i][j][5]
                            idxI1 = i
                            idxJ1 = self._CS[i][j]
                            continue
                        if oldest2 > self._CS[i][j][5]:
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3
                            oldest3 = oldest2
                            idxI3 = idxI2
                            idxJ3 = idxJ2                            
                            oldest2 = self._CS[i][j][5]                            
                            idxI2 = i
                            idxJ2 = self._CS[i][j]
                            continue
                        if oldest3 > self._CS[i][j][5]:
                            oldest4 = oldest3
                            idxI4 = idxI3
                            idxJ4 = idxJ3                            
                            oldest3 = self._CS[i][j][5]
                            idxI3 = i
                            idxJ3 = self._CS[i][j]
                            continue
                        if oldest4 > self._CS[i][j][5]:
                            oldest4 = self._CS[i][j][5]
                            idxI4 = i
                            idxJ4 = self._CS[i][j]               
                self._sizeCS -= self._CS[idxI1][self._CS[idxI1].index(idxJ1)][2]
                del self._CS[idxI1][self._CS[idxI1].index(idxJ1)] #oldest entry
                if len(self._CS[idxI1]) == 0: del self._CS[idxI1] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    #track for next time
                    if idxI2 >= 0: self.futureRem.append([idxI2, idxJ2, oldest2])
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, oldest3]) 
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4])
                    break #enough                
                self._sizeCS -= self._CS[idxI2][self._CS[idxI2].index(idxJ2)][2]
                del self._CS[idxI2][self._CS[idxI2].index(idxJ2)] #remove oldest
                if len(self._CS[idxI2]) == 0: del self._CS[idxI2] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    if idxI3 >= 0: self.futureRem.append([idxI3, idxJ3, oldest3]) 
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4])
                    break #enough                
                self._sizeCS -= self._CS[idxI3][self._CS[idxI3].index(idxJ3)][2]
                del self._CS[idxI3][self._CS[idxI3].index(idxJ3)] #remove oldest
                if len(self._CS[idxI3]) == 0: del self._CS[idxI3] 
                if (self._sizeCS + dataSize) <= self._maxSize:
                    if idxI4 >= 0: self.futureRem.append([idxI4, idxJ4, oldest4])
                    break #enough                
                self._sizeCS -= self._CS[idxI4][self._CS[idxI4].index(idxJ4)][2]
                del self._CS[idxI4][self._CS[idxI4].index(idxJ4)] #remove oldest
                if len(self._CS[idxI4]) == 0: del self._CS[idxI4] 
                if (self._sizeCS + dataSize) <= self._maxSize: break #enough                


    def getStat(self):
        '''
        Get statistics
        '''
        return [self.numCSChecks, self.numCSHits]
