c++ - ロープ データ構造の分割操作

Question

私は、完全に抽象化されたオブジェクトのために C++ で Rope データ構造を実装することに取り組んでいます。私が抱えている問題は、重要な「分割」操作の実装を理解できないことです。ウィキペディアのページは役に立ちますが、あいまいで非常に理論的であり、テキストに添付されている画像はアルゴリズムの理解に役立ちません。良い実装、またはサンプル コードを提供する論文はありますか? 元の論文を読んでみましたが、どちらも役に立ちません。

Answer 1

次のようなロープ構造があるとします。

struct Rope {
    Rope *left;
    union {
        Rope *right;
        const char *string;
    };
    size_t length;
};

が null の場合left、文字はstring[0], ..., string[length - 1]. それ以外の場合、文字は の文字の後に の文字がleft続きrightます。ストレージ管理の問題はさておき、部分文字列操作は次のとおりです。

Rope *substring(const Rope *r, size_t start, size_t length) {
    if (!r->left) {
        Rope *s = new Rope;
        s->left = 0;
        s->string = r->string + start;
        s->length = length;
        return s;
    } else if (start + length <= r->left->length) {
        return substring(r->left, start, length);
    } else if (r->left->length <= start) {
        return substring(r->right, start - r->left->length, length - r->left->length);
    } else {
        Rope *s = new Rope;
        s->left = substring(r->left, start, r->left->length - start);
        s->right = substring(r->right, 0, length - (r->left->length - start));
        s->length = length;
        return s;
    }
}