UT/UT_RefFixArray.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.
 *      20 Maud St.
 *      Toronto, Ontario,  M5V 2M5
 *      Canada
 *      416-366-4607
 *
 * NAME:        Utility Library (C++)
 *
 * COMMENTS:
 *      This is a class template that implements a fixed-size array of 
 *      arbitrary objects. The template parameter represents the type
 *      of object, and is called utRef. You can instantiate this class
 *      with any object or pointer, while also giving a size to the array:
 *              UT_RefFixArray<int, 10>         iObj;
 *              UT_RefFixArray<GeoPrimMesh, 20> mObj;
 *              UT_RefFixArray<GeoPoint*, 50>   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.
 *
 * Revision 1.2  1995/09/28  21:17:53  adubey
 * Fixed #include directive calls.
 *
 * Revision 1.1.1.1  1995/09/17  18:10:26  mark
 * initial source release
 *
 * Revision 1.2  93/11/29  19:44:16  dale
 * put destructor in .C
 * 
 * Revision 1.1  93/10/15  23:33:21  cb
 * Initial revision
 * 
 * 
 */

#include <stdlib.h>
#include "UT_RefFixArray.h"

template <class utRef, unsigned long FixedSize>
UT_RefFixArray<utRef,FixedSize>::~UT_RefFixArray() {}

template <class utRef, unsigned long FixedSize>
long    
UT_RefFixArray<utRef,FixedSize>::insert(const utRef& t,
                                        unsigned short duplicates)
{
    long idx = -1;
    if (nbrEntries == FixedSize)                return -1;
    if (duplicates && ((idx = find(t)) != -1))  return (unsigned long)idx;

    arr[nbrEntries] = t;
    return nbrEntries++;
}

template <class utRef, unsigned long FixedSize>
long            
UT_RefFixArray<utRef,FixedSize>::insert(const utRef& t, unsigned long  index,
                           unsigned short duplicates)
{
    if (index == nbrEntries) insert(t, duplicates);
    long idx = -1;
    return (duplicates && ((idx=find(t)) != -1)) ? (unsigned long)idx
                                                 :  insertAt(t, index);
}

template <class utRef, unsigned long FixedSize>
long    
UT_RefFixArray<utRef,FixedSize>::insert(const utRef& t,
                                 int (*compare)(const void *t1, const void *t2))
{
    long idx = -1;
    if (nbrEntries == FixedSize)        return -1;
    if ((idx=find(t, compare)) != -1)   return (unsigned long)idx;

    arr[nbrEntries] = t;
    return nbrEntries++;
}

template <class utRef, unsigned long FixedSize>
long            
UT_RefFixArray<utRef,FixedSize>::insert(const utRef& t, unsigned long index,
                                 int (*compare)(const void *t1, const void *t2))
{
    if (index == nbrEntries) insert(t, compare);
    long idx = -1;
    return ((idx=find(t, compare)) != -1) ? (unsigned long)idx
                                          :  insertAt(t, index);
}

template <class utRef, unsigned long FixedSize>
long            
UT_RefFixArray<utRef,FixedSize>::remove(const utRef& t,
                                        unsigned short duplicates)
{
    long idx = find(t);
    if (idx < 0) return -1;
    removeAt((unsigned long)idx, duplicates);
    return idx;
}

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

template <class utRef, unsigned long FixedSize>
long            
UT_RefFixArray<utRef,FixedSize>::remove(const utRef& t,
                                 int (*compare)(const void *t1, const void *t2),
                                 unsigned short duplicates)
{
    long idx = find(t, compare);
    if (idx < 0) return -1;
    removeAt((unsigned long)idx, compare, duplicates);
    return idx;
}

template <class utRef, unsigned long FixedSize>
void            
UT_RefFixArray<utRef,FixedSize>::removeAt(unsigned long idx, 
                                 int (*compare)(const void *t1, const void *t2),
                                 unsigned short duplicates)
{
    if (duplicates)
    {
        const utRef &rem = arr[idx];
        long *gapArr = new long[nbrEntries];
        UT_ASSERT(gapArr);
        long  gapCnt = 0;
        for (unsigned long i = 0; i < nbrEntries; i++)
            if (!compare(&arr[i],&rem)) gapArr[gapCnt++] = i;
        for (long g = gapCnt-1; g >= 0; g--, nbrEntries--)
        {
            unsigned long rmIdx = gapArr[g];
            if (rmIdx != nbrEntries)
                memmove(&arr[rmIdx], &arr[rmIdx+1],
                       (int) ((nbrEntries-rmIdx)*sizeof(utRef)));
        }
        delete [] gapArr;
    }
    else if (idx != --nbrEntries)
        memmove(&arr[idx], &arr[idx+1], (int)((nbrEntries-idx)*sizeof(utRef)));
}

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

template <class utRef, unsigned long FixedSize>
long
UT_RefFixArray<utRef,FixedSize>::find(const utRef &t) const
{
    long idx;
    for (idx = 0; idx < nbrEntries; idx++)
        if (arr[idx] == t) return idx;

    return (long)-1;
}

template <class utRef, unsigned long FixedSize>
long
UT_RefFixArray<utRef,FixedSize>::find(const utRef &t, 
                         int (*compare)(const void *t1, const void *t2)) const
{
    if (!nbrEntries) return 0;
    utRef *match = (utRef*) bsearch((const void*)&t, arr, (int)nbrEntries, 
                                    sizeof(utRef), compare);
    return (match) ? match-arr : (long)-1;
}

template <class utRef, unsigned long FixedSize>
void            
UT_RefFixArray<utRef,FixedSize>::sort(int (*compare)(const void*, const void*))
{
    qsort(arr, (int)nbrEntries, sizeof(utRef), compare);
}

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

---