UT/UT_RefFixArray.h

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.
 */

#ifndef __UT_RefFixArray_h__
#define __UT_RefFixArray_h__

#include <string.h>
#include <SYS/SYS_Types.h>
#include "UT_Assert.h"


template <class utRef, unsigned long FixedSize>
class UT_RefFixArray {
public:
    // Trivial constructor and destructor:
    UT_RefFixArray(void)  : nbrEntries(0)       {}
    virtual     ~UT_RefFixArray(void);

    // Append an element to the current entries and return its index in the
    // array, or insert the element at a specified position; if the index is
    // greater than or equal to FixedSize-1, insert() returns -1. The insertion
    // methods use the assignment operator '=' to place the utRef into the
    // right spot; be aware that '=' works differently on objects and pointers.
    // If utRef is an object that uses the default '=' operator, the result of 
    // insert() will be a shallow copy of t, and not t itself.
    // The test for duplicates uses the logical equal operator '=='; as with
    // '=', the behaviour of the equality operator on pointers versus objects
    // is not the same. If utRef is an object, we recommend you either avoid 
    // using insert(), or define both '=' and '==' operators in its class.
    // Use the subscript operators instead of insert() if you are appending
    // to the array, or if  you don't mind overwriting the element already 
    // inserted at the given index.
    long                insert(const utRef& t, unsigned short duplicates = 1);
    long                insert(const utRef& t, unsigned long  index,
                                               unsigned short duplicates = 1);

    // Two more insert() methods that check for duplicates in the array, 
    // assuming that the array is sorted. t1 and t2 must be pointers to utRef.
    long                insert(const utRef& t,
                               int (*compare)(const void *t1, const void *t2)
                              );
    long                insert(const utRef& t,
                               unsigned long  index,
                               int (*compare)(const void *t1, const void *t2)
                              );

    // Remove one element from the array given the element itself or its 
    // position in the list, and fill the gap by shifting the elements down
    // by one position. Both methods return the index if successful, 
    // and (long)-1 if the element is not found. The method that takes 
    // an index argument does not return a reference to the object for safety
    // purposes: if utRef is an object, then when the array is shrunk, the 
    // memory previously used by utRef will be overwritten by the next
    // element. If duplicates is 1, both methods search for all objects that 
    // match t or arr[index] respectively.
    long                remove(const utRef& t, unsigned short duplicates=1);
    long                remove(unsigned long index, unsigned short duplicates=1)
                        {
                            if (index < nbrEntries) removeAt(index, duplicates);
                            return (index < nbrEntries) ? index : -1;
                        }

    // Two more remove() methods that search for the object to be removed and
    // all its duplicates (if duplicates is 1) with a user-defined comparison 
    // function. These methods assume the array is sorted. t1 and t2 must be 
    // pointers to utRef. The methods return the last (removed) object index.
    long                remove(const utRef& t,
                               int (*compare)(const void *t1, const void *t2),
                               unsigned short duplicates = 1);
    long                remove(unsigned long index,
                               int (*compare)(const void *t1, const void *t2),
                               unsigned short duplicates = 1)
                        {
                            if (index < nbrEntries)
                                removeAt(index, compare, duplicates);
                            return (index < nbrEntries) ? index : -1;
                        }

    // Move howMany objects starting at index srcIndex to destIndex;
    // Method returns 0 if OK, -1 if overflow.
    int                 shift(unsigned long srcIdx,
                              unsigned long destIdx,
                              unsigned long howMany);

    // Search for t in one of two ways: linearly using the '==' operator, or
    // binary using the function specified in the parameter list respectively.
    // find() returns the index of the matching element or (long)-1.
    long                 find(const utRef &t) const;
    long                 find(const utRef &t, 
                              int (*compare)(const void *t1, const void *t2)
                             ) const;

    // Sort the array using a comparison function that you must provide. t1 and
    // t2 are pointers to utRef.
    void                sort(int (*compare)(const void *t1, const void *t2));

    // Query the allocated length of the array or the number of elements
    // in the array: capacity() >= entries().
    uint        capacity(void) const    { return FixedSize; }
    int64       getMemoryUsage() const  { return capacity()*sizeof(utRef); }
    uint        entries(void) const     { return nbrEntries; }
    bool        isEmpty(void) const     { return nbrEntries==0; }

    // Subscript operators. operator() does NOT do any bound checking.
    utRef               &operator()(unsigned long i)
                        {
                            if (i >= nbrEntries) nbrEntries = i+1;
                            UT_ASSERT_P(nbrEntries < FixedSize);
                            return arr[i];
                        }
    const utRef         &operator()(unsigned long i) const
                        {
                            UT_ASSERT_P(i < nbrEntries);
                            return arr[i];
                        }
    utRef               &operator[](unsigned long i)
                        {
                            if (i >= FixedSize ) i = FixedSize-1;
                            if (i >= nbrEntries) nbrEntries = i+1;
                            return arr[i];
                        }
    const utRef         &operator[](unsigned long i) const
                        {
                            UT_ASSERT_P(i < nbrEntries);
                            return arr[i];
                        }

    // Apply a user-defined function to each element of the array 
    // as long as the function returns zero. If applyFct returns
    // 1, apply() stops traversing the list and returns the current
    // index; otherwise, apply() returns the number of entries.
    unsigned long       apply(int (*applyFct)(utRef &t, void *d), void *d);


protected:
    // Set the number of entries.
    void         entries(unsigned long ne)      { nbrEntries = ne; }
    
private:
    // List of elements of type utRef:
    utRef               arr[FixedSize];

    // Number of entries in the array:
    unsigned long       nbrEntries;

    // The guts of the public insert(...index...) methods.
    long                 insertAt(const utRef &t, unsigned long index)
                         {
                            long idx;
                            if (nbrEntries < FixedSize) 
                            {
                                if (&arr[0] <= &t && &t <= &arr[FixedSize-1])
                                {
                                    utRef tCopy = t; 
                                    memmove(&arr[index+1], &arr[index],
                                       (int)((nbrEntries-index)*sizeof(utRef)));
                                    arr[index] = tCopy;
                                }
                                else
                                {
                                    memmove(&arr[index+1], &arr[index],
                                       (int)((nbrEntries-index)*sizeof(utRef)));
                                    arr[index] = t;
                                }
                                nbrEntries++;
                                idx = (long) index;
                            }
                            else idx = -1;
                            return idx;
                         }

    // The guts of the remove() methods.
    void                removeAt(unsigned long index,unsigned short duplicates);
    void                removeAt(unsigned long index,
                                 int (*compare)(const void *t1, const void *t2),
                                 unsigned short duplicates);
};


#endif

---