path: root/src/array.h

/*
 * Copyright (C) 2007-2010 Xagasoft, All rights reserved.
 *
 * This file is part of the libbu++ library and is released under the
 * terms of the license contained in the file LICENSE.
 */

#ifndef BU_ARRAY_H
#define BU_ARRAY_H

#include <memory>
#include "bu/exceptionbase.h"
#include "bu/archivebase.h"
#include "bu/sharedcore.h"

namespace Bu
{
	subExceptionDecl( ArrayException )

	template<typename value, int inc, typename valuealloc>
	class ArrayCore
	{
	public:
		ArrayCore() :
			pData( NULL ),
			iSize( 0 ),
			iCapacity( 0 )
		{ }

		void setCapacity( int iNewLen )
		{
			//clear();
			//iCapacity = iCapacity;
			//pData = va.allocate( iCapacity );
			if( iNewLen <= iCapacity ) return;
			value *pNewData = va.allocate( iNewLen );
			if( pData )
			{
				for( int j = 0; j < iSize; j++ )
				{
					va.construct( &pNewData[j], pData[j] );
					va.destroy( &pData[j] );
				}
				va.deallocate( pData, iCapacity );
			}
			pData = pNewData;
			iCapacity = iNewLen;
		}

		virtual ~ArrayCore()
		{
			clear();
		}

		void clear()
		{
			if( pData )
			{
				for( int j = 0; j < iSize; j++ )
				{
					va.destroy( &pData[j] );
				}
				va.deallocate( pData, iCapacity );
				pData = NULL;
			}
			iSize = 0;
			iCapacity = 0;
		}

		void erase( int iPos )
		{
			for( int j = iPos; j < iSize; j++ )
			{
				va.destroy( &pData[j] );
				if( j == iSize-1 )
				{
					iSize--;
					return;
				}
				va.construct( &pData[j], pData[j+1] );
			}
		}

		void swapErase( int iPos )
		{
			if( iPos == iSize-1 )
			{
				erase( iPos );
				return;
			}
			va.destroy( &pData[iPos] );
			va.construct( &pData[iPos], pData[iSize-1] );
			va.destroy( &pData[iSize-1] );
			iSize--;
		}

		valuealloc va;
		value *pData;
		long iSize;
		long iCapacity;
	};

	/**
	 * Array type container, just like a normal array only flexible and keeps
	 * track of your memory for you.
	 *
	 *@param value (typename) The type of data to store in your list
	 *@param valuealloc (typename) Memory Allocator for your value type
	 *@param linkalloc (typename) Memory Allocator for the list links.
	 *@ingroup Containers
	 */
	template<typename value, int inc=10, typename valuealloc=std::allocator<value> >
	class Array : public SharedCore<ArrayCore<value, inc, valuealloc> >
	{
	private:
		typedef class Array<value, inc, valuealloc> MyType;
		typedef class ArrayCore<value, inc, valuealloc> Core;

	protected:
		using SharedCore< Core >::core;
		using SharedCore< Core >::_hardCopy;
		using SharedCore< Core >::_allocateCore;

	public:
		struct const_iterator;
		struct iterator;

		Array()
		{
		}

		Array( const MyType &src ) :
			SharedCore< Core >( src )
		{
		}
		
		Array( long iSetCap )
		{
			setCapacity( iSetCap );
		}

		~Array()
		{
		}

		bool operator==( const MyType &src ) const
		{
			if( core == src.core )
				return true;
			if( core->iSize != src.core->iSize )
				return false;

			for( int j = 0; j < core->iSize; j++ )
			{
				if( core->pData[j] != src.core->pData[j] )
					return false;
			}
			return true;
		}

		bool operator!=( const MyType &src ) const
		{
			return !(*this == src);
		}

		/**
		 * Clear the array.
		 */
		void clear()
		{
			_hardCopy();
			core->clear();
		}

		void append( const value &rVal )
		{
			_hardCopy();
			if( core->iSize == core->iCapacity )
			{
				core->setCapacity( core->iCapacity + inc );
			}

			core->va.construct( &core->pData[core->iSize++], rVal );
		}

		//operator
		value &operator[]( long iIndex )
		{
			_hardCopy();
			if( iIndex < 0 || iIndex >= core->iSize )
				throw ArrayException(
					"Index %d out of range 0:%d", iIndex, core->iSize );

			return core->pData[iIndex];
		}
		
		const value &operator[]( long iIndex ) const
		{
			if( iIndex < 0 || iIndex >= core->iSize )
				throw ArrayException(
					"Index %d out of range 0:%d", iIndex, core->iSize );

			return core->pData[iIndex];
		}

		value &first()
		{
			_hardCopy();
			return core->pData[0];
		}

		const value &first() const
		{
			return core->pData[0];
		}

		value &last()
		{
			_hardCopy();
			return core->pData[core->iSize-1];
		}

		const value &last() const
		{
			return core->pData[core->iSize-1];
		}

		/**
		 * Get the current size of the array.
		 *@returns The current size of the array.
		 */
		long getSize() const
		{
			return core->iSize;
		}

		/**
		 * Get the capacity of the array.  This number will grow as data is
		 * added, and is mainly for the curious, it doesn't really determine
		 * much for the end user.
		 *@returns The current capacity of the array.
		 */
		long getCapacity() const
		{
			return core->iCapacity;
		}

		/**
		 * Change the capacity of the array, very useful if you know you'll be
		 * adding a large amount of already counted items to the array, makes
		 * the appending much faster afterwords.
		 *@param iNewLen The new capacity of the array.
		 *@todo Set this up so it can reduce the size of the array as well as
		 * make it bigger.
		 */
		void setCapacity( long iNewLen )
		{
			_hardCopy();
			core->setCapacity( iNewLen );
		}

		typedef struct iterator
		{
			friend class Array<value, inc, valuealloc>;
		private:
			iterator( MyType &src, long iPos=0 ) :
				src( src ),
				iPos( iPos )
			{
				if( this->iPos >= src.getSize() )
					this->iPos = -1;
			}

			MyType &src;
			long iPos;

		public:
			iterator operator++( int )
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot increment iterator past end of array.");
					iPos++;
				if( iPos >= src.getSize() )
					iPos = -1;
				return *this;
			}
			
			iterator operator++()
			{
				if( iPos >= 0 )
					iPos++;
				if( iPos >= src.getSize() )
					iPos = -1;
				return *this;
			}
			
			iterator operator--( int )
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot increment iterator past end of array.");
					iPos--;
				if( iPos < 0 )
					iPos = -1;
				return *this;
			}
			
			iterator operator--()
			{
				if( iPos < src.getSize() )
					iPos--;
				if( iPos <= 0 )
					iPos = -1;
				return *this;
			}

			bool operator==( const iterator &oth ) const
			{
				return iPos == oth.iPos;
			}

			bool operator!=( const iterator &oth ) const
			{
				return iPos != oth.iPos;
			}

			iterator operator=( const iterator &oth )
			{
				if( &src != &oth.src )
					throw ArrayException(
						"Cannot mix iterators from different array objects.");
				iPos = oth.iPos;
			}

			value &operator*()
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot dereference finished iterator.");
				return src[iPos];
			}

			long getIndex() const
			{
				return iPos;
			}

			operator bool() const
			{
				return iPos >= 0;
			}

			bool isValid() const
			{
				return iPos >= 0;
			}
		} iterator;
		
		typedef struct const_iterator
		{
			friend class Array<value, inc, valuealloc>;
		private:
			const_iterator( const MyType &src, long iPos=0 ) :
				src( src ),
				iPos( iPos )
			{
				if( this->iPos >= src.getSize() )
					this->iPos = -1;
			}

			const MyType &src;
			long iPos;

		public:
			const_iterator operator++( int )
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot increment iterator past end of array.");
					iPos++;
				if( iPos >= src.getSize() )
					iPos = -1;
				return *this;
			}
			
			const_iterator operator++()
			{
				if( iPos >= 0 )
					iPos++;
				if( iPos >= src.getSize() )
					iPos = -1;
				return *this;
			}
			
			const_iterator operator--( int )
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot increment iterator past end of array.");
					iPos--;
				if( iPos < 0 )
					iPos = -1;
				return *this;
			}
			
			const_iterator operator--()
			{
				if( iPos < src.getSize() )
					iPos--;
				if( iPos <= 0 )
					iPos = -1;
				return *this;
			}

			bool operator==( const const_iterator &oth ) const
			{
				return iPos == oth.iPos;
			}

			bool operator!=( const const_iterator &oth ) const
			{
				return iPos != oth.iPos;
			}

			const_iterator operator=( const const_iterator &oth )
			{
				if( &src != &oth.src )
					throw ArrayException(
						"Cannot mix iterators from different array objects.");
				iPos = oth.iPos;
			}

			const value &operator*() const
			{
				if( iPos < 0 )
					throw ArrayException(
						"Cannot dereference finished iterator.");
				return src[iPos];
			}

			long getIndex() const
			{
				return iPos;
			}
			
			operator bool() const
			{
				return iPos >= 0;
			}

			bool isValid() const
			{
				return iPos >= 0;
			}
		} const_iterator;

		iterator begin()
		{
			return iterator( *this );
		}

		const_iterator begin() const
		{
			return const_iterator( *this );
		}

		iterator end()
		{
			return iterator( *this, -1 );
		}

		const_iterator end() const
		{
			return const_iterator( *this, -1 );
		}

		/**
		 * If order is important, use this.  It will delete the suggested item
		 * and move the rest of the data up a spot.  This is a time O(n)
		 * operation.  If the order isn't important, check swapErase
		 */
		void erase( iterator i )
		{
			_hardCopy();
			core->erase( i.iPos );
		}

		/**
		 * In order to make swapErase faster, what it does is swap the given
		 * item in the array with the last item, then make the array shorter
		 * by one.  It changes the order of the elements in the array, so it
		 * should be used carefully, but it is time O(1) instead of O(n) like
		 * erase.
		 */
		void swapErase( iterator i )
		{
			_hardCopy();
			swapErase( i.iPos );
		}

	protected:
		virtual Core *_copyCore( Core *src )
		{
			Core *pRet = _allocateCore();
			pRet->setCapacity( src->iCapacity );
			pRet->iSize = src->iSize;
			for( int j = 0; j < src->iSize; j++ )
			{	
				pRet->va.construct( &pRet->pData[j], src->pData[j] );
			}
			return pRet;
		}

	private:
	};

	class Formatter;
	Formatter &operator<<( Formatter &rOut, char *sStr );
	Formatter &operator<<( Formatter &rOut, signed char c );
	template<typename value>
	Formatter &operator<<( Formatter &f, const Bu::Array<value> &a )
	{
		f << '[';
		for( typename Bu::Array<value>::const_iterator i = a.begin(); i; i++ )
		{
			if( i != a.begin() )
				f << ", ";
			f << *i;
		}
		f << ']';

		return f;
	}

	template<typename value, int inc, typename valuealloc>
	ArchiveBase &operator<<( ArchiveBase &ar,
			const Array<value, inc, valuealloc> &h )
	{
		ar << h.getSize();
		for( typename Array<value, inc, valuealloc>::const_iterator i =
			 h.begin(); i != h.end(); i++ )
		{
			ar << (*i);
		}

		return ar;
	}

	template<typename value, int inc, typename valuealloc>
	ArchiveBase &operator>>(ArchiveBase &ar, Array<value, inc, valuealloc> &h )
	{
		h.clear();
		long nSize;
		ar >> nSize;

		h.setCapacity( nSize );
		for( long j = 0; j < nSize; j++ )
		{
			value v;
			ar >> v;
			h.append( v );
		}
		return ar;
	}

}

#endif