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

Question

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

Answer 1

たちはleftがnullの場合は、文字がstring[0], ..., string[length - 1]ある

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

のようにロープ構造体を持っていると仮定します。それ以外の場合は、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; 
    } 
}