Array.h

Go to the documentation of this file.

//
// Array.h
//
// Copyright (c) 2001-2008 Virtual Terrain Project
// Free for all uses, see license.txt for details.
//
#ifndef ARRAYH
#define ARRAYH

#ifdef _MSC_VER
  #pragma warning(disable: 4786)
  #pragma warning(disable: 4100)
    #if _DEBUG
      #define CRTDBG_MAP_ALLOC
      #include <crtdbg.h>
    #endif
#endif

#include <stdlib.h> // for free()
#include <memory.h> // for memcpy()
#include <assert.h> // for assert()

template <class E> class vtArray
{
public:
    vtArray(uint size = 0);
    vtArray(const vtArray<E>&);
    virtual ~vtArray();

//  Accessors
    uint    GetSize() const;
    uint    GetMaxSize() const;
    bool        SetSize(uint);
    bool        SetMaxSize(uint);
    uint    GetElemSize() const;
    E*          GetData() const;
    void        FreeData();
    bool        IsEmpty() const;
    E&          GetAt(uint i) const;
    bool        SetAt(uint i, E);

//  Other operations
    vtArray<E>& operator=(const vtArray<E>&);
    E&          operator[](uint i);
    const E&    operator[](uint i) const;
    void        Empty();
    bool        RemoveAt(uint i, int n = 1);
    int         Append(const E&);
    int         Append(const vtArray<E>&);
    int         Find(const E&) const;

protected:
//  Internal functions
    virtual bool    Grow(uint);
    virtual void    DestructItems(uint first, uint last);

//  Data members
    uint    m_Size;     // number of elements added so far
    uint    m_MaxSize;  // maximum number of elements we have room for
    E*              m_Data;     // data area for array
};


template <class E> vtArray<E>::vtArray(uint size)
{
    m_Size = 0;             // empty to start
    m_MaxSize = 0;          // remember the size
    m_Data = NULL;
    if (size > 0)           // make room for <size> elements
        Grow(size);
}

template <class E> void vtArray<E>::FreeData()
{
    Empty();
    if (m_Data)
        free(m_Data);
    m_Data = NULL;
    m_MaxSize = 0;
}

template <class E> vtArray<E>::vtArray(const vtArray<E>& a)
{
    if( this == &a )
        return;

    m_Size = 0;     // empty to start
    m_MaxSize = 0;  // remember the size
    m_Data = NULL;
    Append(a);      // copy each element from the given array
}


template <class E> inline void vtArray<E>::DestructItems(uint first, uint last)
{
    //VTLOG("base DestructItems, %d %d\n", start, nitems);
}


template <class E> inline vtArray<E>::~vtArray()
{
    //VTLOG("~vtArray, size %d, max %d\n", m_Size, m_MaxSize);
    Empty();
    free(m_Data);
    m_Data = NULL;
    m_MaxSize = 0;
}

template <class E> bool vtArray<E>::Grow(uint growto)
{
    int n = growto - m_MaxSize;
    E*      old_data;

    if (n >= 0)
    {
        if (m_Data == NULL)                 // make new data area?
        {
//          assert(m_Size == 0);
            m_Data = (E*) malloc(sizeof(E) * growto);
            if (m_Data == NULL)             // could not enlarge?
//              ERROR(("vtArray::Grow: out of memory"), false);
                return false;
        }
        else
        {
            if (growto < 4) growto = 4; // minimum growth
            old_data = m_Data;
            m_Data = (E*) malloc(sizeof(E) * (growto));
            memcpy(m_Data, old_data, sizeof(E) * m_Size);
            free(old_data);
            if (m_Data == NULL)
//              ERROR(("vtArray::Grow: out of memory"), false);
                return false;
        }
        m_MaxSize = growto;                 // remember new size
    }
    return true;
}

template <class E> inline E* vtArray<E>::GetData() const
{
    return m_Data;
}

template <class E> bool vtArray<E>::SetMaxSize(uint s)
{
    if (s > m_MaxSize)          // enlarge array
        return Grow(s);         // if we can
    return true;
}

template <class E> inline uint  vtArray<E>::GetMaxSize() const
    { return m_MaxSize; }

template <class E> inline uint  vtArray<E>::GetElemSize() const
    { return sizeof(E); }

template <class E> bool inline vtArray<E>::SetSize(uint s)
{
    assert(s >= 0);
    if (s > m_MaxSize)
        if (!Grow(s))
            return false;
    m_Size = s;
    return true;
}

template <class E> inline uint vtArray<E>::GetSize() const
    { return m_Size; }

template <class E> bool vtArray<E>::SetAt(uint i, E val)
{
    if (i >= m_MaxSize)         // need to extend array?
       {
        uint n = m_MaxSize;
        n += (n >> 1);          // grow to 1 1/2 times current size
        if (n <= i) n = i + 1;  // unless user wants more
        if (!Grow(n))           // extend failure
            return false;
       }
    m_Data[i] = val;
    if (i >= m_Size)            // enlarge array size if at end
        m_Size = i + 1;
    return true;
}

template <class E> inline E& vtArray<E>::GetAt(uint i) const
    { return m_Data[i]; }

template <class E> inline const E& vtArray<E>::operator[](uint i) const
    { return m_Data[i]; }

template <class E> inline E& vtArray<E>::operator[](uint i)
    { return m_Data[i]; }

template <class E> int vtArray<E>::Find(const E& elem) const
{
    const E* p = m_Data;

    for (uint i = 0; i < m_Size; ++i)   // look for matching element
        if (*p++ == elem)
            return i;                   // found it
    return -1;
}

template <class E> int inline vtArray<E>::Append(const E& v)
{
    int index = m_Size;

    if (!SetAt(index, v))
        return -1;
    return index;
}

template <class E> bool vtArray<E>::RemoveAt(uint i, int n)
{
    E*  elem;
    int shuffle;

    if ((i < 0) || (i >= m_Size))       // element out of range?
        return false;
    if (n == 0) n = 1;                  // default is one element
    shuffle = m_Size - (i + n);         // number to shuffle up
    elem = m_Data + i;
    memcpy(elem, elem + n, sizeof(E) * shuffle);
    m_Size -= n;
    return true;
}

template <class E> int vtArray<E>::Append(const vtArray<E>& src)
{
    int n = m_Size + src.m_Size;

    if (!Grow(n))
        return -1;
    for (uint i = 0; i < src.m_Size; ++i)
        m_Data[m_Size + i] = src.m_Data[i];
    m_MaxSize = n;
    m_Size += src.m_Size;
    return n - 1;
}

template <class E> void vtArray<E>::Empty()
{
    //VTLOG("Empty, size %d\n", m_Size);
    if (m_Size > 0)
        DestructItems(0, m_Size - 1);
    m_Size = 0;
}

template <class E> inline bool vtArray<E>::IsEmpty() const
    { return m_Size == 0; }

#endif