UT/UT_RefMatrix.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.
 *      20 Maud St.
 *      Toronto, Ontario,  M5V 2M5
 *      Canada
 *      416-366-4607
 *
 * NAME:        Utility Library (C++)
 *
 * COMMENTS:
 *      This is a class template that implements a resizable matrix 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_RefMatrix<int>               iObj;
 *              UT_RefMatrix<GeoPrimMesh>       mObj;
 *              UT_RefMatrix<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_ValMatrix, which passes arguments by value to avoid the
 *      referencing overhead.
 */

#ifndef __UT_RefMatrix_h__
#define __UT_RefMatrix_h__

#include "UT_RefArray.h"
#include "UT_PtrArray.h"


template <class utRef>
class UT_RefMatrix {
public:
    // Trivial constructor and destructor:
    explicit UT_RefMatrix(unsigned int mSz = 0, unsigned int nSz = 0) 
    : rowArr(mSz)               { nbrCols = nSz; }
    virtual ~UT_RefMatrix(void);

    // Copy constructor that copies each utRef from the source matrix to 
    // this matrix using the '=' operator.
    UT_RefMatrix(const UT_RefMatrix<utRef> &m);

    // Append a row or insert it at a given index. The matrix is grown to 
    // accommodate it. If dupliCheck is 1, we first search for duplicates; the
    // search method uses the (*compare) function on pairs of Things when
    // specified, and the '==' operator on UT_RefArray pairs otherwise. The
    // fast insertion methods assign the address of the Ref_Array to the 
    // pointer in the row matrix rather than copying each element piece by 
    // piece. All methods return the index of the found or inserted row.
    // t1 and t2 must be pointers to utRef.
    unsigned int        insertRow(unsigned int index); 
    unsigned int        insertRow(const UT_RefArray<utRef> &r, 
                                  unsigned int index,
                                  unsigned short dupliCheck = 0);
    unsigned int        insertRow(const UT_RefArray<utRef> &r, 
                                  unsigned int index,
                                  int (*cmpare)(const void *t1,const void *t2));
    unsigned int        appendRow(const UT_RefArray<utRef> &r, 
                                  unsigned short dupliCheck = 0);
    unsigned int        appendRow(const UT_RefArray<utRef> &r, 
                                  int (*cmpare)(const void *t1,const void *t2));

    // Fast insertion: as mentioned above, we just assign the address of r to
    // the a row array pointer. The UT_RefMatrix destructor will delete &r
    // when called. Use these methods with care.
    unsigned int        insertRowFast(const UT_RefArray<utRef> &r, 
                                      unsigned int index,
                                      unsigned short dupliCheck = 0);
    unsigned int        insertRowFast(const UT_RefArray<utRef> &r, 
                                      unsigned int index, int (*compare)
                                      (const void *t1,const void *t2));
    unsigned int        appendRowFast(const UT_RefArray<utRef> &r, 
                                      unsigned short dupliCheck = 0);
    unsigned int        appendRowFast(const UT_RefArray<utRef> &r,int (*compare)
                                     (const void *t1,const void *t2));

    // Append a column or insert it at a given index. The matrix is grown to 
    // accommodate it. If dupliCheck is 1, we first search for duplicates; the
    // search method uses the (*compare) function on pairs of Things when
    // specified, and the '==' operator otherwise. t1 and t2 must be pointers
    // to utRef. All methods return the index of the found or inserted column,
    // or -1 if the matrix has no rows. It is OK to insert a column into a 
    // matrix with zero row entries but with space already allocated for at 
    // least one row.
    int         insertCol(unsigned int index); 
    int         insertCol(const UT_RefArray<utRef> &c, 
                                 unsigned int index,
                                 unsigned short dupliCheck = 0);
    int         insertCol(const UT_RefArray<utRef> &c, 
                                 unsigned int index,
                                 int (*compare)(const void *t1,const void *t2));
    int         appendCol(const UT_RefArray<utRef> &c, 
                                 unsigned short dupliCheck = 0);
    int         appendCol(const UT_RefArray<utRef> &c, 
                                 int (*compare)(const void *t1,const void *t2));

    // Remove a row and possibly all its duplicates given a row object or its
    // index in the row array. The methods that take a (*compare)() function
    // use it to compare two Things; the other methods use the '==' operator.
    // to compare two UT_RefArrays.
    // If dupliCheck is 1, all duplicates found will be removed too. All
    // methods return the row index (index of first row removed). Do not
    // try to access the row after removal, because its contets are undefined.
    // t1 and t2 must be pointers to utRef.
    // For increased efficiency, try to use the 'index' methods whenever 
    // possible.
    int         removeRow(const UT_RefArray<utRef> &r, 
                                  unsigned short dupliCheck = 0);
    int         removeRow(unsigned int index,
                                  unsigned short dupliCheck = 0);
    int         removeRow(const UT_RefArray<utRef> &r, 
                                  int (*compare)(const void *t1,const void *t2),
                                  unsigned short dupliCheck = 0);
    int         removeRow(unsigned int index,
                                  int (*compare)(const void *t1,const void *t2),
                                  unsigned short dupliCheck = 0);

    // Remove a column and possibly all its dupliCheck given a column object or
    // its index. The methods that take a (*compare)() function
    // use it to compare two Things; the other methods use the '==' operator.
    // If dupliCheck is 1, all duplicates found will be removed too. All
    // methods return the column index (index of last column removed).
    // t1 and t2 must be pointers to utRef.
    // For increased efficiency, try to use the 'index' methods whenever 
    // possible.
    int         removeCol(const UT_RefArray<utRef> &c, 
                                  unsigned short dupliCheck = 0);
    int         removeCol(unsigned int index,
                                  unsigned short dupliCheck = 0);
    int         removeCol(const UT_RefArray<utRef> &c, 
                                  int (*compare)(const void *t1,const void *t2),
                                  unsigned short dupliCheck = 0);
    int         removeCol(unsigned int index,
                                  int (*compare)(const void *t1,const void *t2),
                                  unsigned short dupliCheck = 0);

    // Performs a cyclical shift on the rows and columns
    void                cycle(int rowshift, int colshift);

    // Compare the two matrices: to return 1, they should have the same 
    // number or entries, and their Things should all match when compared
    // with '==' or compare() respectively.
    // t1 and t2 must be pointers to utRef.
    int                 operator==(const UT_RefMatrix<utRef> &m) const;
    int                 isEqual(const UT_RefMatrix<utRef> &m,
                                int (*compare)(const void *t1,const void *t2)
                               ) const;

    // Assignment operator that copies the array piece by piece using the
    // '=' operator defined in UT_RefArray. The row and column size of this
    // matrix must be greater or equal to the "used" row and column count of
    // matrix m.
    UT_RefMatrix<utRef> &operator=(const UT_RefMatrix<utRef> &m);

    // Subscript operators to return rows. operator() does not check if the
    // matrix needs to be resized. operator[] grows the array of rows to 
    // accommodate the index if necessary; .
    UT_RefArray<utRef>          &operator()(unsigned int i)
                                { 
                                    return *rowArr(i); 
                                }
    UT_RefArray<utRef>          &operator[](unsigned int i);
    const UT_RefArray<utRef>    &operator()(unsigned int i) const 
                                { 
                                    return *rowArr(i); 
                                }
    const UT_RefArray<utRef>    &operator[](unsigned int i) const
                                { 
                                    return *rowArr[i]; 
                                }

    // Return an element of the matrix, WITHOUT any BOUND CHECKING. Use 
    // safeGet() if you don't know whether you are within range or not.
    const utRef                 &operator()(unsigned i, unsigned j) const
                                {
                                    return rowArr(i)->operator()(j);
                                }
    utRef                       &operator()(unsigned i, unsigned j) 
                                {
                                    return rowArr(i)->operator()(j);
                                }

    // Return an element of the matrix, growing the matrix if necessary in
    // the non-const case.
    const utRef                 &safeGet(unsigned i, unsigned j) const
                                {
                                    return ((*this)[i])[j]; // yes, operator[]
                                }
    utRef                       &safeGet(unsigned i, unsigned j) 
                                {
                                    if (rowArr.entries() <= i) insertRow(i);
                                    if (j >= rowArr(0)->entries()) insertCol(j);
                                    return ((*this)[i])(j); // yes, operator[]
                                }

    // Return a specified row or column. row() returns an actual reference to
    // the row entry in the matrix WITHOUT growing the array of rows if
    // needed.
    // col() builds a UT_RefArray from scratch by allocating heap space for it
    // and copying each element into it with the '=' operator. The col() 
    // array must be freed by YOU.
    const UT_RefArray<utRef>    &row(unsigned int i) const {return (*this)(i);}
    UT_RefArray<utRef>          &row(unsigned int i)       {return (*this)(i);}
    UT_RefArray<utRef>          &col(unsigned int j) const;

    // Search for t in each row in one of two ways: linearly using the '==' 
    // operator, or binary using the function specified in the parameter list 
    // respectively. find() returns 0 and the indices of the matching element,
    // or -1 if not found. t1 and t2 must be pointers to utRef.
    int         find(const utRef &t, unsigned int *m, unsigned int *n) const;
    int         find(const utRef &t, unsigned int *m, unsigned int *n,
                     int (*compare)(const void *t1, const void *t2)) const;

    // Search for a row or a column in one of two ways: binary, using a user
    // defined function (*compare) to compare two Things, or linearly using
    // the '==' operator between UT_RefArrays in findRow() and between Things
    // in findCol(). Note that the arrays to be compared must have an equal
    // number of entries, and not necessarily the same size.
    // Parameter s indicates what index to start searching at.
    // All methods return the row/col index if found, and -1 otherwise.
    // t1 and t2 must be pointers to utRef.
    int findRow(const UT_RefArray<utRef> &r, unsigned int s = 0) const;
    int findRow(const UT_RefArray<utRef> &r,
                        int (*compare)(const void *t1, const void *t2),
                        unsigned int s = 0) const;
    int findCol(const UT_RefArray<utRef> &c, unsigned int s = 0) const;
    int findCol(const UT_RefArray<utRef> &c,
                        int (*compare)(const void *t1, const void *t2),
                        unsigned int s = 0) const;

    // Return the number of rows and column space has been allocated for, and
    // the number of entries used in the rows and columns.
    unsigned int        rows(void) const        { return rowArr.capacity();   }
    unsigned int        cols(void) const        { return nbrCols; }
    unsigned int        usedRows(void) const    { return rowArr.entries();}
    unsigned int        usedCols(void) const    
                        {
                            // Can you think of a better way to do this?
                            return (rowArr.entries()) ? rowArr(0)->entries():0;
                        }
    unsigned short      isEmpty(void) const
                        { 
                            return rowArr.entries()     == 0 || 
                                  (rowArr.entries()     == 1 &&
                                   rowArr(0)->entries() == 0 );
                        }

    // 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 mSz, unsigned int nSz,
                               unsigned short copyFlag=1);

    // Apply a user-defined function to each element of the matrix 
    // as int as the function returns zero. If applyFct returns
    // 1, apply() stops traversing the list and returns 1; otherwise, apply()
    // returns 0;
    int                 apply(int (*applyFct)(utRef &t, void *d), void *d);


protected:
    // Return a reference to the array of arrays:
    const UT_PtrArray< UT_RefArray<utRef>*> &data(void) const { return rowArr; }
    
private:
    // Array of rows, where each row is a reference array of type utRef:
    UT_PtrArray<UT_RefArray<utRef>*>    rowArr;

    // Number of allocated columns in each row.
    unsigned int         nbrCols;

    // Guts if the insert(...) methods.
    unsigned int        assignRow(const UT_RefArray<utRef> &r, 
                                  unsigned int index)
                        {
                            rowArr(index) = new UT_RefArray<utRef>(nbrCols);
                           *rowArr(index) = r;
                            return index;
                        }
    unsigned int        insertFastFill(const UT_RefArray<utRef> &r, 
                                       unsigned int index);
    unsigned int        insertSlowFill(unsigned int index, 
                                   unsigned int uRows, unsigned int uCols);

    // Guts of removeCol().
    void                removeOneCol(unsigned int index);

    // Guts of removeRow().
    void                removeOneRow(unsigned int index)
                        {
                            UT_RefArray<utRef> *rdel = rowArr(index);
                            rowArr.remove(index);
                            delete rdel;
                        }
};

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


#endif

---