#ifndef __RIARRAY_H

#define __RIARRAY_H

/*------------------------------------------------------------------------

 *

 * OpenVG 1.1 Reference Implementation

 * -----------------------------------

 *

 * Copyright (c) 2007 The Khronos Group Inc.

 * Portions copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).

 *

 * 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:

    friend class Rasterizer;

    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);

    }

    void sort(int first, int last)

    {

        RI_ASSERT(first <= last);

        RI_ASSERT((first >= 0) && (last < m_size));

        if (m_size <= 1)

            return;

        if ((last - first) < 1)

            return;

        quicksort(first, last);

#if defined(RI_DEBUG)

        for (int i = first+1; i <= last; i++)

        {

            RI_ASSERT(m_array[i-1] <= m_array[i]);

        }

#endif

    }

    int     findIndex(const Item& item)

    {

        for(int i = 0; i < m_size; i++)

            if (m_array[i] == item)

                return i;

        return -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 */