Implementing Qt data models is anything but fun. For that reason, I
don’t blame anyone for writing a beginResetModel / endResetModel combo
any time a more complex change has happened.
That is something that we all do, that is something that even Qt
people do in their classes (see QSqlTableModel::select for example).
Resetting a model is an expensive process that can induce overly many
transition animations in QML views. And it is often not really
necessary.
Updates are rarely that complex to warrant invalidation of all data
in the model. Usually, they only consist of a few additions or
removals.
Levenshtein distance
I was planning to fix this in the KActivities data models for some
time now, but haven’t found the time until now.
Recently I started teaching algorithms to my students, coincidentally
some modifications of the usual Levenshtein
distance calculation algorithm. (if you don’t recall the algorithm
courses you had, L.D. calculates how many insertions, deletions and
replacements you have to make in order to convert one string to
another)
Now, the Levenshtein distance is not really a fitting algorithm for
this task. Here, at least in KActivities use-case, most edits are not
per-item. They are more suitable to be represented as sequences of block
operations. Block operations also fit the Qt data model API
perfectly.
After some research, I found a paper by Walter F. Tichy. A paper that
is as old as I am, talking about the string-to-string correction problem
with block moves. The algorithm described there was almost a perfect
fit.
The algorithm
It is a really simple algorithm, that can be described in only a few
lines:
- Take the first character in the destination string
- Find all occurences of said character in the source string, and take
the one that defines the longest matching block
- Now, repeat the algorithm for the first character in the destination
string that was outside of the previously detected block.
For example:
Source: abcabcdefg
| /----/
|/
Destination: abcdefbcg
In this case, for the character ‘a’, it will find two blocks in the
source string: ‘abc’ and ‘abcdef’. It will choose the second one, and
register a block operation that moves it to the beginning of the string.
The next one will detect ‘bc’, and so on.
In the case of KActivities, the situation is a bit simpler. A model
can not contain repeated items, so there is no need to find the biggest
block - there is only one possible block that starts with a specific
element.
The algorithm has O(n²) complexity in the worst case, but in the
common case it tends to be linear - O(n).
Testing
In order to test the updates, the model testing application now has
both QWidget-based UI and QML-based one. All transitions in QML are set
to last for one second, which makes all the events blatantly
obvious.
Why the post title?
So, why is the title of this post ‘there and back again’?
While working on the above algorithm, I wanted to decouple the model
cache implementation from the model itself.
The idea was for the cache class to have methods that do not modify
anything, but to return a sequence of edit operations that need to be
performed.
Something like this:
QList<EditOperation> setItems(...) const;
QList<EditOperation> trimData(...) const;
and a single non-const method that actually performs a specific
operation:
void applyOperation(EditOperation eo);
The model class that uses this cache would get a list of operations
that should be made, and execute one by one while invoking the
corresponding begin(Insert/Remove/Move)Rows / end____Rows methods.
The idea was clean and beautiful, but overly complex and induced some
unnecessary performance penalties. The main problem was in the above
algorithm, because it needs to actually be able to change the cache data
while generating the list of block edits.
For decoupling to work properly, it would need to create a temporary
copy of the cached data just to be able to modify it while calculating
the edit operations. Then, it would destroy it and return a list of
operations it did on the temporary data to be performed on the actual
cache.
So, in the end, I decided that efficiency is more important, and
allowed the cache to directly call
begin_Rows/end_Rows methods.
Conclusion
Is the moral of the story that algorithms are more important to know
then object-oriented programming and encapsulation?
Yes… No… Maybe… :)
