From 70b515048c7bda564bc689439ef10d7d31c36d1d Mon Sep 17 00:00:00 2001
From: Christian Herdtweck <christian.herdtweck@intra2net.com>
Date: Tue, 12 Jan 2016 13:25:48 +0100
Subject: [PATCH] implemented LogarithmicBuffer

---
 buffers.py |   63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 61 insertions(+), 2 deletions(-)

diff --git a/buffers.py b/buffers.py
index bda7d80..b586820 100644
--- a/buffers.py
+++ b/buffers.py
@@ -22,8 +22,8 @@ buffers.py: buffers of various shapes, sizes and functionalities
 Featuring::
 
 * CircularBuffer
-* LogBuffer (saves one of the 2 last items, one of the 4 last items, ..
-             of the 8 last, 16 last, ...
+* LogarithmicBuffer: saves only last N items, and after that less and less so
+*                    very few old items are kept
 
 .. codeauthor:: Christian Herdtweck, christian.herdtweck@intra2net.com
 """
@@ -78,3 +78,62 @@ class CircularBuffer:
             result.append(self._buffer[idx])
 
         return result
+
+
+class LogarithmicBuffer:
+    """ saves only last N items, and after that less and less; old stuff is del
+
+    --> grows only logarithmically in size
+
+    has a data_new which is a CircularBuffer for the last N items
+    data_old is a list of items with ages approx 2, 4, 8, 16, ... counts
+
+    Could easily extend to other bases than 2 to make even scarcer
+    """
+
+    def __init__(self, n_new):
+        self.n_new = n_new
+        if n_new < 0:
+            raise ValueError('n_new must be non-negative!')
+        if n_new == 0:
+            self.data_new = None
+        else:
+            self.data_new = CircularBuffer(n_new)
+        self.count = 0
+        self.data_old = []
+
+    def add(self, new_item):
+        """ add a new item to buffer """
+        if self.data_new:
+            newest_old_item = data_new.add(new_item)
+            age = count - n_new
+        else:
+            newest_old_item = new_item
+            age = count
+
+        _save_old(newest_old_item, age, 0)
+        self.count += 1
+
+    def _save_old(item, age, index):
+        """ internal helper for saving (or not) items in data_old """
+
+        # determine whether we throw it away or actually save it
+        if age % 2**index != 0:
+            return
+
+        # we will save it. But before overwriting the item that was there,
+        # we determine whether that will be saved at next index
+        _save_old(data_old[index], age, index+1)
+
+        # now do save at index, possibly extending data_old
+        if len(data_old) < index:
+            data_old.append(item)
+        else:
+            data_old[index] = item
+
+    def get_all(self):
+        """ get all buffer contents in correct order """
+        if self.data_new:
+            return self.data_old[::-1] + self.data_new.get_all()
+        else:
+            return self.data_old[::-1]
-- 
1.7.1