Rope — KAL

Bayangkan editor teks dengan dokumen berisi jutaan karakter. Operasi standar seperti insert di tengah, delete substring, atau replace bisa sangat lambat pada std::string karena harus memindahkan semua karakter setelah posisi operasi — O(n) per operasi. Untuk dokumen besar, ini tidak acceptable. Rope adalah struktur data berbasis B-tree (balance tree) di mana setiap leaf menyimpan substring kecil, dan setiap node internal menyimpan metadata length. Operasi insert, erase, substr, replace, dan concat semua berjalan O(log n). Library GNU PBDS menyediakan implementasi __gnu_cxx::rope<T> siap pakai. Pada Chapter ini kita memakai rope<char> untuk manipulasi string panjang dan membedah operasi-operasinya.

Aturan: Operasi yang Didukung Rope #

rope<T> mendukung:

push_back(val): tambah elemen di akhir. Amortized O(log n).
substr(pos, len): ambil substring [pos, pos+len). O(log n).
insert(pos, rope_or_string): insert di posisi pos. O(log n).
erase(pos, len): hapus len elemen mulai dari pos. O(log n).
replace(pos, len, new_rope): ganti substring [pos, pos+len) dengan new_rope. O(log n).
operator+: concatenation dua rope. O(log n) (lazy, hanya membuat root baru).
operator[]: random access elemen ke-i. O(log n).
c_str(): konversi ke C-string (mengalokasikan memori O(n)).

Untuk string panjang dengan banyak edit, rope jauh lebih cepat dari std::string (yang O(n) per insert/delete).

Mekanisme: B-tree of Chunks #

Rope internalnya adalah B-tree ber平衡 di mana:

Setiap leaf menyimpan chunk string kecil (panjang ~32-256 byte).
Setiap internal node menyimpan panjang total subtree kiri (untuk navigasi).
Operasi insert(pos, x): cari leaf tempat pos berada, lalu split leaf dan sisipkan chunk baru. Bila leaf menjadi terlalu besar, split lebih lanjut. Bila tree tidak balance, rebalance via rotasi. Semua O(log n).
Operasi substr(pos, len): cari leaf pembuka dan penutup, copy elemen-elemen di antara. O(log n + len).
Operasi replace = erase + insert. O(log n).

Concatenation dengan operator+ sangat efisien — hanya membuat node root baru dengan dua child adalah rope lama. Lazy: tidak menggabung secara fisik sampai diperlukan.

flowchart TD A["root: len=L+R"] --> B["left subtree<br/>stores chars [0..L)"] A --> C["right subtree<br/>stores chars [L..L+R)"] B --> D["leaf: 'Hello, '"] B --> E["leaf: 'World!'"] C --> F["leaf: ' Ini teks.'"]

Implementasi Rope dengan PBDS #

cpp
#include <iostream>
#include <string>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

int main() {
    rope<char> r;
    string s = "Hello, World! Ini adalah teks panjang untuk demonstrasi rope.";
    for (char c : s) r.push_back(c);

    cout << "Isi awal: " << r.c_str() << '\n';
    cout << "Panjang: " << r.size() << '\n';

    // Substring: rope method substr(pos, len)
    rope<char> sub = r.substr(7, 5);
    cout << "\nsubstr(7, 5) = " << sub.c_str() << '\n';

    // Insert di tengah
    r.insert(13, " -- INSERTED --");
    cout << "\nSetelah insert di pos 13:\n  " << r.c_str() << '\n';

    // Delete range [13, 13+15)
    r.erase(13, 15);
    cout << "\nSetelah erase 15 char dari pos 13:\n  " << r.c_str() << '\n';

    // Replace substring
    r.replace(7, 5, "ROPE");
    cout << "\nSetelah replace 'World' dengan 'ROPE':\n  " << r.c_str() << '\n';

    // Concat (rope + rope)
    rope<char> r2;
    string s2 = " Tambahan di akhir.";
    for (char c : s2) r2.push_back(c);
    rope<char> concatenated = r + r2;
    cout << "\nSetelah concatenation:\n  " << concatenated.c_str() << '\n';

    // Indexing (random access)
    cout << "\nIndexing:\n";
    cout << "  concatenated[0] = " << concatenated[0] << '\n';
    cout << "  concatenated[7] = " << concatenated[7] << '\n';
    cout << "  concatenated[20] = " << concatenated[20] << '\n';

    cout << "\nTotal length: " << concatenated.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Isi awal: Hello, World! Ini adalah teks panjang untuk demonstrasi rope.
Panjang: 61

substr(7, 5) = World

Setelah insert di pos 13:
  Hello, World! -- INSERTED -- Ini adalah teks panjang untuk demonstrasi rope.

Setelah erase 15 char dari pos 13:
  Hello, World! Ini adalah teks panjang untuk demonstrasi rope.

Setelah replace 'World' dengan 'ROPE':
  Hello, ROPE! Ini adalah teks panjang untuk demonstrasi rope.

Setelah concatenation:
  Hello, ROPE! Ini adalah teks panjang untuk demonstrasi rope. Tambahan di akhir.

Indexing:
  concatenated[0] = H
  concatenated[7] = R
  concatenated[20] = l

Total length: 79

Bedah Kode Baris-per-Baris #

#include <ext/rope>: header rope. Tersedia di GCC extension.
using namespace __gnu_cxx;: rope ada di namespace __gnu_cxx, bukan std.
rope<char> r: rope dengan elemen char. Bisa juga rope<int> untuk array integer besar.
r.push_back(c): tambah satu karakter. Lebih lambat dari std::string::push_back untuk string kecil (overhead B-tree), tetapi O(log n) untuk string panjang. Untuk konstruksi awal, alternatif: rope<char> r(s.c_str()) dari C-string.
r.c_str(): konversi ke null-terminated C-string. Alokasi O(n) — pakai hanya saat butuh cetak atau interface dengan API C. Jangan dipanggil berulang.
r.substr(pos, len): return rope baru berisi substring [pos, pos+len). O(log n) untuk pembentukan struktur (chunk direferensi, bukan di-copy).
r.insert(pos, "literal"): insert C-string di posisi pos. Implementasi rope mendukung insert literal string, rope<T>, atau T tunggal.
r.erase(pos, len): hapus len karakter mulai dari pos. O(log n).
r.replace(pos, len, "new"): ganti substring [pos, pos+len) dengan "new". O(log n).
r + r2: concatenation. Sangat efisien — rope membuat root baru dengan r dan r2 sebagai child. Tidak menggabungkan fisik. Bila setelah concatenation kita lakukan banyak operasi, rebalance terjadi lazy.
r[i]: random access elemen ke-i. O(log n) — harus traverse tree dari root ke leaf. Lebih lambat dari std::string::operator[] (O(1)) — rope mengorbankan akses random demi insert/delete cepat.
Verifikasi:
- Awal: 61 karakter ("Hello, World! Ini adalah teks panjang untuk demonstrasi rope." panjang = 61). ✓
- substr(7, 5) = "World" (indeks 7-11: “World”). ✓
- Setelah insert(13, " -- INSERTED --"): text di posisi 13+ digeser ke kanan. Hasil: "Hello, World! -- INSERTED -- Ini...". ✓
- Setelah erase(13, 15): hapus 15 karakter " – INSERTED – " dari posisi 13. Kembali ke teks asli. ✓
- Setelah replace(7, 5, "ROPE"): ganti “World” (5 char dari pos 7) dengan “ROPE”. Hasil: "Hello, ROPE! Ini...". ✓
- Setelah concatenation dengan " Tambahan di akhir.": 61 + 18 (panjang Tambahan di akhir. = 19 chars termasuk spasi leading). Wait, length 79. 61 + 18 = 79, tapi " Tambahan di akhir." panjang 19… oh, sebenarnya setelah replace, panjang berubah: "Hello, ROPE! Ini..." — replace 5 char dengan 4 char, jadi kurang 1. Sehingga 61 - 1 = 60. Plus " Tambahan di akhir." panjang 19 = 60 + 19 = 79. ✓
- concatenated[0] = 'H', [7] = 'R' (R dari ROPE), [20] = 'l' (huruf ’l’ ke-3 dari “Hello”, indeks 0=‘H’,1=‘e’,2=‘l’,3=‘l’,4=‘o’,5=’,’,6=’ ‘,7=‘R’,8=‘O’,9=‘P’,10=‘E’,11=’!’,12=’ ‘,13=‘I’,14=‘n’,15=‘i’,16=’ ‘,17=‘a’,18=’d’,19=‘a’,20=‘l’). ✓

Kompleksitas dan Perbandingan #

Operasi	`std::string`	`rope<char>`
`operator[i]`	O(1)	O(log n)
`push_back`	Amortized O(1)	O(log n)
`insert(pos, str)`	O(n)	O(log n)
`erase(pos, len)`	O(n)	O(log n)
`substr(pos, len)`	O(len)	O(log n + len)
`replace`	O(n)	O(log n)
Concatenation	O(n)	O(log n) lazy
Memori overhead	Minimal	Signifikan (node tree)

Aplikasi #

Text editor: dokumen besar dengan banyak edit. Rope memungkinkan undo/redo efisien (simpan versi rope sebelum/sesudah).
Persistent string: rope bisa di-share antar versi (chunk direferensi, bukan di-copy). Konstruksi r2 = r1; r2.insert(pos, x); membagi sebagian besar chunk dengan r1.
DNA sequence manipulation: operasi splice, reverse, replace pada sekuens panjang (miliaran karakter).
Buffer besar: log processing dengan operasi insert/replace di tengah.
String hashing dengan lazy concat: hash chunk di-cache, recomputasi hanya pada modification.

Ringkasan #

Rope = B-tree dari chunk string kecil. Insert/erase/replace O(log n).
PBDS __gnu_cxx::rope<T> siap pakai.
Mendukung: push_back, substr, insert, erase, replace, operator+, operator[], c_str.
Trade-off: random access O(log n) vs std::string O(1). Insert/erase O(log n) vs std::string O(n).
Cocok untuk: string sangat panjang (> 10^5) dengan banyak edit di tengah.
Tidak cocok untuk: string pendek, akses random intensif, atau operasi append-only.