Array.h

#pragma once

/* this template is based on Nikolaus Gebhardt's Array Class in the "Irrlicht Engine". */

// #define BOUNDARY_SAFE
namespace ParaEngine
{
    

    template<class T>
        inline void heapsink(T*array, int element, int max)
    {
        while ((element<<1) < max)  // there is a left child
        {
            int j = (element<<1);

            if (j+1 < max && array[j] < array[j+1])
                j = j+1;                            // take right child

            if (array[element] < array[j])
            {
                T t = array[j];                     // swap elements
                array[j] = array[element];
                array[element] = t;
                element = j;
            }
            else
                return;
        }
    }


    template<class T>
        inline void heapsort(T* array, int size)
    {
        // for heapsink we pretend this is not c++, where
        // arrays start with index 0. So we decrease the array pointer,
        // the maximum always +2 and the element always +1

        T* virtualArray = array - 1;
        int virtualSize = size + 2;
        int i;

        // build heap

        for (i=((size-1)/2); i>=0; --i) 
            heapsink(virtualArray, i+1, virtualSize-1);

        // sort array

        for (i=size-1; i>=0; --i)   
        {
            T t = array[0];
            array[0] = array[i];
            array[i] = t;
            heapsink(virtualArray, 1, i + 1);
        }
    }


    template <class T>
    class array
    {

    public:

        array()
            : data(0), used(0), allocated(0),
            free_when_destroyed(true), is_sorted(true)
        {
        }

        array(DWORD start_count)
            : data(0), used(0), allocated(0),
            free_when_destroyed(true),  is_sorted(true)
        {
            reallocate(start_count);
        }


        array(const array<T>& other)
            : data(0)
        {
            *this = other;
        }



        ~array()
        {
            if (free_when_destroyed)
                delete [] data;
        }



        void reallocate(DWORD new_size)
        {
            T* old_data = data;

            data = new T[new_size];
            allocated = new_size;

            int end = used < new_size ? used : new_size;
            for (int i=0; i<end; ++i)
                data[i] = old_data[i];

            if (allocated < used)
                used = allocated;

            delete [] old_data;
        }



        void push_back(const T& element)
        {
            if (used + 1 > allocated)
                reallocate(used * 2 +1);

            data[used++] = element;
            is_sorted = false;
        }



        void clear()
        {
            delete [] data;
            data = 0;
            used = 0;
            allocated = 0;
            is_sorted = true;
        }



        void set_pointer(T* newPointer, DWORD size)
        {
            delete [] data;
            data = newPointer;
            allocated = size;
            used = size;
            is_sorted = false;
        }



        void set_free_when_destroyed(bool f)
        {
            free_when_destroyed = f;
        }



        void set_used(DWORD usedNow)
        {
            if (allocated < usedNow)
                reallocate(usedNow);

            used = usedNow;
        }



        void operator=(const array<T>& other)
        {
            if (data)
                delete [] data;

            //if (allocated < other.allocated)
            if (other.allocated == 0)
                data = 0;
            else
                data = new T[other.allocated];

            used = other.used;
            free_when_destroyed = other.free_when_destroyed;
            is_sorted = other.is_sorted;
            allocated = other.allocated;

            for (DWORD i=0; i<other.used; ++i)
                data[i] = other.data[i];
        }


        T& operator [](DWORD index)
        {
#ifdef BOUNDARY_SAFE
            if (index>=used)
                return; // access violation
#endif

                return data[index];
        }



        const T& operator [](DWORD index) const
        {
#ifdef BOUNDARY_SAFE
            if (index>=used)
                return; // access violation
#endif

                return data[index];
        }

        const T& getLast() const
        {
#ifdef BOUNDARY_SAFE
            if (!used)
                return; // access violation
#endif

                return data[used-1];
        }

        T& getLast()
        {
#ifdef BOUNDARY_SAFE
            if (!used)
                return; // access violation
#endif

                return data[used-1];
        }


        T* pointer()
        {
            return data;
        }



        const T* const_pointer() const
        {
            return data;
        }



        DWORD size() const
        {
            return used;
        }



        DWORD allocated_size() const
        {
            return allocated;
        }



        bool empty() const
        {
            return used == 0;
        }



        void sort()
        {
            if (is_sorted || used<2)
                return;

            heapsort(data, used);
            is_sorted = true;
        }



        int binary_search(const T& element)
        {
            return binary_search(element, 0, used-1);
        }



        int binary_search(const T& element, int left, int right)
        {
            if (!used)
                return -1;

            sort();

            int m;

            do
            {
                m = (left+right)>>1;

                if (element < data[m])
                    right = m - 1;
                else
                    left = m + 1;

            } while((element < data[m] || data[m] < element) && left<=right);

            // this last line equals to:
            // " while((element != array[m]) && left<=right);"
            // but we only want to use the '<' operator.
            // the same in next line, it is "(element == array[m])"

            if (!(element < data[m]) && !(data[m] < element))
                return m;

            return -1;
        }


        int linear_search(T& element)
        {
            for (DWORD i=0; i<used; ++i)
                if (!(element < data[i]) && !(data[i] < element))
                    return (int)i;

            return -1;
        }


        int linear_reverse_search(T& element)
        {
            for (int i=used-1; i>=0; --i)
                if (data[i] == element)
                    return (int)i;

            return -1;
        }



        void erase(DWORD index)
        {
#ifdef BOUNDARY_SAFE
            if (index>=used || index<0)
                return; // access violation
#endif

                for (DWORD i=index+1; i<used; ++i)
                    data[i-1] = data[i];

            --used;
        }


        void erase(DWORD index, int count)
        {
#ifdef BOUNDARY_SAFE
            if (index>=used || index<0 || count<1 || index+count>used)
                return; // access violation
#endif

                for (DWORD i=index+count; i<used; ++i)
                    data[i-count] = data[i];

            used-= count;
        }


        void set_sorted(bool _is_sorted)
        {
            is_sorted = _is_sorted;
        }


    private:

        T* data;
        DWORD allocated;
        DWORD used;
        bool free_when_destroyed;
        bool is_sorted;
    };

}