/* $Id$ */

#ifndef _RINGBUFFER_HPP_
#define _RINGBUFFER_HPP_

/**********************************************************/

#include <SDL_types.h>
#include "global.hpp"

/**********************************************************/

//! template for a simple ring buffer

/*! This class implements a simple ring buffer.
 *  Its maximal size can be fixed with RingBuffer::setSize or at
 *  creation time using the constructor. After creation this class can
 *  be used like a FIFO or a stack or mixed, whereby additionally
 *  entries can be inserted in the middle of the current data. It
 *  further provides a transparent random access operator [] in range
 *  [0,getSize()-1].
 *
 *  The methods pushFront, pushBack, add entries to the range of valid
 *  data, \b but only, if the buffer is not yet full. This might not
 *  be the behaviour, you expect from a ring buffer. You might wish
 *  the buffer to just add a passed entry at the end of the data part
 *  and \b overwrite the first entry, if the buffer is filled. For
 *  this behaviour please use methods continuousPushBack and
 *  continuousPushFront, respectivly. \br
 *  You also might just modify (not using the assignment operator) the
 *  data in the buffer in this wrap-around access, for example strings
 *  for a ring buffer to store the last 50 error messages. Therefore
 *  you should first create a \b full ring buffer ... look at this
 *  example:
 *
 *  \code
 *  RingBuffer<String> errMsgRing( 50 );
 *  errMsgRing.setFull();
 *
 *  // appending new error message at the ring's head
 *  errMsgRing[0].format( "new message: code %d\n", 5 );
 *  errMsgRing.shift( -1 );
 *
 *  // appending new error message at the ring's tail
 *  errMsgRing[errMsgRing.getSize()-1].format( "new message: code %d\n", 5 );
 *  errMsgRing.shift( 1 );
 *  \endcode
 *
 *  \note The template parameter T must support assignment using
 *        "\c = "
 */
template <class T>
class RingBuffer
{
	public:

		//! create ring buffer with optional maximal size
		RingBuffer( const Uint32 maxSize = 0,
		            const bool   full    = false )
			: m_head(0),
			  m_tail(0),
			  m_size(0),
			  m_maxSize(0),
			  m_data(0x0) {
			setSize( maxSize );
			if( full ) setFull();
		}

		//! destructor
		~RingBuffer() {
			reset();
		};


		//////////////////////////////////////////
		//! \name access and working
		//@{
		//! returns the current size of the valid data part
		Uint32 getSize() const { return m_size; }

		//! returns the maximal size (changable with RingBuffer::setSize)
		Uint32 getMaxSize() const { return m_maxSize; }

		//! virtually "fills" the whole buffer

		/*! This method is meant basically as emulation of filling
		 *  the whole ring buffer with (undefined) values. (See example
		 *  in class description).
		 */
		void setFull() {
			m_tail = m_head = 0;
			m_size = m_maxSize;
		}
		
		//! appends an entry at the tail of the ring buffer

		/*! This method appends an entry at the tail of the current
		 *  valid data part. But only, if there is an empty slot for
		 *  an additional entry, and it returns \b false, if there
		 *  was no free space. Since this is not necessarily the
		 *  behaviour, you expect from a ring buffer, there is also
		 *  the method RingBuffer::continuousPushBack.
		 *  \param entry the entry, that should be appended at the end
		 *  \return \b true, if the call was successfull, \b false in
		 *          case of buffer overflow
		 */
		bool pushBack( const T& entry ) {
			if( getSize() >= getMaxSize() ) {
				DBG(1) CHECK( false, "RingBuffer::pushBack: buffer "
				              "overflow\n" );
				return false;
			}
			m_data[m_tail++] = entry;
			if( m_tail >= m_maxSize )  m_tail = 0;
			m_size++;
			return true;
		}

		//! pull an entry from the head of the ring buffer

		/*! In every case the effect of this method is that the
		 * \b first entry in the ringbuffer is removed. Additionally
		 *  you can receive this entry by passing a pointer of type
		 *  \c *T, where the value is then written to.
		 *  \param entry (optional, default 0x0) If \c !=0x0, the
		 *         method will write the removed entry to this
		 *         address.
		 *  \return \b false, if the ring was empty, otherwise \b true
		 */
		bool pull( T* entry = 0x0 ) {
			if( getSize() <= 0 ) {
				DBG(1) CHECK( false, "RingBuffer::pull: nothing "
				              "there to pull\n" );
				return false;
			}
			if( entry )  *entry = m_data[m_head++];
			if( m_head >= m_maxSize )  m_head = 0;
			m_size--;
			return true;
		}

		//! pop an entry from the tail of the ring buffer
		
		/*! In every case the effect of this method is that the
		 * \b last entry in the ringbuffer is removed. Additionally
		 *  you can receive this entry by passing a pointer of type
		 *  \c *T, where the value is then written to.
		 *  \param entry (optional, default 0x0) If \c !=0x0, the
		 *         method will write the removed entry to this
		 *         address.
		 *  \return \b false, if the ring was empty, otherwise \b true
		 */
		bool pop( T* entry = 0x0 ) {
			if( getSize() <= 0 ) {
				DBG(1) CHECK( false, "RingBuffer::pull: nothing "
				              "there to pop\n" );
				return false;
			}
			if( entry )  *entry = m_data[m_tail];
			if( !m_tail )  m_tail = getMaxSize()-1;
			else           m_tail--;
			m_size--;
			return true;
		}

		//! append an entry at the head of the ring buffer

		/*! \param entry value, that should be appended
		 *  \return \b true, if the call was successfull, \b false in
		 *          case of buffer overflow
		 */
		bool pushFront( const T& entry ) {
			if( getSize() >= getMaxSize() ) {
				DBG(1) CHECK( false, "RingBuffer::pushFront: "
				              "buffer overflow\n", i );
				return false;
			}
			// test BEFORE decrement, since m_head is unsigned
			if( !m_head )  m_head = getMaxSize()-1;
			else           m_head--;
			m_data[m_head] = entry;
			m_size++;
			return true;
		}

		/*! \brief appends an entry at the tail of the ring buffer and
		 *  overwrites the first one, if therefor necessary.
		 */
		void continuousPushBack( const T& entry ) {
			m_data[m_tail++] = entry;
			if( m_tail >= getMaxSize() )  m_tail = 0;
			if( m_size >= getMaxSize() ) {
				if( ++m_head >= getMaxSize() )  m_head = 0;
			} else {
				m_size++;
			}
		}

		/*! \brief appends an entry at the head of the ring buffer and
		 *  overwrites the last one, if therefor necessary.
		 */
		void continuousPushFront( const T& entry ) {
			if( !m_head )  m_head = getMaxSize()-1;
			else           m_head--;
			m_data[m_head] = entry;
			if( m_size >= getMaxSize() ) {
				if( !m_tail )  m_tail = getMaxSize()-1;
				else           m_tail--;
			} else {
				m_size++;
			}
		}

		//! insert a value at an arbitrary position

		/*! \param entry value, that should be inserted
		 *  \return \b true, if the call was successfull, \b false in
		 *          case of buffer overflow
		 */
		bool insert( Uint32 i, const T& entry ) {
			if( getSize() >= getMaxSize() ) {
				DBG(1) CHECK( false, "RingBuffer::insert(%d,..): "
				              "buffer overflow\n", i );
				return false;
			}
			if( i > getSize() )  i = getSize();
			if( i >= getSize()>>1 ) {
				// push dummy value for correct enlargement
				pushBack( m_data[0] );
				for( Uint32 j = getSize()-1; j > i; j-- ) {
					(*this)[j] = (*this)[j-1];
				}
			} else {
				// push dummy value for correct enlargement
				pushFront( m_data[0] );
				for( Uint32 j = 0; j < i; j++ ) {
					(*this)[j] = (*this)[j+1];
				}
			}
			(*this)[i] = entry;
			return true;
		}
		
		//! random access operator []
		T& operator [] ( const Uint32 i ) {
			DBG(1) ASSERT( i < getSize(), "RingBuffer::operator [%u]; "
			               "current size is %u\n", i, getSize() );
			Uint32 index = m_head + i;
			if( index >= m_maxSize )  index -= m_maxSize;
			return m_data[index];
		}

		//! shifts the indexing by the passed jump
		void shift( Sint32 jump ) {
			DBG(1) CHECK( getSize() == getMaxSize(),
			              "RingBuffer::shift(%d): shifting in a "
			              "partially filled ring\n", jump );
			Sint32 v = jump;
			while( jump < 0 )  jump += getMaxSize();
			if( (m_head += v) >= getMaxSize() )  m_head -= getMaxSize();
			if( (m_tail += v) >= getMaxSize() )  m_tail -= getMaxSize();
		}
		//@}

		//////////////////////////////////////////
		//! \name creation, deletion
		//@{
		//! set the new \b maximal size of the ring buffer
		bool setSize( const Uint32 maxSize ) {
			// reset the working data
			m_head = 0;
			m_tail = 0;
			m_size = 0;
			// possible to reuse buffer
			if( m_maxSize == maxSize )  return true;
			
			m_maxSize = 0;
			delete [] m_data;
			m_data = 0x0;
			//
			if( maxSize ) {
				if( CHECK(0x0 != (m_data = NEW T [maxSize]),
				          "RingBuffer::setSize(%u) not enough memory\n",
				          maxSize) ) {
					m_maxSize = maxSize;
					return true;
				} else {
					return false;
				}
			}
			return true;
		}

		//! reset the class
		void reset() { setSize(0); }
		//@}

	protected:

		Uint32  m_head;
		Uint32  m_tail;
		Uint32  m_size;
		Uint32  m_maxSize;
		T      *m_data;
};

/**********************************************************/

#endif // _RINGBUFFER_HPP_