UT/UT_RefArray.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.
 *      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 can 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_h__
#define __UT_RefArray_h__

#ifdef WIN32
    #pragma warning(disable:4251)
    #pragma warning(disable:4275)
#endif
#include <string.h>
#include <malloc.h>
#include "UT_Assert.h"
#include "UT_Algorithm.h"
#include "UT_ArrayHelp.h"


template <class utRef>
class UT_RefArray {
public:
    typedef int (*Comparator)(const utRef *, const utRef *);

    // Trivial constructor and destructor:
    explicit UT_RefArray(unsigned int sz = 0) 
    : arrSize(sz), nbrEntries(0)
    {
        arr = (sz) ? (utRef*)calloc(sizeof(utRef),sz) : 0;
    }
    UT_RefArray(unsigned int sz, unsigned int count);

    virtual ~UT_RefArray(void);

    void swap( UT_RefArray &other );

    // Copy constructor that uses operator '=' to assign each of a's utRefs
    // to this array.
    UT_RefArray(const UT_RefArray<utRef> &a);

    // Append an element to the current entries and return its index in the
    // array, or insert the element at a specified position; if necessary,
    // insert() grows the array to accommodate the element. The insert
    // 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.
    // So, if what you really want to do is create a new object inside the
    // array, first grow the array to a good size, then create your object as
    // follows:
    //          UT_RefArray<GeoPoint>  arr(3);
    //          GeoPoint              *p = new (&arr[0]) GeoPoint(....);
    // 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.
    unsigned int        append(void)            { return insert(nbrEntries); }
    unsigned int        append(const utRef& t);
    unsigned int        append(const utRef& t, unsigned short dupliCheck);
    unsigned int        insert(unsigned int index);
    unsigned int        insert(const utRef& t, unsigned int  index);
    unsigned int        insert(const utRef& t, unsigned int  index,
                                               unsigned short dupliCheck);

    // Takes another pointer array and concatenate it onto my end
    unsigned int        concat(const UT_RefArray<utRef> &a);

    // Insert an element "count" times at the given index. Return the index.
    unsigned  int       multipleInsert(unsigned int index, unsigned int count);

    // 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.
    unsigned int        append(const utRef& t, Comparator compare);
    unsigned int        insert(const utRef& t,
                               unsigned int  index,
                               Comparator compare
                              );
    unsigned int        sortedInsert(const utRef& t, Comparator compare);
    void                sortedUnion(
                            const UT_RefArray<utRef> &other,
                            UT_RefArray<utRef> &result,
                            Comparator compare
                            ) const;

    // Assuming the array is already a heap, it inserts item t maintaining
    // the heap. It returns the index of the inserted item.
    unsigned int        heapPush(const utRef &t, Comparator compare );
    // Assuming the array is already a heap, extracts the top (maximum)
    // element from the heap and returns it.
    void                heapPop(Comparator compare);
    // Assuming the array is already a heap, return the top (maximum)
    // element.
    utRef               &heapMax() const
                        {
                             UT_ASSERT_P(nbrEntries > 0);
                             return arr[0];
                        }

    // An alias for unique element insertion at a certain index. Also used by
    // the other insertion methods.
    unsigned int         insertAt(const utRef &t, unsigned int index);

    // 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 (int)-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 dupliCheck is 1, both methods search for all objects that 
    // match t or arr[index] respectively.
    int         remove(const utRef& t );
    int         remove(unsigned int at_index )
                        {
                            return (at_index < nbrEntries)
                                ? removeAt(at_index) : -1;
                        }
    int         remove(const utRef& t, unsigned short dupliCheck);
    int         remove(unsigned int at_index, unsigned short dupliCheck)
                        {
                            return (at_index < nbrEntries) 
                                ? removeAt(at_index, dupliCheck) : -1;
                        }

    // Two more remove() methods that search for the object to be removed and
    // all its duplicates (if dupliCheck 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.
    int         remove(const utRef& t,
                               Comparator compare,
                               unsigned short dupliCheck = 0);
    int         remove(unsigned int at_index,
                               Comparator compare,
                               unsigned short dupliCheck = 0)
                        {
                            return (at_index < nbrEntries) 
                                ? removeAt(at_index, compare, dupliCheck) : -1;
                        }

    // A convenience method to remove the last element.  The method returns
    // the index if sucessful, and -1 if the array was empty.
    int         removeLast()
                        {
                            return nbrEntries ? removeAt(nbrEntries-1) : -1;
                        }

    // Move howMany objects starting at index srcIndex to destIndex;
    // Method returns 0 if OK, -1 if overflow.
    int                 shift(unsigned int srcIdx,
                              unsigned int destIdx,
                              unsigned int howMany);
    // Move howMany objects starting at index srcIndex to destIndex;
    // Unlike shift, this method moves entries instead of overwriting them.
    void                move(int srcIdx, int destIdx, int howMany);
    // Performs a cyclical shift of the entries by howMany
    void                cycle(int 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 (int)-1.
    // Parameter s indicates the index to start the search at.
    int          find(const utRef &t, unsigned int s = 0) const;
    int          find(const utRef &t, Comparator compare,
                              unsigned int s = 0) const;

    // Search for 'any' until compare() returns 0 and return the index;
    // otherwise return -1. The array is assumed to be sorted.
    int          find(void *any, Comparator compare, unsigned int s = 0) const;

    // The fastest search possible, which does pointer arithmetic to find the 
    // index of the element. WARNING: index() does no out-of-bounds checking.
    int              index(const utRef &t) const { return &t - arr; }
    int          safeIndex(const utRef &t) const 
                 { 
                     return (&t >= arr && (&t - arr < (int)nbrEntries)) ? &t - arr : -1;
                 }

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

    // Resize the array, ie. grow it or shrink it. If copyFlag is 1, the 
    // function copies the data after reallocating space for the array.
    void                resize(unsigned int sz, unsigned short copyFlag=1);
    void                resizeIfNeeded(uint sz, bool copyFlag=true)
                        {
                            if (sz > capacity())
                                resize(sz, copyFlag);
                        }

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

    // Set the number of entries. Normally, you should not have to use it.
    void                entries(unsigned int ne);
    // Resets list to an empty list.
    void        clear() { entries(0); }

    // Assign array a to this array by copying each of a's utRefs with the
    // '=' operator.
    UT_RefArray<utRef>  &operator=(const UT_RefArray<utRef> &a);

    // Compare two array and return 1 if they are equal and 0 otherwise.
    // Two utRefs are checked against each other using operator '==' or
    // compare() respectively. Arrays of different size but equal number of
    // entries are checked for member-wise equality.
    // t1 and t2 must point to utRefs.
    int                 operator==(const UT_RefArray<utRef> &a) const;
    int                 operator!=(const UT_RefArray<utRef> &a) const;
    int                 isEqual(const UT_RefArray<utRef> &a,
                                Comparator compare) const;
     
    // Subscript operators. operator() does NOT do any bound checking, while
    // the non-const operator[] grows the array to accommodate the given index.
    utRef               &operator()(unsigned int i)
                         {
                             UT_ASSERT_P(i < nbrEntries);
                             return arr[i];
                         }
    const utRef         &operator()(unsigned int i) const
                         {
                             UT_ASSERT_P(i < nbrEntries);
                             return arr[i];
                         }
    utRef               &operator[](unsigned int i);
    const utRef         &operator[](unsigned int i) const
                         {
                             UT_ASSERT_P(i < nbrEntries);
                             return arr[i];
                         }

    utRef               &last()
                         {
                             UT_ASSERT_P(nbrEntries);
                             return arr[nbrEntries-1];
                         }

    const utRef         &last() const
                         {
                             UT_ASSERT_P(nbrEntries);
                             return arr[nbrEntries-1];
                         }

    // Apply a user-defined function to each element of the array 
    // as int 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 int        apply(int (*applyFct)(utRef &t, void *d), void *d);

    const utRef         *getRawArray(void) const        { return arr;      }

private:
    // Pointer to a list of elements of type utRef:
    utRef               *arr;

    // The number of elements we have allocated space for versus the actual
    // number of entries in the array:
    unsigned int         arrSize;
    unsigned int         nbrEntries;

    // The guts of the remove() methods.
    int                 removeAt(unsigned int index);
    int                 removeAt(unsigned int index, unsigned short dupliCheck);
    int                 removeAt(unsigned int index, Comparator compare,
                                 unsigned short dupliCheck);

    // The guts of the popHeap() method.
    void                heapify(unsigned int index, Comparator compare);
};

#if defined( WIN32 ) || defined( LINUX ) || defined(MBSD) || defined(GAMEOS)
    #include "UT_RefArray.C"
#endif


UT_SWAPPER_TEMPLATE( UT_RefArray );

#endif

---