Hierachical data in TreeViews and TreeView updating technique

Question

I have lots of (hierachical) data that I show in a TreeView (could be around 20K items or more, including children items). The peculiar problem with my data is that each object shown in the treeview can exist in many treeview items. What I mean by that is that I might have an hierarchy like this one:

1. Item_A -> Item_B -> ItemC
2. Item_B -> Item_C
3. ItemC

Lets assume that Item_A contains Item_B which contains Item_C as it is shown above. This means that my list will also show the hierarchy of Item_B and Item_C. Consider now that something happens to an an object shown as Item_B (e.g name change). Then of course both items must be updated. Consider now thousands of items in the treeview with complex hierarchies. What strategy would you use to update the treeview? Speed is of course the main concern here but also ease of use and maintenance. Currently I hold internal mappings of list items to objects and vice-versa to find and update items quickly. Is that a correct strategy? By recreating the list after each update I can throw lots of code away, but I wouldn't know which item paths were expanded or collapsed. How could I solve this problem? Should I store expanded paths in an internal container?

Thank you.

PS: Programming language is C++, and GUI lib is QT3.

Answer 1

I did something similar long time ago, using the windows TreeView common control.

What I did was set the CUSTOMDRAW flag, keep a single instance of each possible different node and make each node point to this instance: The 3 Item_C nodes would each have a pointer to the same unique Item_C instance.

So, when I change the data on Item_C I only needed to Invoke InvalidateRect() on the 3 Item_C nodes in order to reflect the changes done on the (single) changed data.

I suppose you could apply the same strategy here.

Answer 2

Use Qt4 model/view if you can use Qt4 in your project.

You will have to write your own model which can be tedious if you've never done so, but once setup you can reference/update multiple instances of the same object easily. Selections/Multiple selection can be handled too.

I'm not a big fan of Qt's model/view implementation (given model/view/controller design pattern is quite old) but it helps to organize data in gUIs

Answer 3

Disable updates using widget->setUpdatesEnabled(false), then edit all you want, and then renable it with widget->setUpdatesEnabled(true).

See the Qt documentation.

Answer 4

I solved a similar problem using the wxWidgets tree control. I used a singleton reference counter to track the objects I was putting in the control, and an iterator to traverse them. Here's an example.

class ReferenceCounter
{
public:
    // Singleton pattern. Implementation left up to you.
    static ReferenceCounter& get();

    void add(const TreeData& data) {
        mCounter[data.getId()].push_back(&data);
    }

    void remove(const TreeData& data) {
        const CounterType::const_iterator itr = mCounter.find(data.getId());
        if (itr != mCounter.end()) {
            ItemType& items = itr->second;
            items.erase(std::remove(items.begin(), items.end(), &data), items.end());
            if (items.empty()) {
                mCounter.erase(itr);
            }
        }
    }

    typedef std::vector<TreeData*> ItemType;
    ItemType::iterator begin(const TreeData& data) {
        const CounterType::const_iterator itr = mCounter.find(data.getId());
        if (itr != mCounter.end()) {
            return itr->second.begin();
        }
        // Else condition handling left up to you.
    }

    ItemType::iterator end(const TreeData& data) {
        const CounterType::const_iterator itr = mCounter.find(data.getId());
        if (itr != mCounter.end()) {
            return itr->second.end();
        }
        // Else condition handling left up to you.
    }

private:     
    typedef std::map<int, ItemType> CounterType;
    CounterType mCounter;
};

class TreeData
{
public:
    TreeData() { ReferenceCounter::get().add(*this); }
    ~TreeData() { ReferenceCounter::get().remove(*this); }

    // Get database rows or whatever your tree is tracking.
    int getId() const;
};

So given any TreeData, you can look up all the other TreeData's with matching ids in the reference counter. This makes it easy and fast keeping names and stuff up to date. Our tree handles over 1,000,000 nodes without a problem. In my implementation, I wrapped the iteration stuff up in a boost::iterator_facade class for easier use.