c++ - 绳索数据结构的拆分操作

Question

我正致力于在 C++ 中为完全抽象的对象实现 Rope 数据结构。我遇到的问题是我无法弄清楚关键的“拆分”操作的实现。维基百科页面很有帮助，但含糊不清且理论性很强，文本附带的图像无助于我理解算法。有没有好的实现，或者有提供示例代码的论文？我曾尝试阅读原始论文，但它们也无济于事。

Answer 1

假设我们有一个像这样的绳索结构

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

如果left 为null，则字符为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;
    }
}