irrArray.h

Go to the documentation of this file.

// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine" and the "irrXML" project.
// For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h

#ifndef __IRR_ARRAY_H_INCLUDED__
#define __IRR_ARRAY_H_INCLUDED__

#include "irrTypes.h"
#include "heapsort.h"
#include "irrAllocator.h"
#include "irrMath.h"

namespace irr
{
namespace core
{


template <class T, typename TAlloc = irrAllocator<T> >
class array
{

public:

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



        explicit array(u32 start_count) : data(0), allocated(0), used(0),
                        strategy(ALLOC_STRATEGY_DOUBLE),
                        free_when_destroyed(true), is_sorted(true)
        {
                reallocate(start_count);
        }


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



        ~array()
        {
                clear();
        }



        void reallocate(u32 new_size, bool canShrink=true)
        {
                if (allocated==new_size)
                        return;
                if (!canShrink && (new_size < allocated))
                        return;

                T* old_data = data;

                data = allocator.allocate(new_size); //new T[new_size];
                allocated = new_size;

                // copy old data
                const s32 end = used < new_size ? used : new_size;

                for (s32 i=0; i<end; ++i)
                {
                        // data[i] = old_data[i];
                        allocator.construct(&data[i], old_data[i]);
                }

                // destruct old data
                for (u32 j=0; j<used; ++j)
                        allocator.destruct(&old_data[j]);

                if (allocated < used)
                        used = allocated;

                allocator.deallocate(old_data); //delete [] old_data;
        }



        void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE )
        {
                strategy = newStrategy;
        }



        void push_back(const T& element)
        {
                insert(element, used);
        }



        void push_front(const T& element)
        {
                insert(element);
        }



        void insert(const T& element, u32 index=0)
        {
                _IRR_DEBUG_BREAK_IF(index>used) // access violation

                if (used + 1 > allocated)
                {
                        // this doesn't work if the element is in the same
                        // array. So we'll copy the element first to be sure
                        // we'll get no data corruption
                        const T e(element);

                        // increase data block
                        u32 newAlloc;
                        switch ( strategy )
                        {
                                case ALLOC_STRATEGY_DOUBLE:
                                        newAlloc = used + 5 + (allocated < 500 ? used : used >> 2);
                                        break;
                                default:
                                case ALLOC_STRATEGY_SAFE:
                                        newAlloc = used + 1;
                                        break;
                        }
                        reallocate( newAlloc);

                        // move array content and construct new element
                        // first move end one up
                        for (u32 i=used; i>index; --i)
                        {
                                if (i<used)
                                        allocator.destruct(&data[i]);
                                allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
                        }
                        // then add new element
                        if (used > index)
                                allocator.destruct(&data[index]);
                        allocator.construct(&data[index], e); // data[index] = e;
                }
                else
                {
                        // element inserted not at end
                        if ( used > index )
                        {
                                // create one new element at the end
                                allocator.construct(&data[used], data[used-1]);

                                // move the rest of the array content
                                for (u32 i=used-1; i>index; --i)
                                {
                                        data[i] = data[i-1];
                                }
                                // insert the new element
                                data[index] = element;
                        }
                        else
                        {
                                // insert the new element to the end
                                allocator.construct(&data[index], element);
                        }
                }
                // set to false as we don't know if we have the comparison operators
                is_sorted = false;
                ++used;
        }


        void clear()
        {
                if (free_when_destroyed)
                {
                        for (u32 i=0; i<used; ++i)
                                allocator.destruct(&data[i]);

                        allocator.deallocate(data); // delete [] data;
                }
                data = 0;
                used = 0;
                allocated = 0;
                is_sorted = true;
        }



        void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
        {
                clear();
                data = newPointer;
                allocated = size;
                used = size;
                is_sorted = _is_sorted;
                free_when_destroyed=_free_when_destroyed;
        }



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



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

                used = usedNow;
        }


        const array<T, TAlloc>& operator=(const array<T, TAlloc>& other)
        {
                if (this == &other)
                        return *this;
                strategy = other.strategy;

                if (data)
                        clear();

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

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

                for (u32 i=0; i<other.used; ++i)
                        allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];

                return *this;
        }


        bool operator == (const array<T, TAlloc>& other) const
        {
                if (used != other.used)
                        return false;

                for (u32 i=0; i<other.used; ++i)
                        if (data[i] != other[i])
                                return false;
                return true;
        }


        bool operator != (const array<T, TAlloc>& other) const
        {
                return !(*this==other);
        }


        T& operator [](u32 index)
        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                return data[index];
        }


        const T& operator [](u32 index) const
        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                return data[index];
        }


        T& getLast()
        {
                _IRR_DEBUG_BREAK_IF(!used) // access violation

                return data[used-1];
        }


        const T& getLast() const
        {
                _IRR_DEBUG_BREAK_IF(!used) // access violation

                return data[used-1];
        }



        T* pointer()
        {
                return data;
        }



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



        u32 size() const
        {
                return used;
        }



        u32 allocated_size() const
        {
                return allocated;
        }



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



        void sort()
        {
                if (!is_sorted && used>1)
                        heapsort(data, used);
                is_sorted = true;
        }



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



        s32 binary_search(const T& element) const
        {
                if (is_sorted)
                        return binary_search(element, 0, used-1);
                else
                        return linear_search(element);
        }



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

                s32 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;
        }



        s32 binary_search_multi(const T& element, s32 &last)
        {
                sort();
                s32 index = binary_search(element, 0, used-1);
                if ( index < 0 )
                        return index;

                // The search can be somewhere in the middle of the set
                // look linear previous and past the index
                last = index;

                while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
                {
                        index -= 1;
                }
                // look linear up
                while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
                {
                        last += 1;
                }

                return index;
        }



        s32 linear_search(const T& element) const
        {
                for (u32 i=0; i<used; ++i)
                        if (element == data[i])
                                return (s32)i;

                return -1;
        }



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

                return -1;
        }



        void erase(u32 index)
        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                for (u32 i=index+1; i<used; ++i)
                {
                        allocator.destruct(&data[i-1]);
                        allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
                }

                allocator.destruct(&data[used-1]);

                --used;
        }



        void erase(u32 index, s32 count)
        {
                if (index>=used || count<1)
                        return;
                if (index+count>used)
                        count = used-index;

                u32 i;
                for (i=index; i<index+count; ++i)
                        allocator.destruct(&data[i]);

                for (i=index+count; i<used; ++i)
                {
                        if (i-count >= index+count) // not already destructed before loop
                                allocator.destruct(&data[i-count]);

                        allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];

                        if (i >= used-count) // those which are not overwritten
                                allocator.destruct(&data[i]);
                }

                used-= count;
        }


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



        void swap(array<T, TAlloc>& other)
        {
                core::swap(data, other.data);
                core::swap(allocated, other.allocated);
                core::swap(used, other.used);
                core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
                eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields
                strategy = other.strategy;
                other.strategy = helper_strategy;
                bool helper_free_when_destroyed(free_when_destroyed);
                free_when_destroyed = other.free_when_destroyed;
                other.free_when_destroyed = helper_free_when_destroyed;
                bool helper_is_sorted(is_sorted);
                is_sorted = other.is_sorted;
                other.is_sorted = helper_is_sorted;
        }

        typedef TAlloc allocator_type;
        typedef T value_type;
        typedef u32 size_type;

private:
        T* data;
        u32 allocated;
        u32 used;
        TAlloc allocator;
        eAllocStrategy strategy:4;
        bool free_when_destroyed:1;
        bool is_sorted:1;
};


} // end namespace core
} // end namespace irr

#endif