UT/UT_RefArray.C

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Cristin Barghiel
 *      Side Effects Software Inc.
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        Utility Library (C++)
 *
 * COMMENTS:
 *      This is a class template that implements a resizable array of 
 *      arbitrary objects. The template parameter represents the type
 *      of object, and is called utRef. You cna instantiate this class
 *      with any object or pointer, such as:
 *              UT_RefArray<int>                iObj;
 *              UT_RefArray<GeoPrimMesh>        mObj;
 *              UT_RefArray<GeoPoint*>  pObj; ... etc
 *      The "Ref" in the class name stands for "passed by reference", which 
 *      is the argument passing strategy used by this class. Use this class
 *      if you want to construct arrays of arbitrary objects. Pointers and
 *      primitive types are stored and passed more efficiently in another
 *      class, UT_PtrArray, which passes arguments by value to avoid the
 *      referencing overhead.
 */

#ifndef __UT_RefArray_C__
#define __UT_RefArray_C__
 
#include <stdio.h>
#include <stdlib.h>
#include <new.h>
#include "UT_Assert.h"
#include "UT_RefArray.h"

template <class utRef>
UT_RefArray<utRef>::UT_RefArray(unsigned int sz, unsigned int count)
: arrSize(sz)
{
    arr = (sz) ? (utRef*)calloc(sizeof(utRef), sz) : 0;

    if (sz         < count) count = sz;
    if (nbrEntries = count)
        for (int i = 0; i < nbrEntries; i++)
            new (&arr[i]) utRef();
}

template <class utRef>
UT_RefArray<utRef>::UT_RefArray(const UT_RefArray<utRef> &a)
: arrSize(a.entries()), nbrEntries(a.entries())
{
    unsigned int en =  a.entries();
    arr = (en) ? (utRef*)calloc(sizeof(utRef), en) : 0; 
    for (unsigned int i = 0; i < en; i++)
    {
        new (&arr[i]) utRef(); // make sure it starts clean
        arr[i] = a(i);
    }
}

template <class utRef>
UT_RefArray<utRef>::~UT_RefArray(void)  
{ 
    resize(0);
}

template <class utRef>
void
UT_RefArray<utRef>::swap( UT_RefArray<utRef> &other )
{
    UTswap( arr, other.arr );
    UTswap( arrSize, other.arrSize );
    UTswap( nbrEntries, other.nbrEntries );
}


template <class utRef>
unsigned int    
UT_RefArray<utRef>::insert(unsigned int iindex)
{
    if (iindex >= nbrEntries)
    {
        if (iindex >= arrSize) resize(bumpAlloc(iindex));

        for (unsigned t = nbrEntries; t <= iindex; t++)
            new (&arr[t]) utRef();

        nbrEntries = iindex+1;
        return iindex;
    }
    if (nbrEntries == arrSize)  // we know arr has been allocated
    {
        arrSize = bumpAlloc(arrSize);
        arr = (utRef*)realloc(arr, arrSize*sizeof(utRef));
        UT_ASSERT(arr);
    }
    memmove(&arr[iindex+1], &arr[iindex],((nbrEntries-iindex)*sizeof(utRef)));
    new (&arr[iindex]) utRef();
     
    nbrEntries++;
    return iindex;
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::append(const utRef& t)
{
    if (nbrEntries == arrSize) 
    {
        if (arr <= &t && &t <= arr+nbrEntries)
        {
            utRef save; save = t;  // don't make me define a copy ctor for utRef
            resize(bumpAlloc(arrSize));
            new (&arr[nbrEntries]) utRef();
            arr[nbrEntries] = save;
        }
        else
        {
            resize(bumpAlloc(arrSize));
            new (&arr[nbrEntries]) utRef();
            arr[nbrEntries] = t;
        }
    }
    else
    {
        new (&arr[nbrEntries]) utRef();
        arr[nbrEntries] = t;
    }

    return nbrEntries++;
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::append(const utRef& t, unsigned short dupliCheck)
{
    int idx = -1;
    if (dupliCheck && ((idx = find(t)) != -1)) return (unsigned int)idx;
    return append( t );
}

template <class utRef>
unsigned int            
UT_RefArray<utRef>::insert(const utRef& t, unsigned int  iindex)
{
    // if (iindex == nbrEntries) append(t, dupliCheck);
    return insertAt(t, iindex);
}

template <class utRef>
unsigned int            
UT_RefArray<utRef>::insert(const utRef& t, unsigned int  iindex,
                           unsigned short dupliCheck)
{
    // if (iindex == nbrEntries) append(t, dupliCheck);
    int idx = -1;
    return (dupliCheck && ((idx=find(t)) != -1)) ? (unsigned int)idx
                                                 :  insertAt(t, iindex);
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::append(const utRef& t, Comparator compare)
{
    int idx = -1;
    if ((idx=find(t, compare)) != -1) return (unsigned int)idx;
    if (nbrEntries == arrSize) 
    {
        if (arr <= &t && &t <= arr+nbrEntries)
        {
            utRef save; save = t;  // don't make me define a copy ctor for utRef
            resize(bumpAlloc(arrSize));
            new (&arr[nbrEntries]) utRef();
            arr[nbrEntries] = save;
        }
        else
        {
            resize(bumpAlloc(arrSize));
            new (&arr[nbrEntries]) utRef();
            arr[nbrEntries] = t;
        }
    }
    else
    {
        new (&arr[nbrEntries]) utRef();
        arr[nbrEntries] = t;
    }

    return nbrEntries++;
}

template <class utRef>
unsigned int            
UT_RefArray<utRef>::insert(const utRef& t, unsigned int iindex,
                           Comparator compare)
{
    // if (iindex == nbrEntries) append(t, compare);
    int idx = -1;
    return ((idx=find(t, compare)) != -1) ? (unsigned int)idx
                                          :  insertAt(t, iindex);
}

template <class utRef>
unsigned int            
UT_RefArray<utRef>::sortedInsert(const utRef& t, Comparator compare)
{
    int          lo, mid, hi, half, num;

    lo = 0;
    hi = entries();
    num = entries();

    while( lo < hi )
    {
        half = (hi - lo) / 2;
        mid = lo + half;
        if( compare(&t, &arr[mid]) > 0 )
            lo = mid + 1;
        else
            hi = mid;
    }
    
    return insertAt(t, hi);
}

// this code is from UT_PtrArrayRaw, ultimately from STL
template <class utRef>
void
UT_RefArray<utRef>::sortedUnion( const UT_RefArray<utRef> &other,
        UT_RefArray<utRef> &result,
        Comparator compare
        ) const
{
    utRef       *first1 = arr;
    utRef       *last1 = arr + nbrEntries;
    utRef       *first2 = other.arr;
    utRef       *last2 = other.arr + other.nbrEntries;

    // Can't store to either input.
    UT_ASSERT(&result != this && &result != &other);
    UT_ASSERT(result.entries() == 0);

    while( first1 != last1 && first2 != last2 )
    {
        if( compare(first1, first2) < 0 )
        {
            result.append( *first1 );
            ++first1;
        }
        else if( compare(first2, first1) < 0 )
        {
            result.append( *first2 );
            ++first2;
        }
        else
        {
            result.append( *first1 );
            ++first1;
            ++first2;
        }
    }
    while( first1 != last1 )
    {
        result.append( *first1 );
        ++first1;
    }
    while( first2 != last2 )
    {
        result.append( *first2 );
        ++first2;
    }
}

template <class utRef>
unsigned int
UT_RefArray<utRef>::heapPush(const utRef &t, Comparator compare)
{
    int     i = append(t);

    while( i > 0 && compare(&arr[i / 2], &t) < 0 )
    {
        arr[i] = arr[i / 2];
        i = i / 2;
    }
    arr[i] = t;
    return i;
}

template <class utRef>
void
UT_RefArray<utRef>::heapPop(Comparator compare)
{
    UT_ASSERT_P(nbrEntries > 0);
    if( nbrEntries > 0 )
    {
        arr[0] = arr[nbrEntries - 1];
        removeAt(nbrEntries - 1);
        heapify(0, compare);
    }
    return;
}

template <class utRef>
unsigned int
UT_RefArray<utRef>::concat(const UT_RefArray<utRef> &a)
{
    unsigned int old_entries;
    unsigned int i;

    old_entries = nbrEntries;
    multipleInsert(nbrEntries, a.nbrEntries);

    for ( i = 0; i < a.nbrEntries ; i++ )
        arr[old_entries + i] = a.arr[i];

    return nbrEntries;
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::multipleInsert(unsigned int iindex, unsigned int count)
{
    unsigned bigindex = iindex+count;
    unsigned t;

    if (iindex >= nbrEntries)
    {
        if (bigindex >= arrSize) resize(bumpAlloc(bigindex));

        for (t = nbrEntries; t <= bigindex; t++)
            new (&arr[t]) utRef();

        nbrEntries = bigindex;
        return iindex;
    }
    if ((nbrEntries + count) > arrSize)  // we know arr has been allocated
    {
        resize(bumpAlloc(nbrEntries+count));
        UT_ASSERT(arr);
    }
    memmove(&arr[bigindex], &arr[iindex],((nbrEntries-iindex)*sizeof(utRef)));
    
    nbrEntries += count;

    for (t = count; t-- > 0;)
        new (&arr[iindex+t]) utRef();
     
    return iindex;
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::insertAt(const utRef &t, unsigned int iindex)
{
    const utRef *save;
    if (&arr[iindex] <= &t && &t <= &arr[arrSize-1])
    {
        utRef tCopy; tCopy = t;  // don't make me define a copy ctor for utRef
        save = &tCopy;
    }
    else
        save = &t;

    if (iindex >= nbrEntries)
    {
        int i;
        
        if (iindex >= arrSize) resize(bumpAlloc(iindex));
        for (i = nbrEntries; i <= iindex; i++)
            new (&arr[i]) utRef();
        nbrEntries = iindex+1;
        arr[iindex] = *save;
        return iindex;
    }
    if (nbrEntries == arrSize) 
    {
        // arrSize++;
        arrSize = bumpAlloc(arrSize);
        arr = (utRef*)realloc(arr, arrSize*sizeof(utRef));
        UT_ASSERT(arr);
    }
    memmove(&arr[iindex+1], &arr[iindex],((nbrEntries-iindex)*sizeof(utRef)));

    new (&arr[iindex]) utRef();
    arr[iindex] = *save;

    nbrEntries++;
    return iindex;
}

template <class utRef>
int             
UT_RefArray<utRef>::remove(const utRef& t)
{
    int idx = find(t);
    return (idx < 0) ? -1 : removeAt((unsigned int)idx);
}

template <class utRef>
int             
UT_RefArray<utRef>::remove(const utRef& t, unsigned short dupliCheck)
{
    int idx = find(t);
    return (idx < 0) ? -1 : removeAt((unsigned int)idx, dupliCheck);
}

template <class utRef>
int
UT_RefArray<utRef>::removeAt(unsigned int idx)
{
    arr[idx].~utRef();
    if (idx != --nbrEntries)
        memmove(&arr[idx], &arr[idx+1], ((nbrEntries-idx)*sizeof(utRef)));

    return (int)idx;
}


template <class utRef>
int
UT_RefArray<utRef>::removeAt(unsigned int idx, unsigned short dupliCheck)
{
    if (dupliCheck)
    {
        const utRef &rem = arr[idx];
        unsigned int *gapArr = new unsigned int[nbrEntries];
        UT_ASSERT(gapArr);
        int  gapCnt = 0;
        for (unsigned int i = 0; i < nbrEntries; i++)
            if (arr[i] == rem) gapArr[gapCnt++] = i;
        for (int g = gapCnt-1; g >= 0; g--, nbrEntries--)
        {
            unsigned int rmIdx = gapArr[g];
            arr[rmIdx].~utRef();
            if (rmIdx != nbrEntries)
                memmove(&arr[rmIdx], &arr[rmIdx+1],
                        ((nbrEntries-rmIdx-1)*sizeof(utRef)));
        }
        delete [] gapArr;
    }
    else
    {
        idx = removeAt( idx );
    }
    
    return (int)idx;
}

template <class utRef>
int             
UT_RefArray<utRef>::remove(const utRef& t, Comparator compare,
                           unsigned short dupliCheck)
{
    int idx = find(t, compare);
    return (idx < 0) ? -1 : removeAt((unsigned int)idx, compare, dupliCheck);
}

template <class utRef>
int             
UT_RefArray<utRef>::removeAt(unsigned int idx, Comparator compare,
                             unsigned short dupliCheck)
{
    if (dupliCheck)
    {
        const utRef &rem = arr[idx];
        int *gapArr = new int[nbrEntries];
        UT_ASSERT(gapArr);
        int  gapCnt = 0;
        for (unsigned int i = 0; i < nbrEntries; i++)
            if (!compare(&arr[i],&rem)) gapArr[gapCnt++] = i;
        for (int g = gapCnt-1; g >= 0; g--, nbrEntries--)
        {
            unsigned int rmIdx = gapArr[g];
            arr[rmIdx].~utRef();
            if (rmIdx != nbrEntries)
                memmove(&arr[rmIdx], &arr[rmIdx+1],
                        ((nbrEntries-rmIdx)*sizeof(utRef)));
        }
        delete [] gapArr;
    }
    else
    {
        arr[idx].~utRef();
        if (idx != --nbrEntries)
            memmove(&arr[idx], &arr[idx+1], ((nbrEntries-idx)*sizeof(utRef)));
    }

    return idx;
}

template <class utRef>
int
UT_RefArray<utRef>::shift(unsigned int srcIdx, unsigned int destIdx,
                          unsigned int howMany)
{
    if (srcIdx == destIdx) return 0;
    unsigned int sIdx = srcIdx  + howMany - 1;
    unsigned int dIdx = destIdx + howMany - 1;
    if (sIdx>=arrSize   || dIdx>=arrSize) return -1;
    if (dIdx>=nbrEntries|| (sIdx==nbrEntries-1 && sIdx > dIdx))
        nbrEntries = dIdx+1;
        
    memmove(&arr[destIdx], &arr[srcIdx],  (howMany*sizeof(utRef)));
    return 0;
}

template <class utRef>
void
UT_RefArray<utRef>::move(int srcIdx, int destIdx, int howMany)
{
    // Make sure all the parameters are valid.
    if( srcIdx < 0 )
        srcIdx = 0;
    if( destIdx < 0 )
        destIdx = 0;
    // If we are told to move a set of entries that would extend beyond the
    // end of the current array, trim the group.
    if( srcIdx + howMany > entries() )
        howMany = entries() - srcIdx;
    // If the destIdx would have us move the source beyond the end of the
    // current array, move the destIdx back.
    if( destIdx + howMany > entries() )
        destIdx = entries() - howMany;
    if( srcIdx != destIdx && howMany > 0 )
    {
        utRef           *tmp = 0;
        unsigned int     savelen;

        savelen = abs(srcIdx - destIdx);
        tmp = (utRef *)calloc(savelen, sizeof(utRef));
        if( srcIdx > destIdx && howMany > 0 )
        {
            // We're moving the group backwards. Save all the stuff that
            // we would overwrite, plus everything beyond that to the
            // start of the source group. Then move the source group, then
            // tack the saved data onto the end of the moved group.
            memcpy(tmp, &arr[destIdx],  (savelen*sizeof(utRef)));
            memmove(&arr[destIdx], &arr[srcIdx], (howMany*sizeof(utRef)));
            memcpy(&arr[destIdx+howMany], tmp, (savelen*sizeof(utRef)));
        }
        if( srcIdx < destIdx && howMany > 0 )
        {
            // We're moving the group forwards. Save from the end of the
            // group being moved to the end of the where the destination
            // group will end up. Then copy the source to the destination.
            // Then move back up to the original source location and drop
            // in our saved data.
            memcpy(tmp, &arr[srcIdx+howMany],  (savelen*sizeof(utRef)));
            memmove(&arr[destIdx], &arr[srcIdx], (howMany*sizeof(utRef)));
            memcpy(&arr[srcIdx], tmp, (savelen*sizeof(utRef)));
        }
        free(tmp);
    }
}

template <class utRef>
void
UT_RefArray<utRef>::cycle(int howMany)
{
    char  *tempPtr;
    int    numShift;            //  The number of items we shift
    int    theRest;             //  nbrEntries - numShift

    if (howMany == 0 || nbrEntries < 1) return;

    numShift = howMany % (int)nbrEntries;
    if (numShift < 0) numShift += (int)nbrEntries;
    theRest = (int)nbrEntries - numShift;
    tempPtr = new char [numShift * sizeof(utRef)];

    memmove(tempPtr,        &arr[theRest],  (numShift * sizeof(utRef)));
    memmove(&arr[numShift], &arr[0],        (theRest  * sizeof(utRef)));
    memmove(&arr[0],        tempPtr,        (numShift * sizeof(utRef)));

    delete [] tempPtr;
}

template <class utRef>
int
UT_RefArray<utRef>::find(const utRef &t, unsigned int s) const
{
    int idx;
    for (idx = (int)s; ((unsigned)idx) < nbrEntries; idx++)
        if (arr[idx] == t) return idx;

    return (int)-1;
}

template <class utRef>
int
UT_RefArray<utRef>::find(const utRef &t, Comparator compare,
                         unsigned int s) const
{
    if (!nbrEntries) return -1;
    utRef *match = (utRef*) bsearch((const void*)&t, arr+s, nbrEntries, 
                            sizeof(utRef), (ut_ptr_compare_func_t)compare);
    return (match) ? match-arr : (int)-1;
}

template <class utRef>
int
UT_RefArray<utRef>::find(void *any, Comparator compare,
                         unsigned int s) const
{
    if (!nbrEntries) return -1;
    utRef *match = (utRef*) bsearch(any, arr+s, nbrEntries, 
                            sizeof(utRef), (ut_ptr_compare_func_t)compare);
    return (match) ? match-arr : (int)-1;
}

template <class utRef>
void            
UT_RefArray<utRef>::sort(Comparator compare)
{
    qsort(arr, nbrEntries, sizeof(utRef), (ut_ptr_compare_func_t)compare);
}

template <class utRef>
void            
UT_RefArray<utRef>::resize(unsigned int sz, unsigned short )
{
    if (sz == arrSize)
        return;

    if (sz == 0)
    {
        if (arr)
        {
            for( unsigned i = 0; i < nbrEntries; i++ )
                arr[i].~utRef();
            free(arr);
        }
        arr     = 0;
        arrSize = nbrEntries = 0;
        return; 
    }

    if (sz < nbrEntries)
    {
        for( unsigned i = sz; i < nbrEntries; i++ )
            arr[i].~utRef();
        nbrEntries = sz;
    }

    if( arr )
    {
        arr = (utRef*)realloc(arr, sz*sizeof(utRef));
        // We do not need to clear the new memory since we
        // did an inplace new that will do the right thing
        // for ints, floats, etc.
    }
    else
        arr = (utRef*)calloc(sizeof(utRef), sz);

    arrSize = sz;
    UT_ASSERT(arr);
}

template <class utRef>
void            
UT_RefArray<utRef>::entries(unsigned int ne)
{
    UT_ASSERT(ne <= arrSize);
    if( nbrEntries > ne )
    {
        for( int i = ne; i < nbrEntries; i++ )
            arr[i].~utRef();
    }
    else if( nbrEntries < ne )
    {
        for( int i = nbrEntries; i < ne; i++ )
            new (&arr[i]) utRef();
    }
    nbrEntries = ne;
}

/*
template <class utRef>
utRef   &
UT_RefArray<utRef>::operator()(unsigned int i)
{
    if (i >= nbrEntries)
    {
        for (int t = nbrEntries; t <= i; t++)
            new (&arr[t]) utRef();
        nbrEntries = i+1;
    }
    return arr[i];
}
*/

template <class utRef>
utRef   &
UT_RefArray<utRef>::operator[](unsigned int i)
{
    if (i >= arrSize   ) resize(i+1);
    if (i >= nbrEntries)
    {
        for (unsigned t = nbrEntries; t <= i; t++)
            new (&arr[t]) utRef();
        nbrEntries = i+1;
    }
    return arr[i];
}

template <class utRef>
UT_RefArray<utRef> &
UT_RefArray<utRef>::operator=(const UT_RefArray<utRef> &a)
{
    if (this == &a) return *this;

    // Grow the raw array if necessary.
    resizeIfNeeded( a.entries() );

    // Make sure destructors and constructors are called on all elements
    // being removed/added.
    entries(a.entries());

    // The = operator will clean up existing elements.
    for (unsigned int i = 0; i < a.entries(); i++)
        arr[i] = a(i);

    return *this;
}

template <class utRef>
int
UT_RefArray<utRef>::operator==(const UT_RefArray<utRef> &a) const
{
    if (this == &a) return 1;
    if (entries() != a.entries()) return 0;
    for (unsigned int i = 0; i < a.entries(); i++)
        if (!(arr[i] == a(i))) return 0;
    return 1;
}

template <class utRef>
int
UT_RefArray<utRef>::operator!=(const UT_RefArray<utRef> &a) const
{
    return !(*this == a);
}

template <class utRef>
int
UT_RefArray<utRef>::isEqual(const UT_RefArray<utRef> &a,
                            Comparator compare
                           ) const
{
    if (this == &a) return 1;
    if (entries() != a.entries()) return 0;
    for (unsigned int i = 0; i < a.entries(); i++)
        if (compare(&arr[i], &a(i))) return 0;
    return 1;
}

template <class utRef>
unsigned int    
UT_RefArray<utRef>::apply(int (*applyFct)(utRef &t, void *d), void *d)
{
    unsigned int i;
    for (i = 0; i < nbrEntries; i++)
        if (applyFct(arr[i],d)) break;
    return i;
}

template <class utRef>
void
UT_RefArray<utRef>::heapify(unsigned int idx, Comparator compare)
{
    int  lidx = 2*idx, ridx = lidx + 1;
    int  largest = idx;

    if( lidx < nbrEntries && compare(&arr[lidx], &arr[largest]) > 0 )
    {
        largest = lidx;
    }
    if( ridx < nbrEntries && compare(&arr[ridx], &arr[largest]) > 0 )
    {
        largest = ridx;
    }
    if( largest != idx )
    {
        utRef temp; temp = arr[largest];
        arr[largest] = arr[idx];
        arr[idx] = temp;
        heapify(largest, compare);
    }
}

#endif // __UT_RefArray_C__

---