Increase version to 1.7.4

[pyi2ncommon] / src / buffers.py

# The software in this package is distributed under the GNU General
# Public License version 2 (with a special exception described below).
#
# A copy of GNU General Public License (GPL) is included in this distribution,
# in the file COPYING.GPL.
#
# As a special exception, if other files instantiate templates or use macros
# or inline functions from this file, or you compile this file and link it
# with other works to produce a work based on this file, this file
# does not by itself cause the resulting work to be covered
# by the GNU General Public License.
#
# However the source code for this file must still be made available
# in accordance with section (3) of the GNU General Public License.
#
# This exception does not invalidate any other reasons why a work based
# on this file might be covered by the GNU General Public License.
#
# Copyright (c) 2016-2018 Intra2net AG <info@intra2net.com>

"""
buffers.py: buffers of various shapes, sizes and functionalities

Featuring::
    - CircularBuffer
    - LogarithmicBuffer: saves only last N items, and after that less and less so
                         very few old items are kept
"""


class CircularBuffer:
    """ circular buffer for data; saves last N sets

    can return or run func on them afterwards in correct order

    public attributes (please read only!): buffer_size, n_items
    """

    buffer_size = None
    _buffer = None
    _buff_idx = None
    n_items = None

    def __init__(self, size, empty_element=None):
        """ initialize with N = size """
        if size < 1:
            raise ValueError('size must be positive!')
        self.buffer_size = size
        self._buffer = [empty_element for _ in range(size)]
        self._buff_idx = 0
        self.n_items = 0

    def add(self, new_item):
        """ add a new item to buffer -- might replace the oldest item """
        oldest_item = self._buffer[self._buff_idx]
        self._buffer[self._buff_idx] = new_item
        self._buff_idx = (self._buff_idx + 1) % self.buffer_size
        self.n_items += 1
        return oldest_item

    def run_func(self, some_func):
        """ run some_func(item) on last saved items in correct order """
        if self.n_items >= self.buffer_size:
            for idx in range(self._buff_idx, self.buffer_size):
                some_func(self._buffer[idx])

        for idx in range(0, self._buff_idx):
            some_func(self._buffer[idx])

    def get_all(self):
        """ return the buffered contents in correct order """
        result = []
        if self.n_items >= self.buffer_size:
            for idx in range(self._buff_idx, self.buffer_size):
                result.append(self._buffer[idx])

        for idx in range(0, self._buff_idx):
            result.append(self._buffer[idx])

        return result


class LogarithmicBuffer:
    """ saves only last N items, and after that less and less old data

    --> grows only logarithmically in size

    has a data_new which is a CircularBuffer for the newest 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 = self._data_new.add(new_item)
            age = self._count - self.n_new
        else:
            newest_old_item = new_item
            age = self._count

        if age >= 0:
            self._save_old(newest_old_item, age, 0)
        self._count += 1

    def _save_old(self, 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 save it. But before check if we need to extend data_old or
        # save the item we would overwrite
        if len(self._data_old) <= index:
            self._data_old.append(item)
        else:
            self._save_old(self._data_old[index], age, index + 1)
            self._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]

    def get_size(self):
        """ returns current number of saved elements in buffer

        size is O(log n) where n = number of added items

        more precisely: size is n_new + floor(log_2(m-1))+1
                 where: m = n-n_new > 1
                        (m=0 --> size=n_new;   m=1 --> size=n_new+1)
        """
        return self.n_new + len(self._data_old)