The central area of a QMainWindow can be occupied by any kind of widget. Here’s an overview of the possibilities:

Layouts, splitters, and MDI areas can be combined with standard Qt widgets or with custom widgets. Chapter 6 covers these classes in depth.

For the Spreadsheet application, a QTableWidget subclass is used as the central widget. The QTableWidget class already provides most of the spreadsheet capability we need, but it doesn’t support clipboard operations and doesn’t understand spreadsheet formulas such as “=A1+A2+A3”. We will implement this missing functionality in the Spreadsheet class.

The Spreadsheet class is derived from QTableWidget, as Figure 4.1 shows. A QTableWidget is effectively a grid that represents a two-dimensional sparse array. It displays whichever cells the user scrolls to, within its specified dimensions. When the user enters some text into an empty cell, QTableWidget automatically creates a QTableWidgetItem to store the text.

Figure 4.1. Inheritance trees for Spreadsheet and Cell

QTableWidget is derived from QTableView, one of the model/view classes that we will look at more closely in Chapter 10. Another table, which has a lot more functionality out of the box, is QicsTable, available from http://www.ics.com/.

Let’s start implementing Spreadsheet, beginning with the header file:

#ifndef SPREADSHEET_H
#define SPREADSHEET_H

#include <QTableWidget>

class Cell;
class SpreadsheetCompare;

The header starts with forward declarations for the Cell and SpreadsheetCompare classes.

The attributes of a QTableWidget cell, such as its text and its alignment, are stored in a QTableWidgetItem. Unlike QTableWidget, QTableWidgetItem isn’t a widget class; it is a pure data class. The Cell class is derived from QTableWidgetItem and will be explained in this chapter’s last section.

class Spreadsheet : public QTableWidget
{
    Q_OBJECT

public:
    Spreadsheet(QWidget *parent = 0);

    bool autoRecalculate() const { return autoRecalc; }
    QString currentLocation() const;
    QString currentFormula() const;
    QTableWidgetSelectionRange selectedRange() const;
    void clear();
    bool readFile(const QString &fileName);
    bool writeFile(const QString &fileName);
    void sort(const SpreadsheetCompare &compare);

The autoRecalculate() function is implemented inline since it just returns whether or not auto-recalculation is in force.

In Chapter 3, we relied on some public functions in Spreadsheet when we implemented MainWindow. For example, we called clear() from MainWindow::newFile() to reset the spreadsheet. We also used some functions inherited from QTableWidget, notably setCurrentCell() and setShowGrid().

public slots:
    void cut();
    void copy();
    void paste();
    void del();
    void selectCurrentRow();
    void selectCurrentColumn();
    void recalculate();
    void setAutoRecalculate(bool recalc);
    void findNext(const QString &str, Qt::CaseSensitivity cs);
    void findPrevious(const QString &str, Qt::CaseSensitivity cs);

signals:
    void modified();

Spreadsheet provides many slots that implement actions from the Edit, Tools, and Options menus, and it provides one signal, modified(), to announce any change that has occurred.

private slots:
    void somethingChanged();

We define one private slot used internally by the Spreadsheet class.

private:
    enum { MagicNumber = 0x7F51C883, RowCount = 999, ColumnCount = 26 };

    Cell *cell(int row, int column) const;
    QString text(int row, int column) const;
    QString formula(int row, int column) const;
    void setFormula(int row, int column, const QString &formula);

    bool autoRecalc;
};

In the class’s private section, we declare three constants, four functions, and one variable.

class SpreadsheetCompare
{
public:
    bool operator()(const QStringList &row1,
                    const QStringList &row2) const;

    enum { KeyCount = 3 };
    int keys[KeyCount];
    bool ascending[KeyCount];
};

#endif

The header file ends with the SpreadsheetCompare class definition. We will explain this when we review Spreadsheet::sort().

We will now look at the implementation:

#include <QtGui>

#include "cell.h"
#include "spreadsheet.h"

Spreadsheet::Spreadsheet(QWidget *parent)
    : QTableWidget(parent)
{
    autoRecalc = true;

    setItemPrototype(new Cell);
    setSelectionMode(ContiguousSelection);

    connect(this, SIGNAL(itemChanged(QTableWidgetItem *)),
            this, SLOT(somethingChanged()));

    clear();
}

Normally, when the user enters some text on an empty cell, the QTableWidget will automatically create a QTableWidgetItem to hold the text. In our spreadsheet, we want Cell items to be created instead. This is achieved by the setItemPrototype() call in the constructor. Internally, QTableWidget clones the item passed as a prototype every time a new item is required.

Also in the constructor, we set the selection mode to QAbstractItemView::ContiguousSelection to allow a single rectangular selection. We connect the table widget’s itemChanged() signal to the private somethingChanged() slot; this ensures that when the user edits a cell, the somethingChanged() slot is called. Finally, we call clear() to resize the table and to set the column headings.

void Spreadsheet::clear()
{
    setRowCount(0);
    setColumnCount(0);
    setRowCount(RowCount);
    setColumnCount(ColumnCount);

    for (int i = 0; i < ColumnCount; ++i) {
        QTableWidgetItem *item = new QTableWidgetItem;
        item->setText(QString(QChar('A' + i)));
        setHorizontalHeaderItem(i, item);
    }

    setCurrentCell(0, 0);
}

The clear() function is called from the Spreadsheet constructor to initialize the spreadsheet. It is also called from MainWindow::newFile().

We could have used QTableWidget::clear() to clear all the items and any selections, but that would have left the headers at their current size. Instead, we resize the table down to 0 × 0. This clears the entire spreadsheet, including the headers. We then resize the table to ColumnCount × RowCount (26 × 999) and populate the horizontal header with QTableWidgetItems containing the column names “A”, “B”, ..., “Z”. We don’t need to set the vertical header labels, because these default to “1”, “2”, ..., “999”. At the end, we move the cell cursor to cell A1.

A QTableWidget is composed of several child widgets. It has a horizontal QHeaderView at the top, a vertical QHeaderView on the left, and two QScrollBars. The area in the middle is occupied by a special widget called the viewport, on which QTableWidget draws the cells. The different child widgets are accessible through functions inherited from QTableView and QAbstractScrollArea (see Figure 4.2). QAbstractScrollArea provides a scrollable viewport and two scroll bars, which can be turned on and off. We cover the QScrollArea subclass in Chapter 6.

Figure 4.2. QTableWidget’s constituent widgets

Cell *Spreadsheet::cell(int row, int column) const
{
    return static_cast<Cell *>(item(row, column));
}

The cell() private function returns the Cell object for a given row and column. It is almost the same as QTableWidget::item(), except that it returns a Cell pointer instead of a QTableWidgetItem pointer.

QString Spreadsheet::text(int row, int column) const
{
    Cell *c = cell(row, column);
    if (c) {
        return c->text();
    } else {
        return "";
    }
}

The text() private function returns the text for a given cell. If cell() returns a null pointer, the cell is empty, so we return an empty string.

QString Spreadsheet::formula(int row, int column) const
{
    Cell *c = cell(row, column);
    if (c) {
        return c->formula();
    } else {
        return "";
    }
}

The formula() function returns the cell’s formula. In many cases, the formula and the text are the same; for example, the formula “Hello” evaluates to the string “Hello”, so if the user types “Hello” into a cell and presses Enter, that cell will show the text “Hello”. But there are a few exceptions:

The task of converting a formula into a value is performed by the Cell class. For the moment, the thing to bear in mind is that the text shown in the cell is the result of evaluating the formula, not the formula itself.

void Spreadsheet::setFormula(int row, int column,
                             const QString &formula)
{
    Cell *c = cell(row, column);
    if (!c) {
        c = new Cell;
        setItem(row, column, c);
    }
    c->setFormula(formula);
}

The setFormula() private function sets the formula for a given cell. If the cell already has a Cell object, we reuse it. Otherwise, we create a new Cell object and call QTableWidget::setItem() to insert it into the table. At the end, we call the cell’s own setFormula() function, which will cause the cell to be repainted if it’s shown on-screen. We don’t need to worry about deleting the Cell object later on; QTableWidget takes ownership of the cell and will delete it automatically at the right time.

QString Spreadsheet::currentLocation() const
{
    return QChar('A' + currentColumn())
           + QString::number(currentRow() + 1);
}

The currentLocation() function returns the current cell’s location in the usual spreadsheet format of column letter followed by row number. MainWindow::updateStatusBar() uses it to show the location in the status bar.

QString Spreadsheet::currentFormula() const
{
    return formula(currentRow(), currentColumn());
}

The currentFormula() function returns the current cell’s formula. It is called from MainWindow::updateStatusBar().

void Spreadsheet::somethingChanged()
{
    if (autoRecalc)
        recalculate();
    emit modified();
}

The somethingChanged() private slot recalculates the whole spreadsheet if “auto-recalculate” is enabled. It also emits the modified() signal.

We will now implement the loading and saving of Spreadsheet files using a custom binary format. We will do this using QFile and QDataStream, which together provide platform-independent binary I/O.

We will start with writing a Spreadsheet file:

bool Spreadsheet::writeFile(const QString &fileName)
{
    QFile file(fileName);
    if (!file.open(QIODevice::WriteOnly)) {
        QMessageBox::warning(this, tr("Spreadsheet"),
                             tr("Cannot write file %1:
%2.")
                             .arg(file.fileName())
                             .arg(file.errorString()));
        return false;
    }
    QDataStream out(&file);
    out.setVersion(QDataStream::Qt_4_3);

    out << quint32(MagicNumber);

    QApplication::setOverrideCursor(Qt::WaitCursor);
    for (int row = 0; row < RowCount; ++row) {

        for (int column = 0; column < ColumnCount; ++column) {
            QString str = formula(row, column);
            if (!str.isEmpty())
                out << quint16(row) << quint16(column) << str;
        }
    }
    QApplication::restoreOverrideCursor();
    return true;
}

The writeFile() function is called from MainWindow::saveFile() to write the file to disk. It returns true on success, false on error.

We create a QFile object with the given file name and call open() to open the file for writing. We also create a QDataStream object that operates on the QFile and use it to write out the data.

Just before we write the data, we change the application’s cursor to the standard wait cursor (usually an hourglass) and restore the normal cursor once all the data is written. At the end of the function, the file is automatically closed by QFile’s destructor.

QDataStream supports basic C++ types as well as many of Qt’s types. The syntax is modeled after the Standard C++ <iostream> classes. For example,

out << x << y << z;

writes the variables x, y, and z to a stream, and

in >> x >> y >> z;

reads them from a stream. Because the C++ primitive integer types may have different sizes on different platforms, it is safest to cast these values to one of qint8, quint8, qint16, quint16, qint32, quint32, qint64, and quint64, which are guaranteed to be of the size they advertise (in bits).

The Spreadsheet application’s file format is fairly simple. A Spreadsheet file starts with a 32-bit number that identifies the file format (MagicNumber, defined as 0x7F51C883 in spreadsheet.h, an arbitrary random number). Then comes a series of blocks, each containing a single cell’s row, column, and formula. To save space, we don’t write out empty cells. The format is shown in Figure 4.3.

Figure 4.3. The Spreadsheet file format

The precise binary representation of the data types is determined by QDataStream. For example, a quint16 is stored as two bytes in big-endian order, and a QString as the string’s length followed by the Unicode characters.

The binary representation of Qt types has evolved quite a lot since Qt 1.0. It is likely to continue evolving in future Qt releases to keep pace with the evolution of existing types and to allow for new Qt types. By default, QDataStream uses the most recent version of the binary format (version 9 in Qt 4.3), but it can be set to read older versions. To avoid any compatibility problems if the application is recompiled later using a newer Qt release, we explicitly tell QDataStream to use version 9 irrespective of the version of Qt we are compiling against. (QDataStream::Qt_4_3 is a convenience constant that equals 9.)

QDataStream is very versatile. It can be used on a QFile, and also on a QBuffer, a QProcess, a QTcpSocket, a QUdpSocket, or a QSslSocket. Qt also offers a QTextStream class that can be used instead of QDataStream for reading and writing text files. Chapter 12 explains these classes in depth, and also describes various approaches to handling different QDataStream versions.

bool Spreadsheet::readFile(const QString &fileName)
{
    QFile file(fileName);
    if (!file.open(QIODevice::ReadOnly)) {
        QMessageBox::warning(this, tr("Spreadsheet"),
                             tr("Cannot read file %1:
%2.")
                             .arg(file.fileName())
                             .arg(file.errorString()));
        return false;
    }

    QDataStream in(&file);
    in.setVersion(QDataStream::Qt_4_3);

    quint32 magic;
    in >> magic;
    if (magic != MagicNumber) {
        QMessageBox::warning(this, tr("Spreadsheet"),
                             tr("The file is not a Spreadsheet file."));
        return false;
    }

    clear();

    quint16 row;
    quint16 column;
    QString str;

    QApplication::setOverrideCursor(Qt::WaitCursor);
    while (!in.atEnd()) {
        in >> row >> column >> str;
        setFormula(row, column, str);
    }
    QApplication::restoreOverrideCursor();
    return true;
}

The readFile() function is very similar to writeFile(). We use QFile to read in the file, but this time using the QIODevice::ReadOnly flag rather than QIODevice::WriteOnly. Then we set the QDataStream version to 9. The format for reading must always be the same as for writing.

If the file has the correct magic number at the beginning, we call clear() to blank out all the cells in the spreadsheet, and we read in the cell data. Since the file only contains the data for non-empty cells, and it is very unlikely that every cell in the spreadsheet will be set, we must ensure that all cells are cleared before reading.

We are now ready to implement the slots that correspond to the application’s Edit menu. The menu is shown in Figure 4.4.

Figure 4.4. The Spreadsheet application’s Edit menu

void Spreadsheet::cut()
{
    copy();
    del();
}

The cut() slot corresponds to Edit|Cut. The implementation is simple since Cut is the same as Copy followed by Delete.

void Spreadsheet::copy()
{
    QTableWidgetSelectionRange range = selectedRange();
    QString str;

    for (int i = 0; i < range.rowCount(); ++i) {
        if (i > 0)
            str += "
";
        for (int j = 0; j < range.columnCount(); ++j) {
            if (j > 0)
                str += "	";
            str += formula(range.topRow() + i, range.leftColumn() + j);
        }
    }
    QApplication::clipboard()->setText(str);
}

The copy() slot corresponds to Edit|Copy. It iterates over the current selection (which is simply the current cell if there is no explicit selection). Each selected cell’s formula is added to a QString, with rows separated by newline characters and columns separated by tab characters. This is illustrated in Figure 4.5.

Figure 4.5. Copying a selection onto the clipboard

The system clipboard is available in Qt through the QApplication::clipboard() static function. By calling QClipboard::setText(), we make the text available on the clipboard, both to this application and to other applications that support plain text. Our format with tab and newline characters as separators is understood by a variety of applications, including Microsoft Excel.

The QTableWidget::selectedRanges() function returns a list of selection ranges. We know there cannot be more than one because we set the selection mode to QAbstractItemView::ContiguousSelection in the constructor. For our convenience, we define a selectedRange() function that returns the selection range:

QTableWidgetSelectionRange Spreadsheet::selectedRange() const
{
    QList<QTableWidgetSelectionRange> ranges = selectedRanges();
    if (ranges.isEmpty())
        return QTableWidgetSelectionRange();
    return ranges.first();
}

If there is a selection at all, we simply return the first (and only) one. There should always be a selection since the ContiguousSelection mode treats the current cell as being selected. But to protect against the possibility of a bug in our program that makes no cell current, we handle this case.

void Spreadsheet::paste()
{
    QTableWidgetSelectionRange range = selectedRange();
    QString str = QApplication::clipboard()->text();
    QStringList rows = str.split('
'),
    int numRows = rows.count();
    int numColumns = rows.first().count('	') + 1;

    if (range.rowCount() * range.columnCount() != 1
            && (range.rowCount() != numRows
                || range.columnCount() != numColumns)) {

        QMessageBox::information(this, tr("Spreadsheet"),
                tr("The information cannot be pasted because the copy "
                   "and paste areas aren't the same size."));
        return;
    }

    for (int i = 0; i < numRows; ++i) {
        QStringList columns = rows[i].split('	'),
        for (int j = 0; j < numColumns; ++j) {
            int row = range.topRow() + i;
            int column = range.leftColumn() + j;
            if (row < RowCount && column < ColumnCount)
                setFormula(row, column, columns[j]);
        }
    }
    somethingChanged();
}

The paste() slot corresponds to Edit|Paste. We fetch the text on the clipboard and call the static function QString::split() to break the string into a QStringList. Each row becomes one string in the list.

Next, we determine the dimensions of the copy area. The number of rows is the number of strings in the QStringList; the number of columns is the number of tab characters in the first row, plus 1. If only one cell is selected, we use that cell as the top-left corner of the paste area; otherwise, we use the current selection as the paste area.

To perform the paste, we iterate over the rows and split each of them into cells by using QString::split() again, but this time using tab as the separator. Figure 4.6 illustrates the steps.

Figure 4.6. Pasting clipboard text into the spreadsheet

void Spreadsheet::del()
{
    QList<QTableWidgetItem *> items = selectedItems();
    if (!items.isEmpty()) {
        foreach (QTableWidgetItem *item, items)
            delete item;
        somethingChanged();
    }
}

The del() slot corresponds to Edit|Delete. If there are selected items, the function deletes them and calls somethingChanged(). It is sufficient to use delete on each Cell object in the selection to clear the cells. The QTableWidget notices when its QTableWidgetItems are deleted and automatically repaints itself if any of the items were visible. If we call cell() with the location of a deleted cell, it will return a null pointer.

void Spreadsheet::selectCurrentRow()
{
    selectRow(currentRow());
}

void Spreadsheet::selectCurrentColumn()
{
    selectColumn(currentColumn());
}

The selectCurrentRow() and selectCurrentColumn() functions correspond to the Edit|Select|Row and Edit|Select|Column menu options. The implementations rely on QTableWidget’s selectRow() and selectColumn() functions. We do not need to implement the functionality behind Edit|Select|All, since that is provided by QTableWidget’s inherited function QAbstractItemView::selectAll().

void Spreadsheet::findNext(const QString &str, Qt::CaseSensitivity cs)
{
    int row = currentRow();
    int column = currentColumn() + 1;

    while (row < RowCount) {
        while (column < ColumnCount) {
            if (text(row, column).contains(str, cs)) {
                clearSelection();
                setCurrentCell(row, column);
                activateWindow();
                return;
            }
            ++column;
        }
        column = 0;
        ++row;
    }
    QApplication::beep();
}

The findNext() slot iterates through the cells starting from the cell to the right of the cursor and moving right until the last column is reached, then continues from the first column in the row below, and so on until the text is found or until the very last cell is reached. For example, if the current cell is cell C24, we search D24, E24, ..., Z24, then A25, B25, C25, ..., Z25, and so on until Z999.

If we find a match, we clear the current selection, move the cell cursor to the cell that matched, and make the window that contains the Spreadsheet active. If no match is found, we make the application beep to indicate that the search finished unsuccessfully.

void Spreadsheet::findPrevious(const QString &str,
                               Qt::CaseSensitivity cs)
{
    int row = currentRow();
    int column = currentColumn() - 1;

    while (row >= 0) {
        while (column >= 0) {
            if (text(row, column).contains(str, cs)) {
                clearSelection();
                setCurrentCell(row, column);
                activateWindow();
                return;
            }
            --column;
        }
        column = ColumnCount - 1;
        --row;
    }
    QApplication::beep();
}

The findPrevious() slot is similar to findNext(), except that it iterates backward and stops at cell A1.

We will now implement the slots for the Tools and Options menus. These menus are shown in Figure 4.7.

Figure 4.7. The Spreadsheet application’s Tools and Options menus

void Spreadsheet::recalculate()
{
    for (int row = 0; row < RowCount; ++row) {
        for (int column = 0; column < ColumnCount; ++column) {
            if (cell(row, column))
                cell(row, column)->setDirty();
        }
    }
    viewport()->update();
}

The recalculate() slot corresponds to Tools|Recalculate. It is also called automatically by Spreadsheet when necessary.

We iterate over all the cells and call setDirty() on every cell to mark each one as requiring recalculation. The next time QTableWidget calls text() on a Cell to obtain the value to show in the spreadsheet, the value will be recalculated.

Then we call update() on the viewport to repaint the whole spreadsheet. The repaint code in QTableWidget then calls text() on each visible cell to obtain the value to display. Because we called setDirty() on every cell, the calls to text() will use a freshly calculated value. The calculation may require non-visible cells to be recalculated, cascading the calculation until every cell that needs to be recalculated to display the correct text in the viewport has been freshly calculated. The calculation is performed by the Cell class.

void Spreadsheet::setAutoRecalculate(bool recalc)
{
    autoRecalc = recalc;
    if (autoRecalc)
        recalculate();
}

The setAutoRecalculate() slot corresponds to Options|Auto-Recalculate. If the feature is being turned on, we recalculate the whole spreadsheet immediately to make sure that it’s up-to-date; afterward, recalculate() is called automatically from somethingChanged().

We don’t need to implement anything for Options|Show Grid because QTableWidget already has a setShowGrid() slot, which it inherits from QTableView. All that remains is Spreadsheet::sort(), which is called from MainWindow::sort():

void Spreadsheet::sort(const SpreadsheetCompare &compare)
{
    QList<QStringList> rows;
    QTableWidgetSelectionRange range = selectedRange();
    int i;

    for (i = 0; i < range.rowCount(); ++i) {
        QStringList row;
        for (int j = 0; j < range.columnCount(); ++j)
            row.append(formula(range.topRow() + i,
                               range.leftColumn() + j));
        rows.append(row);
    }

    qStableSort(rows.begin(), rows.end(), compare);

    for (i = 0; i < range.rowCount(); ++i) {
        for (int j = 0; j < range.columnCount(); ++j)
            setFormula(range.topRow() + i, range.leftColumn() + j,
                       rows[i][j]);
    }

    clearSelection();
    somethingChanged();
}

Sorting operates on the current selection and reorders the rows according to the sort keys and sort orders stored in the compare object. We represent each row of data with a QStringList and store the selection as a list of rows. We use Qt’s qStableSort() algorithm, and for simplicity sort by formula rather than by value. The process is illustrated by Figures 4.8 and 4.9. We cover Qt’s standard algorithms and data structures in Chapter 11.

Figure 4.8. Storing the selection as a list of rows

Figure 4.9. Putting the data back into the table after sorting

The qStableSort() function accepts a begin iterator, an end iterator, and a comparison function. The comparison function is a function that takes two arguments (two QStringLists) and that returns true if the first argument is “less than” the second argument, false otherwise. The compare object we pass as the comparison function isn’t really a function, but it can be used as one, as we will see shortly.

After performing the qStableSort(), we move the data back into the table, clear the selection, and call somethingChanged().

In spreadsheet.h, the SpreadsheetCompare class was defined like this:

class SpreadsheetCompare
{
public:
    bool operator()(const QStringList &row1,
                    const QStringList &row2) const;

    enum { KeyCount = 3 };
    int keys[KeyCount];
    bool ascending[KeyCount];
};

The SpreadsheetCompare class is special because it implements a () operator. This allows us to use the class as though it were a function. Such classes are called function objects, or functors. To understand how functors work, we will start with a simple example:

class Square
{
public:
    int operator()(int x) const { return x * x; }
}

The Square class provides one function, operator()(int), that returns the square of its parameter. By naming the function operator()(int) rather than, say, compute(int), we gain the capability of using an object of type Square as though it were a function:

Square square;
int y = square(5);
// y equals 25

Now let’s see an example involving SpreadsheetCompare:

QStringList row1, row2;
SpreadsheetCompare compare;
...
if (compare(row1, row2)) {
    // row1 is less than row2
}

The compare object can be used just as though it had been a plain compare() function. Additionally, its implementation can access all the sort keys and sort orders, which are stored as member variables.

An alternative to this scheme would have been to store the sort keys and sort orders in global variables and use a plain compare() function. However, communicating through global variables is inelegant and can lead to subtle bugs. Functors are a more powerful idiom for interfacing with template functions such as qStableSort().

Here is the implementation of the function that is used to compare two spreadsheet rows:

bool SpreadsheetCompare::operator()(const QStringList &row1,
                                    const QStringList &row2) const
{
    for (int i = 0; i < KeyCount; ++i) {
        int column = keys[i];
        if (column != -1) {
            if (row1[column] != row2[column]) {
                if (ascending[i]) {
                    return row1[column] < row2[column];
                } else {
                    return row1[column] > row2[column];
                }
                }
        }
    }
    return false;
}

The operator returns true if the first row is less than the second row; otherwise, it returns false. The qStableSort() function uses the result of this function to perform the sort.

The SpreadsheetCompare object’s keys and ascending arrays are populated in the MainWindow::sort() function (shown in Chapter 2). Each key holds a column index, or −1 (“None”).

We compare the corresponding cell entries in the two rows for each key in order. As soon as we find a difference, we return an appropriate true or false value. If all the comparisons turn out to be equal, we return false. The qStableSort() function uses the order before the sort to resolve tie situations; if row1 preceded row2 originally and neither compares as “less than” the other, row1 will still precede row2 in the result. This is what distinguishes qStableSort() from its unstable cousin qSort().

We have now completed the Spreadsheet class. In the next section, we will review the Cell class. This class is used to hold cell formulas and provides a reimplementation of the QTableWidgetItem::data() function that Spreadsheet calls indirectly, through the QTableWidgetItem::text() function, to display the result of calculating a cell’s formula.

The Cell class is derived from QTableWidgetItem. The class is designed to work well with Spreadsheet, but it has no specific dependencies on that class and could in theory be used in any QTableWidget. Here’s the header file:

#ifndef CELL_H
#define CELL_H

#include <QTableWidgetItem>

class Cell : public QTableWidgetItem
{
public:
    Cell();

    QTableWidgetItem *clone() const;
    void setData(int role, const QVariant &value);
    QVariant data(int role) const;
    void setFormula(const QString &formula);
    QString formula() const;
    void setDirty();

private:
    QVariant value() const;
    QVariant evalExpression(const QString &str, int &pos) const;
    QVariant evalTerm(const QString &str, int &pos) const;
    QVariant evalFactor(const QString &str, int &pos) const;

    mutable QVariant cachedValue;
    mutable bool cacheIsDirty;
};

#endif

The Cell class extends QTableWidgetItem by adding two private variables:

We use QVariant because some cells have a double value, while others have a QString value.

The cachedValue and cacheIsDirty variables are declared with the C++ mutable keyword. This allows us to modify these variables in const functions. Alternatively, we could recalculate the value each time text() is called, but that would be needlessly inefficient.

Notice that there is no Q_OBJECT macro in the class definition. Cell is a plain C++ class, with no signals or slots. In fact, because QTableWidgetItem isn’t derived from QObject, we cannot have signals and slots in Cell as it stands. Qt’s item classes are not derived from QObject to keep their overhead to the barest minimum. If signals and slots are needed, they can be implemented in the widget that contains the items or, exceptionally, using multiple inheritance with QObject.

Here’s the start of cell.cpp:

#include <QtGui>

#include "cell.h"

Cell::Cell()
{
    setDirty();
}

In the constructor, we only need to set the cache as dirty. There is no need to pass a parent; when the cell is inserted into a QTableWidget with setItem(), the QTableWidget will automatically take ownership of it.

Every QTableWidgetItem can hold some data, up to one QVariant for each data “role”. The most commonly used roles are Qt::EditRole and Qt::DisplayRole. The edit role is used for data that is to be edited, and the display role is for data that is to be displayed. Often the data for both is the same, but in Cell the edit role corresponds to the cell’s formula and the display role corresponds to the cell’s value (the result of evaluating the formula).

QTableWidgetItem *Cell::clone() const
{
    return new Cell(*this);
}

The clone() function is called by QTableWidget when it needs to create a new cell—for example, when the user starts typing into an empty cell that has not been used before. The instance passed to QTableWidget::setItemPrototype() is the item that is cloned. Since member-wise copying is sufficient for Cell, we are relying on the default copy constructor automatically created by C++ to create new Cell instances in the clone() function.

void Cell::setFormula(const QString &formula)
{
    setData(Qt::EditRole, formula);
}

The setFormula() function sets the cell’s formula. It is simply a convenience function for calling setData() with the edit role. It is called from Spreadsheet::setFormula().

QString Cell::formula() const
{
    return data(Qt::EditRole).toString();
}

The formula() function is called from Spreadsheet::formula(). Like setFormula(), it is a convenience function, this time retrieving the item’s EditRole data.

void Cell::setData(int role, const QVariant &value)
{
    QTableWidgetItem::setData(role, value);
    if (role == Qt::EditRole)
        setDirty();
}

If we have a new formula, we set cacheIsDirty to true to ensure that the cell is recalculated the next time text() is called.

There is no text() function defined in Cell, although we call text() on Cell instances in Spreadsheet::text(). The text() function is a convenience function provided by QTableWidgetItem; it is the equivalent of calling data(Qt::DisplayRole).toString().

void Cell::setDirty()
{
    cacheIsDirty = true;
}

The setDirty() function is called to force a recalculation of the cell’s value. It simply sets cacheIsDirty to true, meaning that cachedValue is no longer up-to-date. The recalculation isn’t performed until it is necessary.

QVariant Cell::data(int role) const
{
    if (role == Qt::DisplayRole) {
        if (value().isValid()) {
            return value().toString();
        } else {
            return "####";
        }
    } else if (role == Qt::TextAlignmentRole) {
        if (value().type() == QVariant::String) {
            return int(Qt::AlignLeft | Qt::AlignVCenter);
        } else {
            return int(Qt::AlignRight | Qt::AlignVCenter);
        }
    } else {
        return QTableWidgetItem::data(role);
    }
}

The data() function is reimplemented from QTableWidgetItem. It returns the text that should be shown in the spreadsheet if called with Qt::DisplayRole, and the formula if called with Qt::EditRole. It returns a suitable alignment if called with Qt::TextAlignmentRole. In the DisplayRole case, it relies on value() to compute the cell’s value. If the value is invalid (because the formula is wrong), we return “####”.

The Cell::value() function used in data() returns a QVariant. A QVariant can store values of different types, such as double and QString, and provides functions to convert the variant to other types. For example, calling toString() on a variant that holds a double value produces a string representation of the double. A QVariant constructed using the default constructor is an “invalid” variant.

const QVariant Invalid;
QVariant Cell::value() const
{
    if (cacheIsDirty) {
        cacheIsDirty = false;

        QString formulaStr = formula();
        if (formulaStr.startsWith(''')) {
            cachedValue = formulaStr.mid(1);
        } else if (formulaStr.startsWith('=')) {
            cachedValue = Invalid;
            QString expr = formulaStr.mid(1);
            expr.replace(" ", "");
            expr.append(QChar::Null);

            int pos = 0;
            cachedValue = evalExpression(expr, pos);
            if (expr[pos] != QChar::Null)
                cachedValue = Invalid;
        } else {
            bool ok;
            double d = formulaStr.toDouble(&ok);
            if (ok) {
                cachedValue = d;
            } else {
                cachedValue = formulaStr;
            }
        }
    }
    return cachedValue;
}

The value() private function returns the cell’s value. If cacheIsDirty is true, we need to recalculate the value.

If the formula starts with a single quote (e.g., “’12345”), the single quote occupies position 0 and the value is the string from position 1 to the end.

If the formula starts with an equals sign (‘=’), we take the string from position 1 and remove any spaces it may contain. Then we call evalExpression() to compute the value of the expression. The pos argument is passed by reference; it indicates the position of the character where parsing should begin. After the call to evalExpression(), the character at position pos should be the QChar::Null character we appended, if it was successfully parsed. If the parse failed before the end, we set cachedValue to be Invalid.

If the formula doesn’t begin with a single quote or an equals sign, we attempt to convert it to a floating-point value using toDouble(). If the conversion works, we set cachedValue to be the resulting number; otherwise, we set cachedValue to be the formula string. For example, a formula of “1.50” causes toDouble() to set ok to true and return 1.5, while a formula of “World Population” causes toDouble() to set ok to false and return 0.0.

By giving toDouble() a pointer to a bool, we are able to distinguish between the conversion of a string that represents the numeric value 0.0 and a conversion error (where 0.0 is also returned but the bool is set to false). Sometimes the returning of a zero value on conversion failure is exactly what we need, in which case we do not bother passing a pointer to a bool. For performance and portability reasons, Qt never uses C++ exceptions to report failure. This doesn’t prevent you from using them in Qt programs if your compiler supports them.

The value() function is declared const. We had to declare cachedValue and cacheIsValid as mutable variables so that the compiler will allow us to modify them in const functions. It might be tempting to make value() non-const and remove the mutable keywords, but that would not compile because we call value() from data(), a const function.

We have now completed the Spreadsheet application, apart from parsing formulas. The rest of this section covers evalExpression() and the two helper functions evalTerm() and evalFactor(). The code is a bit complicated, but it is included here to make the application complete. Since the code is not related to GUI programming, you can safely skip it and continue reading from Chapter 5.

The evalExpression() function returns the value of a spreadsheet expression. An expression is defined as one or more terms separated by ‘+’ or ‘−’ operators. The terms themselves are defined as one or more factors separated by ‘*’ or ‘/’ operators. By breaking down expressions into terms and terms into factors, we ensure that the operators are applied with the correct precedence.

For example, “2*C5+D6” is an expression with “2*C5” as its first term and “D6” as its second term. The term “2*C5” has “2” as its first factor and “C5” as its second factor, and the term “D6” consists of the single factor “D6”. A factor can be a number (“2”), a cell location (“C5”), or an expression in parentheses, optionally preceded by a unary minus.

The syntax of spreadsheet expressions is defined in Figure 4.10. For each symbol in the grammar (Expression, Term, and Factor), there is a corresponding member function that parses it and whose structure closely follows the grammar. Parsers written this way are called recursive-descent parsers.

Figure 4.10. Syntax diagram for spreadsheet expressions

Let’s start with evalExpression(), the function that parses an Expression:

QVariant Cell::evalExpression(const QString &str, int &pos) const
{
    QVariant result = evalTerm(str, pos);
    while (str[pos] != QChar::Null) {
        QChar op = str[pos];
        if (op != '+' && op != '-')
            return result;
        ++pos;

        QVariant term = evalTerm(str, pos);
        if (result.type() == QVariant::Double
                && term.type() == QVariant::Double) {
            if (op == '+') {
                result = result.toDouble() + term.toDouble();
            } else {
                result = result.toDouble() - term.toDouble();
            }
        } else {
            result = Invalid;
        }
    }
    return result;
}

First, we call evalTerm() to get the value of the first term. If the following character is ‘+’ or ‘−’, we continue by calling evalTerm() a second time; otherwise, the expression consists of a single term, and we return its value as the value of the whole expression. After we have the value of the first two terms, we compute the result of the operation, depending on the operator. If both terms evaluated to a double, we compute the result as a double; otherwise, we set the result to be Invalid.

We continue like this until there are no more terms. This works correctly because addition and subtraction are left-associative; that is, “1−2−3” means “(1−2)−3”, not “1−(2−3)”.

QVariant Cell::evalTerm(const QString &str, int &pos) const
{
    QVariant result = evalFactor(str, pos);
    while (str[pos] != QChar::Null) {
        QChar op = str[pos];
        if (op != '*' && op != '/')
            return result;
        ++pos;

        QVariant factor = evalFactor(str, pos);
        if (result.type() == QVariant::Double
                && factor.type() == QVariant::Double) {
            if (op == '*') {
                result = result.toDouble() * factor.toDouble();
            } else {
                if (factor.toDouble() == 0.0) {
                    result = Invalid;
                } else {
                    result = result.toDouble() / factor.toDouble();
                }
            }
        } else {
            result = Invalid;
        }
    }
    return result;
}

The evalTerm() function is very similar to evalExpression(), except that it deals with multiplication and division. The only subtlety in evalTerm() is that we must avoid division by zero, since it is an error on some processors. While it is generally inadvisable to test floating-point values for equality because of rounding errors, it is safe to test for equality against 0.0 to prevent division by zero.

QVariant Cell::evalFactor(const QString &str, int &pos) const
{
    QVariant result;
    bool negative = false;

    if (str[pos] == '-') {
        negative = true;
        ++pos;
    }
    if (str[pos] == '(') {
        ++pos;
        result = evalExpression(str, pos);
        if (str[pos] != ')')
            result = Invalid;
        ++pos;
    } else {
        QRegExp regExp("[A-Za-z][1-9][0-9]{0,2}");
        QString token;

        while (str[pos].isLetterOrNumber() || str[pos] == '.') {
            token += str[pos];
            ++pos;
        }
        if (regExp.exactMatch(token)) {
            int column = token[0].toUpper().unicode() - 'A';
            int row = token.mid(1).toInt() - 1;

            Cell *c = static_cast<Cell *>(
                              tableWidget()->item(row, column));
            if (c) {
                result = c->value();
            } else {
                result = 0.0;
            }
        } else {
            bool ok;
            result = token.toDouble(&ok);
            if (!ok)
                result = Invalid;
        }
    }

    if (negative) {
        if (result.type() == QVariant::Double) {
            result = -result.toDouble();
        } else {
            result = Invalid;
        }
    }
    return result;
}

The evalFactor() function is a bit more complicated than evalExpression() and evalTerm(). We start by noting whether the factor is negated. We then see if it begins with an open parenthesis. If it does, we evaluate the contents of the parentheses as an expression by calling evalExpression(). When parsing a parenthesized expression, evalExpression() calls evalTerm(), which calls evalFactor(), which calls evalExpression() again. This is where recursion occurs in the parser.

If the factor isn’t a nested expression, we extract the next token, which should be a cell location or a number. If the token matches the QRegExp, we take it to be a cell reference and we call value() on the cell at the given location. The cell could be anywhere in the spreadsheet, and it could have dependencies on other cells. The dependencies are not a problem; they will simply trigger more value() calls and (for “dirty” cells) more parsing until all the dependent cell values are calculated. If the token isn’t a cell location, we take it to be a number.

What happens if cell A1 contains the formula “=A1”? Or if cell A1 contains “=A2” and cell A2 contains “=A1”? Although we have not written any special code to detect circular dependencies, the parser handles these cases gracefully by returning an invalid QVariant. This works because we set cacheIsDirty to false and cachedValue to Invalid in value() before we call evalExpression(). If evalExpression() recursively calls value() on the same cell, it returns Invalid immediately, and the whole expression then evaluates to Invalid.

We have now completed the formula parser. It would be straightforward to extend it to handle predefined spreadsheet functions, such as “sum()” and “avg()”, by extending the grammatical definition of Factor. Another easy extension is to implement the ‘+’ operator with string operands (as concatenation); this requires no changes to the grammar.