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 "UT_Algorithm.h"
#include "UT_ArrayHelp.h"
#include "UT_Assert.h"
#include "UT_VectorTypes.h"

#include <SYS/SYS_TypeTraits.h>
#include <SYS/SYS_Types.h>

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
#include <stdio.h>
#include <string.h>


UT_API extern void UTsetCompareFloatsTolerance(float tol);
UT_API extern float UTgetCompareFloatsTolerance();
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_Array
{
public:
    typedef T       value_type;

    typedef int (*Comparator)(const T *, const T *);

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

    void            swap(UT_Array<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(const T &t);
    unsigned int    append(const T &t, bool check_dup)
                    {
                        int     idx;
                        if (check_dup && ((idx = find(t)) != -1))
                            return idx;
                        return append(t);
                    }
    void            appendMultiple(const T &t, int count);
    unsigned int    insert(unsigned index);
    unsigned int    insert(const 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(const T &t, Comparator compare);
    template <typename ComparatorBool>
    unsigned int    sortedInsert(const T &t, ComparatorBool is_less);

    unsigned int    uniqueSortedInsert(const T &t, Comparator compare);
    template <typename ComparatorBool>
    unsigned int    uniqueSortedInsert(const T &t, ComparatorBool is_less);

    // 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(const T &item, Comparator compare) const;
    template <typename ComparatorBool>
    int             uniqueSortedFind(const T &item, ComparatorBool is_less) const;

    // 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
    template <typename ComparatorBool>
    void            merge(const UT_Array<T> &other, int direction,
                          bool allow_dups, ComparatorBool is_less);

    bool            hasSortedSubset(const UT_Array<T> &other,
                                    Comparator compare) const;

    void            sortedUnion(const UT_Array<T> &other, Comparator compare);
    void            sortedUnion(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        Comparator compare);
    void            sortedIntersection(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        Comparator compare);
    void            sortedSetDifference(
                        const UT_Array<T> &other,
                        UT_Array<T> &result,
                        Comparator compare) const;

    // 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(const T &t, Comparator compare);
    template <typename ComparatorBool>
    unsigned int    heapPush(const T &t, ComparatorBool is_less);

    // Assuming the array is already a heap, extracts the top (maximum)
    // element from the heap and returns it.
    T               heapPop(Comparator compare);
    template <typename ComparatorBool>
    T               heapPop(ComparatorBool is_greater);

    // Assuming the array is already a heap, return the top (maximum)
    // element.
    const 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_Array<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(const 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.  Return the index of the element remove or -1 if
    // the value was not found.
    int             findAndRemove(const T &t);
    int             removeIndex(unsigned int index)
                    {
                        return (index < nbrEntries) ? removeAt(index) : -1;
                    }
    void            removeLast()
                    {
                        if (nbrEntries) removeAt(nbrEntries-1);
                    }

    // Remove the range [begin_i,end_i) of elements from the array.
    void            removeRange(unsigned int begin_i, unsigned int end_i);

    // Removes all matching entries from the list, shuffling down and changing
    // entries() appropriately.
    // Returns the number of entries left.
    template <typename IsEqual>
    int             removeIf(IsEqual is_equal);

    // Remove all matching entries. Also resizes the array.
    template <typename IsEqual>
    void            collapseIf(IsEqual is_equal)
                    {
                        removeIf(is_equal);
                        resize(entries());
                    }

    // Move howMany objects starting at index srcIndex to destIndex;
    // This method will remove the elements at [srcIdx, srcIdx+howMany) and
    // then insert them at destIdx.  This method can be used in place of
    // the old shift() operation.
    void            move(int srcIdx, int destIdx, 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(const T &v);
    void            zero();

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

    // 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;

    void            reverse();

    // 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 T &t) const { return &t - arr; }
    int             safeIndex(const T &t) const 
                    { 
                        return (&t >= arr && &t < (arr + nbrEntries))
                            ? &t - arr : -1;
                    }

    /// Sort the array using a comparison function that you must provide. t1 and
    /// t2 are pointers to Thing.  The comparison function uses strcmp()
    /// semantics (i.e. -1 if less than, 0 if equal, 1 if greater).
    void            sort(Comparator compare);

    /// Sort using std::sort.  The ComparatorBool uses the less-than semantics
    template <typename ComparatorBool>
    void            stdsort(ComparatorBool is_less)
                    {
                        std::sort(arr, arr + nbrEntries, is_less);
                    }

    /// 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 T a, const T 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 is_less)
                    {
                        // No-op for small/empty arrays, avoiding out of
                        // bounds assert on array()
                        if (entries() < 2)
                            return;

                        std::stable_sort(array(),
                                         array() + entries(),
                                         is_less);
                    }

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

    // 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!
    template <typename ComparatorBool>
    T               selectNthLargest(int idx, ComparatorBool is_less);

    // 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() const        { return arrSize; }
    int64           getMemoryUsage() const  { return capacity()*sizeof(T); }
    uint            entries() const         { return nbrEntries; }
    bool            isEmpty() const         { return nbrEntries==0; }

    // Set the number of entries.
    void            entries(unsigned int ne)
                    {
                        resizeIfNeeded(ne);
                        if (nbrEntries > ne)
                            trivialDestructRange(arr + ne, nbrEntries - ne);
                        else if (ne > nbrEntries)
                            trivialConstructRange(
                                    arr + nbrEntries, ne - nbrEntries);
                        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_Array<T> &   operator=(const UT_Array<T> &a);

    // 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.
    // WARNING: Will *NOT* reduce nbrEntries, will only increase if necessary
    UT_Array<T> &   assignSubset(const UT_Array<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_Array<T> &a) const;
    bool            operator!=(const UT_Array<T> &a) const;
    int             isEqual(const UT_Array<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 >= nbrEntries)
                            entries(i+1);
                        return arr[i];
                    }
    // const operator[] does NOT grow the array, and will return default
    // objects for out of bound array indices.
    T               operator[](unsigned int i) const
                    {
                        return i < nbrEntries ? arr[i] : T();
                    }
    T &             last()
                    {
                        UT_ASSERT_P(nbrEntries);
                        return arr[nbrEntries-1];
                    }
    const T &       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)(T &t, void *d), void *d);

    template <typename BinaryOp>
    T               accumulate(T init_value, BinaryOp add) const;

    const T *       getRawArray() const             { return arr;      }
    T *             array()                         { return arr;      }
    T *             getArray() const                { 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; }

    template <bool FORWARD>
    class iteratorT
    {
        public:
            iteratorT()
                : myArray(NULL)
                , myCurr(0)
            {}
            iteratorT(const iteratorT<FORWARD> &src)
            {
                *this = src;
            }
            ~iteratorT() {}

            T           &operator*() const
                            { return const_cast<T&>((*myArray)(myCurr)); }
            T           &item() const
                            { return const_cast<T&>((*myArray)(myCurr)); }

            uint         index() const          { return myCurr; }

            int         operator==(const iteratorT &cmp) const
                        {
                            // If both arrays are at the end
                            if (atEnd() && cmp.atEnd())
                                return true;
                            return ((!myArray && !cmp.myArray) ||
                                    ((myArray == cmp.myArray) &&
                                     (myCurr == cmp.myCurr)));
                        }
            int         operator!=(const iteratorT &cmp) const
                            { return !(*this == cmp); }

            iteratorT   &operator=(const iteratorT &src)
                        {
                            myArray = src.myArray;
                            myCurr = src.myCurr;
                            return *this;
                        }

            /// Pre-increment operator
            iteratorT   &operator++()
                        {
                            advance();
                            return *this;
                        }
            /// Post-increment operator
            iteratorT   &operator++(int)
                        {
                            iteratorT   tmp = *this;
                            advance();
                            return tmp;
                        }
            bool        atEnd() const
                        {
                            if (FORWARD)
                                return !myArray || myCurr >= myArray->entries();
                            else
                                return !myArray || myCurr < 0;
                        }
            void        advance()
                        {
                            if (FORWARD)
                                myCurr++;
                            else
                                myCurr--;
                        }
            void        rewind()
                        {
                            if (FORWARD)
                                myCurr = 0;
                            else
                                myCurr = myArray ? (exint)myArray->entries() - 1 : -1;
                        }
        private:
            iteratorT(const UT_Array<T> &array)
                : myArray(&array)
                , myCurr(0)
            {
                rewind();
            }

            const UT_Array<T>   *myArray;
            exint                myCurr;
            friend class         UT_Array<T>;
    };
    typedef iteratorT<true>     const_iterator;
    typedef iteratorT<false>    reverse_iterator;
    typedef const_iterator      traverser;      // For backward compatibility

    /// Begin iterating over the array.  The array may not be modified during
    /// the traversal.
    const_iterator      begin() const
                        {
                            if (arr && nbrEntries)
                                return const_iterator(*this);
                            return const_iterator();
                        }
    /// End const iterator.  Consider using it.atEnd() instead.
    const_iterator      end() const
                        {
                            return const_iterator();
                        }
    /// Begin iterating over the array in reverse.  This allows for elements to
    /// be removed/deleted from the array during traveral.
    reverse_iterator    rbegin() const
                        {
                            if (arr && nbrEntries)
                                return reverse_iterator(*this);
                            return reverse_iterator();
                        }
    /// End reverse iterator.  Consider using it.atEnd() instead.
    reverse_iterator    rend() const
                        {
                            return reverse_iterator();
                        }

    /// Remove item specified by the reverse_iterator.
    void                removeItem(reverse_iterator &it)
                        {
                            removeAt(it.index());
                        }


    /// Very dangerous methods to share arrays.
    /// The array is not aware of the sharing, so ensure you clear
    /// out the array prior a destructor or resize operation.
    void            unsafeShareData(UT_Array<T> &src)
                    {
                        arr = src.arr;
                        arrSize = src.arrSize;
                        nbrEntries = src.nbrEntries;
                    }
    void            unsafeClearData()
                    {
                        arr = 0;
                        arrSize = 0;
                        nbrEntries = 0;
                    }
protected:
    // Check whether T may have a constructor, destructor, or copy
    // constructor.  This test is conservative in that some POD types will
    // not be recognized as POD by this function. To mark your type as POD,
    // use the SYS_DECLARE_IS_POD() macro in SYS_TypeTraits.h.
    static bool     isPOD()
                    {
                        return SYSisPOD<T>();
                    }

    // Copy construct the given type
    static void     copyConstruct(T &dst, const T &src)
                    {
                        if (isPOD())
                            dst = src;
                        else
                            new (&dst) T(src);
                    }
    static void     copyConstructRange(T *dst, const T *src, int n)
                    {
                        if (isPOD())
                            memcpy(dst, src, n * sizeof(T));
                        else
                        {
                            for (int i = 0; i < n; i++)
                                new (&dst[i]) T(src[i]);
                        }
                    }

    // Constructor
    static void     trivialConstruct(T &dst)
                    {
                        if (!isPOD())
                            new (&dst) T();
                    }
    static void     trivialConstructRange(T *dst, int n)
                    {
                        if (!isPOD())
                        {
                            for (int i = 0; i < n; i++)
                                new (&dst[i]) T();
                        }
                    }

    // Destructor
    static void     trivialDestruct(T &dst)
                    {
                        if (!isPOD())
                            dst.~T();
                    }
    static void     trivialDestructRange(T *dst, int n)
                    {
                        if (!isPOD())
                        {
                            for (int i = 0; i < n; i++)
                                dst[i].~T();
                        }
                    }

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);
    template <typename ComparatorBool>
    void            heapify(unsigned int index, ComparatorBool is_greater);
    
    template<typename OS, typename S>
    friend OS &operator<<(OS &os, const UT_Array<S> &d);
};

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

    // Trivial constructor and destructor:
    explicit        UT_ValArray(unsigned int sz = 0) 
                        : UT_Array<T>::UT_Array(sz)
                    {}
                    UT_ValArray(unsigned int sz, unsigned int count)
                        : UT_Array<T>::UT_Array(sz, count)
                        {}

    static bool     compareElementsBool(const T &a, const T &b)
                    {
                        return a < b;
                    }

    // Sort and then remove all duplicate entries
    void            sortAndRemoveDuplicates()
                    {
                        stableSort(compareElementsBool);
                        UT_Array<T>::sortedRemoveDuplicates();
                    }

    static int      compareElements(const T *a, const T *b)
                    {
                        if (*a > *b)
                            return 1;
                        if (*a < *b)
                            return -1;
                        return 0;
                    }

    void            sort(Comparator compare)
                    {
                        UT_Array<T>::sort(compare);
                    }
    template <typename ComparatorBool>
    void            stdsort(ComparatorBool is_less)
                    {
                        UT_Array<T>::stdsort(is_less);
                    }
    void            sort()
                    {
                        stdsort(std::less<T>());
                    }
    void            sortAscending()
                    {
                        sort();
                    }

    template<typename ComparatorBool>
    void            stableSort(ComparatorBool is_less)
                    {
                        UT_Array<T>::stableSort(is_less);
                    }
    void            stableSort()
                    {
                        stableSort(std::less<T>());
                    }

    template <typename ComparatorBool>
    T               selectNthLargest(int idx, ComparatorBool is_less)
                    {
                        return UT_Array<T>::selectNthLargest(idx, is_less);
                    }
    T               selectNthLargest(int idx)
                    {
                        return selectNthLargest(idx, std::less<T>());
                    }

    int             uniqueSortedFind(const T &item, Comparator compare) const
                    {
                        return UT_Array<T>::uniqueSortedFind(item, compare);
                    }
    template <typename ComparatorBool>
    int             uniqueSortedFind(const T &item, ComparatorBool is_less) const
                    {
                        return UT_Array<T>::uniqueSortedFind(item, is_less);
                    }
    int             uniqueSortedFind(const T &item) const
                    {
                        return uniqueSortedFind(item, std::less<T>());
                    }
    int             uniqueSortedFindAscending(const T &item) const
                    {
                        return uniqueSortedFind(item);
                    }

    unsigned int    sortedInsert(const T &t, Comparator compare)
                    {
                        return UT_Array<T>::sortedInsert(t, compare);
                    }
    template <typename ComparatorBool>
    unsigned int    sortedInsert(const T &t, ComparatorBool is_less)
                    {
                        return UT_Array<T>::sortedInsert(t, is_less);
                    }
    unsigned int    sortedInsert(const T &t)
                    {
                        return sortedInsert(t, std::less<T>());
                    }

    unsigned int    uniqueSortedInsert(const T &t, Comparator compare)
                    {
                        return UT_Array<T>::uniqueSortedInsert(t, compare);
                    }
    template <typename ComparatorBool>
    unsigned int    uniqueSortedInsert(const T &t, ComparatorBool is_less)
                    {
                        return UT_Array<T>::uniqueSortedInsert(t, is_less);
                    }
    unsigned int    uniqueSortedInsert(const T &t)
                    {
                        return uniqueSortedInsert(t, std::less<T>());
                    }
    unsigned int    uniqueSortedInsertAscending(const T &t)
                    {
                        return uniqueSortedInsert(t);
                    }

    template <typename ComparatorBool>
    void            merge(
                            const UT_Array<T> &other,
                            int direction,
                            bool allow_dups,
                            ComparatorBool is_less)
                    {
                        UT_Array<T>::merge(other, direction, allow_dups,
                                           is_less);
                    }
    void            merge(
                            const UT_ValArray<T> &other,
                            int direction,
                            bool allow_dups)
                    {
                        merge(other, direction, allow_dups, std::less<T>());
                    }

    bool            hasSortedSubset(
                            const UT_ValArray<T> &other,
                            Comparator compare = compareElements) const
                    {
                        return UT_Array<T>::hasSortedSubset(other, compare);
                    }
    void            sortedUnion(
                            const UT_ValArray<T> &other,
                            Comparator compare = compareElements)
                    {
                        UT_Array<T>::sortedUnion(other, compare);
                    }
    void            sortedUnion(
                            const UT_ValArray<T> &other,
                            UT_ValArray<T> &result,
                            Comparator compare = compareElements) const
                    {
                        UT_Array<T>::sortedUnion(other, result, compare);
                    }
    void            sortedIntersection(
                            const UT_ValArray<T> &other,
                            Comparator compare = compareElements)
                    {
                        UT_Array<T>::sortedIntersection(other, compare);
                    }
    void            sortedIntersection(
                            const UT_ValArray<T> &other,
                            UT_ValArray<T> &result,
                            Comparator compare = compareElements) const
                    {
                        UT_Array<T>::sortedIntersection(other, result, compare);
                    }
    void            sortedSetDifference(
                            const UT_ValArray<T> &other,
                            Comparator compare = compareElements)
                    {
                        UT_Array<T>::sortedSetDifference(other, compare);
                    }
    void            sortedSetDifference(
                            const UT_ValArray<T> &other,
                            UT_ValArray<T> &result,
                            Comparator compare = compareElements) const
                    {
                        UT_Array<T>::sortedSetDifference(other, result, compare);
                    }

    unsigned int    heapPush(const T &t, Comparator compare)
                    {
                        return UT_Array<T>::heapPush(t, compare);
                    }
    template <typename ComparatorBool>
    unsigned int    heapPush(const T &t, ComparatorBool is_less)
                    {
                        return UT_Array<T>::heapPush(t, is_less);
                    }
    unsigned int    heapPush(const T &t)
                    {
                        return heapPush(t, std::less<T>());
                    }
    T               heapPop(Comparator compare)
                    {
                        return UT_Array<T>::heapPop(compare);
                    }
    template <typename ComparatorBool>
    T               heapPop(ComparatorBool is_greater)
                    {
                        return UT_Array<T>::heapPop(is_greater);
                    }
    T               heapPop()
                    {
                        return heapPop(std::greater<T>());
                    }

    static bool     isElementZero(const T &a)
                    {
                        return !a;
                    }

    int             removeZeros()
                    {
                        return this->removeIf(isElementZero);
                    }

    // Remove zeros and also resize the array.
    void            collapse()
                    {
                        this->collapseIf(isElementZero);
                    }

    /// Functions which are only specialized for int{32,64}, fpreal{32,64}
    // @{
    /// Returns the sum of the entries in the array.
    T               sum() const
                    {
                        UT_ASSERT(!"Invalid function");
                        return T();
                    }
    /// Prints the constents of the array
    void            display() const
                    {
                        printf("%d entries, contents not displayable.\n",
                                UT_Array<T>::entries());
                    }
    // @}

private:

};

// Assigns src to dest, using the default C++ conversion operator.
template <typename T, typename S>
void
UTconvertArray(UT_Array<T> &dest, const UT_Array<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_Array<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_Array<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_Array );

template <>
inline int
UT_ValArray<fpreal32>::compareElements(const fpreal32 *a, const fpreal32 *b)
{
    const float tol = UTgetCompareFloatsTolerance();
    if( *a>*b+tol )
        return 1;
    if( *a<*b-tol )
        return -1;
    return 0;
}

template <>
inline int
UT_ValArray<fpreal64>::compareElements(const fpreal64 *a, const fpreal64 *b)
{
    const float tol = UTgetCompareFloatsTolerance();
    if( *a>*b+tol )
        return 1;
    if( *a<*b-tol )
        return -1;
    return 0;
}

#define UT_DECL_ARITHMETIC_SPECIALIZATION(T)    \
            template <> UT_API T    UT_ValArray<T>::sum() const; \
            template <> UT_API void UT_ValArray<T>::display() const; \
            /**/
    UT_DECL_ARITHMETIC_SPECIALIZATION(int32)
    UT_DECL_ARITHMETIC_SPECIALIZATION(int64)
    UT_DECL_ARITHMETIC_SPECIALIZATION(fpreal32)
    UT_DECL_ARITHMETIC_SPECIALIZATION(fpreal64)
#undef UT_DECL_ARITHMETIC_SPECIALIZATION

template <>
UT_API void UT_Array<fpreal32>::constant(const fpreal32 &val);

// A helper class to selectively restrict the number of items output by the
// ostream.operator<< 
template<typename T>
class UT_API UT_ArrayPrintLimit
{
public:
    UT_ArrayPrintLimit(const UT_Array<T> &a, uint limit = 100) :
        myA(a), myLimit(limit) {}
private:
    const UT_Array<T>   &myA;
    uint                 myLimit;

    template<typename OS, typename S>
    friend OS &operator<<(OS &os, const UT_ArrayPrintLimit<S> &d);
};

template<typename OS, typename S>
inline OS &
operator<<(OS &os, const UT_ArrayPrintLimit<S> &d)
{
    uint        idx;
    
    os << "[" << d.myA.entries() << "]={";
    for (idx = 0; idx < d.myA.entries(); idx++)
    {
        if (idx > 0) os << ", ";
        if (idx > d.myLimit)
        {
            cerr << "...";
            break;
        }
        os << d.myA(idx);
    }
    os << "}";
    return os;
}

template<typename OS, typename S>
inline OS &
operator<<(OS &os, const UT_Array<S> &d)
{
    os << UT_ArrayPrintLimit<S>(d);
    return os;
}

#endif

---