irrArray.hpp

// 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 nirtcpp/nirtcpp.hpp and nirtcpp/irrXML.hpp
 
#ifndef NIRT_ARRAY_HPP_INCLUDED
#define NIRT_ARRAY_HPP_INCLUDED
 
#include <nirtcpp/core/engine/nirt_types.hpp>
#include <nirtcpp/core/engine/heapsort.hpp>
#include <nirtcpp/core/engine/irrAllocator.hpp>
#include <nirtcpp/core/engine/irrMath.hpp>
 
namespace nirt
{
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)
    {
        NIRT_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_data(const T* newData, u32 newSize, bool newDataIsSorted=false, bool canShrink=false)
    {
        reallocate(newSize, canShrink);
        set_used(newSize);
        for ( u32 i=0; i<newSize; ++i)
        {
            data[i] = newData[i];
        }
        is_sorted = newDataIsSorted;
    }
 
 
    bool equals(const T* otherData, u32 size) const
    {
        if (used != size)
            return false;
 
        for (u32 i=0; i<size; ++i)
            if (data[i] != otherData[i])
                return false;
        return true;
    }
 
 
 
 
    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;
 
        // (TODO: we could probably avoid re-allocations of data when (allocated < other.allocated)
 
        if (data)
            clear();
 
        used = other.used;
        free_when_destroyed = true;
        is_sorted = other.is_sorted;
        allocated = other.allocated;
 
        if (other.allocated == 0)
        {
            data = 0;
        }
        else
        {
            data = allocator.allocate(other.allocated); // new T[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
    {
        return equals(other.const_pointer(), other.size());
    }
 
 
    bool operator != (const array<T, TAlloc>& other) const
    {
        return !(*this==other);
    }
 
 
    T& operator [](u32 index)
    {
        NIRT_DEBUG_BREAK_IF(index>=used) // access violation
 
        return data[index];
    }
 
 
    const T& operator [](u32 index) const
    {
        NIRT_DEBUG_BREAK_IF(index>=used) // access violation
 
        return data[index];
    }
 
 
    T& getLast()
    {
        NIRT_DEBUG_BREAK_IF(!used) // access violation
 
        return data[used-1];
    }
 
 
    const T& getLast() const
    {
        NIRT_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;
    }
 
 
 
    template <class E>
    s32 linear_search(const E& element) const
    {
        for (u32 i=0; i<used; ++i)
            if (data[i] == element)
                return (s32)i;
 
        return -1;
    }
 
 
 
    template <class E>
    s32 linear_reverse_search(const E& element) const
    {
        for (s32 i=used-1; i>=0; --i)
            if (data[i] == element)
                return i;
 
        return -1;
    }
 
 
 
    void erase(u32 index)
    {
        NIRT_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;
    }
 
    using allocator_type = TAlloc;
    using value_type = T;
    using size_type = u32;
 
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 nirt
 
#endif