RingBuffer.h

Go to the documentation of this file.

// this is for emacs file handling -*- mode: c++; indent-tabs-mode: nil -*-

// -- BEGIN LICENSE BLOCK ----------------------------------------------
// This file is part of FZIs ic_workspace.
//
// This program is free software licensed under the LGPL
// (GNU LESSER GENERAL PUBLIC LICENSE Version 3).
// You can find a copy of this license in LICENSE folder in the top
// directory of the source code.
//
// © Copyright 2014 FZI Forschungszentrum Informatik, Karlsruhe, Germany
//
// -- END LICENSE BLOCK ------------------------------------------------

//----------------------------------------------------------------------
//----------------------------------------------------------------------
#ifndef ICL_CORE_RING_BUFFER_H_INCLUDED
#define ICL_CORE_RING_BUFFER_H_INCLUDED

#include <stdexcept>
#include <iterator>
#include <vector>

#include "icl_core/BaseTypes.h"

#ifdef _IC_BUILDER_DEPRECATED_STYLE_
# include "icl_core/Deprecate.h"
#endif

namespace icl_core {

template <typename T>
class RingBuffer
{
public:
  typedef T value_type;
  typedef typename std::vector<T>::size_type size_type;
  typedef typename std::vector<T>::difference_type difference_type;
  typedef std::pair<T*, size_type> array_range;
  typedef std::pair<const T*, size_type> const_array_range;
  static const size_type cDEFAULT_CAPACITY = 32;

  class const_iterator : public std::iterator<std::random_access_iterator_tag, T>
  {
    friend class RingBuffer;

  public:
    const_iterator(const const_iterator& other)
      : m_current(other.m_current), m_cbegin(other.m_cbegin), m_cend(other.m_cend), m_begin(other.m_begin)
    { }

    const_iterator& operator = (const const_iterator& other)
    {
      m_current = other.m_current; m_cbegin = other.m_cbegin; m_cend = other.m_cend; m_begin = other.m_begin;
      return *this;
    }

    const_iterator& operator ++ ()
    {
      ++m_current;
      if (m_current == m_cend) { m_current = m_cbegin; }
      return *this;
    }
    const_iterator operator ++ (int)
    {
      const_iterator answer = *this;
      operator ++ ();
      return answer;
    }

    const_iterator& operator -- ()
    {
      if (m_current == m_cbegin)
      {
        m_current = m_cend;
      }
      --m_current;
      return *this;
    }
    const_iterator operator -- (int)
    {
      const_iterator answer = *this;
      operator -- ();
      return answer;
    }

    const_iterator& operator += (difference_type offset)
    {
      m_current += offset;
      if (m_current > m_cend)
      {
        m_current -= m_cend - m_cbegin;
      }
      if (m_cbegin > m_current)
      {
        m_current += m_cend - m_cbegin;
      }
      return *this;
    }
    const_iterator& operator -= (difference_type offset)
    {
      return operator += (-offset);
    }
    const_iterator operator + (difference_type offset) const
    {
      const_iterator answer = *this;
      answer += offset;
      return answer;
    }
    const_iterator operator - (difference_type offset) const
    {
      const_iterator answer = *this;
      answer -= offset;
      return answer;
    }

    difference_type operator - (const const_iterator& other) const
    {
      if ((m_current >= m_begin && other.m_current >= other.m_begin)
          || (m_current < m_begin && other.m_current < other.m_begin))
      {
        return m_current - other.m_current;
      }
      else if (m_current >= m_begin)
      {
        return m_current - other.m_current + m_cbegin - m_cend;
      }
      else
      {
        return m_current - other.m_current + m_cend - m_cbegin;
      }
    }

    bool operator == (const const_iterator& other) const { return m_current == other.m_current; }
    bool operator != (const const_iterator& other) const { return m_current != other.m_current; }

    const T& operator * () const { return *m_current; }
    const T *operator -> () const { return m_current; }

  protected:
    const_iterator(T *current, T *cbegin, T *cend, T *begin)
      : m_current(current), m_cbegin(cbegin), m_cend(cend), m_begin(begin)
    { }

    T *m_current;
    T *m_cbegin;
    T *m_cend;
    T *m_begin;
  };

  class iterator : public const_iterator
  {
    friend class RingBuffer;

  public:
    iterator(const iterator& other)
      : const_iterator(other)
    { }

    iterator& operator = (const iterator& other)
    {
      const_iterator::m_current = other.m_current;
      const_iterator::m_cbegin = other.m_cbegin;
      const_iterator::m_cend = other.m_cend;
      const_iterator::m_begin = other.m_begin;
      return *this;
    }

    T& operator * () const { return *const_iterator::m_current; }
    T *operator -> () const { return const_iterator::m_current; }

  protected:
    iterator(T *current, T *cbegin, T *cend, T *begin)
      : const_iterator(current, cbegin, cend, begin)
    { }
  };

  RingBuffer(size_type capacity = cDEFAULT_CAPACITY)
    : m_buffer(capacity+1), m_write(0), m_read(0)
  { }

  RingBuffer(const RingBuffer<T>& other)
    : m_buffer(other.m_buffer), m_write(other.m_write), m_read(other.m_read)
  { }

  RingBuffer& operator = (const RingBuffer<T>& other)
  {
    m_buffer = other.m_buffer;
    m_write = other.m_write;
    m_read = other.m_read;
    return *this;
  }

  void clear() { m_write = 0; m_read = 0; }

  bool empty() const { return m_write == m_read; }

  bool full() const { return ((m_write+1) % m_buffer.size()) == m_read; }


  void write(const T& val, bool overwrite=false)
  {
    size_type new_write_pos = m_write+1;
    if (new_write_pos >= m_buffer.size())
    {
      new_write_pos = 0;
    }
    if (new_write_pos == m_read)
    {
      if (overwrite)
      {
        skip();
      }
      else
      {
        throw std::out_of_range("RingBuffer::write: capacity exceeded");
      }
    }
    m_buffer[m_write] = val;
    m_write = new_write_pos;
  }

  void fakeWrite(size_t count);


  const T& at(size_type pos) const
  {
    if (pos < size())
    {
      pos += m_read;
      if (pos >= m_buffer.size())
      {
        pos -= m_buffer.size();
      }
      return m_buffer[pos];
    }
    else
    {
      throw std::out_of_range("RingBuffer::at: out of range");
    }
  }


  T& at(size_type pos)
  {
    if (pos < size())
    {
      pos += m_read;
      if (pos >= m_buffer.size())
      {
        pos -= m_buffer.size();
      }
      return m_buffer[pos];
    }
    else
    {
      throw std::out_of_range("RingBuffer::at: out of range");
    }
  }

  const T& front() const { return at(0); }
  T& front() { return at(0); }

  void skip()
  {
    if (m_write == m_read)
    {
      throw std::out_of_range("RingBuffer::skip: buffer empty");
    }
    m_read++;
    if (m_read >= m_buffer.size())
    {
      m_read = 0;
    }
  }

  void skip(size_type count);


  T read()
  {
    if (m_write == m_read)
    {
      throw std::out_of_range("RingBuffer::read: buffer empty");
    }
    size_type read_pos = m_read;
    m_read++;
    if (m_read >= m_buffer.size())
    {
      m_read = 0;
    }
    return m_buffer[read_pos];
  }

  inline size_type size() const
  {
    if (m_write >= m_read)
    {
      return m_write-m_read;
    }
    else
    {
      return m_write+m_buffer.size()-m_read;
    }
  }

  size_type capacity() const { return m_buffer.size()-1; }

  size_type reserve() const
  {
    return capacity() - size();
  }


  void setCapacity(size_type capacity)
  {
    size_type old_size = size();
    size_type new_size = (capacity < old_size) ? capacity : old_size;
    std::vector<T> old_buffer(m_buffer);
    size_type old_read = m_read;

    // Adjust capacity.
    m_buffer.resize(capacity+1);
    // Skip elements that will not fit.
    old_read += old_size-new_size;
    if (old_read >= old_buffer.size())
    {
      old_read -= old_buffer.size();
    }
    // Copy the rest.
    for (size_type i=0; i<new_size; i++)
    {
      m_buffer[i] = old_buffer[old_read];
      old_read++;
      if (old_read >= old_buffer.size())
      {
        old_read = 0;
      }
    }
    // Update pointers.
    m_read = 0;
    m_write = new_size;
  }

  ~RingBuffer()
  { }

  const_iterator begin() const
  { return const_iterator(&m_buffer[m_read], &m_buffer[0], &m_buffer[0]+m_buffer.size(), &m_buffer[m_read]); }
  iterator begin()
  { return iterator(&m_buffer[m_read], &m_buffer[0], &m_buffer[0]+m_buffer.size(), &m_buffer[m_read]); }

  const_iterator end() const
  { return const_iterator(&m_buffer[m_write], &m_buffer[0], &m_buffer[0]+m_buffer.size(), &m_buffer[m_read]); }
  iterator end()
  { return iterator(&m_buffer[m_write], &m_buffer[0], &m_buffer[0]+m_buffer.size(), &m_buffer[m_read]); }

  array_range arrayOne();
  const_array_range arrayOne() const;

  array_range arrayTwo();
  const_array_range arrayTwo() const;

  array_range emptyArrayOne();
  const_array_range emptyArrayOne() const;
  array_range emptyArrayTwo();
  const_array_range emptyArrayTwo() const;

#ifdef _IC_BUILDER_DEPRECATED_STYLE_

  ICL_CORE_VC_DEPRECATE_STYLE void Clear() ICL_CORE_GCC_DEPRECATE_STYLE;


  ICL_CORE_VC_DEPRECATE_STYLE
  void Write(const T& val, bool overwrite=false) ICL_CORE_GCC_DEPRECATE_STYLE;


  ICL_CORE_VC_DEPRECATE_STYLE const T& At(size_type pos) const ICL_CORE_GCC_DEPRECATE_STYLE;


  ICL_CORE_VC_DEPRECATE_STYLE T& At(size_type pos) ICL_CORE_GCC_DEPRECATE_STYLE;

  ICL_CORE_VC_DEPRECATE_STYLE void Skip() ICL_CORE_GCC_DEPRECATE_STYLE;


  ICL_CORE_VC_DEPRECATE_STYLE T Read() ICL_CORE_GCC_DEPRECATE_STYLE;

  inline ICL_CORE_VC_DEPRECATE_STYLE size_type Size() const ICL_CORE_GCC_DEPRECATE_STYLE;

  ICL_CORE_VC_DEPRECATE_STYLE size_type Capacity() const ICL_CORE_GCC_DEPRECATE_STYLE;


  ICL_CORE_VC_DEPRECATE_STYLE void SetCapacity(size_type capacity) ICL_CORE_GCC_DEPRECATE_STYLE;

#endif


private:
  std::vector<T> m_buffer;
  size_type m_write;
  size_type m_read;
};

}

#include "icl_core/RingBuffer.hpp"

#endif