Map table to tree through model/view possible?

[Coises]

The row and column of a QModelIndex are relative to the item’s parent. To create the tree structure you describe, the row and column mapping from source to target is easy: the column of every item in the tree is 0; the row of every item from column 0 of the source is the same as its row in the source, and the row of every item from any column other than 0 is 0.

So nearly all the row/column information from the table is thrown away when you map to the row/column values for the tree. Obviously, you must have some way to recover this information to make the QModelIndexes into the tree meaningful.

The QAbstractItemModel::createIndex functions do not take the parent as an argument; though there is a QModelIndex::parent() function, this just delegates the operation to QAbstractItemModel::parent. Tree structure information is not stored in a QModelIndex, but must be provided by the model.

What you do have in a QModelIndex is an “opaque” value — either a void* or a quint32 (not both) — in which a model can store information it needs to identify the item. You would need to use this field in some way that will allow you to implement QAbstractItemModel::index, QAbstractItemModel::parent, QSortFilterProxyModel::mapFromSource and QSortFilterProxyModel::mapToSource consistently.

If it happens that the ranges of source row and column numbers are limited such that you can squeeze both values into a total of 32 bits, the job is easy — just save the source row and column in the opaque field of each tree QModelIndex, and you’ll have all the information you need to implement the required functions.

If you cannot pack the source row and column into a 32-bit field, it gets messy; you might use a hash table containing row/column pairs, locating or adding each distinct pair as needed and passing the address of the pair as the third argument to createIndex.

[Davor]

The row and column of a QModelIndex are relative to the item’s parent. To create the tree structure you describe, the row and column mapping from source to target is easy: the column of every item in the tree is 0; the row of every item from column 0 of the source is the same as its row in the source, and the row of every item from any column other than 0 is 0.

So nearly all the row/column information from the table is thrown away when you map to the row/column values for the tree. Obviously, you must have some way to recover this information to make the QModelIndexes into the tree meaningful.

The QAbstractItemModel::createIndex functions do not take the parent as an argument; though there is a QModelIndex::parent() function, this just delegates the operation to QAbstractItemModel::parent. Tree structure information is not stored in a QModelIndex, but must be provided by the model.

What you do have in a QModelIndex is an “opaque” value — either a void* or a quint32 (not both) — in which a model can store information it needs to identify the item. You would need to use this field in some way that will allow you to implement QAbstractItemModel::index, QAbstractItemModel::parent, QSortFilterProxyModel::mapFromSource and QSortFilterProxyModel::mapToSource consistently.

If it happens that the ranges of source row and column numbers are limited such that you can squeeze both values into a total of 32 bits, the job is easy — just save the source row and column in the opaque field of each tree QModelIndex, and you’ll have all the information you need to implement the required functions.

If you cannot pack the source row and column into a 32-bit field, it gets messy; you might use a hash table containing row/column pairs, locating or adding each distinct pair as needed and passing the address of the pair as the third argument to createIndex.

I can enumerate uniquely every index/dataitem in the table by the following enumeration method: ((row+column)^2+row-column)/2. I tried to use it as quint32, but the problem was that I didn't understood it's possibilities: quint32 is hardly documented, so I had no idea what to do with it. Can I return it with QModelIndex::internalId ()? Guess not as it is an qint64... The description says: “returns a*qint64*used by the model to associate the index with the internal data structure”... so one has to figure out what this data structure refers to, and what quint32 stands for.

[JD2000]

So isn't the mapping function

Table(n,m) -> Tree(n,0) child(m)?

[wysota]

The mapping is different on "0" level and different on all other levels. It is also different when mapping from the proxy to the source (and that's the problem). I managed to implement everything but the parent() method. In my opinion there is no way of backtracking indexes into the source model other than providing a structure (or two, to be exact) for mapping between indexes of the two models. That's ok as QSortFilterProxyModel does something similar but it is quite complex to implement as there are synchronization issues to consider.

[Davor]

The mapping is different on "0" level and different on all other levels. It is also different when mapping from the proxy to the source (and that's the problem). I managed to implement everything but the parent() method. In my opinion there is no way of backtracking indexes into the source model other than providing a structure (or two, to be exact) for mapping between indexes of the two models. That's ok as QSortFilterProxyModel does something similar but it is quite complex to implement as there are synchronization issues to consider.

I have implemented the topicissue without problems with the TreeItem and TreeModel (from Qt's source snippets) Here is a snippet from the adjusted TreeModel::setupModelData method which works:

QList<TreeItem*> parents;
    parents << parent;
 
    QSqlTableModel table(this, db->returnConnection());
    table.setTable("edg_5_lvl_ext");
    table.select();
 
    for (int row = 0; row < table.rowCount(); row++)
    {
        for (int column = 0; column < table.columnCount(); column++)
        {
            QList<QVariant> data;
            data << table.data(table.index(row,column, QModelIndex()),Qt::DisplayRole);
            parents.last()->appendChild(new TreeItem(data, parents.last()));
            parents << parents.last()->child(parents.last()->childCount()-1);
        }
        parents << parent;
    }

QList<TreeItem*> parents;
    parents << parent;
    
    QSqlTableModel table(this, db->returnConnection());
    table.setTable("edg_5_lvl_ext");
    table.select();

    for (int row = 0; row < table.rowCount(); row++)
    {
        for (int column = 0; column < table.columnCount(); column++)
        {
            QList<QVariant> data;
            data << table.data(table.index(row,column, QModelIndex()),Qt::DisplayRole);
            parents.last()->appendChild(new TreeItem(data, parents.last()));
            parents << parents.last()->child(parents.last()->childCount()-1);
        }
        parents << parent;
    }

To copy to clipboard, switch view to plain text mode 

In the process I got some more insight into how the TreeModel class is made: primarily with QModelIndex::internalPointer ()

Maybe one could use the same method with a proxy for pointing to indexes from the sourceModel(). Here some brainstorming for the mapToSource method:

QModelIndex mapToSource(const QModelIndex &proxyIndex)
    {
      if (*(QModelIndex*) proxyIndex.internalPointer() == QModelIndex()) return QModelIndex();
      if (((QModelIndex*) proxyIndex.internalPointer())->column() == 0) return QModelIndex();
      return sourceModel()->index(proxyIndex.row(), proxyIndex.column());
    }

QModelIndex mapToSource(const QModelIndex &proxyIndex)
    {
      if (*(QModelIndex*) proxyIndex.internalPointer() == QModelIndex()) return QModelIndex();
      if (((QModelIndex*) proxyIndex.internalPointer())->column() == 0) return QModelIndex();
      return sourceModel()->index(proxyIndex.row(), proxyIndex.column());
    }

To copy to clipboard, switch view to plain text mode 

Something else wysota. I don't know what you had in mind when you said that you always miss one value: colum/row or parent. But maybe if you could use the qint32 from an index, you maybe could extract the unknown row from ((row+column)^2+row-column)/2 formula, provided you know the column.

[wysota]

I have implemented the topicissue without problems with the TreeItem and TreeModel (from Qt's source snippets) Here is a snippet from the adjusted TreeModel::setupModelData method which works

This is easy because you only have to map one way. It's the other way that causes problems. The other problem - the parent() method is easily avoidable with tree items because you can simply store a pointer to the parent item in the item itself. You don't have such pointers when operating on bare indices.

Something else wysota. I don't know what you had in mind when you said that you always miss one value: colum/row or parent. But maybe if you could use the qint32 from an index, you maybe could extract the unknown row from ((row+column)^2+row-column)/2 formula, provided you know the column.

If the formula is correct then probably so. I might give it a try.

Edit: Nope, it won't work. I don't need the formula - I can store the row number in the index, that's not a problem. But it's still not possible to do the mapping both ways. You need to store both column and row.

I can do that, that's not a problem but the model will only be able to hold 32k rows and 32k columns Here is the code:

#include <QtGui>                        
 
class MyProxy : public QAbstractProxyModel {
public:                                     
    MyProxy() : QAbstractProxyModel(){}     
    QModelIndex mapToSource(const QModelIndex &proxyIndex) const {
        if(!proxyIndex.isValid()) return QModelIndex();           
        int c = columnFromIndex(proxyIndex);                      
        int r = rowFromIndex(proxyIndex);                         
        return sourceModel()->index(r,c);                         
    }                                                             
 
    QModelIndex mapFromSource(const QModelIndex &sourceIndex) const {
        if(!sourceIndex.isValid()) return QModelIndex();             
        if(sourceIndex.column()==0)                                  
            return createIndex(sourceIndex.row(), 0, calculateId(sourceIndex));
        return createIndex(0, 0, calculateId(sourceIndex));                    
    }                                                                          
    int columnCount(const QModelIndex &parent = QModelIndex()) const {         
        return 1;                                                              
    }                                                                          
    int rowCount(const QModelIndex &parent = QModelIndex()) const {            
        if(!parent.isValid())                                                  
            return qMin(0x10000, sourceModel()->rowCount());                   
        int c = mapToSource(parent).column();                                  
        if(c==sourceModel()->columnCount()-1)                                  
           return 0;                                                           
        return 1;                                                              
    }                                                                          
    QModelIndex index(int row, int column, const QModelIndex &parent = QModelIndex()) const {
        if(parent.isValid()) {                                                               
            // if parent is valid then in the source model                                   
            // we want to receive the same row but the next column, provided that row==0 && col==0
            // otherwise the index is not valid                                                   
            if(row!=0 || column!=0) return QModelIndex();                                         
            return createIndex(row, column, (int)parent.internalId()+1);                          
        }                                                                                         
        if(column!=0) return QModelIndex();                                                       
        // parent is not valid thus we can calculate the id the same way as for the source model  
        return createIndex(row, 0, calculateId(row, 0));                                          
    }                                                                                             
    QModelIndex parent(const QModelIndex &child) const {                                          
        if(!child.isValid())                                                                      
            return QModelIndex();                                                                 
        // parent of an index in the source model is the same row but previous column             
        int c = mapToSource(child).column();                                                      
        int r = mapToSource(child).row();                                                         
        if(c==0){                                                                                 
          // if original column == 0 then there is no parent                                      
          return QModelIndex();                                                                   
        }                                                                                         
        c -= 1;                                                                                   
        if(c==0){                                                                                 
            return createIndex(r, 0, calculateId(r, c));                                          
        }                                                                                         
        return createIndex(0, 0, calculateId(r, c));                                              
    }                                                                                             
private:                                                                                          
    int columnFromIndex(const QModelIndex &proxyIndex) const {
         quint32 id = proxyIndex.internalId();
         int c = (id & 0xffff);
         return c;
    }
    int rowFromIndex(const QModelIndex &proxyIndex) const {
         quint32 id = proxyIndex.internalId();
         int r = (id & 0xffff0000) >> 16;
         return r;
    }
    int calculateId(const QModelIndex &sourceIndex) const {
        quint32 r = sourceIndex.row();
        quint32 c = sourceIndex.column();
        return calculateId(r, c);
    }
    int calculateId(quint32 r, quint32 c) const{
        return (((r & 0xffff) << 16) | (c & 0xffff));
    }
};
 
int main(int argc, char **argv) {
    QApplication app(argc, argv);
    QTreeView tv;
    QStandardItemModel model(40,20);
    for(int i=0; i<model.rowCount(); i++){
      for(int j=0; j<model.columnCount(); j++){
          model.setData(model.index(i,j), qrand() % 100, Qt::DisplayRole);
      }
    }
    MyProxy proxy;
    proxy.setSourceModel(&model);
    tv.setModel(&proxy);
    tv.show();
    QTableView orig;
    orig.setModel(&model);
    orig.show();
    return app.exec();
}

#include <QtGui>                        

class MyProxy : public QAbstractProxyModel {
public:                                     
    MyProxy() : QAbstractProxyModel(){}     
    QModelIndex mapToSource(const QModelIndex &proxyIndex) const {
        if(!proxyIndex.isValid()) return QModelIndex();           
        int c = columnFromIndex(proxyIndex);                      
        int r = rowFromIndex(proxyIndex);                         
        return sourceModel()->index(r,c);                         
    }                                                             

    QModelIndex mapFromSource(const QModelIndex &sourceIndex) const {
        if(!sourceIndex.isValid()) return QModelIndex();             
        if(sourceIndex.column()==0)                                  
            return createIndex(sourceIndex.row(), 0, calculateId(sourceIndex));
        return createIndex(0, 0, calculateId(sourceIndex));                    
    }                                                                          
    int columnCount(const QModelIndex &parent = QModelIndex()) const {         
        return 1;                                                              
    }                                                                          
    int rowCount(const QModelIndex &parent = QModelIndex()) const {            
        if(!parent.isValid())                                                  
            return qMin(0x10000, sourceModel()->rowCount());                   
        int c = mapToSource(parent).column();                                  
        if(c==sourceModel()->columnCount()-1)                                  
           return 0;                                                           
        return 1;                                                              
    }                                                                          
    QModelIndex index(int row, int column, const QModelIndex &parent = QModelIndex()) const {
        if(parent.isValid()) {                                                               
            // if parent is valid then in the source model                                   
            // we want to receive the same row but the next column, provided that row==0 && col==0
            // otherwise the index is not valid                                                   
            if(row!=0 || column!=0) return QModelIndex();                                         
            return createIndex(row, column, (int)parent.internalId()+1);                          
        }                                                                                         
        if(column!=0) return QModelIndex();                                                       
        // parent is not valid thus we can calculate the id the same way as for the source model  
        return createIndex(row, 0, calculateId(row, 0));                                          
    }                                                                                             
    QModelIndex parent(const QModelIndex &child) const {                                          
        if(!child.isValid())                                                                      
            return QModelIndex();                                                                 
        // parent of an index in the source model is the same row but previous column             
        int c = mapToSource(child).column();                                                      
        int r = mapToSource(child).row();                                                         
        if(c==0){                                                                                 
          // if original column == 0 then there is no parent                                      
          return QModelIndex();                                                                   
        }                                                                                         
        c -= 1;                                                                                   
        if(c==0){                                                                                 
            return createIndex(r, 0, calculateId(r, c));                                          
        }                                                                                         
        return createIndex(0, 0, calculateId(r, c));                                              
    }                                                                                             
private:                                                                                          
    int columnFromIndex(const QModelIndex &proxyIndex) const {
         quint32 id = proxyIndex.internalId();
         int c = (id & 0xffff);
         return c;
    }
    int rowFromIndex(const QModelIndex &proxyIndex) const {
         quint32 id = proxyIndex.internalId();
         int r = (id & 0xffff0000) >> 16;
         return r;
    }
    int calculateId(const QModelIndex &sourceIndex) const {
        quint32 r = sourceIndex.row();
        quint32 c = sourceIndex.column();
        return calculateId(r, c);
    }
    int calculateId(quint32 r, quint32 c) const{
        return (((r & 0xffff) << 16) | (c & 0xffff));
    }
};

int main(int argc, char **argv) {
    QApplication app(argc, argv);
    QTreeView tv;
    QStandardItemModel model(40,20);
    for(int i=0; i<model.rowCount(); i++){
      for(int j=0; j<model.columnCount(); j++){
          model.setData(model.index(i,j), qrand() % 100, Qt::DisplayRole);
      }
    }
    MyProxy proxy;
    proxy.setSourceModel(&model);
    tv.setModel(&proxy);
    tv.show();
    QTableView orig;
    orig.setModel(&model);
    orig.show();
    return app.exec();
}

To copy to clipboard, switch view to plain text mode 

[Davor]

Edit: Nope, it won't work. I don't need the formula - I can store the row number in the index, that's not a problem. But it's still not possible to do the mapping both ways. You need to store both column and row.

I can do that, that's not a problem but the model will only be able to hold 32k rows and 32k columns

You're awesome. You really deserve the “Guru” tag

Your enumeration is indeed the best way to solve this. I also have to say that I have learned more from your example that from all the Qt docs I have read up till now.

You post should be made to stick out someway, so the one who searches for the solution, might not get scared from the rest of the posts. I can not edit my initial post, so maybe the admin could refer from it to wysota's solution?

Thanks again wysota.

[wysota]

I think I'll post it on the wiki, it's a nice example indeed although a bit hackish.

[JD2000]

Seems overly complicated to me, how about this:

#include <QtGui>
 
int main(int argc, char **argv) {
    QApplication app(argc, argv);
 
    QStandardItemModel tableModel(4, 4);
    for (int row = 0; row < 4; ++row) {
        for (int column = 0; column < 4; ++column) {
             QStandardItem *item = new QStandardItem(QString("row %0, column %1").arg(row).arg(column));
             tableModel.setItem(row, column, item);
        }
    }
    QTableView tablev;
    tablev.setModel(&tableModel);
    tablev.show();
 
    QTreeView treev;
    QSortFilterProxyModel *proxyModel = new QSortFilterProxyModel();
 
    proxyModel->setSourceModel(&tableModel);
    treev.setModel(proxyModel);
    treev.show();
 
    return app.exec();
 
}

#include <QtGui>

int main(int argc, char **argv) {
    QApplication app(argc, argv);

    QStandardItemModel tableModel(4, 4);
    for (int row = 0; row < 4; ++row) {
        for (int column = 0; column < 4; ++column) {
             QStandardItem *item = new QStandardItem(QString("row %0, column %1").arg(row).arg(column));
             tableModel.setItem(row, column, item);
        }
    }
    QTableView tablev;
    tablev.setModel(&tableModel);
    tablev.show();

    QTreeView treev;
    QSortFilterProxyModel *proxyModel = new QSortFilterProxyModel();

    proxyModel->setSourceModel(&tableModel);
    treev.setModel(proxyModel);
    treev.show();

    return app.exec();

}

To copy to clipboard, switch view to plain text mode 

I've hardcoded the table dimensions at 4x4 for the sake of brevity, but you get the idea.

[wysota]

Does it cause a flat model to become a hierarchical one? Or maybe I am missing the point of this example...

[JD2000]

Ah, good point.

You certainly end up with a table and tree, both referencing the data held in the table and both having 4 rows (in this case) but yes, each table row becomes a tree column 0 element.

My take on this was as stated in the title - map a table to a tree - I don't know whether the parent child relationship between table row elements is actually that important. It makes a great intellectual exercise though, well solved!

[Davor]

Ah, good point.

You certainly end up with a table and tree, both referencing the data held in the table and both having 4 rows (in this case) but yes, each table row becomes a tree column 0 element.

My take on this was as stated in the title - map a table to a tree - I don't know whether the parent child relationship between table row elements is actually that important. It makes a great intellectual exercise though, well solved!

On the importance: currently, Qt framework doesn't allow any direct mapping between one table and a hierarchical structure. That's unfortunate, at least because both structures are isomorphic. Here a practical example: Suppose you gather data which is hierarchically representable, store it into a relational database (see my other post, here for reference: Kaufmann's Joe Celko's Trees and Hierarchies in SQL for Smarties) and which you want to reproduce/visualize. From such databases you only get tables... no trees.

The whole problem isn't solved yet: you still have redundant trees: take the following table of primary keys forming the edges between two nodes (i.e. two other tables):
11
12
23

Both 1 and 2 from the second row refer tot the same PK from the first column, so they should form one tree with two children.

Tree should look something like this:
1
|||1
|||2
2
|||3

Such tables are simple to generate with relational databases. What is needed is some way to translate them into trees. Wysota has made the first step. I will not bother him for the second, but just note this as an answer to your question.

And as for how to make it.... unfortunately it is not that easy again. The most important is the fact that the parent is uniquely identified by the preceding (primary key) fields (and not by the column and it's PK, as it would seem from the relational model).

Here is an example on how to populate the tree:

for each row
---for each column
------check column = primary
------PK = readPKfrommodel(row,column)
------append PK into PathIDVector (which is the parent's ID)
------If PathIDVector does not exist yet --> make a treeitem(PathIDVector) which is the child of treeitem(PathIDVector_less_one)

Currently I have this with TreeItem/TreeModel, and it's no pretty code. If I find time, I'll try to implement it in wysota's code, and post it here.

[JD2000]

Tables and trees are not isomorphic, that is the problem.

A tree holds what are essentially tables (their elements are indexed by [row,column]) in some sort of

hierarchy. If you collapse a tree, you end up with a table.

In order to impose such a hierarchy on a table, the table / table elements need to store their

row/column data as usual plus references to their parents. Then when you rebuild the tree check this

reference to find out which node to attach the table element to.

Alternatively for example in cases like yours where there is a defined structure, the parent reference

is not needed because it can be calculated by the model being used:

#include <QtGui>
 
int main(int argc, char **argv) {
    QApplication app(argc, argv);
 
    int maxrows = 4;
    int maxcols = 4;
 
    QStandardItemModel tableModel(maxrows, maxcols);
    for (int row = 0; row < maxrows; ++row) {
        for (int column = 0; column < maxcols; ++column) {
             QStandardItem *item = new QStandardItem(QString("row %0, column %1").arg(row).arg(column));
             tableModel.setItem(row, column, item);
        }
    }
 
    QTableView tablev;
    tablev.setModel(&tableModel);
    tablev.show();
 
    QStandardItemModel treeModel;
    QStandardItem *parentItem = treeModel.invisibleRootItem();
 
    for (int row = 0; row < maxrows; ++row) {
        for (int col = 0; col < maxcols; ++col) {
           // grab the data out of the table
            QStandardItem *item = new QStandardItem(tableModel.data(tableModel.index(row, col, QModelIndex()), Qt::DisplayRole).toString());
            parentItem->appendRow(item);
            parentItem = item;
        }
    parentItem = treeModel.invisibleRootItem();
    }
 
    QTreeView treev;
    treev.setModel(&treeModel);
    treev.show();
 
    return app.exec();
 
}

#include <QtGui>

int main(int argc, char **argv) {
    QApplication app(argc, argv);

    int maxrows = 4;
    int maxcols = 4;

    QStandardItemModel tableModel(maxrows, maxcols);
    for (int row = 0; row < maxrows; ++row) {
        for (int column = 0; column < maxcols; ++column) {
             QStandardItem *item = new QStandardItem(QString("row %0, column %1").arg(row).arg(column));
             tableModel.setItem(row, column, item);
        }
    }

    QTableView tablev;
    tablev.setModel(&tableModel);
    tablev.show();

    QStandardItemModel treeModel;
    QStandardItem *parentItem = treeModel.invisibleRootItem();

    for (int row = 0; row < maxrows; ++row) {
        for (int col = 0; col < maxcols; ++col) {
           // grab the data out of the table
            QStandardItem *item = new QStandardItem(tableModel.data(tableModel.index(row, col, QModelIndex()), Qt::DisplayRole).toString());
            parentItem->appendRow(item);
            parentItem = item;
        }
    parentItem = treeModel.invisibleRootItem();
    }

    QTreeView treev;
    treev.setModel(&treeModel);
    treev.show();

    return app.exec();

}

To copy to clipboard, switch view to plain text mode 

The problem here is that after creation, the tree and table are independant of each other.

I suppose that they could be kept in sync by implementing their respective data changed signals/slots.