Table (2D array)

[haydxn]

This is a class template for 2D arrays. There are actually two classes - TableAllocationBase handles most of the guts, but Table is the one to use.
It allows you to add/insert/remove columns and rows, and it automatically does all the horrible moving-memory-about business. You can also use functions like addRowWithValue(value), and setEntireColumn(value) to quickly populate it. Also, since it’s row major, you can use getRowData(rowIndex) to return a pointer to the contiguous data for that row (which should be valid as an array of getNumColumns() elements).

There are still plenty of things missing (it doesn’t have any additional constructors yet, for example), and it whilst it has been working fine for me, I haven’t tried to do anything too mental with it yet. In particular, I’ve yet to verify the thread safety of it in any way - it’s got all the locks and stuff though so who knows !

[code]///////////////////////////////////////////////////////////////////////////////
// Table terminology assumes a ROW MAJOR orientation
///////////////////////////////////////////////////////////////////////////////

template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
class TableAllocationBase : public TypeOfCriticalSectionToUse
{
public:

TableAllocationBase ()
:   numColumns(0),
    numRows(0)
{
}
    
~TableAllocationBase ()
{
}
    
inline int getNumColumns () const
{
    return numColumns;
}

inline int getNumRows () const
{
    return numRows;
}

inline int getTotalSize () const
{
    return data.numAllocated;
}

inline ElementType* cellData (int column, int row)
{
    return data.elements + cellIndex (column, row);
}

inline const ElementType* cellData (int column, int row) const
{
    return data.elements + cellIndex (column, row);
}

inline ElementType* getRowStart (int row) const
{
    return data.elements + (row * numColumns);
}

inline ElementType* getColumnStart (int column) const
{
    return data.elements + column;
}
    
inline int cellIndex (int column, int row) const
{
    return (row * numColumns) + column;
}
    
void setSize (int newNumColumns, int newNumRows)
{
    if (newNumColumns == numColumns && newNumRows == numRows)
        return;
        
    int newSize = newNumRows * newNumColumns;

    if (newSize > data.numAllocated)
        data.setAllocatedSize (newSize);
        
    if (newNumColumns > numColumns)
        enlargeRows (newNumColumns, newNumRows);
    else if (newNumColumns < numColumns)
        shrinkRows (newNumColumns, newNumRows);
        
    if (newNumRows > numRows)
        clearNewRows (newNumColumns, newNumRows);
        
    if (newSize < data.numAllocated)
        data.setAllocatedSize (newSize);
        
    numRows = newNumRows;
    numColumns = newNumColumns;
}

void ensureSize (int requiredNumColumns, int requiredNumRows)
{
    if (requiredNumColumns > numColumns || requiredNumRows > numRows)
    {
        requiredNumColumns = jmax (numColumns,requiredNumColumns);
        requiredNumRows = jmax (numRows,requiredNumRows);
        setSize(requiredNumColumns, requiredNumRows);
    }
}

void moveRows (int startRow, int numRowsToMove, int distance)
{
    jassert (validateMoveParameters(startRow,numRowsToMove,distance,numRows));

    int rowSizeInBytes = numColumns * sizeof(ElementType);
    int numBytesToMove = rowSizeInBytes * numRowsToMove;
    ElementType* sourceStart = getRowStart (startRow);
    ElementType* destStart = getRowStart (startRow + distance);
    memmove(destStart,sourceStart,numBytesToMove);
}

void moveColumns (int startColumn, int numColumnsToMove, int distance)
{
    jassert (validateMoveParameters(startColumn,numColumnsToMove,distance,numColumns));
    
    int rowChunkSizeInBytes = numColumnsToMove * sizeof(ElementType);
    int destColumn = startColumn + distance;
    for (int row = 0; row<numRows; ++row)
    {
        ElementType* sourceStart = cellData (startColumn, row);
        ElementType* destStart = cellData (destColumn, row);
        memmove(destStart,sourceStart,rowChunkSizeInBytes);
    }
}

bool validateMoveParameters (int start, int numToMove, int distance, int axisSize)
{
    // The upper and lower limits of both start and end regions must fit.
    // This can no doubt be done quicker!
    
    int lastToMove = start + numToMove - 1;
    
    if (!isPositiveAndBelow(start, axisSize))
        return false;
    if (!isPositiveAndBelow(lastToMove, axisSize))
        return false;
    if (!isPositiveAndBelow(start + distance, axisSize))
        return false;
    if (!isPositiveAndBelow(lastToMove + distance, axisSize))
        return false;

    return true;
}

private:

void enlargeRows (int newNumColumns, int newNumRows)
{
    jassert(newNumColumns > numColumns);
    jassert (data.numAllocated >= (newNumColumns * newNumRows)); // Must already be big enough!

    int oldRowSizeInBytes = numColumns * sizeof(ElementType);
    int rowGrowthInBytes = (newNumColumns - numColumns) * sizeof(ElementType);

    int topRow = jmin(numRows, newNumRows) - 1;
        
    // We need to move the kept old rows up to their new positions
    for (int row = topRow; row > 0; --row)
    {
        ElementType* oldStart = data.elements + (row * numColumns);
        ElementType* newStart = data.elements + (row * newNumColumns);
            
        // Move the old row up...
        memmove (newStart, oldStart, oldRowSizeInBytes);
        // Clear the end of the new row...
        memset (newStart + numColumns, 0, rowGrowthInBytes);
    }
        
    if (numRows > 0)
    {
        // ... and clear the end of the first row (we don't need to move it)
        memset (data.elements + numColumns, 0, rowGrowthInBytes);
    }
}

void shrinkRows (int newNumColumns, int newNumRows)
{
    jassert(newNumColumns < numColumns);

    int newRowSizeInBytes = newNumColumns * sizeof(ElementType);
    int topRow = jmin(numRows, newNumRows) - 1;
        
    // We need to move the kept old rows down to their new positions
    for (int row = 1; row <= topRow; ++row)
    {
        ElementType* oldStart = data.elements + (row * numColumns);
        ElementType* newStart = data.elements + (row * newNumColumns);
            
        // Move the old row down...
        memmove (newStart, oldStart, newRowSizeInBytes);
    }
}
    
void clearNewRows (int newNumColumns, int newNumRows)
{
    jassert (data.numAllocated >= (newNumColumns * newNumRows)); // Must already be enlarged!

    if (newNumRows > numRows)
    {
        // Clear the new rows
        ElementType* newRowStart = data.elements + (numRows * newNumColumns);
        int numNewRows = newNumRows - numRows;
        int totalNewBytesToClear = (numNewRows * newNumColumns) * sizeof(ElementType);
        memset (newRowStart, 0, totalNewBytesToClear);
    }
}
    
ArrayAllocationBase< ElementType, DummyCriticalSection > data;
int numColumns;
int numRows;

};

///////////////////////////////////////////////////////////////////////////

template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
class Table
{
private:
typedef PARAMETER_TYPE (ElementType) ParameterType;

public:

Table ()
:   rowsUsed(0),
    columnsUsed(0)
{
}

~Table ()
{
}

int getNumRows () const
{
    return rowsUsed;
}

int getNumColumns () const
{
    return columnsUsed;
}

int getTotalSize () const
{
    return rowsUsed * columnsUsed;
}

int getNumAllocatedRows () const
{
    return data.getNumRows();
}

int getNumAllocatedColumns () const
{
    return data.getNumColumns();
}

void setSize (int desiredNumColumns, int desiredNumRows)
{
    jassert ((desiredNumColumns * desiredNumRows) >= 0);
    const ScopedLockType lock (getLock());
    
    // could probably have something clever to determine the
    // optimal order to do this in... but right now, in the
    // words of Tim Gunn... "Make it work!"

    const int rowsToAdd = desiredNumRows - rowsUsed;
    if (rowsToAdd > 0)
        insertRows (rowsUsed, rowsToAdd);
    else if (rowsToAdd < 0)
        removeRows (desiredNumRows, -rowsToAdd);

    const int columnsToAdd = desiredNumColumns - columnsUsed;
    if (columnsToAdd > 0)
        insertColumns (columnsUsed, columnsToAdd);
    else if (columnsToAdd < 0)
        removeColumns (desiredNumColumns, -columnsToAdd);
}

ElementType get (int column, int row) const
{
    const ScopedLockType lock (getLock());
    if (isPositiveAndBelow(column, columnsUsed) && isPositiveAndBelow(row, rowsUsed))
        return *data.cellData (column, row);
    return ElementType();
}

ElementType& getReference (int column, int row)
{
    const ScopedLockType lock (getLock());
    jassert (isPositiveAndBelow(column, columnsUsed) && isPositiveAndBelow(row, rowsUsed));
    return *data.cellData (column, row);
}

const ElementType* getRowData (int row) const
{
    return data.getRowStart (row);
}

ElementType* getRowData (int row)
{
    return data.getRowStart (row);
}

void set (int column, int row, ParameterType value)
{
    const ScopedLockType lock (getLock());
    if (isPositiveAndBelow(column, columnsUsed) && isPositiveAndBelow(row, rowsUsed))
        *data.cellData (column,row) = value;
}

void setUnchecked (int column, int row, ParameterType value)
{
    const ScopedLockType lock (getLock());
    *data.cellData (column, row) = value;
}

void ensureAllocatedRows (int requiredRows)
{
    const ScopedLockType lock (getLock());
    data.ensureSize (columnsUsed, requiredRows);
}

void ensureAllocatedColumns (int requiredColumns)
{
    const ScopedLockType lock (getLock());
    data.ensureSize (requiredColumns, rowsUsed);
}

void ensureAllocatedSize (int requiredColumns, int requiredRows)
{
    const ScopedLockType lock (getLock());
    data.ensureSize (requiredColumns, requiredRows);
}

void setEntireRow (int rowIndex, ParameterType value)
{
    const ScopedLockType lock (getLock());
    if (isPositiveAndBelow(rowIndex, rowsUsed))
    {
        ElementType* cell = data.getRowStart(rowIndex);
        ElementType* end = cell + columnsUsed;
        while (cell != end)
        {
            *cell++ = value;
        }
    }
}

void setEntireColumn (int columnIndex, ParameterType value)
{
    const ScopedLockType lock (getLock());
    if (isPositiveAndBelow(columnIndex, columnsUsed))
    {
        ElementType* cell = data.getColumnStart(columnIndex);
        int columnStride = data.getNumColumns();
        ElementType* end = cell + (rowsUsed * columnStride);
        while (cell != end)
        {
            *cell = value;
            cell += columnStride;
        }
    }
}

void addRow ()
{
    const ScopedLockType lock (getLock());
    data.ensureSize (columnsUsed, rowsUsed + 1);
    constructEntireRow(rowsUsed++);
}

void addRowWithValue (ParameterType value)
{
    insertRowsWithValue(-1, 1, value);
}

void addColumnWithValue (ParameterType value)
{
    insertColumnsWithValue(-1, 1, value);
}

void addColumn ()
{
    const ScopedLockType lock (getLock());
    data.ensureSize (columnsUsed + 1, rowsUsed);
    constructEntireColumn(columnsUsed++);
}

void insertRows (int indexToInsertAt, int numToInsert)
{
    const ScopedLockType lock (getLock());
    ensureAllocatedRows(rowsUsed + numToInsert);

    if (isPositiveAndBelow (indexToInsertAt, rowsUsed))
    {
        int numRowsToMove = rowsUsed - indexToInsertAt;
        data.moveRows (indexToInsertAt, numRowsToMove, numToInsert);
        
        int end = indexToInsertAt + numToInsert;
        for (int i = indexToInsertAt; i < end; ++i)
        {
            constructEntireRow(i);
        }
        rowsUsed += numToInsert;
    }
    else
    {
        int end = rowsUsed + numToInsert;
        for (int i = rowsUsed; i < end; ++i)
        {
            constructEntireRow(i);
        }
        rowsUsed += numToInsert;
    }
}

void insertRowsWithValue (int indexToInsertAt, int numToInsert, ParameterType value)
{
    const ScopedLockType lock (getLock());
    ensureAllocatedRows(rowsUsed + numToInsert);
    
    if (isPositiveAndBelow (indexToInsertAt, rowsUsed))
    {
        int numRowsToMove = rowsUsed - indexToInsertAt;
        data.moveRows (indexToInsertAt, numRowsToMove, numToInsert);
        
        int end = indexToInsertAt + numToInsert;
        for (int i = indexToInsertAt; i < end; ++i)
        {
            constructEntireRowAs(i,value);
        }
        rowsUsed += numToInsert;
    }
    else
    {
        int end = rowsUsed + numToInsert;
        for (int i = rowsUsed; i < end; ++i)
        {
            constructEntireRowAs(i,value);
        }
        rowsUsed += numToInsert;
    }
}

void insertColumns (int indexToInsertAt, int numToInsert)
{
    const ScopedLockType lock (getLock());
    ensureAllocatedColumns(columnsUsed + numToInsert);
    
    if (isPositiveAndBelow (indexToInsertAt, columnsUsed))
    {
        int numColumnsToMove = columnsUsed - indexToInsertAt;
        data.moveColumns (indexToInsertAt, numColumnsToMove, numToInsert);
        
        int end = indexToInsertAt + numToInsert;
        for (int i = indexToInsertAt; i < end; ++i)
        {
            constructEntireColumn(i);
        }
        columnsUsed += numToInsert;
    }
    else
    {
        int end = columnsUsed + numToInsert;
        for (int i = columnsUsed; i < end; ++i)
        {
            constructEntireColumn(i);
        }
        columnsUsed += numToInsert;
    }
}

void insertColumnsWithValue (int indexToInsertAt, int numToInsert, ParameterType value)
{
    const ScopedLockType lock (getLock());
    ensureAllocatedColumns(columnsUsed + numToInsert);
    
    if (isPositiveAndBelow (indexToInsertAt, columnsUsed))
    {
        int numColumnsToMove = columnsUsed - indexToInsertAt;
        data.moveColumns (indexToInsertAt, numColumnsToMove, numToInsert);
        
        int end = indexToInsertAt + numToInsert;
        for (int i = indexToInsertAt; i < end; ++i)
        {
            constructEntireColumnAs(i, value);
        }
        columnsUsed += numToInsert;
    }
    else
    {
        int end = columnsUsed + numToInsert;
        for (int i = columnsUsed; i < end; ++i)
        {
            constructEntireColumnAs(i, value);
        }
        columnsUsed += numToInsert;
    }
}

void removeRow (int index)
{
    removeRows (index,1);
}

void removeColumn (int index)
{
    removeColumns (index,1);
}

void removeRows (int startIndex, int numberToRemove)
{
    const ScopedLockType lock (getLock());
    const int endIndex = jlimit (0, rowsUsed, startIndex + numberToRemove);
    startIndex = jlimit (0, rowsUsed, startIndex);
    
    if (endIndex > startIndex)
    {
        numberToRemove = endIndex - startIndex;
        for (int i = startIndex; i < endIndex; ++i)
        {
            destructEntireRow(i);
        }
        
        const int numToMove = rowsUsed - endIndex;
        if (numToMove > 0)
        {
            data.moveRows (startIndex + numberToRemove, numToMove, -numberToRemove);
        }
        rowsUsed -= numberToRemove;
    }
}

void removeColumns (int startIndex, int numberToRemove)
{
    const ScopedLockType lock (getLock());
    const int endIndex = jlimit (0, columnsUsed, startIndex + numberToRemove);
    startIndex = jlimit (0, columnsUsed, startIndex);
    
    if (endIndex > startIndex)
    {
        numberToRemove = endIndex - startIndex;
        for (int i = startIndex; i < endIndex; ++i)
        {
            destructEntireColumn(i);
        }
        
        const int numToMove = columnsUsed - endIndex;
        if (numToMove > 0)
        {
            data.moveColumns (startIndex + numberToRemove, numToMove, -numberToRemove);
        }
        columnsUsed -= numberToRemove;
    }
}

void compact ()
{
    data.setSize (columnsUsed,rowsUsed);
}

inline const TypeOfCriticalSectionToUse& getLock() const noexcept      { return data; }

/** Returns the type of scoped lock to use for locking this table */
typedef typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType;

private:

// NOTE: assuming that lock is already taken for these private construct/destruct calls

void constructEntireRow (int rowIndex)
{
    jassert(isPositiveAndBelow(rowIndex, data.getNumRows()));
    ElementType* cell = data.getRowStart(rowIndex);
    ElementType* end = cell + columnsUsed;
    while (cell != end)
    {
        new (cell++) ElementType ();
    }
}

void constructEntireRowAs (int rowIndex, ParameterType value)
{
    jassert(isPositiveAndBelow(rowIndex, data.getNumRows()));
    ElementType* cell = data.getRowStart(rowIndex);
    ElementType* end = cell + columnsUsed;
    while (cell != end)
    {
        new (cell++) ElementType (value);
    }
}

void constructEntireColumn (int columnIndex)
{
    jassert(isPositiveAndBelow (columnIndex, data.getNumColumns()));
    ElementType* cell = data.getColumnStart(columnIndex);
    int columnStride = data.getNumColumns();
    ElementType* end = cell + (rowsUsed * columnStride);
    while (cell != end)
    {
        new (cell) ElementType ();
        cell += columnStride;
    }
}

void constructEntireColumnAs (int columnIndex, ParameterType value)
{
    jassert(isPositiveAndBelow (columnIndex, data.getNumColumns()));
    ElementType* cell = data.getColumnStart(columnIndex);
    int columnStride = data.getNumColumns();
    ElementType* end = cell + (rowsUsed * columnStride);
    while (cell != end)
    {
        new (cell) ElementType (value);
        cell += columnStride;
    }
}

void destructEntireRow (int rowIndex)
{
    jassert(isPositiveAndBelow(rowIndex, data.getNumRows()));
    ElementType* cell = data.getRowStart(rowIndex);
    ElementType* end = cell + columnsUsed;
    while (cell != end)
    {
        (cell++)->~ElementType();
    }
}

void destructEntireColumn (int columnIndex)
{
    jassert(isPositiveAndBelow (columnIndex, data.getNumColumns()));
    ElementType* cell = data.getColumnStart(columnIndex);
    int columnStride = data.getNumColumns();
    ElementType* end = cell + (rowsUsed * columnStride);
    while (cell != end)
    {
        cell->~ElementType ();
        cell += columnStride;
    }
}

TableAllocationBase< ElementType, TypeOfCriticalSectionToUse > data;
int rowsUsed;
int columnsUsed;

};
[/code]