Commit | Line | Data |
---|---|---|
e102ab9b CH |
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. | |
f365f614 CH |
18 | # |
19 | # Copyright (c) 2016-2018 Intra2net AG <info@intra2net.com> | |
e102ab9b CH |
20 | |
21 | """ | |
e1ebb38e CH |
22 | buffers.py: buffers of various shapes, sizes and functionalities |
23 | ||
24 | Featuring:: | |
7628bc48 CH |
25 | - CircularBuffer |
26 | - LogarithmicBuffer: saves only last N items, and after that less and less so | |
27 | very few old items are kept | |
e102ab9b CH |
28 | """ |
29 | ||
7628bc48 | 30 | |
e1ebb38e | 31 | class CircularBuffer: |
e14eed4a | 32 | """ circular buffer for data; saves last N sets |
0e5309f0 | 33 | |
e14eed4a | 34 | can return or run func on them afterwards in correct order |
e102ab9b | 35 | |
e14eed4a | 36 | public attributes (please read only!): buffer_size, n_items |
e102ab9b CH |
37 | """ |
38 | ||
39 | buffer_size = None | |
40 | _buffer = None | |
41 | _buff_idx = None | |
e14eed4a | 42 | n_items = None |
e102ab9b | 43 | |
e14eed4a | 44 | def __init__(self, size, empty_element=None): |
e102ab9b | 45 | """ initialize with N = size """ |
e14eed4a CH |
46 | if size < 1: |
47 | raise ValueError('size must be positive!') | |
e102ab9b | 48 | self.buffer_size = size |
7628bc48 | 49 | self._buffer = [empty_element for _ in range(size)] |
e102ab9b | 50 | self._buff_idx = 0 |
e14eed4a | 51 | self.n_items = 0 |
e102ab9b | 52 | |
e14eed4a CH |
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 | |
e102ab9b | 57 | self._buff_idx = (self._buff_idx + 1) % self.buffer_size |
e14eed4a CH |
58 | self.n_items += 1 |
59 | return oldest_item | |
e102ab9b | 60 | |
e14eed4a CH |
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: | |
e102ab9b | 64 | for idx in range(self._buff_idx, self.buffer_size): |
e14eed4a | 65 | some_func(self._buffer[idx]) |
e102ab9b CH |
66 | |
67 | for idx in range(0, self._buff_idx): | |
e14eed4a CH |
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 | |
70b51504 CH |
81 | |
82 | ||
83 | class LogarithmicBuffer: | |
0e5309f0 | 84 | """ saves only last N items, and after that less and less old data |
70b51504 CH |
85 | |
86 | --> grows only logarithmically in size | |
87 | ||
0e5309f0 | 88 | has a data_new which is a CircularBuffer for the newest N items |
70b51504 CH |
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: | |
0e5309f0 | 99 | self._data_new = None |
70b51504 | 100 | else: |
0e5309f0 CH |
101 | self._data_new = CircularBuffer(n_new) |
102 | self._count = 0 | |
103 | self._data_old = [] | |
70b51504 CH |
104 | |
105 | def add(self, new_item): | |
106 | """ add a new item to buffer """ | |
0e5309f0 CH |
107 | if self._data_new: |
108 | newest_old_item = self._data_new.add(new_item) | |
109 | age = self._count - self.n_new | |
70b51504 CH |
110 | else: |
111 | newest_old_item = new_item | |
0e5309f0 | 112 | age = self._count |
70b51504 | 113 | |
0e5309f0 CH |
114 | if age >= 0: |
115 | self._save_old(newest_old_item, age, 0) | |
116 | self._count += 1 | |
70b51504 | 117 | |
0e5309f0 | 118 | def _save_old(self, item, age, index): |
70b51504 CH |
119 | """ internal helper for saving (or not) items in data_old """ |
120 | ||
121 | # determine whether we throw it away or actually save it | |
7628bc48 | 122 | if age % 2 ** index != 0: |
70b51504 CH |
123 | return |
124 | ||
0e5309f0 CH |
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) | |
70b51504 | 129 | else: |
7628bc48 | 130 | self._save_old(self._data_old[index], age, index + 1) |
0e5309f0 | 131 | self._data_old[index] = item |
70b51504 CH |
132 | |
133 | def get_all(self): | |
134 | """ get all buffer contents in correct order """ | |
0e5309f0 CH |
135 | if self._data_new: |
136 | return self._data_old[::-1] + self._data_new.get_all() | |
70b51504 | 137 | else: |
0e5309f0 CH |
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) |