base_types_array.hh

Go to the documentation of this file.

/*
 * LEGAL:   COPYRIGHT (C) 2007 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
 *****************************************************************************/

#ifndef BASE_TYPES_ARRAY_HH
#define BASE_TYPES_ARRAY_HH 1

#include "base_shared_ptr.hh"
#include "base_types.hh"
#include "base_types2.hh"
#include "base_funcs2.hh"

namespace base {

//==============================================================================
//==============================================================================
//                    Virtual methods forbidden in this section
//==============================================================================
//==============================================================================

// Basic types must be fast, prevent them having virtual functions.
#define virtual VIRTUAL_METHODS_IN_BASIC_TYPES_IS_TOO_SLOW

template<typename T>
class Array : public Shared
{

public:
    typedef T Type;
    // Writing new elements is restricted to push_back().
    Array( void ) { }
    // Writing new elements can be done by operator[].
    explicit Array( uint cnt ) { ASSERT( cnt < MAX_ELEMS ); mVector.resize( cnt ); }
    ~Array() { }
    T*                PTR( void ) const { return const_cast<T*>( &mVector[0] ); }
    const T*    CONST_PTR( void ) const { return &mVector[0]; }
    T&          operator[]( uint i )       { ASSERT( i < mVector.size() ); return mVector[i]; }
    const T&    operator[]( uint i ) const { ASSERT( i < mVector.size() ); return mVector[i]; }
    void        push_back( const T& v ) { mVector.push_back( v ); }
    bool        empty( void ) const { return mVector.empty(); }
    void        clear( void ) { mVector.clear(); }
    uint        size( void ) const  { return mVector.size(); }
    void        resize( uint cnt )  { mVector.resize( cnt ); }  // immediate reallocation
    void        reserve( uint cnt ) { mVector.reserve( cnt ); }  // just a hint for allocator
    friend bool operator<( const Array& a, const Array& b ) { return a.mVector < b.mVector; }

//  typedef STLIterator<T,vector<T> > Iterator;
//  Iterator    GetIterator( void ) const { return Iterator( mVector ); }

private:
    vector<T>           mVector;
    CLASS_CONST uint    MAX_ELEMS = 20 * MILLION;
};

template<uint CNT, typename T=int>
class TinyArray
{
public:
    typedef T Type;  // type of element

public:
    TinyArray( void )
    {
        // NOP
    }

    explicit TinyArray( const T val )
    {
        Fill( val );
    }

    TinyArray( const TinyArray<CNT,T>& src )
    {
        *this = src;  // invoke operator=()
    }

    // Copy constructor from a C array.
    // This syntax, which would be convenient, the compiler won't accept: TinyArray<> = { };
    TinyArray( const T src[] )
    {
        for ( uint i = 0; i < CNT; ++i )
            mArray[i] = src[i];         
    }

    uint GetCnt( void ) const
    {
        return CNT;
    }

    void Fill( T val )
    {
        for ( uint i = 0; i < CNT; ++i )
            mArray[i] = val;
    }

    T& operator[]( uint i )                 // compiled unless TinyArray is const
    {
        ASSERT( i < CNT );
        return mArray[i];
    }

    const T& operator[]( uint i ) const     // compiled if TinyArray is const
    {
        ASSERT( i < CNT );
        return mArray[i];
    }

    TinyArray<CNT,T>& operator=( const TinyArray<CNT,T>& src )
    {
        for ( uint i = 0; i < CNT; ++i )
            mArray[i] = src.mArray[i];  // assign
        return *this;
    }

    bool operator==( const TinyArray<CNT,T>& src ) const
    {
        for ( uint i = 0; i < CNT; ++i )
            if ( mArray[i] != src.mArray[i] ) return false; // different
        return true; // all elements equal
    }

    bool operator!=( const TinyArray<CNT,T>& src ) const
    {
        // Same as operator==() but retvals opposite.
        for ( uint i = 0; i < CNT; ++i )
            if ( mArray[i] != src.mArray[i] ) return true; // different
        return false; // all elements equal
    }

    bool operator<( const TinyArray<CNT,T>& src ) const
    {
        for ( uint i = 0; i < CNT; ++i )
        {
            if ( mArray[i] < src.mArray[i] )
                return true;
            else if ( src.mArray[i] < mArray[i] )  // swapping operands substitutes greater than
                return false;
            // continue, at this point, only know a subset is equal
        }
        return false; // all elements equal
    }

    // These are dangerous: overrunning TinyArray will corrupt call stack!
    T*             PTR( void ) const { return const_cast<T*>(mArray); }
    const T* CONST_PTR( void ) const { return mArray; }

    uint size( void ) const
    {
        return CNT;
    }

    bool empty( void ) const
    {
        return false;  // always has CNT elements
    }

private:
    T   mArray[CNT];
};

template<uint CNT, typename T>
bool operator<( const TinyArray<CNT,T>& a1,
                const TinyArray<CNT,T>& a2 )
{
    return a1.operator<( a2 );  // yuck
}

template<uint FIXED_SIZE, typename T=int>
class SmallArray
{
public:
    typedef T Type;  // type of element

public:
    SmallArray( const uint varSize = 0 )
    :   mVarSize(varSize)
    {
        // NOP
    }

    SmallArray( const SmallArray<FIXED_SIZE,T>& src )
    {
        *this = src;  // invoke operator=()
    }

    T& operator[]( uint i )                 // compiled unless const
    {
    ASSERT( (i < mVarSize) && (i < FIXED_SIZE) );
        return mArray[i];
    }

    const T& operator[]( uint i ) const     // compiled if const
    {
    ASSERT( (i < mVarSize) && (i < FIXED_SIZE) );
        return mArray[i];
    }

    SmallArray<FIXED_SIZE,T>& operator=( const SmallArray<FIXED_SIZE,T>& src )
    {
        mVarSize = src.mVarSize;                    // assign variable-size
        for ( uint i = 0; i < src.mVarSize; ++i )   // copying all elements isn't necessary
            mArray[i] = src.mArray[i];
        return *this;
    }

    bool operator==( const SmallArray<FIXED_SIZE,T>& src ) const
    {
        if ( mVarSize == src.mVarSize )
        {
            for ( uint i = 0; i < mVarSize; ++i )
                if ( mArray[i] != src.mArray[i] ) return false;  // different
            return true;  // all elements equal
        }
        else
        {
            return false;  // different sizes
        }
    }

    bool operator!=( const SmallArray<FIXED_SIZE,T>& src ) const
    {
        return not (*this == src);
    }

    bool operator<( const SmallArray<FIXED_SIZE,T>& src ) const
    {
        if ( mVarSize < src.mVarSize )
        {
            return true;
        }
        else  // same size
        {
            for ( uint i = 0; i < mVarSize; ++i )
            {
                if ( mArray[i] < src.mArray[i] )
                    return true;
                else if ( src.mArray[i] < mArray[i] )  // swapping operands substitutes greater than
                    return false;
                // continue, at this point, only know a subset is equal
            }
            return false;  // all elements equal
        }
    }

    // These are dangerous: overrunning SmallArray will corrupt call stack!
    T*             PTR( void ) const { return const_cast<T*>(mArray); }
    const T* CONST_PTR( void ) const { return mArray; }

    uint size( void ) const
    {
        return mVarSize;
    }

    void resize( const uint varSize )
    {
    ASSERT( varSize < FIXED_SIZE );

        mVarSize = varSize;
    }

    void clear( void )
    {
        mVarSize = 0;
    }

    bool empty( void ) const
    {
        return mVarSize == 0;
    }

    void push_back( T item )
    {
    ASSERT( mVarSize < FIXED_SIZE );

        mArray[mVarSize++] = item;
    }

private:
    uint    mVarSize;
    T       mArray[FIXED_SIZE];
};

template<uint FIXED_SIZE, typename T>
bool operator<( const SmallArray<FIXED_SIZE,T>& a1,
                const SmallArray<FIXED_SIZE,T>& a2 )
{
    return a1.operator<( a2 );  // phooey
}

template<typename T,typename CONTAINER=vector<T> >
class SortedArray
{

public:
    typedef T Type;  // type of element

    // Non-const operator is omitted intentionally.
    SortedArray( const uint size_ = 0 )
    :   mArray(size_)
    {
        SET_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    }

    SortedArray( const SortedArray<T>& src )
    :   mArray(src.mArray)
    {
        SET_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    }

    ~SortedArray()
    {
        INVALIDATE_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    }

    const T& operator[]( uint i ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    ASSERT( i < mArray.size() );

        return mArray[i];
    }

    SortedArray<T>& operator=( const SortedArray<T>& src )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    CHECK_TYPESIG(&src,TYPESIG_SORTED_ARRAY);

        mArray = src.mArray; return *this;
    }

    bool operator==( const SortedArray<T>& src ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    CHECK_TYPESIG(&src,TYPESIG_SORTED_ARRAY);

        return mArray == src.mArray;
    }

    bool operator!=( const SortedArray<T>& src ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    CHECK_TYPESIG(&src,TYPESIG_SORTED_ARRAY);

        return mArray != src.mArray;
    }

    bool operator<( const SortedArray<T>& src ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    CHECK_TYPESIG(&src,TYPESIG_SORTED_ARRAY);

        return mArray < src.mArray;
    }

    // Limited STL compatibility. push_back() make no sense for SortedArray.
    uint size( void ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        return mArray.size();
    }

    void resize( const uint size_ )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        mArray.resize( size_ );
    }

    void clear( void )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        mArray.clear();
    }

    bool empty( void ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        return mArray.empty();
    }

    pair<bool,uint> find( const T item ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        if ( mArray.empty() )
        {
            return make_pair<bool,uint>( false, 0xb00bb00b );
        }
        else if ( mArray.front() == item )
        {
            return make_pair<bool,uint>( true, 0 );
        }
        else if ( mArray.back() == item )
        {
            return make_pair<bool,uint>( true, mArray.size()-1 );
        }
        else if ( (mArray.front() < item) && (item < mArray.back()) )
        {
            int a = 0;                   // idx of first
            int z = int(mArray.size());  // idx of end (in STL terms)
            while ( z - a > 1 )
            {
              //int m = a + ((z - a) >> 1);  // midpoint
                int m = (a + z) >> 1;        // average is equivalent but faster
                ASSERT( uint(m) < uint(mArray.size()) );
                if ( item < mArray[m] )
                {
                    z = m;
                }
                else if ( mArray[m] < item )  // item > mArray[m]
                {
                    a = m;
                }
                else // item == mArray[m]
                {
                    return make_pair<bool,uint>( true, m );
                }
            }
            // not found
            return make_pair<bool,uint>( false, 0xb00bb00b );
        }
        else  // item is less than or greater than all others
        {
            return make_pair<bool,uint>( false, 0xb00bb00b );
        }
    }

    pair<bool,uint> find_first( const T item ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        pair<bool,uint> match = find( item );
        if ( match.first )
        {
            // Scan BACKWARD for the FIRST equal element.
            // match.second was index of WHICHEVER equal match.
            while ( (int(match.second)-1 > 0) && (mArray[match.second-1] == item) )
                --match.second;  // ^^ signed int in case match.second was 0
        }
        return match;
    }

    pair<bool,uint> find_last( const T item ) const
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        pair<bool,uint> match = find( item );
        if ( match.first )
        {
            // Scan FORWARD for the LAST equal element.
            // match.second was index of WHICHEVER equal match.
            while ( (match.second+1 < mArray.size()) && (mArray[match.second+1] == item) )
                ++match.second;
        }
        return match;
    }

    uint insert_last( const T item )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        // upper_bound() is used with insertion so that a new item will follow older equal items.
        // distance() is called before before insert() which invalidates iterators.

        typename CONTAINER::iterator iter = std::upper_bound( mArray.begin(), mArray.end(), item );
        const uint idx = std::distance( mArray.begin(), iter );

        mArray.insert( iter, item );  // invalidates iter!

        return idx;
    }

    void remove_idx( const uint idx )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);
    ASSERT( idx < mArray.size() );

        mArray.erase( mArray.begin() + idx );  // iterator arithmetic
    }

    pair<bool,uint> remove_first( const T item )
    {
    CHECK_TYPESIG(this,TYPESIG_SORTED_ARRAY);

        const pair<bool,uint> match = find_first( item );
        if ( EX( match.first ) )
        {
        ASSERT( match.second < mArray.size() );  // check idx
            mArray.erase( mArray.begin() + match.second );  // iterator arithmetic
        }
        return match;
    }

private:
    CONTAINER   mArray;
public:
    
};

template<typename T,T* TEMP, uint TEMP_SIZE>  // amazing that a C++ compiler will accept this
class TempArray : public NonThreadable, public Shared
{
public:
    typedef T Type;
                TempArray( void ) : mSize(0) { }
    explicit    TempArray( uint cnt ) : mSize(cnt) { }
                ~TempArray() { }  // leave allocated
    T*                PTR( void ) const     { ASSERT( mSize > 0 ); return const_cast<T*>(TEMP); }
    const T*    CONST_PTR( void ) const     { ASSERT( mSize > 0 ); return TEMP; }
    T&          operator[]( uint i )        { ASSERT( i < mSize ); return TEMP[i]; }
    const T&    operator[]( uint i ) const  { ASSERT( i < mSize ); return TEMP[i]; }
    void        push_back( const T& val )   { ASSERT( mSize < TEMP_SIZE ); TEMP[mSize++] = val; }
    uint        empty( void ) const         { return mSize == 0; }
    uint        size( void ) const          { return mSize; }
    void        resize( uint cnt )          { ASSERT( cnt < TEMP_SIZE ); mSize = cnt; }
    void        reserve( UNUSED uint cnt )  { }
private:
    uint        mSize;  // current number of elements in this array
};

template<typename T,typename BASE=Void>  // optionally, BASE can be Shared
class Array2D : public BASE
{

public:
    Array2D( void )
    :   mSx(0), mSy(0), mVec()
    {
    }

    Array2D( int sx, int sy )
    {
        resize( sx, sy );
    }

    ~Array2D()
    {
    }

    void clear( void )
    {
        mSx = mSy = 0;
        mVec.clear();
    }

    void resize( int sx, int sy )
    {
    ASSERT( (sx > 0) && (sy > 0) );  // prevent mSx-1 overflowing

        mSx = sx;
        mSy = sy;
        mVec.resize( sx * sy );

    ASSERT( mVec.size() < base::defs::MAX_ELEMS );
    }

    uint size( void ) const
    {
        return mVec.size();
    }

    uint GetIdx( int x, int y ) const
    {
        // Clamp the 2D indexs in range {0,..,size-1}.
        x = Clamp( x, mSx-1 );
        y = Clamp( y, mSy-1 );

        // Compute flat index into underlying array.
        // Formula follows from this order of "for" loops.
        // Each x has to fully iterate y, hence, (x * mSy).
        // for ( x = 0; x < mSx; ++x )
        // for ( y = 0; y < mSy; ++y )

        const uint idx = (x * mSy) + y;
        ASSERT( idx < mVec.size() );
        return idx;
    }

    // Access element by 2D coordinates.  Can be used to write to element.
    T& Get( int x, int y )
    {
        return mVec[GetIdx(x,y)];
    }

    const T& Get( int x, int y ) const
    {
        return mVec[GetIdx(x,y)];
    }

    // Access element by flat index.
    T& operator[]( uint i )
    {
    ASSERT( i < mVec.size() );
        return mVec[i];
    }

    const T& operator[]( uint i ) const
    {
    ASSERT( i < mVec.size() );
        return mVec[i];
    }

public:
    int         mSx;    
    int         mSy;    
    vector<T>   mVec;
};

#undef virtual

} // namespace base

#endif // BASE_TYPES_ARRAY_HH

Palomino 3D Engine documents generated by doxygen 1.5.3 on Fri Nov 23 11:26:07 2007