CircularBuffer.h

Go to the documentation of this file.

/*
 * Copyright (c) 2018-2019 pongasoft
 *
 * Licensed under the Apache License, Version 2.0 or the MIT license,
 * at your option. You may not use this file except in compliance with
 * one of these licenses. You may obtain copies of the licenses at:
 *
 * https://www.apache.org/licenses/LICENSE-2.0
 * https://opensource.org/licenses/MIT
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 *
 * @author Yan Pujante
 */
#ifndef __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__
#define __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__
 
#include <cassert>
#include <memory>
#include <concepts>
 
namespace pongasoft {
namespace Utils {
namespace Collection {

template<typename Op, typename U, typename T>
concept FoldOp =
  std::invocable<Op, U const&, T const&> &&
  std::same_as<std::invoke_result_t<Op, U const&, T const&>, U>;

template<typename Op, typename U, typename T>
concept FoldOpWithIndex =
  std::invocable<Op, int, U const&, T const&> &&
  std::same_as<std::invoke_result_t<Op, int, U const&, T const&>, U>;
 
template<typename T>
class CircularBuffer
{
public:
  explicit CircularBuffer(int iSize) : fSize(iSize), fStart(0)
  {
    assert(fSize > 0);
 
    fBuf = new T[iSize];
  };
 
  CircularBuffer(CircularBuffer const& iOther) : fSize(iOther.fSize), fStart(iOther.fStart)
  {
    fBuf = new T[fSize];
    memcpy(fBuf, iOther.fBuf, fSize * sizeof(T));
  }
 
  ~CircularBuffer()
  {
    delete[] fBuf;
  }
 
  // handle negative offsets as well
  int getSize() const
  {
    return fSize;
  }
 
  T getAt(int offset) const
  {
    return fBuf[adjustIndexFromOffset(offset)];
  }
 
  void setAt(int offset, T e)
  {
    fBuf[adjustIndexFromOffset(offset)] = e;
  }
 
  void incrementHead()
  {
    fStart = adjustIndex(fStart + 1);
  }
 
  void push(T e)
  {
    setAt(0, e);
    incrementHead();
  }
 
  void init(T initValue)
  {
    for(int i = 0; i < fSize; ++i)
    {
      fBuf[i] = initValue;
    }
  }
 
  void copyToBuffer(int startOffset, T *oBuffer, int iSize)
  {
    int adjStartOffset = adjustIndexFromOffset(startOffset);
 
    if(adjStartOffset + iSize < fSize)
    {
      memcpy(oBuffer, &fBuf[adjStartOffset], iSize * sizeof(T));
    }
    else
    {
      int i = adjStartOffset;
      for(int k = 0; k < iSize; k++)
      {
        oBuffer[k] = fBuf[i];
        i++;
        if(i == fSize)
          i = 0;
      }
    }
  }
 

  template<typename U, FoldOp<U, T> Op>
  U fold(int startOffset, int endOffsetNotIncluded, U initValue, Op &op) const
  {
    if(startOffset == endOffsetNotIncluded)
      return initValue;
 
    U resultValue = initValue;
 
    int i = adjustIndexFromOffset(startOffset);
 
    if(startOffset < endOffsetNotIncluded)
    {
      int size = endOffsetNotIncluded - startOffset;
      while(size > 0)
      {
        resultValue = std::invoke(op, resultValue, fBuf[i]);
        ++i;
        if(i == fSize)
          i = 0;
        size--;
      }
    }
    else
    {
      int size = startOffset - endOffsetNotIncluded;
      while(size > 0)
      {
        resultValue = std::invoke(op, resultValue, fBuf[i]);
        --i;
        if(i == -1)
          i = fSize - 1;
        size--;
      }
    }
 
    return resultValue;
  }

  template<typename U, FoldOp<U, T> Op>
  U fold(int endOffsetNotIncluded, U initValue, Op &op) const
  {
    return fold(0, endOffsetNotIncluded, initValue, op);
  }

  template<typename U, FoldOp<U, T> Op>
  U fold(U initValue, Op &op) const
  {
    return fold(0, fSize, initValue, op);
  }

  template<typename U, FoldOpWithIndex<U, T> Op>
  U foldWithIndex(int startOffset, int endOffsetNotIncluded, U initValue, Op &op) const
  {
    if(startOffset == endOffsetNotIncluded)
      return initValue;
 
    U resultValue = initValue;
 
    int i = adjustIndexFromOffset(startOffset);
    int index = startOffset;
 
    if(startOffset < endOffsetNotIncluded)
    {
      int size = endOffsetNotIncluded - startOffset;
      while(size > 0)
      {
        resultValue = std::invoke(op, index, resultValue, fBuf[i]);
        ++i;
        if(i == fSize)
          i = 0;
        size--;
        index++;
      }
    }
    else
    {
      int size = startOffset - endOffsetNotIncluded;
      while(size > 0)
      {
        resultValue = std::invoke(op, index, resultValue, fBuf[i]);
        --i;
        if(i == -1)
          i = fSize - 1;
        size--;
        index--;
      }
    }
 
    return resultValue;
  }

  template<typename U, FoldOpWithIndex<U, T> Op>
  U foldWithIndex(int endOffsetNotIncluded, U initValue, Op &op) const
  {
    return foldWithIndex(0, endOffsetNotIncluded, initValue, op);
  }

  template<typename U, FoldOpWithIndex<U, T> Op>
  U foldWithIndex(U initValue, Op &op) const
  {
    return foldWithIndex(0, fSize, initValue, op);
  }
 
private:
  int adjustIndexFromOffset(int offset) const
  {
    if(offset == 0)
      return fStart;
 
    return adjustIndex(fStart + offset);
  }
 
  int adjustIndex(int index) const
  {
    // shortcut since this is a frequent use case
    if(index == fSize)
      return 0;
 
    while(index < 0)
      index += fSize;
 
    while(index >= fSize)
      index -= fSize;
 
    return index;
  }
 
  int fSize;
  T *fBuf;
  int fStart;
};
 
}
}
}
 
#endif // __PONGASOFT_UTILS_COLLECTION_CIRCULAR_BUFFER_H__