UT/UT_ValArray.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 that is used by UT_ValArray to do all the work...
 *
 */

#ifndef __UT_ValArray_h__
#define __UT_ValArray_h__

#include "UT_API.h"
#include <stdlib.h>
#include <vector>
#include <SYS/SYS_Types.h>
#include "UT_Assert.h"
#include "UT_Algorithm.h"
#include "UT_ArrayHelp.h"
#include "UT_VectorTypes.h"

UT_API extern void UTsetCompareFloatsTolerance( float tol );
UT_API extern int UTcompareFloats(const float *a, const float *b);
UT_API extern int UTcompareInts(const int *a, const int *b);

template <typename T>
class UT_ValArray {
public:
    typedef int (*Comparator)(const T *, const T *);

    UT_ValArray(const UT_ValArray<T> &a);
    UT_ValArray(unsigned int sz, unsigned int count)
    {
        arr = (sz) ? (T *)calloc(sizeof(T), sz) : 0;
        if (sz         < count) count = sz;
        nbrEntries = count;
        arrSize = sz;
    }
    explicit UT_ValArray(unsigned int sz = 0) : arrSize(sz), nbrEntries(0)
    {
        arr = (sz) ? (T *)calloc(sizeof(T), sz) : 0;
    }
    ~UT_ValArray(void);

    void swap( UT_ValArray<T> &other );

    // 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 Thing 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 insert(nbrEntries); }
    unsigned int        append(T t);
    void                appendMultiple(T t, int count);
    unsigned int        insert(unsigned index);
    unsigned int        insert(T t, unsigned index);

    // Assuming the array is sorted, it inserts item t maintaining the sorted
    // state of the array. It returns the index of the inserted item.
    unsigned int        sortedInsert(T t, Comparator compare );
    unsigned int        sortedInsert(T t);
    unsigned int        uniqueSortedInsert(T t, Comparator compare );
    unsigned int        uniqueSortedInsert(T t);
    unsigned int        uniqueSortedInsertAscending(T t)
    { return uniqueSortedInsert(t); }
    // Convenience method to perform binary search of a ascending sorted array
    // with no duplicates.  Returns the index of the specified item, -1 if not
    // found.
    int                 uniqueSortedFind(T item) const;
    int                 uniqueSortedFindAscending(T item) const
    { return uniqueSortedFind(item); }

    // Merge the given array into us.
    // If direction is -1, then it assumes us and 'other' are both already
    // sorted in descending order. Similarly, +1 means ascending.
    // If allow_dups is false, then it further assumes that both arrays have no
    // duplicates and will produce a result that also has no duplicates.
    // More work will be needed if you want allow_dups to mean remove duplicates
    void merge( const UT_ValArray<T> &other, int direction, bool allow_dups );

    void sortedUnion(           const UT_ValArray<T> &other );
    void sortedUnion(           const UT_ValArray<T> &other,
                                UT_ValArray<T> &result ) const;
    void sortedIntersection(    const UT_ValArray<T> &other );
    void sortedIntersection(    const UT_ValArray<T> &other,
                                UT_ValArray<T> &result ) const;
    void sortedSetDifference(   const UT_ValArray<T> &other );
    void sortedSetDifference(   const UT_ValArray<T> &other,
                                UT_ValArray<T> &result ) const;

    /// Assuming this array is sorted, remove all duplicate entries.
    void sortedRemoveDuplicates();

    // Convert from and to a std::vector.
    void                 fromStdVector(const std::vector<T> &vec);
    void                 toStdVector(std::vector<T> &vec) 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(T t, Comparator compare );
    unsigned int        heapPush(T t);
    // Assuming the array is already a heap, extracts the top (maximum)
    // element from the heap and returns it.
    T                   heapPop(Comparator compare);
    T                   heapPop();
    // Assuming the array is already a heap, return the top (maximum)
    // element.
    T                   heapMax() const
                        {
                             UT_ASSERT_P(nbrEntries > 0);
                             return arr[0];
                        }

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

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

    // An alias for unique element insertion at a certain index. Also used by
    // the other insertion methods.
    unsigned int         insertAt(T 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, 
    // If dupliCheck is 1, both methods search for all objects that match t or 
    // arr[index] respectively.
    int         findAndRemove(T t);
    int         removeIndex(unsigned int index)
                {
                    return (index < nbrEntries) ? removeAt(index) : -1;
                }
    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);

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

    // Quickly set the array to a single value
    // The defaualt does a memset of 0.
    void                constant(T v);
    void                constant();
    void                zero() { constant(); }

    // 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(T t, unsigned int s = 0) const;
    int          find(T t, Comparator compare) const;

    void                reverse();

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

    // Partitions the array into values greater than or less than
    // the Nth element, returns the resulting partition number.
    // idx == 0 will get the minimum value, idx == entries()-1 the
    // maximum value.  This does modify this array!
    T                   selectNthLargest(int idx);

    // 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(T); }
    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)        { nbrEntries = ne; }
    // Decreases, but never expands, to the given number of entries.
    void        truncate(unsigned int ne) { if (entries() > ne) entries(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 
    // memcpy
    UT_ValArray<T>      &operator=(const UT_ValArray<T> &a);

    // 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.
    bool                operator==(const UT_ValArray<T> &a) const;
    bool                operator!=(const UT_ValArray<T> &a) const;
    int                 isEqual(const UT_ValArray<T> &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.
    T                   &operator()(unsigned int i)
                         {
                             UT_ASSERT_P(i < nbrEntries);
                             return arr[i];
                         }
    const T             &operator()(unsigned int i) const
                         {
                             UT_ASSERT_P(i < nbrEntries);
                             return arr[i];
                         }
    T                   &operator[](unsigned int i)
                         {
                            if (i >= arrSize   ) resize(bumpAlloc(i+1));
                            if (i >= nbrEntries) nbrEntries = i+1;
                            return arr[i];
                         }
    const T             &operator[](unsigned int i) const
                         {
                            UT_ASSERT_P(i < nbrEntries);
                            return arr[i]; 
                         }
    T                   &last()
                         {
                             UT_ASSERT_P(nbrEntries);
                             return arr[nbrEntries-1];
                         }
    T                    last() const
                         {
                             return nbrEntries ? arr[nbrEntries-1] : ((T)0);
                         }

    void         copyMemory(const UT_ValArray<T> &from) { *this = from; }

    // 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)(T &t, void *d), void *d);

    const T     *getRawArray(void) const        { return arr;      }
    T           *array(void)                    { return arr;      }
    void         setCapacity(unsigned int sz)   { arrSize    = sz; }

    // This method allows you to swap in a new raw T array, which must be
    // the same size as arrSize. Use caution with this method.
    T           *aliasArray(T *newdata)
                 { T *data = arr; arr = newdata; return data; }

    // Returns the sum of the entries in the array.
    T            sum() const
                 {
                     T    s = 0.0f;
                     for (int i = 0; i < entries(); i++)
                         s += arr[i];
                     return s;
                 }
    
    void         display() const;
private:
    // Pointer to a list of elements of type Thing:
    T                   *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);
    // The guts of the popHeap() method.
    void                heapify(unsigned int index, Comparator compare);
    void                heapify(unsigned int index);
};

// Assigns src to dest, using the default C++ conversion operator.
template <typename T, typename S>
void
UTconvertArray(UT_ValArray<T> &dest, const UT_ValArray<S> &src)
{
    int n = src.entries();
    dest.resize(n);
    dest.entries(n);
    for (int i = 0; i < n; i++)
        dest(i) = T(src(i));
}
template <typename T, typename S>
void
UTconvertArray(UT_ValArray<T> &dest, const S *src, int n)
{
    dest.resize(n);
    dest.entries(n);
    for (int i = 0; i < n; i++)
        dest(i) = T(src[i]);
}
template <typename T, typename S>
void
UTconvertArray(T *dest, const UT_ValArray<S> &src)
{
    // We assume here that dest has enough memory for src.entries()
    int n = src.entries();
    for (int i = 0; i < n; i++)
        dest[i] = T(src(i));
}
template <typename T, typename S>
void
UTconvertArray(T *dest, const S *src, int64 n)
{
    // We assume here that dest has enough memory for n elements
    for (int64 i = 0; i < n; i++)
        dest[i] = T(src[i]);
}

#if defined( WIN32 ) || defined( LINUX ) || defined(MBSD) || defined(GAMEOS)
    #include "UT_ValArrayImpl.h"
#endif

UT_SWAPPER_TEMPLATE( UT_ValArray );

template <>
UT_API void UT_ValArray<fpreal32>::display() const;
template <>
UT_API void UT_ValArray<fpreal64>::display() const;
template <>
UT_API void UT_ValArray<int32>::display() const;
template <>
UT_API void UT_ValArray<fpreal32>::constant(fpreal32 val);

UT_API extern int UTcompareFloats(const float *a, const float *b);
UT_API extern int UTcompareInts(const int *a, const int *b);
#endif

---