UT/UT_ValArrayImpl.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 meant to be included by UT_ValArray.h and includes
 *      the template implementations needed by external code.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <VM/VM_Math.h>
#include "UT_Assert.h"
#include "UT_ValArray.h"
#include "UT_Types.h"
#include "UT_Math.h"
#include <algorithm>

template <typename T>
UT_ValArray<T>::UT_ValArray(const UT_ValArray<T> &a)
                    : arrSize(a.entries()), nbrEntries(a.entries())
{
    int64       en;
    
    en = a.entries();
    if (en)
    {
        arr = (T *)calloc(sizeof(T), en);
        memcpy(arr, a.arr, en * sizeof(T));
    }
    else arr = 0;
}

template <typename T>
UT_ValArray<T>::~UT_ValArray()
{ 
   if (arr) free(arr); 
}

template <typename T>
void
UT_ValArray<T>::swap( UT_ValArray<T> &other )
{
    UTswap( arr, other.arr );
    UTswap( arrSize, other.arrSize );
    UTswap( nbrEntries, other.nbrEntries );
}

template <typename T>
unsigned int    
UT_ValArray<T>::insert(unsigned int index)
{
    if (index >= nbrEntries)
    {
        if (index >= arrSize) resize(bumpAlloc(index));
        nbrEntries = index+1;
        return index;
    }
    if (nbrEntries == arrSize)  // we know arr has been allocated
    {
        resize(bumpAlloc(arrSize+1));
    }
    memmove(&arr[index+1], &arr[index],((nbrEntries-index)*sizeof(T)));
     
    nbrEntries++;
    return index;
}

template <typename T>
unsigned int    
UT_ValArray<T>::append(T t)
{
    if (nbrEntries == arrSize) 
        resize(bumpAlloc(arrSize+1));

    arr[nbrEntries] = t;
    return nbrEntries++;
}

template <typename T>
void
UT_ValArray<T>::appendMultiple(T t, int count)
{
    UT_ASSERT_P(count >= 0);
    if (count <= 0)
        return;
    if (nbrEntries + count >= arrSize)
        resize(bumpAlloc(nbrEntries + count));

    int         i;
    for (i = 0; i < count; i++)
        arr[nbrEntries+i] = t;
    nbrEntries += count;
}

template <typename T>
unsigned int            
UT_ValArray<T>::insert(T t, unsigned int  index)
{
    if (index == nbrEntries) return append(t);
    return insertAt(t, index);
}

template <typename T>
unsigned int
UT_ValArray<T>::sortedInsert(T t, Comparator compare)
{
    int     low, mid, high;

    low = 0;
    high = entries() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (compare(&t, &arr[mid]) < 0)
            high = mid - 1;
        else if (compare(&t, &arr[mid]) > 0)
            low = mid + 1;
        else
        {
            insertAt(t, mid);
            return mid;
        }
    }
    insertAt(t, low);
    return low;
}

template <typename T>
unsigned int
UT_ValArray<T>::sortedInsert(T t)
{
    int     low, mid, high;

    low = 0;
    high = entries() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (t < arr[mid])
            high = mid - 1;
        else if (t > arr[mid])
            low = mid + 1;
        else
        {
            insertAt(t, mid);
            return mid;
        }
    }
    insertAt(t, low);
    return low;
}

template <typename T>
unsigned int
UT_ValArray<T>::uniqueSortedInsert(T t, Comparator compare)
{
    int     low, mid, high;

    low = 0;
    high = entries() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (compare(&t, &arr[mid]) < 0)
            high = mid - 1;
        else if (compare(&t, &arr[mid]) > 0)
            low = mid + 1;
        else
            return (unsigned)mid;
    }
    insertAt(t, low);
    return low;
}

template <typename T>
unsigned int
UT_ValArray<T>::uniqueSortedInsert(T t)
{
    int     low, mid, high;

    low = 0;
    high = entries() - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (t < arr[mid])
            high = mid - 1;
        else if (t > arr[mid])
            low = mid + 1;
        else
            return (unsigned)mid;
    }
    insertAt(t, low);
    return low;
}

template <typename T>
int
UT_ValArray<T>::uniqueSortedFind(T item) const
{
    int     low;
    int     mid;
    int     high;

    low = 0;
    high = entries() - 1;
    while( low <= high )
    {
        mid = (low + high) / 2;
        if( item < arr[mid] )
            high = mid - 1;
        else if( item > arr[mid] )
            low = mid + 1;
        else // found item
            return mid;
    }

    return -1;
}

template <typename T>
unsigned int
UT_ValArray<T>::heapPush(T t, Comparator compare)
{
    int     i = append(t);

    while( i > 0 && compare(&arr[i / 2], &t) < 0 )
    {
        arr[i] = arr[i / 2];
        i = i / 2;
    }
    arr[i] = t;
    return i;
}

template <typename T>
unsigned int
UT_ValArray<T>::heapPush(T t)
{
    int     i = append(t);

    while( i > 0 && (arr[i / 2] < t) )
    {
        arr[i] = arr[i / 2];
        i = i / 2;
    }
    arr[i] = t;
    return i;
}

template <typename T>
T
UT_ValArray<T>::heapPop(Comparator compare)
{
    UT_ASSERT_P(nbrEntries > 0);
    T result = (T)0;
    if( nbrEntries > 0 )
    {
        result = arr[0];
        arr[0] = arr[nbrEntries - 1];
        removeAt(nbrEntries - 1);
        heapify(0, compare);
    }
    return result;
}

template <typename T>
T
UT_ValArray<T>::heapPop()
{
    UT_ASSERT_P(nbrEntries > 0);
    T result = (T)0;
    if( nbrEntries > 0 )
    {
        result = arr[0];
        arr[0] = arr[nbrEntries - 1];
        removeAt(nbrEntries - 1);
        heapify(0);
    }
    return result;
}


template <typename T>
unsigned int
UT_ValArray<T>::concat(const UT_ValArray<T> &a)
{
    unsigned int extraSpace;

    extraSpace = a.nbrEntries;

    if ( ( arrSize - nbrEntries ) <= extraSpace )
        resize( arrSize + extraSpace ); // for sure this is enough

    memcpy( &arr[nbrEntries], &(a.arr[0]), extraSpace * sizeof(T) );

    return (nbrEntries += extraSpace);
}

template <typename T>
unsigned int    
UT_ValArray<T>::multipleInsert(unsigned int index, unsigned int count)
{
    int bigindex = index+count;

    if (index >= nbrEntries)
    {
        if (bigindex >= (int)arrSize) resize(bumpAlloc(bigindex));
        nbrEntries = bigindex;
        return index;
    }
    if ((nbrEntries + count) > arrSize)  // we know arr has been allocated
    {
        resize(bumpAlloc(nbrEntries+count));
    }

    memmove(&arr[bigindex], &arr[index],((nbrEntries-index)*sizeof(T)));
    nbrEntries += count;
    return index;
}

template <typename T>
unsigned int    
UT_ValArray<T>::insertAt(T t, unsigned int index)
{
    if (index >= nbrEntries)
    {
        if (index >= arrSize) resize(bumpAlloc(index));
        nbrEntries = index+1;
        arr[index] = t;
        return index;
    }
    if (nbrEntries == arrSize) // we know arr has been allocated
    {
        resize(bumpAlloc(arrSize));
    }
    memmove(&arr[index+1], &arr[index],((nbrEntries-index)*sizeof(T)));
    arr[index] = t;

    nbrEntries++;
    return index;
}

template <typename T>
int             
UT_ValArray<T>::findAndRemove(T t)
{
    int idx = find(t);
    return (idx < 0) ? -1 : removeAt((unsigned int)idx);
}

template <typename T>
int
UT_ValArray<T>::removeAt(unsigned int idx)
{
    if (idx != --nbrEntries)
        memmove(&arr[idx], &arr[idx+1], ((nbrEntries-idx)*sizeof(T)));

    return idx;
}

template <typename T>
int
UT_ValArray<T>::shift(unsigned int srcIdx, unsigned int destIdx,
                          unsigned int howMany)
{
    if (srcIdx == destIdx) return 0;
    unsigned int sIdx = srcIdx  + howMany - 1;
    unsigned int dIdx = destIdx + howMany - 1;
    if (sIdx>=arrSize || dIdx>=arrSize) return -1;
    if (dIdx>=nbrEntries|| (sIdx==nbrEntries-1 && sIdx > dIdx))
        nbrEntries = dIdx+1;
        
    memmove(&arr[destIdx], &arr[srcIdx],  (howMany*sizeof(T)));
    return 0;
}

template <typename T>
void
UT_ValArray<T>::cycle(int howMany)
{
    T           *tempPtr;
    int          numShift;      //  The number of items we shift
    int          remaining;     //  nbrEntries - numShift

    if (howMany == 0 || nbrEntries < 1) return;

    numShift = howMany % (int)nbrEntries;
    if (numShift < 0) numShift += nbrEntries;
    remaining = nbrEntries - numShift;
    tempPtr = new T[numShift];

    memmove(tempPtr,        &arr[remaining], (numShift * sizeof(T)));
    memmove(&arr[numShift], &arr[0],         (remaining  * sizeof(T)));
    memmove(&arr[0],        tempPtr,         (numShift * sizeof(T)));

    delete [] tempPtr;
}

template <typename T>
void
UT_ValArray<T>::constant(T value)
{
    for (int i = 0; i < nbrEntries; i++)
    {
        arr[i] = value;
    }
}

template <typename T>
void
UT_ValArray<T>::constant()
{
    memset(arr, 0, nbrEntries*sizeof(T));
}

template <typename T>
int
UT_ValArray<T>::find(T t, unsigned int s) const
{
    const T             *p, *end;

    for( p = arr + s, end = arr + nbrEntries; p < end;  ++p )
        if( *p == t ) return (p - arr);
    return -1;
}

template <typename T>
int
UT_ValArray<T>::find(T t, Comparator compare) const
{
    T   *found;

    if( nbrEntries == 0 ) return -1;

    found = (T *)::bsearch(&t, arr, (int)nbrEntries, sizeof(T),
                        (ut_ptr_compare_func_t)compare);
    return found ? (found - arr) : -1;
}

template <typename T>
void
UT_ValArray<T>::reverse()
{
    int  i;
    for( i=0; i<nbrEntries/2; i++ )
        UTswap( arr[i], arr[nbrEntries-1-i] );
}

template <typename T>
void            
UT_ValArray<T>::sort(Comparator compare)
{
    qsort(arr, nbrEntries, sizeof(T), (ut_ptr_compare_func_t)compare);
}

template <typename T>
void
UT_ValArray<T>::sortAscending()
{
    // Since our members are fungible, stable vs non-stable is irrelevant.
    std::sort(arr, arr + nbrEntries);
}

template <typename T>
T
UT_ValArray<T>::selectNthLargest(int idx)
{
    // The idea of returning doesn't make sense if we have
    // an empty array.
    UT_ASSERT(entries() > 0);
    if (entries() == 0)
        return (T)0;

    idx = SYSclamp(idx, (int)0, (int)(entries())-1);

    std::nth_element(arr, &arr[idx], &arr[entries()]);

    return arr[idx];
}

template <typename T>
void            
UT_ValArray<T>::resize(unsigned int sz, unsigned short)
{
    if (sz == arrSize) return;
    if (sz == 0      )
    {
        if (arr) free(arr);
        arr     = 0;
        arrSize = nbrEntries = 0;
        return; 
    }


    if (arr)
    {
         arr = (T *)realloc(arr, sz*sizeof(T));
         // Zero clear new stuff.
         if (sz > arrSize)
             memset(arr+arrSize, 0, sizeof(T)*(sz-arrSize));
    }
    else arr = (T *)calloc(sizeof(T), sz);

    if (sz < arrSize && nbrEntries > sz) nbrEntries = sz;
    arrSize = sz;
}

template <typename T>
UT_ValArray<T> &
UT_ValArray<T>::operator=(const UT_ValArray<T> &a)
{
    if (this == &a)
        return *this;

    if (arrSize < a.entries())
        resize(a.entries());

    memcpy(arr, a.arr, a.entries()*sizeof(T));
    nbrEntries = a.entries();

    return *this;
}

template <typename T>
bool
UT_ValArray<T>::operator==(const UT_ValArray<T> &a) const
{
    if (this == &a) return true;
    if (nbrEntries != a.entries()) return false;
    for (int i = 0; i < nbrEntries; i++)
        if (!(arr[i] == a(i))) return false;
    return true;
}

template <typename T>
bool
UT_ValArray<T>::operator!=(const UT_ValArray<T> &a) const
{
    return (!operator==(a));
}

template <typename T>
int
UT_ValArray<T>::isEqual(const UT_ValArray<T> &a, Comparator compare) const
{
    if (this == &a) return 1;
    if (nbrEntries != a.entries()) return 0;
    for (unsigned int i = 0; i < nbrEntries; i++)
    {
        T       v2 = a(i);
        if (compare(&arr[i], &v2)) return 0;
    }
    return 1;
}

template <typename T>
unsigned int    
UT_ValArray<T>::apply(int (*applyFct)(T &t, void *d), void *d)
{
    unsigned int i;
    for (i = 0; i < nbrEntries; i++)
        if (applyFct(arr[i], d)) break;
    return i;
}

template <typename T>
void
UT_ValArray<T>::display() const
{
    printf("%d entries, contents not displayable.\n");
}

template <typename T>
void
UT_ValArray<T>::heapify(unsigned int idx, Comparator compare)
{
    int  lidx = 2*idx, ridx = lidx + 1;
    int  largest = idx;

    if( lidx < nbrEntries && compare(&arr[lidx], &arr[largest]) > 0 )
    {
        largest = lidx;
    }
    if( ridx < nbrEntries && compare(&arr[ridx], &arr[largest]) > 0 )
    {
        largest = ridx;
    }
    if( largest != idx )
    {
        UTswap(arr[idx], arr[largest]);
        heapify(largest, compare);
    }
}

template <typename T>
void
UT_ValArray<T>::heapify(unsigned int idx)
{
    int  lidx = 2*idx, ridx = lidx + 1;
    int  largest = idx;

    if( lidx < nbrEntries && (arr[lidx] > arr[largest]) )
    {
        largest = lidx;
    }
    if( ridx < nbrEntries && (arr[ridx] > arr[largest]) )
    {
        largest = ridx;
    }
    if( largest != idx )
    {
        UTswap(arr[idx], arr[largest]);
        heapify(largest);
    }
}

template <typename T>
void
UT_ValArray<T>::fromStdVector(const std::vector<T> &vec)
{
    entries(0);
    for (int i=0; i<vec.size(); ++i)
        append(vec[i]);
}

template <typename T>
void
UT_ValArray<T>::toStdVector(std::vector<T> &vec) const
{
    vec.clear();
    for (int i=0; i < entries(); ++i)
        vec.push_back((*this)(i));
}

// 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 T>
void
UT_ValArray<T>::merge( const UT_ValArray<T> &other, int direction, bool allow_dups )
{
    UT_ValArray<T>      result;
    int         our_item;
    int         our_idx;
    int         other_item;
    int         other_idx;
    int         item_dir;

    // handle trivial cases to avoid extra work
    if (other.entries() == 0)
        return;
    if (entries() == 0)
    {
        concat(other);
        return;
    }

    UT_ASSERT( direction == -1 || direction == +1 );
    direction = (direction > 0) ? +1 : -1;

    our_idx = 0;
    other_idx = 0;
    while( our_idx < entries() && other_idx < other.entries() )
    {
        our_item = (*this)(our_idx);
        other_item = other(other_idx);

        item_dir = our_item - other_item;
        if( item_dir != 0 )
        {
            // we need to do an comparison in the next line to take care of the
            // fact that -INT_MIN is still less than 0.
            item_dir = ( (item_dir > 0) ? +1 : -1 ) * direction;
        }

        if( item_dir < 0 )
        {
            result.append( our_item );
            our_idx++;
        }
        else if( item_dir > 0 )
        {
            result.append( other_item );
            other_idx++;
        }
        else
        {
            result.append( our_item );
            our_idx++;
            if( allow_dups )
                result.append( other_item );
            other_idx++;
        }
    }

    UT_ASSERT( our_idx == entries() || other_idx == other.entries() );
    // TODO: these loops are inefficient, we should be using memcpy instead
    for( ; our_idx < entries(); our_idx++ )
        result.append( (*this)(our_idx) );
    for( ; other_idx < other.entries(); other_idx++ )
        result.append( other(other_idx) );

    // finally swap the result into us
    swap( result );
}

template <typename T>
void
UT_ValArray<T>::sortedUnion(const UT_ValArray<T> &other)
{
    UT_ValArray<T>          temp;
    sortedUnion( other, temp );
    swap( temp );
}

template <typename T>
void
UT_ValArray<T>::sortedUnion(const UT_ValArray<T> &other,
                            UT_ValArray<T> &result) const
{
    T       *first1 = arr;
    T       *last1 = arr + nbrEntries;
    T       *first2 = other.arr;
    T       *last2 = other.arr + other.nbrEntries;

    // Can't store to either input.
    UT_ASSERT(&result != this && &result != &other);
    UT_ASSERT(result.entries() == 0);

    while( first1 != last1 && first2 != last2 )
    {
        if( *first1 < *first2 )
        {
            result.append( *first1 );
            ++first1;
        }
        else if( *first2 < *first1 )
        {
            result.append( *first2 );
            ++first2;
        }
        else
        {
            result.append( *first1 );
            ++first1;
            ++first2;
        }
    }
    while( first1 != last1 )
    {
        result.append( *first1 );
        ++first1;
    }
    while( first2 != last2 )
    {
        result.append( *first2 );
        ++first2;
    }
}

template <typename T>
void
UT_ValArray<T>::sortedIntersection(const UT_ValArray<T> &other)
{
    UT_ValArray<T>          temp;
    sortedIntersection( other, temp );
    swap( temp );
}

template <typename T>
void
UT_ValArray<T>::sortedIntersection( const UT_ValArray<T> &other,
                            UT_ValArray<T> &result ) const
{
    T           *first1 = arr;
    T           *last1 = arr + nbrEntries;
    T           *first2 = other.arr;
    T           *last2 = other.arr + other.nbrEntries;

    while (first1 != last1 && first2 != last2) 
        if( *first1 < *first2 )
            ++first1;
        else if( *first2 < *first1 )
            ++first2;
        else {
            result.append( *first1 );
            ++first1;
            ++first2;
        }
}

template <typename T>
void
UT_ValArray<T>::sortedSetDifference(const UT_ValArray<T> &other)
{
    UT_ValArray<T>          temp;
    sortedSetDifference( other, temp );
    swap( temp );
}

template <typename T>
void
UT_ValArray<T>::sortedSetDifference( const UT_ValArray<T> &other,
                            UT_ValArray<T> &result ) const
{
    T           *first1 = arr;
    T           *last1 = arr + nbrEntries;
    T           *first2 = other.arr;
    T           *last2 = other.arr + other.nbrEntries;

    while (first1 != last1 && first2 != last2)
    {
        if( *first1 < *first2 )
        {
            result.append( *first1 );
            ++first1;
        }
        else if( *first2 < *first1 )
            ++first2;
        else
        {
            ++first1;
            ++first2;
        }
    }
    while( first1 != last1 )
    {
        result.append( *first1 );
        ++first1;
    }
}

template <typename T>
void
UT_ValArray<T>::sortedRemoveDuplicates()
{
    int                 src, dst, n;
    T                   cmp;

    n = entries();

    // Trivial, no duplicates!
    if (n < 2)
        return;

    dst = 1;
    cmp = (*this)(0);
    for (src = 1; src < n; src++)
    {
        if ((*this)(src) == cmp)
        {
            // Don't increment dst.
        }
        else
        {
            if (src != dst)
            {
                (*this)(dst) = (*this)(src);
            }
            dst++;
        }
    }

    // Store the number of remaining elements.
    entries(dst);
}

---