Split operation on rope data structures

I am working on implementing the Rope data structure in C++ for completely abstract objects. The problem I am having is that I can't figure out the implementation of the critical "split" operation. The Wikipedia page is helpful, but vague and highly theoretical, and the images attached to the text do not help my understanding of the algorithm. Is there a good implementation, or a paper that provides sample code? I have tried reading the original papers, but they don't really help either.

---

Suppose we have a rope structure like

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

If left is null, then the characters are string[0], ..., string[length - 1] . Otherwise, the characters are the ones in left followed by the ones in right . Leaving aside questions of storage management, the substring operation is

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;
    }
}

链接地址: http://www.djcxy.com/p/39800.html

上一篇: 无法在C ++中实现“绳索”数据结构

下一篇: 在绳索数据结构上拆分操作