CLFT onsite prep -- window_key_map

window_key_v1.py

"""
windowed k, v map
first version with t for debug
"""
class Node:
    def __init__(self, time=0, val=0, key=0):
        self.time = time 
        self.val = val 
        self.key = key 
        self.next = None
        self.prev = None
    
    def __repr__(self):
        return '(key: {0}, value: {1}, time: {2})'.format(self.key, self.val, self.time)

class WindowedMap:
    def __init__(self):
        self.nodemap = dict()
        self.head = Node()
        self.tail = Node()
        self.head.next, self.tail.prev = self.tail, self.head
        self.sum = 0
        self.timeout = 5
    
    def remove(self, node):
        # remove node from dll
        prev, next = node.prev, node.next
        prev.next, next.prev = next, prev

    def insert(self, node):
        # insert at the end
        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node

    def put(self, key, value, t=0):
        # timestamp = t 
        if key in self.nodemap:
            self.sum -= self.nodemap[key].val
            self.remove(self.nodemap[key])
            self.nodemap.pop(key)
        if key not in self.nodemap:
            self.sum += value
        newnode = Node(t, value, key)
        self.insert(newnode)
        self.nodemap[key] = newnode

    def get(self, key, t=0):
        start = t - self.timeout
        if key not in self.nodemap:
            return -1
        if self.nodemap[key].time < start:
            return -1
        return self.nodemap[key].val

    def get_average(self, t=0):
        # remove expired stuff, worst case O(n)
        start = t - self.timeout
        itr = self.head.next
        while itr != self.tail:
            nextnode = itr.next
            if itr.time < start:
                self.sum -= itr.val
                self.nodemap.pop(itr.key)
                self.remove(itr)
            itr = nextnode
        if len(self.nodemap) == 0:
            return 0
        return self.sum / len(self.nodemap)