Jamba C++ API  5.0.0
CircularBuffer.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2018-2019 pongasoft
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy of
6  * the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations under
14  * the License.
15  *
16  * @author Yan Pujante
17  */
18 #ifndef __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__
19 #define __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__
20 
21 #include <cassert>
22 #include <memory>
23 
24 namespace pongasoft {
25 namespace Utils {
26 namespace Collection {
27 
28 template<typename T>
30 {
31 public:
32  explicit CircularBuffer(int iSize) : fSize(iSize), fStart(0)
33  {
34  assert(fSize > 0);
35 
36  fBuf = new T[iSize];
37  };
38 
39  CircularBuffer(CircularBuffer const& iOther) : fSize(iOther.fSize), fStart(iOther.fStart)
40  {
41  fBuf = new T[fSize];
42  memcpy(fBuf, iOther.fBuf, fSize * sizeof(T));
43  }
44 
46  {
47  delete[] fBuf;
48  }
49 
50  // handle negative offsets as well
51  inline int getSize() const
52  {
53  return fSize;
54  }
55 
56  inline T getAt(int offset) const
57  {
58  return fBuf[adjustIndexFromOffset(offset)];
59  }
60 
61  inline void setAt(int offset, T e)
62  {
63  fBuf[adjustIndexFromOffset(offset)] = e;
64  };
65 
66  inline void incrementHead()
67  {
68  fStart = adjustIndex(fStart + 1);
69  }
70 
71  inline void push(T e)
72  {
73  setAt(0, e);
74  incrementHead();
75  }
76 
77  inline void init(T initValue)
78  {
79  for(int i = 0; i < fSize; ++i)
80  {
81  fBuf[i] = initValue;
82  }
83  }
84 
85  inline void copyToBuffer(int startOffset, T *oBuffer, int iSize)
86  {
87  int adjStartOffset = adjustIndexFromOffset(startOffset);
88 
89  if(adjStartOffset + iSize < fSize)
90  {
91  memcpy(oBuffer, &fBuf[adjStartOffset], iSize * sizeof(T));
92  }
93  else
94  {
95  int i = adjStartOffset;
96  for(int k = 0; k < iSize; k++)
97  {
98  oBuffer[k] = fBuf[i];
99  i++;
100  if(i == fSize)
101  i = 0;
102  }
103  }
104  }
105 
106 
129  template<typename U, class BinaryPredicate>
130  inline U fold(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicate &op) const
131  {
132  if(startOffset == endOffsetNotIncluded)
133  return initValue;
134 
135  U resultValue = initValue;
136 
137  int i = adjustIndexFromOffset(startOffset);
138 
139  if(startOffset < endOffsetNotIncluded)
140  {
141  int size = endOffsetNotIncluded - startOffset;
142  while(size > 0)
143  {
144  resultValue = op(resultValue, fBuf[i]);
145  ++i;
146  if(i == fSize)
147  i = 0;
148  size--;
149  }
150  }
151  else
152  {
153  int size = startOffset - endOffsetNotIncluded;
154  while(size > 0)
155  {
156  resultValue = op(resultValue, fBuf[i]);
157  --i;
158  if(i == -1)
159  i = fSize - 1;
160  size--;
161  }
162  }
163 
164  return resultValue;
165  }
166 
170  template<typename U, class BinaryPredicate>
171  inline U fold(int endOffsetNotIncluded, U initValue, BinaryPredicate &op) const
172  {
173  return fold(0, endOffsetNotIncluded, initValue, op);
174  }
175 
179  template<typename U, class BinaryPredicate>
180  inline U fold(U initValue, BinaryPredicate &op) const
181  {
182  return fold(0, fSize, initValue, op);
183  }
184 
191  template<typename U, class BinaryPredicateWithIndex>
192  inline U foldWithIndex(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &op) const
193  {
194  if(startOffset == endOffsetNotIncluded)
195  return initValue;
196 
197  U resultValue = initValue;
198 
199  int i = adjustIndexFromOffset(startOffset);
200  int index = startOffset;
201 
202  if(startOffset < endOffsetNotIncluded)
203  {
204  int size = endOffsetNotIncluded - startOffset;
205  while(size > 0)
206  {
207  resultValue = op(index, resultValue, fBuf[i]);
208  ++i;
209  if(i == fSize)
210  i = 0;
211  size--;
212  index++;
213  }
214  }
215  else
216  {
217  int size = startOffset - endOffsetNotIncluded;
218  while(size > 0)
219  {
220  resultValue = op(index, resultValue, fBuf[i]);
221  --i;
222  if(i == -1)
223  i = fSize - 1;
224  size--;
225  index--;
226  }
227  }
228 
229  return resultValue;
230  }
231 
235  template<typename U, class BinaryPredicateWithIndex>
236  inline U foldWithIndex(int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &op) const
237  {
238  return foldWithIndex(0, endOffsetNotIncluded, initValue, op);
239  }
240 
244  template<typename U, class BinaryPredicateWithIndex>
245  inline U foldWithIndex(U initValue, BinaryPredicateWithIndex &op) const
246  {
247  return foldWithIndex(0, fSize, initValue, op);
248  }
249 
250 private:
251  inline int adjustIndexFromOffset(int offset) const
252  {
253  if(offset == 0)
254  return fStart;
255 
256  return adjustIndex(fStart + offset);
257  }
258 
259  inline int adjustIndex(int index) const
260  {
261  // shortcut since this is a frequent use case
262  if(index == fSize)
263  return 0;
264 
265  while(index < 0)
266  index += fSize;
267 
268  while(index >= fSize)
269  index -= fSize;
270 
271  return index;
272  }
273 
274  int fSize;
275  T *fBuf;
276  int fStart;
277 };
278 
279 }
280 }
281 }
282 
283 #endif // __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__
CircularBuffer(int iSize)
Definition: CircularBuffer.h:32
void copyToBuffer(int startOffset, T *oBuffer, int iSize)
Definition: CircularBuffer.h:85
U foldWithIndex(int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &op) const
Shortcut with startOffset = 0.
Definition: CircularBuffer.h:236
U fold(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicate &op) const
"standard" implementation of the fold algorithm starting at startOffset and ending at endOffsetNotInc...
Definition: CircularBuffer.h:130
U foldWithIndex(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &op) const
Similar to fold but BinaryPredicateWithIndex is also provided the index (starting at startOffset)
Definition: CircularBuffer.h:192
Definition: Clock.h:22
void setAt(int offset, T e)
Definition: CircularBuffer.h:61
void init(T initValue)
Definition: CircularBuffer.h:77
~CircularBuffer()
Definition: CircularBuffer.h:45
U fold(int endOffsetNotIncluded, U initValue, BinaryPredicate &op) const
Shortcut with startOffset 0.
Definition: CircularBuffer.h:171
int adjustIndexFromOffset(int offset) const
Definition: CircularBuffer.h:251
U fold(U initValue, BinaryPredicate &op) const
Shortcut for entire buffer (starting at startOffset 0)
Definition: CircularBuffer.h:180
void incrementHead()
Definition: CircularBuffer.h:66
void push(T e)
Definition: CircularBuffer.h:71
Definition: CircularBuffer.h:29
U foldWithIndex(U initValue, BinaryPredicateWithIndex &op) const
Shortcut for entire buffer (starting at startOffset 0)
Definition: CircularBuffer.h:245
int getSize() const
Definition: CircularBuffer.h:51
int fStart
Definition: CircularBuffer.h:276
T * fBuf
Definition: CircularBuffer.h:275
T getAt(int offset) const
Definition: CircularBuffer.h:56
int adjustIndex(int index) const
Definition: CircularBuffer.h:259
CircularBuffer(CircularBuffer const &iOther)
Definition: CircularBuffer.h:39
int fSize
Definition: CircularBuffer.h:274