CFLT onsite prep -- windowed time map

window_key_v2.py

"""
windowed k, v map
"""
import time

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, default_timeout):
        self.nodemap = dict()
        self.head = Node()
        self.tail = Node()
        self.head.next, self.tail.prev = self.tail, self.head
        self.sum = 0
        # in seconds
        self.timeout = default_timeout
    
    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):
        # 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(time.time(), value, key)
        self.insert(newnode)
        self.nodemap[key] = newnode
        print (self.nodemap)

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

    def get_average(self):
        # remove expired stuff, worst case O(n)
        start = time.time() - 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)