CircularBuffer.h

Go to the documentation of this file.

/*
 * Copyright (c) 2018-2019 pongasoft
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * 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>

namespace pongasoft {
namespace Utils {
namespace Collection {

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
  inline int getSize() const
  {
    return fSize;
  }

  inline T getAt(int offset) const
  {
    return fBuf[adjustIndexFromOffset(offset)];
  }

  inline void setAt(int offset, T e)
  {
    fBuf[adjustIndexFromOffset(offset)] = e;
  };

  inline void incrementHead()
  {
    fStart = adjustIndex(fStart + 1);
  }

  inline void push(T e)
  {
    setAt(0, e);
    incrementHead();
  }

  inline void init(T initValue)
  {
    for(int i = 0; i < fSize; ++i)
    {
      fBuf[i] = initValue;
    }
  }

  inline 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, class BinaryPredicate>
  inline U fold(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicate &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 = op(resultValue, fBuf[i]);
        ++i;
        if(i == fSize)
          i = 0;
        size--;
      }
    }
    else
    {
      int size = startOffset - endOffsetNotIncluded;
      while(size > 0)
      {
        resultValue = op(resultValue, fBuf[i]);
        --i;
        if(i == -1)
          i = fSize - 1;
        size--;
      }
    }

    return resultValue;
  }

  template<typename U, class BinaryPredicate>
  inline U fold(int endOffsetNotIncluded, U initValue, BinaryPredicate &op) const
  {
    return fold(0, endOffsetNotIncluded, initValue, op);
  }

  template<typename U, class BinaryPredicate>
  inline U fold(U initValue, BinaryPredicate &op) const
  {
    return fold(0, fSize, initValue, op);
  }

  template<typename U, class BinaryPredicateWithIndex>
  inline U foldWithIndex(int startOffset, int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &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 = op(index, resultValue, fBuf[i]);
        ++i;
        if(i == fSize)
          i = 0;
        size--;
        index++;
      }
    }
    else
    {
      int size = startOffset - endOffsetNotIncluded;
      while(size > 0)
      {
        resultValue = op(index, resultValue, fBuf[i]);
        --i;
        if(i == -1)
          i = fSize - 1;
        size--;
        index--;
      }
    }

    return resultValue;
  }

  template<typename U, class BinaryPredicateWithIndex>
  inline U foldWithIndex(int endOffsetNotIncluded, U initValue, BinaryPredicateWithIndex &op) const
  {
    return foldWithIndex(0, endOffsetNotIncluded, initValue, op);
  }

  template<typename U, class BinaryPredicateWithIndex>
  inline U foldWithIndex(U initValue, BinaryPredicateWithIndex &op) const
  {
    return foldWithIndex(0, fSize, initValue, op);
  }

private:
  inline int adjustIndexFromOffset(int offset) const
  {
    if(offset == 0)
      return fStart;

    return adjustIndex(fStart + offset);
  }

  inline 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__