#
# data stored in two lists: self.back[:] and self[:]
#
#
import random

from common import DictList

#to do: Name peerCache is not appropriate.need change to randPeerCache
class peerCache(list):
    def __init__(self,  cacheMaxSize= 10000):
      #  self.back = init_cache
        self.cacheSize =  0 #len(init_cache)
        if cacheMaxSize < self.cacheSize:
            cacheMaxSize = self.cacheSize
        self.cacheMaxSize = cacheMaxSize
        self.order = 'increase'
        self.back = []

    def _enqueue(self, elt):
        self.back.append(elt)
        
    def _dequeue(self):
        if self:
            return self.pop()
        else:
            self.back.reverse()
            self[:] = self.back
            self.back = []
            return self.pop()

    def _shift(self):
        """internal function
        copy records in back to self
        """
        self.back.reverse()
        self[:] = self.back + self[:]
        self.back = []

    def _print(self):
        """for debug purpose"""
        print 'self', self
        print 'back', self.back
        
    def add(self,obj):
        """insert an obj (in our case:Dict) into list
        the last record in list may be removed if the cacheSize
        is out of cacheMaxSize
        """
        if self.cacheSize < self.cacheMaxSize:
            self._enqueue(obj)
            self.cacheSize += 1
        else:
            self._enqueue(obj)
            self._dequeue()
        return self.cacheSize

    def remove(self):
        """first came first out"""
        if self.cacheSize > 0:
            self._dequeue()
            self.cacheSize -= 1
            return self.cacheSize
        else:
            return 0
    def removeN(self,num):
        """first num came first num out"""
        for i in range(num):
           size =  self.remove()
        return size

    def getAll(self):
        """get all record
        remember this is get a copy not ref
        """
        a = self.back[:]
        a.reverse()
        a = a[:] + self[:]
#        for b in a[:]:
#            print b
        return a

    def printAll(self):
        """print on sceen"""
        a = self.back[:]
        a.reverse()
        for b in a[:]:
            print b
        for b in self[:]:
            print b

    def getARecord(self,index):
        """get a record implemented by Dict"""
        index = int(index)
        if (index >= self.cacheSize)| (index < 0):
            return None
        popSize = len(self)
       #print 'popsize', popSize , 'index', index
        if index < popSize:
            return self[popSize - index - 1]
        else:
            return self.back[index - popSize]

    def getRecords(self,indexs):
        """get a set of records"""
        self._shift()
        a=[]
        for i in indexs:
            a.append(self[i])
        return a

    def getLength(self):
        return self.cacheSize

    def getMaxCacheSize(self):
        return self.cacheMaxSize

    def getMaxSize(self):
        return self.cacheMaxSize

    def getCurSize(self):
        return self.cacheSize

    def getPeer(self,index):
        return self.getARecord(index)

    def getPeers(self,indexs):
        return self.getRecords(indexs)

    def getRandomPeer(self):
        size = self.cacheSize
        index = random.randint(0, size-1) # random int 0<=  <= size-1
        return self.getPeer(index)
        
    def getRandomPeers(self,numPeers):
        size = self.cacheSize
        if numPeers > size:
            numPeers = size
        index = []
        for i in range(numPeers):
            a = random.choice(range(size)) # random int 0<=  <= size-1
            index.append(a)
        return self.getPeers(index)
###################################################################
# randomly sample a peer based on ranking
###################################################################
    def getSampledPeer(self,ranking):
        peers  = self.getAll()  # should make a copy
        rankAccum = 0
        for peer in peers:
            rankAccum = rankAccum +  peer[ranking]
            peer[ranking]=rankAccum
        randVar = random.random()*rankAccum
        prePeerRank = 0
        for peer in peers:
            if prePeerRank < randVar and peer[ranking] >= randVar:
                break
        return peer

   
    
###################################################################################
# increase: higher value is in a higher index. index=0 is the smallest one: default
# decrease: low value is in a higher index. index = 0  is the largest one
##################################################################################
    def sortedby(self,key, method='overwrite',order ='increase'):
        #orignial sort algrithm
        if False:
            self.order = order
            self.key = key
            print 'current key', self.key 
            self._shift()
            if method == 'overwrite':
                peers = self
            else:
                peers = self[:]
            peers.sort(self._compare)
            return peers
        else:
            #new one
            self._shift()
            sort = Sorter()
            sort(self,key)
            return self

    def find(self,key,value):
        self._shift()
        result =[-1,'']
        try:
            for a in range(self.cacheSize): #print a, self[a]
                a = int(a)
            #    print 'compare:', self[a][key], 'to', value
                if self[a][key]== value:
                    result[0]= a
                    result[1]= self[a]
                    break
        except:
            print 'key:', key, type(key), 'index',a,'cacheSize', self.cacheSize,'lists:',self[a], self[a][key]
        #print result
        return result
    
    def _compare(self,x,y):
        print type(self)
        print x, y
        if self.key  and x.has_key(self.key) and y.has_key(self.key):
            #print type(x),type(self.index),y[self.index]
            if self.order == 'increase':
               # print 'increase'
                return cmp(x[self.key],y[self.key])
            else :
               # print 'decrease'
                return cmp(y[self.key],x[self.key])
        else:
            print 'need define index key first!', x, y

class Sorter:
    def _helper(self, data, aux, inplace):
        aux.sort( )
        result = [data[i] for junk, i in aux]
        if inplace: data[:] = result
        return result

    def byItem(self, data, itemindex=None, inplace=1):
        if itemindex is None:
            if inplace:
                data.sort( )
                result = data
            else:
                result = data[:]
                result.sort( )
                return result
        else:
            aux = [(data[i][itemindex], i) for i in range(len(data))]
            return self._helper(data, aux, inplace)
            # a couple of handy synonyms
    sort = byItem
    __call__ = byItem

    def byAttribute(self, data, attributename, inplace=1):
        aux = [(getattr(data[i],attributename),i) for i in range(len(data))]
        return self._helper(data, aux, inplace)
            
def testPeerCache():
    a = peerCache(cacheMaxSize = 5)
    print a.add({'ip':'1.1.1.1','peer_id':2})
    print a.add({'ip':'1.1.1.2','peer_id':8})
    print a.add({'ip':'1.1.1.3','peer_id':7})
    print a.add({'ip':'1.1.1.4','peer_id':5})
    print a.add({'ip':'1.1.1.5'})
    print a.add({'ip':'1.1.1.6','peer_id':3})
    print a.add({'ip':'1.1.1.7','peer_id':4})
    print 'all the data'
    a._print()
    a.remove()
    print a.add({'ip':'1.1.1.9','peer_id':13})
    print a.add({'ip':'1.1.1.8','peer_id':12})
    print 'remove one add two, all the data' 
    a._print()
    print 'sorted by ip'
    #a.sortedby('ip')
    a._shift()
    sort = Sorter()
    sort(a,'ip')
    print 'we are done the sort'
    a.printAll()
    print 'sorted by peerid'
    a.sortedby('peer_id')
    a.printAll() 
    result = a.find('peer_id',6)
    print 'find peerid 6 at', result[0], result[1]
    a.remove()
    a.printAll()
    print a.getPeer(a.cacheSize-1)
    return 

if '__main__'== __name__:
    testPeerCache()