#ifndef __RIARRAY_H
#define __RIARRAY_H

/*------------------------------------------------------------------------
 *
 * OpenVG 1.1 Reference Implementation
 * -----------------------------------
 *
 * Copyright (c) 2007 The Khronos Group Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and /or associated documentation files
 * (the "Materials "), to deal in the Materials without restriction,
 * including without limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of the Materials,
 * and to permit persons to whom the Materials are furnished to do so,
 * subject to the following conditions: 
 *
 * The above copyright notice and this permission notice shall be included 
 * in all copies or substantial portions of the Materials. 
 *
 * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR
 * THE USE OR OTHER DEALINGS IN THE MATERIALS.
 *
 *//**
 * \file
 * \brief	Array class.
 * \note	
 *//*-------------------------------------------------------------------*/

#ifndef __RIDEFS_H
#include "riDefs.h"
#endif

#include <string.h>	//for memcpy

namespace OpenVGRI
{

//=======================================================================

/*-------------------------------------------------------------------*//*!
* \brief	An array class similar to std::vector.
* \param	
* \return	
* \note		Follows std::vector's naming convention (except resizeAndReallocate).
*//*-------------------------------------------------------------------*/

template <class Item> class Array
{
public:
	Array() : m_array(NULL), m_size(0), m_allocated(0) {}	//throws bad_alloc
	~Array()
	{
		RI_DELETE_ARRAY(m_array);
	}

	void		swap(Array& s)
	{
		Item* tarray = m_array;
		m_array = s.m_array;
		s.m_array = tarray;

		int tsize = m_size;
		m_size = s.m_size;
		s.m_size = tsize;

		int tallocated = m_allocated;
		m_allocated = s.m_allocated;
		s.m_allocated = tallocated;
	}

	//if more room is needed, reallocate, otherwise return
	void		reserve( int items )	//throws bad_alloc
	{
		RI_ASSERT( items >= 0 );
		if( items <= m_allocated )
			return;	//if there is room already, return

		RI_ASSERT( items > m_allocated );

		Item* newa = RI_NEW_ARRAY(Item, items);	//throws bad_alloc if runs out of memory
		for(int i=0;i<m_size;i++)
			newa[i] = m_array[i];
		RI_DELETE_ARRAY(m_array);
		m_array = newa;
		m_allocated = items;
		//doesn't change size
	}

	//reserve and change size
	void		resize( int items )	//throws bad_alloc
	{
		reserve( items );	//throws bad_alloc if runs out of memory
		m_size = items;
	}

	//resize and allocate exactly the correct amount of memory
	void		resizeAndReallocate( int items )	//throws bad_alloc
	{
		RI_ASSERT( items >= 0 );
		if( items == m_allocated )
		{
			m_size = items;
			return;
		}

		if( items == 0 )
		{
			RI_DELETE_ARRAY(m_array);
			m_size = 0;
			m_allocated = 0;
			return;
		}

		Item* newa = RI_NEW_ARRAY(Item, items);	//throws bad_alloc if runs out of memory
		int copySize = (m_size < items) ? m_size : items;	//min(m_size,items)
		for(int i=0;i<copySize;i++)
			newa[i] = m_array[i];
		RI_DELETE_ARRAY(m_array);
		m_array = newa;
		m_allocated = items;
		m_size = items;		//changes also size
	}
	void		clear()
	{
		m_size = 0;
	}

    //sort array (needs operator< defined for Item. Define it with < for increasing order and > for decreasing.)
	void		sort()
	{
		if(m_size <= 1)
			return;
		quicksort(0, m_size - 1);
	}

    //remove the first occurrence of an item from the array
    bool        remove(const Item& item)
    {
        int i=0;
        for(;i<m_size;i++)
        {
            if(m_array[i] == item)
                break;
        }
        if(i >= m_size)
            return false;   //not found
        for(;i<m_size-1;i++)
        {
            m_array[i] = m_array[i+1];
        }
        m_size--;
        return true;
    }

	RI_INLINE void			push_back( const Item& item )	//throws bad_alloc
	{
		if( m_size >= m_allocated )
			reserve( (!m_allocated) ? 8 : m_allocated * 2 );	//by default, reserve 8. throws bad_alloc if runs out of memory
		m_array[m_size++] = item;
	}
	RI_INLINE int			size() const				{ return m_size; }
	RI_INLINE Item&			operator[](int i)			{ RI_ASSERT(i >= 0 && i < m_size); return m_array[i]; }
	RI_INLINE const Item&	operator[](int i) const		{ RI_ASSERT(i >= 0 && i < m_size); return m_array[i]; }

private:
	Array(const Array& s);				//!< Not allowed.
	void operator=(const Array& s);		//!< Not allowed.

	void quicksort(int left, int right)
	{
		int i = left, j = right;
		Item x = m_array[(left+right)>>1];

		do
		{    
			while (m_array[i] < x)
				i++;
			while (x < m_array[j])
				j--;
			if (i<=j)
			{
				Item tmp = m_array[i];
				m_array[i] = m_array[j];
				m_array[j] = tmp;
				i++;
				j--;
			}
		} while (i<=j);

		if(left < j) quicksort(left, j);
		if(i < right) quicksort(i, right);
	}


	Item*		m_array;
	int			m_size;
	int			m_allocated;
};

//=======================================================================

}	//namespace OpenVGRI

#endif /* __RIARRAY_H */