FastDiffRunner Proposal

Objective

The current implementation of DiffRunner requires the user to convert a C++ data structure into QVariantMap then perform a comparison. It is an easy to use solution and fast enough for the small amount of data. But since the average time complexity is O(n) even the data is unchanged. Therefore, it may be difficult to handle a huge amount of data.

To solve this problem, a new FastDiffRunner is proposed. It uses the implicitly shared data class (Immutable type) in Qt. The big-O to compare data without changes is O(1). And it doesn't convert data to QVariantMap for comparison. It should be much faster than the original DiffRunner.

Preparation

1. Immutable Data

FastDiffRunner only works with an immutable data type. User should create their data structure by File -> New File or Project -> C++ Class. Tick Include QShared Data in Qt Creator

Example (Generated by Qt Creator)

class CustomDataData;

class CustomData
{
public:
    CustomData();
    CustomData(const CustomData &);
    CustomData &operator=(const CustomData &);
    ~CustomData();

private:
    QSharedDataPointer<CustomDataData> data;
};

2. Implements isSharedWith() and key() function

class CustomDataData;

class CustomData
{
    Q_GADGET

public:
    CustomData();
    CustomData(const CustomData &);
    CustomData &operator=(const CustomData &);
    ~CustomData();

    bool isSharedWith(const CustomData& other);

    Q_INVOKABLE QVariant key(); // Optional function. 

private:
    QSharedDataPointer<CustomDataData> data;
};

inline bool CustomData::isSharedWith(const CustomData &other)
{
    return this->data == other.data;
}

3. Implements custom convertor function [Optional]

QVariantMap convert(const CustomData& data) {
  /// Insert your code here
}

If you have declared your property via Q_PROPERTY(), then it is not needed.

Usage

The interface of FastDiffRunner is almost same as the DiffRunner, expect you may need apply a custom data convertor function and doesn't need to set key field.

QList<CustomData> previous, current; 

// load previous and current 

QSFastDiffRunner<CustomData> runner(convert); 

QList<QSPatch> patches = runner.compare(previous, current);

runner.patch(listModel, patches);

Pros & Cons

Pros

1. O(1) comparison for unchanged data

Cons

1. It don't work for JavaScript

Request for Comment

If you have any suggestion toward the design, please feel free to leave a comment here. Thx

Discussion

Discussion 1

Interface Class

Should it use an abstract interface instead of just using Q_GADGET?

Example

class QSImmutable {
  Q_GADGET
public:
  bool iSharedWith(const QSImmutable*) = 0;
  QVariant key() const;
  bool hasKey() const; // User should implement this function if key is present in the data structure
}