lldarray.h

Go to the documentation of this file.

#ifndef LL_LLDARRAY_H
#define LL_LLDARRAY_H

#include "llmath.h"
#include "llerror.h"

#include <vector>
#include <map>

// class LLDynamicArray<>; // = std::vector + reserves <BlockSize> elements
// class LLDynamicArrayIndexed<>; // = std::vector + std::map if indices, only supports operator[] and begin(),end()

//--------------------------------------------------------
// LLDynamicArray declaration
//--------------------------------------------------------
// NOTE: BlockSize is used to reserve a minimal initial amount
template <typename Type, int BlockSize = 32> 
class LLDynamicArray : public std::vector<Type>
{
public:
        enum
        {
                OKAY = 0,
                FAIL = -1
        };
        
        LLDynamicArray(S32 size=0) : std::vector<Type>(size) { if (size < BlockSize) std::vector<Type>::reserve(BlockSize); }

        void reset() { std::vector<Type>::resize(0); }

        // ACCESSORS
        const Type& get(S32 index) const                                { return std::vector<Type>::operator[](index); }
        Type&       get(S32 index)                                              { return std::vector<Type>::operator[](index); }
        S32                     find(const Type &obj) const;

        S32                     count() const                                           { return std::vector<Type>::size(); }
        S32                     getLength() const                                       { return std::vector<Type>::size(); }
        S32                     getMax() const                                          { return std::vector<Type>::capacity(); }

        // MANIPULATE
        S32         put(const Type &obj);                                       // add to end of array, returns index
//      Type*           reserve(S32 num);                                       // reserve a block of indices in advance
        Type*           reserve_block(U32 num);                 // reserve a block of indices in advance

        S32                     remove(S32 index);                              // remove by index, no bounds checking
        S32                     removeObj(const Type &obj);                             // remove by object
        S32                     removeLast();

        void            operator+=(const LLDynamicArray<Type,BlockSize> &other);
};

//--------------------------------------------------------
// LLDynamicArray implementation
//--------------------------------------------------------

template <typename Type,int BlockSize>
inline S32 LLDynamicArray<Type,BlockSize>::find(const Type &obj) const
{
        typename std::vector<Type>::const_iterator iter = std::find(this->begin(), this->end(), obj);
        if (iter != this->end())
        {
                return iter - this->begin();
        }
        return FAIL;
}


template <typename Type,int BlockSize>
inline S32 LLDynamicArray<Type,BlockSize>::remove(S32 i)
{
        // This is a fast removal by swapping with the last element
        S32 sz = this->size();
        if (i < 0 || i >= sz)
        {
                return FAIL;
        }
        if (i < sz-1)
        {
                this->operator[](i) = this->back();
        }
        this->pop_back();
        return i;
}

template <typename Type,int BlockSize>
inline S32 LLDynamicArray<Type,BlockSize>::removeObj(const Type& obj)
{
        typename std::vector<Type>::iterator iter = std::find(this->begin(), this->end(), obj);
        if (iter != this->end())
        {
                S32 res = iter - this->begin();
                typename std::vector<Type>::iterator last = this->end(); 
                --last;
                *iter = *last;
                this->pop_back();
                return res;
        }
        return FAIL;
}

template <typename Type,int BlockSize>
inline S32      LLDynamicArray<Type,BlockSize>::removeLast()
{
        if (!this->empty())
        {
                this->pop_back();
                return OKAY;
        }
        return FAIL;
}

template <typename Type,int BlockSize>
inline Type* LLDynamicArray<Type,BlockSize>::reserve_block(U32 num)
{
        U32 sz = this->size();
        this->resize(sz+num);
        return &(this->operator[](sz));
}

template <typename Type,int BlockSize>
inline S32      LLDynamicArray<Type,BlockSize>::put(const Type &obj) 
{
        this->push_back(obj);
        return this->size() - 1;
}

template <typename Type,int BlockSize>
inline void LLDynamicArray<Type,BlockSize>::operator+=(const LLDynamicArray<Type,BlockSize> &other)
{
        insert(this->end(), other.begin(), other.end());
}

//--------------------------------------------------------
// LLDynamicArrayIndexed declaration
//--------------------------------------------------------

template <typename Type, typename Key, int BlockSize = 32> 
class LLDynamicArrayIndexed
{
public:
        typedef typename std::vector<Type>::iterator iterator;
        typedef typename std::vector<Type>::const_iterator const_iterator;
        typedef typename std::vector<Type>::reverse_iterator reverse_iterator;
        typedef typename std::vector<Type>::const_reverse_iterator const_reverse_iterator;
        typedef typename std::vector<Type>::size_type size_type;
protected:
        std::vector<Type> mVector;
        std::map<Key, U32> mIndexMap;
        
public:
        LLDynamicArrayIndexed() { mVector.reserve(BlockSize); }
        
        iterator begin() { return mVector.begin(); }
        const_iterator begin() const { return mVector.begin(); }
        iterator end() { return mVector.end(); }
        const_iterator end() const { return mVector.end(); }

        reverse_iterator rbegin() { return mVector.rbegin(); }
        const_reverse_iterator rbegin() const { return mVector.rbegin(); }
        reverse_iterator rend() { return mVector.rend(); }
        const_reverse_iterator rend() const { return mVector.rend(); }

        void reset() { mVector.resize(0); mIndexMap.resize(0); }
        bool empty() const { return mVector.empty(); }
        size_type size() const { return mVector.size(); }
        
        Type& operator[](const Key& k)
        {
                typename std::map<Key, U32>::const_iterator iter = mIndexMap.find(k);
                if (iter == mIndexMap.end())
                {
                        U32 n = mVector.size();
                        mIndexMap[k] = n;
                        mVector.resize(n+1);
                        llassert(mVector.size() == mIndexMap.size());
                        return mVector[n];
                }
                else
                {
                        return mVector[iter->second];
                }
        }

        const_iterator find(const Key& k) const
        {
                typename std::map<Key, U32>::const_iterator iter = mIndexMap.find(k);
                if(iter == mIndexMap.end())
                {
                        return mVector.end();
                }
                else
                {
                        return mVector.begin() + iter->second;
                }
        }
};

#endif

---