developer.intra2net.com Git - pyi2ncommon/blob - src/buffers.py

   1 # The software in this package is distributed under the GNU General
   2 # Public License version 2 (with a special exception described below).
   3 #
   4 # A copy of GNU General Public License (GPL) is included in this distribution,
   5 # in the file COPYING.GPL.
   6 #
   7 # As a special exception, if other files instantiate templates or use macros
   8 # or inline functions from this file, or you compile this file and link it
   9 # with other works to produce a work based on this file, this file
  10 # does not by itself cause the resulting work to be covered
  11 # by the GNU General Public License.
  12 #
  13 # However the source code for this file must still be made available
  14 # in accordance with section (3) of the GNU General Public License.
  15 #
  16 # This exception does not invalidate any other reasons why a work based
  17 # on this file might be covered by the GNU General Public License.
  18 #
  19 # Copyright (c) 2016-2018 Intra2net AG <info@intra2net.com>
  20
  21 """
  22 buffers.py: buffers of various shapes, sizes and functionalities
  23
  24 Featuring::
  25     - CircularBuffer
  26     - LogarithmicBuffer: saves only last N items, and after that less and less so
  27                          very few old items are kept
  28 """
  29
  30
  31 class CircularBuffer:
  32     """ circular buffer for data; saves last N sets
  33
  34     can return or run func on them afterwards in correct order
  35
  36     public attributes (please read only!): buffer_size, n_items
  37     """
  38
  39     buffer_size = None
  40     _buffer = None
  41     _buff_idx = None
  42     n_items = None
  43
  44     def __init__(self, size, empty_element=None):
  45         """ initialize with N = size """
  46         if size < 1:
  47             raise ValueError('size must be positive!')
  48         self.buffer_size = size
  49         self._buffer = [empty_element for _ in range(size)]
  50         self._buff_idx = 0
  51         self.n_items = 0
  52
  53     def add(self, new_item):
  54         """ add a new item to buffer -- might replace the oldest item """
  55         oldest_item = self._buffer[self._buff_idx]
  56         self._buffer[self._buff_idx] = new_item
  57         self._buff_idx = (self._buff_idx + 1) % self.buffer_size
  58         self.n_items += 1
  59         return oldest_item
  60
  61     def run_func(self, some_func):
  62         """ run some_func(item) on last saved items in correct order """
  63         if self.n_items >= self.buffer_size:
  64             for idx in range(self._buff_idx, self.buffer_size):
  65                 some_func(self._buffer[idx])
  66
  67         for idx in range(0, self._buff_idx):
  68             some_func(self._buffer[idx])
  69
  70     def get_all(self):
  71         """ return the buffered contents in correct order """
  72         result = []
  73         if self.n_items >= self.buffer_size:
  74             for idx in range(self._buff_idx, self.buffer_size):
  75                 result.append(self._buffer[idx])
  76
  77         for idx in range(0, self._buff_idx):
  78             result.append(self._buffer[idx])
  79
  80         return result
  81
  82
  83 class LogarithmicBuffer:
  84     """ saves only last N items, and after that less and less old data
  85
  86     --> grows only logarithmically in size
  87
  88     has a data_new which is a CircularBuffer for the newest N items
  89     data_old is a list of items with ages approx 2, 4, 8, 16, ... counts
  90
  91     Could easily extend to other bases than 2 to make even scarcer
  92     """
  93
  94     def __init__(self, n_new):
  95         self.n_new = n_new
  96         if n_new < 0:
  97             raise ValueError('n_new must be non-negative!')
  98         if n_new == 0:
  99             self._data_new = None
 100         else:
 101             self._data_new = CircularBuffer(n_new)
 102         self._count = 0
 103         self._data_old = []
 104
 105     def add(self, new_item):
 106         """ add a new item to buffer """
 107         if self._data_new:
 108             newest_old_item = self._data_new.add(new_item)
 109             age = self._count - self.n_new
 110         else:
 111             newest_old_item = new_item
 112             age = self._count
 113
 114         if age >= 0:
 115             self._save_old(newest_old_item, age, 0)
 116         self._count += 1
 117
 118     def _save_old(self, item, age, index):
 119         """ internal helper for saving (or not) items in data_old """
 120
 121         # determine whether we throw it away or actually save it
 122         if age % 2 ** index != 0:
 123             return
 124
 125         # we save it. But before check if we need to extend data_old or
 126         # save the item we would overwrite
 127         if len(self._data_old) <= index:
 128             self._data_old.append(item)
 129         else:
 130             self._save_old(self._data_old[index], age, index + 1)
 131             self._data_old[index] = item
 132
 133     def get_all(self):
 134         """ get all buffer contents in correct order """
 135         if self._data_new:
 136             return self._data_old[::-1] + self._data_new.get_all()
 137         else:
 138             return self._data_old[::-1]
 139
 140     def get_size(self):
 141         """ returns current number of saved elements in buffer
 142
 143         size is O(log n) where n = number of added items
 144
 145         more precisely: size is n_new + floor(log_2(m-1))+1
 146                  where: m = n-n_new > 1
 147                         (m=0 --> size=n_new;   m=1 --> size=n_new+1)
 148         """
 149         return self.n_new + len(self._data_old)