// Copyright 2005 Rutger E.W. van Beusekom.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef __CIRCULAR_BUFFER_HPP__
#define __CIRCULAR_BUFFER_HPP__

#include "error_handling.hpp"

#include <algorithm>
#include <vector>

template <typename T, typename B = std::vector<T> >
class circular_buffer
{
  typedef unsigned size_t;
  typedef T value_type;

  B data_;
  size_t capacity_;
  size_t index_;
  size_t size_;
public:
  template <typename S, typename C>
  class Iterator
  {
    friend class circular_buffer<T, B>;
    
    C* C_;
    size_t index_;
    
    Iterator(C* C, size_t index)
    : C_(C)
    , index_(index)
    {}
  public:
    typedef S                               value_type;
    typedef size_t                          difference_type;
    typedef std::random_access_iterator_tag iterator_category;
    typedef S&                              reference;
    typedef S*                              pointer;

    Iterator()
    : C_(0)
    , index_(0)
    {}
    Iterator(const Iterator& iter)
    : C_(iter.C_)
    , index_(iter.index_)
    {}
    Iterator& operator = (const Iterator& iter)
    {
      C_ = iter.C_;
      index_  = iter.index_;
    }
    Iterator& operator ++ ()
    {
      ++index_;
      return *this;
    }
    Iterator operator ++ (int)
    {
      Iterator temp(*this);
      ++index_;
      return temp;
    }
    Iterator& operator -- ()
    {
      --index_;
      return *this;
    }
    Iterator operator -- (int)
    {
      Iterator temp(*this);
      --index_;
      return temp;
    }
    S& operator * ()
    {
      throw_assert(0 != C_);
      return C_->at(index_);
    }
    S* operator -> ()
    {
      throw_assert(0 != C_);
      return &C_->at(index_);
    }
    friend size_t operator - (const Iterator& lhs, const Iterator& rhs)
    {
      return lhs.index_ - rhs.index_;
    }
    friend bool operator == (const Iterator& lhs, const Iterator& rhs)
    {
      return lhs.C_ == rhs.C_
          && lhs.index_  == rhs.index_;
    }
    friend bool operator != (const Iterator& lhs, const Iterator& rhs)
    {
      return lhs.C_ == rhs.C_
          && lhs.index_ != rhs.index_;
    }
  };
  typedef Iterator<const T, const circular_buffer<T, B> > const_iterator;
  typedef Iterator<T, circular_buffer<T, B> > iterator;

  circular_buffer():
    data_(),
    capacity_(data_.size()),
    index_(0),
    size_(0)
  {}
  circular_buffer(size_t capacity):
    data_(capacity),
    capacity_(data_.size()),
    index_(0),
    size_(0)
  {}
  template <typename I>
  circular_buffer(const I& begin, const I& end)
  : data_(begin, end)
  , capacity_(data_.size())
  , index_(0)
  , size_(capacity_)
  {}
  ~circular_buffer()
  {}
  size_t size() const
  {
    return size_;
  }
  void swap(circular_buffer<T, B>& rhs)
  {
    std::swap(data_, rhs.data_);
    std::swap(capacity_, rhs.capacity_);
    std::swap(index_, rhs.index_);
    std::swap(size_, rhs.size_);
  }
  void reserve(size_t size)
  {
    throw_assert(size >= size_);

    B temp(begin(), end());
    temp.resize(size);
    data_.swap(temp);

    index_ = 0;
    capacity_ = size;
  }
  size_t capacity() const
  {
    return capacity_;
  }
  bool empty() const
  {
    return 0 == size_;
  }
  bool full() const
  {
    return capacity_ == size_;
  }
  void clear()
  {
    size_ = 0;
  }
  iterator begin()
  {
    return iterator(this, 0);
  }
  const_iterator begin() const
  {
    return const_iterator(this, 0);
  }
  iterator end()
  {
    return iterator(this, size_);
  }
  const_iterator end() const
  {
    return const_iterator(this, size_);
  }
  T& at(size_t index)
  {
    throw_assert(index < size_);
    index = (index_ + index) % capacity_;
    return data_[index];
  }
  const T& at(size_t index) const
  {
    throw_assert(index < size_);
    index = (index_ + index) % capacity_;
    return data_[index];
  }
  T& operator[](size_t index)
  {
    return at(index);
  }
  const T& operator[](size_t index) const
  {
    return at(index);
  }
  void push_back(const T& t)
  {
    throw_assert(capacity_ > size_);
    data_[(index_ + size_) % capacity_] = t;
    ++size_;
  }
  void push_front(const T& t)
  {
    throw_assert(capacity_ > size_);
    data_[--index_ % capacity_] = t;
    ++size_;
  }
  void pop_front()
  {
    throw_assert(0 < size_);
    ++index_;
    --size_;
  }
  void pop_back()
  {
    throw_assert(0 < size_);
    --size_;
  }
  const T& front() const
  {
    throw_assert(0 < size_);
    return data_[index_ % capacity_];
  }
  const T& back() const
  {
    throw_assert(0 < size_);
    return data_[(index_ + size_ - 1) % capacity_];
  }
};

#endif