UT/UT_PtrArray.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 utPtr. You can instantiate this class
 *      with any object or pointer, such as:
 *              UT_PtrArray<GeoPoint*>          pObj;
 */

#ifndef __UT_PtrArray_h__
#define __UT_PtrArray_h__

#ifdef WIN32
    #pragma warning(disable:4251)
    #pragma warning(disable:4275)
#endif

#include "UT_ArrayHelp.h"
#include "UT_PtrArrayRaw.h"
#include "UT_Algorithm.h"
#include "UT_MakePtrConst.h"
#include <algorithm>

template <typename utPtr>
class UT_PtrArray {

    // friend class     UT_PtrMatrix;

public:
    typedef int (*Comparator)(const utPtr *, const utPtr *);

    // Trivial constructor and destructor:
    // UT_PtrArray(unsigned int sz = 0);
    // virtual ~UT_PtrArray(void);
    explicit UT_PtrArray(unsigned int sz=0) : array(sz) {}
#if defined(SOLARIS)
    ~UT_PtrArray() {}   // Solaris can't deal with virtual destructors here
#else
    virtual ~UT_PtrArray() {}
#endif

    // Copy constructor that uses operator '=' to assign each of a's Things
    // to this array.
    UT_PtrArray(const UT_PtrArray<utPtr> &a) : array(a.array) { }

    void swap( UT_PtrArray< utPtr > &other ) { array.swap( other.array ); }

    // 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 utPtr into the
    // right spot; be aware that '=' works differently on objects and pointers.
    // 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.
    // 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 array.append(); }
    unsigned int        append(utPtr t)
                        { return array.append((const void*)t); }
    unsigned int        append(utPtr t, unsigned short checkForDup)
                        { return array.append((const void*)t, checkForDup); }

    unsigned int        insert(unsigned idx) { return array.insert(idx); }
    unsigned int        insert(utPtr t, unsigned index)
                        {
                            return array.insert((const void *)t, index);
                        }

    unsigned int        sortedInsert(utPtr t, Comparator compare )
                        {
                            return array.sortedInsert((const void *)t,
                                    (ut_ptr_compare_func_t)compare);
                        }
    unsigned int        uniqueSortedInsert(utPtr t, Comparator compare )
                        {
                            return array.uniqueSortedInsert((const void *)t,
                                    (ut_ptr_compare_func_t)compare);
                        }
    bool                hasSortedSubset(
                            UT_PtrArray<utPtr> const& other,
                            Comparator compare = (Comparator)&UTcomparePointers
                            ) const
                        {
                            return array.hasSortedSubset(
                                            other.array,
                                            (ut_ptr_compare_func_t)compare);
                        }
    void                sortedIntersection(
                            UT_PtrArray<utPtr> const& other,
                            Comparator compare = (Comparator)&UTcomparePointers
                            )
                        {
                            array.sortedIntersection(
                                            other.array,
                                            (ut_ptr_compare_func_t)compare);
                        }
    void                sortedIntersection(
                            UT_PtrArray<utPtr> const& other,
                            UT_PtrArray<utPtr> &result,
                            Comparator compare = (Comparator)&UTcomparePointers
                            ) const
                        {
                            array.sortedIntersection(
                                            other.array, result.array,
                                            (ut_ptr_compare_func_t)compare);
                        }
    void                sortedUnion(
                            UT_PtrArray<utPtr> const& other,
                            Comparator compare = (Comparator)&UTcomparePointers
                            )
                        {
                            array.sortedUnion(other.array,
                                              (ut_ptr_compare_func_t)compare);
                        }
    void                sortedUnion(
                            UT_PtrArray<utPtr> const& other,
                            UT_PtrArray<utPtr> &result,
                            Comparator compare = (Comparator)&UTcomparePointers
                            ) const
                        {
                            array.sortedUnion(other.array, result.array,
                                              (ut_ptr_compare_func_t)compare);
                        }


    // Assuming that the array is sorted without duplicates, it inserts item t
    // provided that it does not already exist in the array.
    // Returns the index of the inserted item, or the index of the existing
    // item if found.
    // Keep in mind that the resultant order could change every Houdini
    // session so should not be depended on being consistent cook to cook.
    unsigned int        uniqueSortedInsert(utPtr t)
                        {
                            return array.uniqueSortedInsert((const void *)t);
                        }

    // 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(utPtr t, Comparator compare )
                        {
                            return array.heapPush(t,
                                            (ut_ptr_compare_func_t)compare);
                        }
    // Assuming the array is already a heap, extracts the top (maximum)
    // element from the heap and returns it.
    utPtr               heapPop(Comparator compare)
                        {
                            return (utPtr)array.heapPop(
                                            (ut_ptr_compare_func_t)compare);
                        }
    // Assuming the array is already a heap, return the top (maximum)
    // element.
    utPtr               heapMax() const
                        {
                            return (utPtr)array.heapMax();
                        }

    unsigned int        concat(const UT_PtrArray<utPtr> &a)
                        {
                            return array.concat(a.array);
                        }


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

    // An alias for unique element insertion at a certain index. Also used by
    // the other insertion methods.
    unsigned int         insertAt(utPtr t, unsigned int index)
                         {
                             return array.insert((const void *)t, 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, 
    // If dupliCheck is 1, both methods search for all objects that match t or 
    // arr[index] respectively.
    int         remove(utPtr t)   { return array.remove((const void*)t); }
    int         remove(unsigned int index) { return array.remove(index); }
    int         removeIndex(unsigned int index) { return array.remove(index); }
    utPtr       removeLast()      { return (utPtr)array.removeLast() ; }

    // Removes all the zero entries from the list, shuffling down
    // and changing entries() appropriately.
    // Returns the number of entries left.
    int         removeZeros()     { return array.removeZeros(); }

    // Sort and remove all duplicate entries
    void        sortAndRemoveDuplicates()
                                  { array.sortAndRemoveDuplicates(); }

    // 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)
                        {
                            return array.shift(srcIdx, destIdx, 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)
                        {
                            array.move(srcIdx, destIdx, howMany);
                        }

    // Collapse the array to remove all the null pointer entries.
    // Note: Indices to elements may change due to shifting
    void                collapse() { array.collapse(); }

    // Cyclically shifts the entire array by howMany
    void                cycle(int howMany) { array.cycle(howMany); }

    // Reverse the entries in the array
    void                reverse()           { array.reverse(); }

    // 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 the search should start at.
    int          find(utPtr t, unsigned int s = 0) const
                 {
                    return array.find((const void *)t, s);
                 }
    int          find(utPtr t, Comparator compare) const
                 {
                    return array.find((const void *)t,
                                     (ut_ptr_compare_func_t)compare);
                 }

    // Searches for the given string assuming that our array points to
    // strings.
    // The advantage is that we avoid all callbacks, can inline code,
    // so should be super fast.
    int          findString(const char *str) const
                 {
                     return array.findString(str);
                 }

    // functions for sorting the array -- one uses pointer subtraction, the
    // other lets you use your own sort function.  Beware of sorting by pointer
    // order where order must be the the same between different runs of Houdini.
    void        sort(Comparator compare = (Comparator)&UTcomparePointers)
                {
                    array.sort((ut_ptr_compare_func_t)compare);
                }
    /// stableSort is both stable, so keeps equal elements in the same
    /// order (note this is very useful for compatibility between 
    /// compilers) and templated.
    /// Either use a bool sort function or make a utility class with
    /// bool operator()(const utPtr *a, const utPtr *b)
    /// the utility class lets you bind data to avoid globals.
    /// The comparator returns true if a must occur before b in the list.
    /// For sorting ascending, this is a less than operation.
    template<typename ComparatorBool>
    void        stableSort(ComparatorBool compare)
                {
                    // No-op for small/empty arrays, avoiding out of bounds
                    // assert on array()
                    if (entries() < 2)
                        return;

                    // NOTE: UT_MakePtrConst will NOT work with function
                    //       pointers. If you want this to work for function
                    //       pointers, use UT_RefArray instead.
                    typedef typename UT_MakePtrConst<utPtr>::type utCPtr;

                    std::stable_sort((utCPtr *)&array(0),
                                     (utCPtr *)&array(0) + array.entries(),
                                     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)
                {
                    array.resize(sz, copyFlag);
                }
    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 array.arrSize;       }
    int64       getMemoryUsage() const  { return capacity()*sizeof(void*); }
    uint        entries(void) const     { return array.nbrEntries;    }
    bool        isEmpty(void) const     { return array.nbrEntries==0; }

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

    // Assign array a to this array by copying each of a's Things with the
    // '=' operator. The size of this array must be greater or equal to the 
    // entry count of array a.
    UT_PtrArray<utPtr>  &operator=(const UT_PtrArray<utPtr> &a)
                        {
                            array = a.array;
                            return *this;
                        }

    // Compare two array and return 1 if they are equal and 0 otherwise.
    // Two Things 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 Things.
    int                 operator==(const UT_PtrArray<utPtr> &a) const
                        {
                            return array == a.array;
                        }
    int                 operator!=(const UT_PtrArray<utPtr> &a) const
                        {
                            return !(array == a.array);
                        }
    int                 isEqual(const UT_PtrArray<utPtr> &a,
                                int (*compare)(const void *t1, const void *t2)
                               ) const
                        {
                            return array.isEqual(a.array, compare);
                        }
     
    // Subscript operators. operator() does NOT do any bound checking, while
    // the non-const operator[] grows the array to accommodate the given index.
    utPtr               &operator()(unsigned int i)
                        {
                            return (utPtr &)array(i);
                        }
    utPtr               operator()(unsigned int i) const
                        {
                            return (utPtr)array(i);
                        }
    utPtr               &operator[](unsigned int i)
                        {
                            return (utPtr &)array[i];
                        }
    utPtr               operator[](unsigned int i) const
                        {
                            return (utPtr)array[i];
                        }

    utPtr               &last()
                        {
                            return (utPtr &)array(array.nbrEntries-1);
                        }
    utPtr               last() const
                        {
                            return (utPtr)array(array.nbrEntries-1);
                        }

    // 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 int        apply(int (*fcn)(utPtr t, void *d), void *d)
                        {
                            return array.apply((int (*)(void *, void*))fcn, d);
                        }

    UT_PtrArrayRaw       &getRawArray() { return array; }
    const UT_PtrArrayRaw &getRawArray() const { return array; }
    utPtr                *getArray(void) const { return (utPtr *)array.arr; }

protected:
    // Derived class should use these three methods to get a handle to the
    // internal data, and set the array size.
    void         setSize(unsigned int sz)       { array.arrSize = sz; }
    
private:
    // Pointer to a list of elements of type utPtr:
    UT_PtrArrayRaw      array;
};

typedef UT_PtrArray<const char *>       UT_StringList;


UT_SWAPPER_TEMPLATE(UT_PtrArray);

#endif

---