Rope (data structure)
Data structure for storing strings
- 18 min read
- 3 chapters
Related on Lably
Through Computer programming, Data structure and String (computer science)
Description
A rope is a type of binary tree where each leaf (end node) holds a string of manageable size and length (also known as a weight), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. A node with two children thus divides the whole string into two parts: the left subtree stores the first part of the string, the right subtree stores the second part of the string, and a node's weight is the length of the first part.
For rope operations, the strings stored in nodes are assumed to be constant immutable objects in the typical nondestructive case, allowing for some copy-on-write behavior. Leaf nodes are usually implemented as basic fixed-length strings with a reference count attached for deallocation when no longer needed, although other garbage collection methods can be used as well.
Sign in to keep reading
2 more chapters are free with a Lably account.
Operations
In the following definitions, N is the length of the rope, that is, the weight of the root node. These examples are defined in the Java programming language.
Collect leaves
- Definition: Create a stack S and a list L. Traverse down the left-most spine of the tree until reaching a leaf l', adding each node n to S. Add l' to L. The parent of l' (p) is at the top of the stack. Repeat the procedure for p's right subtree.
<span id="mwLg"></span><span class="kn" id="mwLw">package</span><span class="w" id="mwMA"> </span><span class="nn" id="mwMQ">org.wikipedia.example</span><span class="p" id="mwMg">;</span> <span class="kn" id="mwMw">import</span><span class="w" id="mwNA"> </span><span class="nn" id="mwNQ">java.util.ArrayDeque</span><span class="p" id="mwNg">;</span> <span class="kn" id="mwNw">import</span><span class="w" id="mwOA"> </span><span class="nn" id="mwOQ">java.util.Deque</span><span class="p" id="mwOg">;</span> <span class="kn" id="mwOw">import</span><span class="w" id="mwPA"> </span><span class="nn" id="mwPQ">java.util.Iterator</span><span class="p" id="mwPg">;</span> <span class="kn" id="mwPw">import</span><span class="w" id="mwQA"> </span><span class="nn" id="mwQQ">jakarta.annotation.NonNull</span><span class="p" id="mwQg">;</span> <span class="kd" id="mwQw">class</span> <span class="nc" id="mwRA">RopeLike</span><span class="w" id="mwRQ"> </span><span class="p" id="mwRg">{</span> <span class="w" id="mwRw"> </span><span class="kd" id="mwSA">private</span><span class="w" id="mwSQ"> </span><span class="n" id="mwSg">RopeLike</span><span class="w" id="mwSw"> </span><span class="n" id="mwTA">left</span><span class="p" id="mwTQ">;</span> <span class="w" id="mwTg"> </span><span class="kd" id="mwTw">private</span><span class="w" id="mwUA"> </span><span class="n" id="mwUQ">RopeLike</span><span class="w" id="mwUg"> </span><span class="n" id="mwUw">right</span><span class="p" id="mwVA">;</span> <span class="w" id="mwVQ"> </span><span class="kd" id="mwVg">public</span><span class="w" id="mwVw"> </span><span class="nf" id="mwWA">RopeLike</span><span class="p" id="mwWQ">(</span><span class="n" id="mwWg">RopeLike</span><span class="w" id="mwWw"> </span><span class="n" id="mwXA">left</span><span class="p" id="mwXQ">,</span><span class="w" id="mwXg"> </span><span class="n" id="mwXw">RopeLike</span><span class="w" id="mwYA"> </span><span class="n" id="mwYQ">right</span><span class="p" id="mwYg">)</span><span class="w" id="mwYw"> </span><span class="p" id="mwZA">{</span> <span class="w" id="mwZQ"> </span><span class="k" id="mwZg">this</span><span class="p" id="mwZw">.</span><span class="na" id="mwaA">left</span><span class="w" id="mwaQ"> </span><span class="o" id="mwag">=</span><span class="w" id="mwaw"> </span><span class="n" id="mwbA">left</span><span class="p" id="mwbQ">;</span> <span class="w" id="mwbg"> </span><span class="k" id="mwbw">this</span><span class="p" id="mwcA">.</span><span class="na" id="mwcQ">right</span><span class="w" id="mwcg"> </span><span class="o" id="mwcw">=</span><span class="w" id="mwdA"> </span><span class="n" id="mwdQ">right</span><span class="p" id="mwdg">;</span> <span class="w" id="mwdw"> </span><span class="p" id="mweA">}</span> <span class="w" id="mweQ"> </span><span class="kd" id="mweg">public</span><span class="w" id="mwew"> </span><span class="n" id="mwfA">RopeLike</span><span class="w" id="mwfQ"> </span><span class="nf" id="mwfg">getLeft</span><span class="p" id="mwfw">()</span><span class="w" id="mwgA"> </span><span class="p" id="mwgQ">{</span> <span class="w" id="mwgg"> </span><span class="k" id="mwgw">return</span><span class="w" id="mwhA"> </span><span class="n" id="mwhQ">left</span><span class="p" id="mwhg">;</span> <span class="w" id="mwhw"> </span><span class="p" id="mwiA">}</span> <span class="w" id="mwiQ"> </span><span class="kd" id="mwig">public</span><span class="w" id="mwiw"> </span><span class="n" id="mwjA">RopeLike</span><span class="w" id="mwjQ"> </span><span class="nf" id="mwjg">getRight</span><span class="p" id="mwjw">()</span><span class="w" id="mwkA"> </span><span class="p" id="mwkQ">{</span> <span class="w" id="mwkg"> </span><span class="k" id="mwkw">return</span><span class="w" id="mwlA"> </span><span class="n" id="mwlQ">right</span><span class="p" id="mwlg">;</span> <span class="w" id="mwlw"> </span><span class="p" id="mwmA">}</span> <span class="p" id="mwmQ">}</span> <span class="kd" id="mwmg">public</span><span class="w" id="mwmw"> </span><span class="kd" id="mwnA">final</span><span class="w" id="mwnQ"> </span><span class="kd" id="mwng">class</span> <span class="nc" id="mwnw">InOrderRopeIterator</span><span class="w" id="mwoA"> </span><span class="kd" id="mwoQ">implements</span><span class="w" id="mwog"> </span><span class="n" id="mwow">Iterator</span><span class="o" id="mwpA"><</span><span class="n" id="mwpQ">RopeLike</span><span class="o" id="mwpg">></span><span class="w" id="mwpw"> </span><span class="p" id="mwqA">{</span> <span class="w" id="mwqQ"> </span><span class="kd" id="mwqg">private</span><span class="w" id="mwqw"> </span><span class="kd" id="mwrA">final</span><span class="w" id="mwrQ"> </span><span class="n" id="mwrg">Deque</span><span class="o" id="mwrw"><</span><span class="n" id="mwsA">RopeLike</span><span class="o" id="mwsQ">></span><span class="w" id="mwsg"> </span><span class="n" id="mwsw">stack</span><span class="p" id="mwtA">;</span> <span class="w" id="mwtQ"> </span><span class="kd" id="mwtg">public</span><span class="w" id="mwtw"> </span><span class="nf" id="mwuA">InOrderRopeIterator</span><span class="p" id="mwuQ">(</span><span class="nd" id="mwug">@NonNull</span><span class="w" id="mwuw"> </span><span class="n" id="mwvA">RopeLike</span><span class="w" id="mwvQ"> </span><span class="n" id="mwvg">root</span><span class="p" id="mwvw">)</span><span class="w" id="mwwA"> </span><span class="p" id="mwwQ">{</span> <span class="w" id="mwwg"> </span><span class="n" id="mwww">stack</span><span class="w" id="mwxA"> </span><span class="o" id="mwxQ">=</span><span class="w" id="mwxg"> </span><span class="k" id="mwxw">new</span><span class="w" id="mwyA"> </span><span class="n" id="mwyQ">ArrayDeque</span><span class="o" id="mwyg"><></span><span class="p" id="mwyw">();</span> <span class="w" id="mwzA"> </span><span class="n" id="mwzQ">RopeLike</span><span class="w" id="mwzg"> </span><span class="n" id="mwzw">c</span><span class="w" id="mw0A"> </span><span class="o" id="mw0Q">=</span><span class="w" id="mw0g"> </span><span class="n" id="mw0w">root</span><span class="p" id="mw1A">;</span> <span class="w" id="mw1Q"> </span><span class="k" id="mw1g">while</span><span class="w" id="mw1w"> </span><span class="p" id="mw2A">(</span><span class="n" id="mw2Q">c</span><span class="w" id="mw2g"> </span><span class="o" id="mw2w">!=</span><span class="w" id="mw3A"> </span><span class="kc" id="mw3Q">null</span><span class="p" id="mw3g">)</span><span class="w" id="mw3w"> </span><span class="p" id="mw4A">{</span> <span class="w" id="mw4Q"> </span><span class="n" id="mw4g">stack</span><span class="p" id="mw4w">.</span><span class="na" id="mw5A">push</span><span class="p" id="mw5Q">(</span><span class="n" id="mw5g">c</span><span class="p" id="mw5w">);</span> <span class="w" id="mw6A"> </span><span class="n" id="mw6Q">c</span><span class="w" id="mw6g"> </span><span class="o" id="mw6w">=</span><span class="w" id="mw7A"> </span><span class="n" id="mw7Q">c</span><span class="p" id="mw7g">.</span><span class="na" id="mw7w">getLeft</span><span class="p" id="mw8A">();</span> <span class="w" id="mw8Q"> </span><span class="p" id="mw8g">}</span> <span class="w" id="mw8w"> </span><span class="p" id="mw9A">}</span> <span class="w" id="mw9Q"> </span><span class="nd" id="mw9g">@Override</span> <span class="w" id="mw9w"> </span><span class="kd" id="mw-A">public</span><span class="w" id="mw-Q"> </span><span class="kt" id="mw-g">boolean</span><span class="w" id="mw-w"> </span><span class="nf" id="mw_A">hasNext</span><span class="p" id="mw_Q">()</span><span class="w" id="mw_g"> </span><span class="p" id="mw_w">{</span> <span class="w" id="mwAQA"> </span><span class="k" id="mwAQE">return</span><span class="w" id="mwAQI"> </span><span class="n" id="mwAQM">stack</span><span class="p" id="mwAQQ">.</span><span class="na" id="mwAQU">size</span><span class="p" id="mwAQY">()</span><span class="w" id="mwAQc"> </span><span class="o" id="mwAQg">></span><span class="w" id="mwAQk"> </span><span class="mi" id="mwAQo">0</span><span class="p" id="mwAQs">;</span> <span class="w" id="mwAQw"> </span><span class="p" id="mwAQ0">}</span> <span class="w" id="mwAQ4"> </span><span class="nd" id="mwAQ8">@Override</span> <span class="w" id="mwARA"> </span><span class="kd" id="mwARE">public</span><span class="w" id="mwARI"> </span><span class="n" id="mwARM">RopeLike</span><span class="w" id="mwARQ"> </span><span class="nf" id="mwARU">next</span><span class="p" id="mwARY">()</span><span class="w" id="mwARc"> </span><span class="p" id="mwARg">{</span> <span class="w" id="mwARk"> </span><span class="n" id="mwARo">RopeLike</span><span class="w" id="mwARs"> </span><span class="n" id="mwARw">result</span><span class="w" id="mwAR0"> </span><span class="o" id="mwAR4">=</span><span class="w" id="mwAR8"> </span><span class="n" id="mwASA">stack</span><span class="p" id="mwASE">.</span><span class="na" id="mwASI">pop</span><span class="p" id="mwASM">();</span> <span class="w" id="mwASQ"> </span><span class="k" id="mwASU">if</span><span class="w" id="mwASY"> </span><span class="p" id="mwASc">(</span><span class="o" id="mwASg">!</span><span class="n" id="mwASk">stack</span><span class="p" id="mwASo">.</span><span class="na" id="mwASs">isEmpty</span><span class="p" id="mwASw">())</span><span class="w" id="mwAS0"> </span><span class="p" id="mwAS4">{</span> <span class="w" id="mwAS8"> </span><span class="n" id="mwATA">RopeLike</span><span class="w" id="mwATE"> </span><span class="n" id="mwATI">parent</span><span class="w" id="mwATM"> </span><span class="o" id="mwATQ">=</span><span class="w" id="mwATU"> </span><span class="n" id="mwATY">stack</span><span class="p" id="mwATc">.</span><span class="na" id="mwATg">pop</span><span class="p" id="mwATk">();</span> <span class="w" id="mwATo"> </span><span class="n" id="mwATs">RopeLike</span><span class="w" id="mwATw"> </span><span class="n" id="mwAT0">right</span><span class="w" id="mwAT4"> </span><span class="o" id="mwAT8">=</span><span class="w" id="mwAUA"> </span><span class="n" id="mwAUE">parent</span><span class="p" id="mwAUI">.</span><span class="na" id="mwAUM">getRight</span><span class="p" id="mwAUQ">();</span> <span class="w" id="mwAUU"> </span><span class="k" id="mwAUY">if</span><span class="w" id="mwAUc"> </span><span class="p" id="mwAUg">(</span><span class="n" id="mwAUk">right</span><span class="w" id="mwAUo"> </span><span class="o" id="mwAUs">!=</span><span class="w" id="mwAUw"> </span><span class="kc" id="mwAU0">null</span><span class="p" id="mwAU4">)</span><span class="w" id="mwAU8"> </span><span class="p" id="mwAVA">{</span> <span class="w" id="mwAVE"> </span><span class="n" id="mwAVI">stack</span><span class="p" id="mwAVM">.</span><span class="na" id="mwAVQ">push</span><span class="p" id="mwAVU">(</span><span class="n" id="mwAVY">right</span><span class="p" id="mwAVc">);</span> <span class="w" id="mwAVg"> </span><span class="n" id="mwAVk">RopeLike</span><span class="w" id="mwAVo"> </span><span class="n" id="mwAVs">cleft</span><span class="w" id="mwAVw"> </span><span class="o" id="mwAV0">=</span><span class="w" id="mwAV4"> </span><span class="n" id="mwAV8">right</span><span class="p" id="mwAWA">.</span><span class="na" id="mwAWE">getLeft</span><span class="p" id="mwAWI">();</span> <span class="w" id="mwAWM"> </span><span class="k" id="mwAWQ">while</span><span class="w" id="mwAWU"> </span><span class="p" id="mwAWY">(</span><span class="n" id="mwAWc">cleft</span><span class="w" id="mwAWg"> </span><span class="o" id="mwAWk">!=</span><span class="w" id="mwAWo"> </span><span class="kc" id="mwAWs">null</span><span class="p" id="mwAWw">)</span><span class="w" id="mwAW0"> </span><span class="p" id="mwAW4">{</span> <span class="w" id="mwAW8"> </span><span class="n" id="mwAXA">stack</span><span class="p" id="mwAXE">.</span><span class="na" id="mwAXI">push</span><span class="p" id="mwAXM">(</span><span class="n" id="mwAXQ">cleft</span><span class="p" id="mwAXU">);</span> <span class="w" id="mwAXY"> </span><span class="n" id="mwAXc">cleft</span><span class="w" id="mwAXg"> </span><span class="o" id="mwAXk">=</span><span class="w" id="mwAXo"> </span><span class="n" id="mwAXs">cleft</span><span class="p" id="mwAXw">.</span><span class="na" id="mwAX0">getLeft</span><span class="p" id="mwAX4">();</span> <span class="w" id="mwAX8"> </span><span class="p" id="mwAYA">}</span> <span class="w" id="mwAYE"> </span><span class="p" id="mwAYI">}</span> <span class="w" id="mwAYM"> </span><span class="p" id="mwAYQ">}</span> <span class="w" id="mwAYU"> </span><span class="k" id="mwAYY">return</span><span class="w" id="mwAYc"> </span><span class="n" id="mwAYg">result</span><span class="p" id="mwAYk">;</span> <span class="w" id="mwAYo"> </span><span class="p" id="mwAYs">}</span> <span class="p" id="mwAYw">}</span>Rebalance
- Definition: Collect the set of leaves L and rebuild the tree from the bottom-up.
<span id="mwAZQ"></span><span class="kn" id="mwAZU">import</span><span class="w" id="mwAZY"> </span><span class="nn" id="mwAZc">java.util.List</span><span class="p" id="mwAZg">;</span> <span class="kd" id="mwAZk">static</span><span class="w" id="mwAZo"> </span><span class="kt" id="mwAZs">boolean</span><span class="w" id="mwAZw"> </span><span class="nf" id="mwAZ0">isBalanced</span><span class="p" id="mwAZ4">(</span><span class="n" id="mwAZ8">RopeLike</span><span class="w" id="mwAaA"> </span><span class="n" id="mwAaE">r</span><span class="p" id="mwAaI">)</span><span class="w" id="mwAaM"> </span><span class="p" id="mwAaQ">{</span> <span class="w" id="mwAaU"> </span><span class="kt" id="mwAaY">int</span><span class="w" id="mwAac"> </span><span class="n" id="mwAag">depth</span><span class="w" id="mwAak"> </span><span class="o" id="mwAao">=</span><span class="w" id="mwAas"> </span><span class="n" id="mwAaw">r</span><span class="p" id="mwAa0">.</span><span class="na" id="mwAa4">depth</span><span class="p" id="mwAa8">();</span> <span class="w" id="mwAbA"> </span><span class="k" id="mwAbE">if</span><span class="w" id="mwAbI"> </span><span class="p" id="mwAbM">(</span><span class="n" id="mwAbQ">depth</span><span class="w" id="mwAbU"> </span><span class="o" id="mwAbY">>=</span><span class="w" id="mwAbc"> </span><span class="n" id="mwAbg">FIBONACCI_SEQUENCE</span><span class="p" id="mwAbk">.</span><span class="na" id="mwAbo">length</span><span class="w" id="mwAbs"> </span><span class="o" id="mwAbw">-</span><span class="w" id="mwAb0"> </span><span class="mi" id="mwAb4">2</span><span class="p" id="mwAb8">)</span><span class="w" id="mwAcA"> </span><span class="p" id="mwAcE">{</span> <span class="w" id="mwAcI"> </span><span class="k" id="mwAcM">return</span><span class="w" id="mwAcQ"> </span><span class="kc" id="mwAcU">false</span><span class="p" id="mwAcY">;</span> <span class="w" id="mwAcc"> </span><span class="p" id="mwAcg">}</span> <span class="w" id="mwAck"> </span><span class="k" id="mwAco">return</span><span class="w" id="mwAcs"> </span><span class="n" id="mwAcw">FIBONACCI_SEQUENCE</span><span class="o" id="mwAc0">[</span><span class="n" id="mwAc4">depth</span><span class="w" id="mwAc8"> </span><span class="o" id="mwAdA">+</span><span class="w" id="mwAdE"> </span><span class="mi" id="mwAdI">2</span><span class="o" id="mwAdM">]</span><span class="w" id="mwAdQ"> </span><span class="o" id="mwAdU"><=</span><span class="w" id="mwAdY"> </span><span class="n" id="mwAdc">r</span><span class="p" id="mwAdg">.</span><span class="na" id="mwAdk">weight</span><span class="p" id="mwAdo">();</span> <span class="p" id="mwAds">}</span> <span class="kd" id="mwAdw">static</span><span class="w" id="mwAd0"> </span><span class="n" id="mwAd4">RopeLike</span><span class="w" id="mwAd8"> </span><span class="nf" id="mwAeA">rebalance</span><span class="p" id="mwAeE">(</span><span class="n" id="mwAeI">RopeLike</span><span class="w" id="mwAeM"> </span><span class="n" id="mwAeQ">r</span><span class="p" id="mwAeU">)</span><span class="w" id="mwAeY"> </span><span class="p" id="mwAec">{</span> <span class="w" id="mwAeg"> </span><span class="k" id="mwAek">if</span><span class="w" id="mwAeo"> </span><span class="p" id="mwAes">(</span><span class="o" id="mwAew">!</span><span class="n" id="mwAe0">isBalanced</span><span class="p" id="mwAe4">(</span><span class="n" id="mwAe8">r</span><span class="p" id="mwAfA">))</span><span class="w" id="mwAfE"> </span><span class="p" id="mwAfI">{</span> <span class="w" id="mwAfM"> </span><span class="n" id="mwAfQ">List</span><span class="o" id="mwAfU"><</span><span class="n" id="mwAfY">RopeLike</span><span class="o" id="mwAfc">></span><span class="w" id="mwAfg"> </span><span class="n" id="mwAfk">leaves</span><span class="w" id="mwAfo"> </span><span class="o" id="mwAfs">=</span><span class="w" id="mwAfw"> </span><span class="n" id="mwAf0">Ropes</span><span class="p" id="mwAf4">.</span><span class="na" id="mwAf8">collectLeaves</span><span class="p" id="mwAgA">(</span><span class="n" id="mwAgE">r</span><span class="p" id="mwAgI">);</span> <span class="w" id="mwAgM"> </span><span class="k" id="mwAgQ">return</span><span class="w" id="mwAgU"> </span><span class="n" id="mwAgY">merge</span><span class="p" id="mwAgc">(</span><span class="n" id="mwAgg">leaves</span><span class="p" id="mwAgk">,</span><span class="w" id="mwAgo"> </span><span class="mi" id="mwAgs">0</span><span class="p" id="mwAgw">,</span><span class="w" id="mwAg0"> </span><span class="n" id="mwAg4">leaves</span><span class="p" id="mwAg8">.</span><span class="na" id="mwAhA">size</span><span class="p" id="mwAhE">());</span> <span class="w" id="mwAhI"> </span><span class="p" id="mwAhM">}</span> <span class="w" id="mwAhQ"> </span><span class="k" id="mwAhU">return</span><span class="w" id="mwAhY"> </span><span class="n" id="mwAhc">r</span><span class="p" id="mwAhg">;</span> <span class="p" id="mwAhk">}</span> <span class="kd" id="mwAho">static</span><span class="w" id="mwAhs"> </span><span class="n" id="mwAhw">RopeLike</span><span class="w" id="mwAh0"> </span><span class="nf" id="mwAh4">merge</span><span class="p" id="mwAh8">(</span><span class="n" id="mwAiA">List</span><span class="o" id="mwAiE"><</span><span class="n" id="mwAiI">RopeLike</span><span class="o" id="mwAiM">></span><span class="w" id="mwAiQ"> </span><span class="n" id="mwAiU">leaves</span><span class="p" id="mwAiY">)</span><span class="w" id="mwAic"> </span><span class="p" id="mwAig">{</span> <span class="w" id="mwAik"> </span><span class="k" id="mwAio">return</span><span class="w" id="mwAis"> </span><span class="n" id="mwAiw">merge</span><span class="p" id="mwAi0">(</span><span class="n" id="mwAi4">leaves</span><span class="p" id="mwAi8">,</span><span class="w" id="mwAjA"> </span><span class="mi" id="mwAjE">0</span><span class="p" id="mwAjI">,</span><span class="w" id="mwAjM"> </span><span class="n" id="mwAjQ">leaves</span><span class="p" id="mwAjU">.</span><span class="na" id="mwAjY">size</span><span class="p" id="mwAjc">());</span> <span class="p" id="mwAjg">}</span> <span class="kd" id="mwAjk">static</span><span class="w" id="mwAjo"> </span><span class="n" id="mwAjs">RopeLike</span><span class="w" id="mwAjw"> </span><span class="nf" id="mwAj0">merge</span><span class="p" id="mwAj4">(</span><span class="n" id="mwAj8">List</span><span class="o" id="mwAkA"><</span><span class="n" id="mwAkE">RopeLike</span><span class="o" id="mwAkI">></span><span class="w" id="mwAkM"> </span><span class="n" id="mwAkQ">leaves</span><span class="p" id="mwAkU">,</span><span class="w" id="mwAkY"> </span><span class="kt" id="mwAkc">int</span><span class="w" id="mwAkg"> </span><span class="n" id="mwAkk">start</span><span class="p" id="mwAko">,</span><span class="w" id="mwAks"> </span><span class="kt" id="mwAkw">int</span><span class="w" id="mwAk0"> </span><span class="n" id="mwAk4">end</span><span class="p" id="mwAk8">)</span><span class="w" id="mwAlA"> </span><span class="p" id="mwAlE">{</span> <span class="w" id="mwAlI"> </span><span class="kt" id="mwAlM">int</span><span class="w" id="mwAlQ"> </span><span class="n" id="mwAlU">range</span><span class="w" id="mwAlY"> </span><span class="o" id="mwAlc">=</span><span class="w" id="mwAlg"> </span><span class="n" id="mwAlk">end</span><span class="w" id="mwAlo"> </span><span class="o" id="mwAls">-</span><span class="w" id="mwAlw"> </span><span class="n" id="mwAl0">start</span><span class="p" id="mwAl4">;</span> <span class="w" id="mwAl8"> </span><span class="k" id="mwAmA">switch</span><span class="w" id="mwAmE"> </span><span class="p" id="mwAmI">(</span><span class="n" id="mwAmM">range</span><span class="p" id="mwAmQ">)</span><span class="w" id="mwAmU"> </span><span class="p" id="mwAmY">{</span> <span class="w" id="mwAmc"> </span><span class="k" id="mwAmg">case</span><span class="w" id="mwAmk"> </span><span class="mi" id="mwAmo">1</span><span class="p" id="mwAms">:</span> <span class="w" id="mwAmw"> </span><span class="k" id="mwAm0">return</span><span class="w" id="mwAm4"> </span><span class="n" id="mwAm8">leaves</span><span class="p" id="mwAnA">.</span><span class="na" id="mwAnE">get</span><span class="p" id="mwAnI">(</span><span class="n" id="mwAnM">start</span><span class="p" id="mwAnQ">);</span> <span class="w" id="mwAnU"> </span><span class="k" id="mwAnY">case</span><span class="w" id="mwAnc"> </span><span class="mi" id="mwAng">2</span><span class="p" id="mwAnk">:</span> <span class="w" id="mwAno"> </span><span class="k" id="mwAns">return</span><span class="w" id="mwAnw"> </span><span class="k" id="mwAn0">new</span><span class="w" id="mwAn4"> </span><span class="n" id="mwAn8">RopeLikeTree</span><span class="p" id="mwAoA">(</span><span class="n" id="mwAoE">leaves</span><span class="p" id="mwAoI">.</span><span class="na" id="mwAoM">get</span><span class="p" id="mwAoQ">(</span><span class="n" id="mwAoU">start</span><span class="p" id="mwAoY">),</span><span class="w" id="mwAoc"> </span><span class="n" id="mwAog">leaves</span><span class="p" id="mwAok">.</span><span class="na" id="mwAoo">get</span><span class="p" id="mwAos">(</span><span class="n" id="mwAow">start</span><span class="w" id="mwAo0"> </span><span class="o" id="mwAo4">+</span><span class="w" id="mwAo8"> </span><span class="mi" id="mwApA">1</span><span class="p" id="mwApE">));</span> <span class="w" id="mwApI"> </span><span class="k" id="mwApM">default</span><span class="p" id="mwApQ">:</span> <span class="w" id="mwApU"> </span><span class="kt" id="mwApY">int</span><span class="w" id="mwApc"> </span><span class="n" id="mwApg">mid</span><span class="w" id="mwApk"> </span><span class="o" id="mwApo">=</span><span class="w" id="mwAps"> </span><span class="n" id="mwApw">start</span><span class="w" id="mwAp0"> </span><span class="o" id="mwAp4">+</span><span class="w" id="mwAp8"> </span><span class="p" id="mwAqA">(</span><span class="n" id="mwAqE">range</span><span class="w" id="mwAqI"> </span><span class="o" id="mwAqM">/</span><span class="w" id="mwAqQ"> </span><span class="mi" id="mwAqU">2</span><span class="p" id="mwAqY">);</span> <span class="w" id="mwAqc"> </span><span class="k" id="mwAqg">return</span><span class="w" id="mwAqk"> </span><span class="k" id="mwAqo">new</span><span class="w" id="mwAqs"> </span><span class="n" id="mwAqw">RopeLikeTree</span><span class="p" id="mwAq0">(</span><span class="n" id="mwAq4">merge</span><span class="p" id="mwAq8">(</span><span class="n" id="mwArA">leaves</span><span class="p" id="mwArE">,</span><span class="w" id="mwArI"> </span><span class="n" id="mwArM">start</span><span class="p" id="mwArQ">,</span><span class="w" id="mwArU"> </span><span class="n" id="mwArY">mid</span><span class="p" id="mwArc">),</span><span class="w" id="mwArg"> </span><span class="n" id="mwArk">merge</span><span class="p" id="mwAro">(</span><span class="n" id="mwArs">leaves</span><span class="p" id="mwArw">,</span><span class="w" id="mwAr0"> </span><span class="n" id="mwAr4">mid</span><span class="p" id="mwAr8">,</span><span class="w" id="mwAsA"> </span><span class="n" id="mwAsE">end</span><span class="p" id="mwAsI">));</span> <span class="w" id="mwAsM"> </span><span class="p" id="mwAsQ">}</span> <span class="p" id="mwAsU">}</span>Insert
- Definition:
Insert(i, S’): insert the string S’ beginning at position i in the string s, to form a new string C1, ..., Ci, S', Ci + 1, ..., Cm. - Time complexity: .
This operation can be done by a Split() and two Concat() operations. The cost is the sum of the three.
<span id="mwAtc"></span><span class="kn" id="mwAtg">import</span><span class="w" id="mwAtk"> </span><span class="nn" id="mwAto">javafx.util.Pair</span><span class="p" id="mwAts">;</span> <span class="kd" id="mwAtw">public</span><span class="w" id="mwAt0"> </span><span class="n" id="mwAt4">Rope</span><span class="w" id="mwAt8"> </span><span class="nf" id="mwAuA">insert</span><span class="p" id="mwAuE">(</span><span class="kt" id="mwAuI">int</span><span class="w" id="mwAuM"> </span><span class="n" id="mwAuQ">idx</span><span class="p" id="mwAuU">,</span><span class="w" id="mwAuY"> </span><span class="n" id="mwAuc">CharSequence</span><span class="w" id="mwAug"> </span><span class="n" id="mwAuk">sequence</span><span class="p" id="mwAuo">)</span><span class="w" id="mwAus"> </span><span class="p" id="mwAuw">{</span> <span class="w" id="mwAu0"> </span><span class="k" id="mwAu4">if</span><span class="w" id="mwAu8"> </span><span class="p" id="mwAvA">(</span><span class="n" id="mwAvE">idx</span><span class="w" id="mwAvI"> </span><span class="o" id="mwAvM">==</span><span class="w" id="mwAvQ"> </span><span class="mi" id="mwAvU">0</span><span class="p" id="mwAvY">)</span><span class="w" id="mwAvc"> </span><span class="p" id="mwAvg">{</span> <span class="w" id="mwAvk"> </span><span class="k" id="mwAvo">return</span><span class="w" id="mwAvs"> </span><span class="n" id="mwAvw">prepend</span><span class="p" id="mwAv0">(</span><span class="n" id="mwAv4">sequence</span><span class="p" id="mwAv8">);</span> <span class="w" id="mwAwA"> </span><span class="p" id="mwAwE">}</span><span class="w" id="mwAwI"> </span><span class="k" id="mwAwM">else</span><span class="w" id="mwAwQ"> </span><span class="k" id="mwAwU">if</span><span class="w" id="mwAwY"> </span><span class="p" id="mwAwc">(</span><span class="n" id="mwAwg">idx</span><span class="w" id="mwAwk"> </span><span class="o" id="mwAwo">==</span><span class="w" id="mwAws"> </span><span class="n" id="mwAww">length</span><span class="p" id="mwAw0">())</span><span class="w" id="mwAw4"> </span><span class="p" id="mwAw8">{</span> <span class="w" id="mwAxA"> </span><span class="k" id="mwAxE">return</span><span class="w" id="mwAxI"> </span><span class="n" id="mwAxM">append</span><span class="p" id="mwAxQ">(</span><span class="n" id="mwAxU">sequence</span><span class="p" id="mwAxY">);</span> <span class="w" id="mwAxc"> </span><span class="p" id="mwAxg">}</span><span class="w" id="mwAxk"> </span><span class="k" id="mwAxo">else</span><span class="w" id="mwAxs"> </span><span class="p" id="mwAxw">{</span> <span class="w" id="mwAx0"> </span><span class="n" id="mwAx4">Pair</span><span class="o" id="mwAx8"><</span><span class="n" id="mwAyA">RopeLike</span><span class="p" id="mwAyE">,</span><span class="w" id="mwAyI"> </span><span class="n" id="mwAyM">RopeLike</span><span class="o" id="mwAyQ">></span><span class="w" id="mwAyU"> </span><span class="n" id="mwAyY">lhs</span><span class="w" id="mwAyc"> </span><span class="o" id="mwAyg">=</span><span class="w" id="mwAyk"> </span><span class="n" id="mwAyo">base</span><span class="p" id="mwAys">.</span><span class="na" id="mwAyw">split</span><span class="p" id="mwAy0">(</span><span class="n" id="mwAy4">idx</span><span class="p" id="mwAy8">);</span> <span class="w" id="mwAzA"> </span><span class="k" id="mwAzE">return</span><span class="w" id="mwAzI"> </span><span class="k" id="mwAzM">new</span><span class="w" id="mwAzQ"> </span><span class="n" id="mwAzU">Rope</span><span class="p" id="mwAzY">(</span><span class="n" id="mwAzc">Ropes</span><span class="p" id="mwAzg">.</span><span class="na" id="mwAzk">concat</span><span class="p" id="mwAzo">(</span><span class="n" id="mwAzs">lhs</span><span class="p" id="mwAzw">.</span><span class="na" id="mwAz0">getKey</span><span class="p" id="mwAz4">().</span><span class="na" id="mwAz8">append</span><span class="p" id="mwA0A">(</span><span class="n" id="mwA0E">sequence</span><span class="p" id="mwA0I">),</span><span class="w" id="mwA0M"> </span><span class="n" id="mwA0Q">lhs</span><span class="p" id="mwA0U">.</span><span class="na" id="mwA0Y">getValue</span><span class="p" id="mwA0c">()));</span> <span class="w" id="mwA0g"> </span><span class="p" id="mwA0k">}</span> <span class="p" id="mwA0o">}</span>Index
- Definition:
Index(i): return the character at position i - Time complexity:
To retrieve the i-th character, we begin a recursive search from the root node:
<span id="mwA10"></span><span class="nd" id="mwA14">@Override</span> <span class="kd" id="mwA18">public</span><span class="w" id="mwA2A"> </span><span class="kt" id="mwA2E">int</span><span class="w" id="mwA2I"> </span><span class="nf" id="mwA2M">indexOf</span><span class="p" id="mwA2Q">(</span><span class="kt" id="mwA2U">char</span><span class="w" id="mwA2Y"> </span><span class="n" id="mwA2c">ch</span><span class="p" id="mwA2g">,</span><span class="w" id="mwA2k"> </span><span class="kt" id="mwA2o">int</span><span class="w" id="mwA2s"> </span><span class="n" id="mwA2w">startIndex</span><span class="p" id="mwA20">)</span><span class="w" id="mwA24"> </span><span class="p" id="mwA28">{</span> <span class="w" id="mwA3A"> </span><span class="k" id="mwA3E">if</span><span class="w" id="mwA3I"> </span><span class="p" id="mwA3M">(</span><span class="n" id="mwA3Q">startIndex</span><span class="w" id="mwA3U"> </span><span class="o" id="mwA3Y">></span><span class="w" id="mwA3c"> </span><span class="n" id="mwA3g">weight</span><span class="p" id="mwA3k">)</span><span class="w" id="mwA3o"> </span><span class="p" id="mwA3s">{</span> <span class="w" id="mwA3w"> </span><span class="k" id="mwA30">return</span><span class="w" id="mwA34"> </span><span class="n" id="mwA38">right</span><span class="p" id="mwA4A">.</span><span class="na" id="mwA4E">indexOf</span><span class="p" id="mwA4I">(</span><span class="n" id="mwA4M">ch</span><span class="p" id="mwA4Q">,</span><span class="w" id="mwA4U"> </span><span class="n" id="mwA4Y">startIndex</span><span class="w" id="mwA4c"> </span><span class="o" id="mwA4g">-</span><span class="w" id="mwA4k"> </span><span class="n" id="mwA4o">weight</span><span class="p" id="mwA4s">);</span> <span class="w" id="mwA4w"> </span><span class="p" id="mwA40">}</span><span class="w" id="mwA44"> </span><span class="k" id="mwA48">else</span><span class="w" id="mwA5A"> </span><span class="p" id="mwA5E">{</span> <span class="w" id="mwA5I"> </span><span class="k" id="mwA5M">return</span><span class="w" id="mwA5Q"> </span><span class="n" id="mwA5U">left</span><span class="p" id="mwA5Y">.</span><span class="na" id="mwA5c">indexOf</span><span class="p" id="mwA5g">(</span><span class="n" id="mwA5k">ch</span><span class="p" id="mwA5o">,</span><span class="w" id="mwA5s"> </span><span class="n" id="mwA5w">startIndex</span><span class="p" id="mwA50">);</span> <span class="w" id="mwA54"> </span><span class="p" id="mwA58">}</span> <span class="p" id="mwA6A">}</span>For example, to find the character at i=10 in Figure 2.1 shown on the right, start at the root node (A), find that 22 is greater than 10 and there is a left child, so go to the left child (B). 9 is less than 10, so subtract 9 from 10 (leaving i=1) and go to the right child (D). Then because 6 is greater than 1 and there's a left child, go to the left child (G). 2 is greater than 1 and there's a left child, so go to the left child again (J). Finally 2 is greater than 1 but there is no left child, so the character at index 1 of the short string "na" (ie "n") is the answer. (1-based index)
Concat
- Definition:
Concat(S1, S2): concatenate two ropes, S1 and S2, into a single rope. - Time complexity: (or time to compute the root weight)
A concatenation can be performed simply by creating a new root node with left = S1 and right = S2, which is constant time. The weight of the parent node is set to the length of the left child S1, which would take time, if the tree is balanced.
As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation.
Split
- Definition:
Split (i, S): split the string S into two new strings S1 and S2, S1 = C1, ..., Ci and S2 = Ci + 1, ..., Cm. - Time complexity:
There are two cases that must be dealt with:
- The split point is at the end of a string (i.e. after the last character of a leaf node)
- The split point is in the middle of a string.
The second case reduces to the first by splitting the string at the split point to create two new leaf nodes, then creating a new node that is the parent of the two component strings.
For example, to split the 22-character rope pictured in Figure 2.3 into two equal component ropes of length 11, query the 12th character to locate the node K at the bottom level. Remove the link between K and G. Go to the parent of G and subtract the weight of K from the weight of D. Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight of K from their parent nodes (only node D and A, in this case). Finally, build up the newly orphaned nodes K and H by concatenating them and creating a new parent P with weight equal to the length of the left node K.
As most rope operations require balanced trees, the tree may need to be re-balanced after splitting.
<span id="mwA-c"></span><span class="kn" id="mwA-g">import</span><span class="w" id="mwA-k"> </span><span class="nn" id="mwA-o">javafx.util.Pair</span><span class="p" id="mwA-s">;</span> <span class="kd" id="mwA-w">public</span><span class="w" id="mwA-0"> </span><span class="n" id="mwA-4">Pair</span><span class="o" id="mwA-8"><</span><span class="n" id="mwA_A">RopeLike</span><span class="p" id="mwA_E">,</span><span class="w" id="mwA_I"> </span><span class="n" id="mwA_M">RopeLike</span><span class="o" id="mwA_Q">></span><span class="w" id="mwA_U"> </span><span class="nf" id="mwA_Y">split</span><span class="p" id="mwA_c">(</span><span class="kt" id="mwA_g">int</span><span class="w" id="mwA_k"> </span><span class="n" id="mwA_o">index</span><span class="p" id="mwA_s">)</span><span class="w" id="mwA_w"> </span><span class="p" id="mwA_0">{</span> <span class="w" id="mwA_4"> </span><span class="k" id="mwA_8">if</span><span class="w" id="mwBAA"> </span><span class="p" id="mwBAE">(</span><span class="n" id="mwBAI">index</span><span class="w" id="mwBAM"> </span><span class="o" id="mwBAQ"><</span><span class="w" id="mwBAU"> </span><span class="n" id="mwBAY">weight</span><span class="p" id="mwBAc">)</span><span class="w" id="mwBAg"> </span><span class="p" id="mwBAk">{</span> <span class="w" id="mwBAo"> </span><span class="n" id="mwBAs">Pair</span><span class="o" id="mwBAw"><</span><span class="n" id="mwBA0">RopeLike</span><span class="p" id="mwBA4">,</span><span class="w" id="mwBA8"> </span><span class="n" id="mwBBA">RopeLike</span><span class="o" id="mwBBE">></span><span class="w" id="mwBBI"> </span><span class="n" id="mwBBM">split</span><span class="w" id="mwBBQ"> </span><span class="o" id="mwBBU">=</span><span class="w" id="mwBBY"> </span><span class="n" id="mwBBc">left</span><span class="p" id="mwBBg">.</span><span class="na" id="mwBBk">split</span><span class="p" id="mwBBo">(</span><span class="n" id="mwBBs">index</span><span class="p" id="mwBBw">);</span> <span class="w" id="mwBB0"> </span><span class="k" id="mwBB4">return</span><span class="w" id="mwBB8"> </span><span class="n" id="mwBCA">Pair</span><span class="p" id="mwBCE">.</span><span class="na" id="mwBCI">of</span><span class="p" id="mwBCM">(</span><span class="n" id="mwBCQ">rebalance</span><span class="p" id="mwBCU">(</span><span class="n" id="mwBCY">split</span><span class="p" id="mwBCc">.</span><span class="na" id="mwBCg">getKey</span><span class="p" id="mwBCk">()),</span><span class="w" id="mwBCo"> </span><span class="n" id="mwBCs">rebalance</span><span class="p" id="mwBCw">(</span><span class="k" id="mwBC0">new</span><span class="w" id="mwBC4"> </span><span class="n" id="mwBC8">RopeLikeTree</span><span class="p" id="mwBDA">(</span><span class="n" id="mwBDE">split</span><span class="p" id="mwBDI">.</span><span class="na" id="mwBDM">getValue</span><span class="p" id="mwBDQ">(),</span><span class="w" id="mwBDU"> </span><span class="n" id="mwBDY">right</span><span class="p" id="mwBDc">)));</span> <span class="w" id="mwBDg"> </span><span class="p" id="mwBDk">}</span><span class="w" id="mwBDo"> </span><span class="k" id="mwBDs">else</span><span class="w" id="mwBDw"> </span><span class="k" id="mwBD0">if</span><span class="w" id="mwBD4"> </span><span class="p" id="mwBD8">(</span><span class="n" id="mwBEA">index</span><span class="w" id="mwBEE"> </span><span class="o" id="mwBEI">></span><span class="w" id="mwBEM"> </span><span class="n" id="mwBEQ">weight</span><span class="p" id="mwBEU">)</span><span class="w" id="mwBEY"> </span><span class="p" id="mwBEc">{</span> <span class="w" id="mwBEg"> </span><span class="n" id="mwBEk">Pair</span><span class="o" id="mwBEo"><</span><span class="n" id="mwBEs">RopeLike</span><span class="p" id="mwBEw">,</span><span class="w" id="mwBE0"> </span><span class="n" id="mwBE4">RopeLike</span><span class="o" id="mwBE8">></span><span class="w" id="mwBFA"> </span><span class="n" id="mwBFE">split</span><span class="w" id="mwBFI"> </span><span class="o" id="mwBFM">=</span><span class="w" id="mwBFQ"> </span><span class="n" id="mwBFU">right</span><span class="p" id="mwBFY">.</span><span class="na" id="mwBFc">split</span><span class="p" id="mwBFg">(</span><span class="n" id="mwBFk">index</span><span class="w" id="mwBFo"> </span><span class="o" id="mwBFs">-</span><span class="w" id="mwBFw"> </span><span class="n" id="mwBF0">weight</span><span class="p" id="mwBF4">);</span> <span class="w" id="mwBF8"> </span><span class="k" id="mwBGA">return</span><span class="w" id="mwBGE"> </span><span class="n" id="mwBGI">Pair</span><span class="p" id="mwBGM">.</span><span class="na" id="mwBGQ">of</span><span class="p" id="mwBGU">(</span><span class="n" id="mwBGY">rebalance</span><span class="p" id="mwBGc">(</span><span class="k" id="mwBGg">new</span><span class="w" id="mwBGk"> </span><span class="n" id="mwBGo">RopeLikeTree</span><span class="p" id="mwBGs">(</span><span class="n" id="mwBGw">left</span><span class="p" id="mwBG0">,</span><span class="w" id="mwBG4"> </span><span class="n" id="mwBG8">split</span><span class="p" id="mwBHA">.</span><span class="na" id="mwBHE">getKey</span><span class="p" id="mwBHI">())),</span><span class="w" id="mwBHM"> </span><span class="n" id="mwBHQ">rebalance</span><span class="p" id="mwBHU">(</span><span class="n" id="mwBHY">split</span><span class="p" id="mwBHc">.</span><span class="na" id="mwBHg">getValue</span><span class="p" id="mwBHk">()));</span> <span class="w" id="mwBHo"> </span><span class="p" id="mwBHs">}</span><span class="w" id="mwBHw"> </span><span class="k" id="mwBH0">else</span><span class="w" id="mwBH4"> </span><span class="p" id="mwBH8">{</span> <span class="w" id="mwBIA"> </span><span class="k" id="mwBIE">return</span><span class="w" id="mwBII"> </span><span class="n" id="mwBIM">Pair</span><span class="p" id="mwBIQ">.</span><span class="na" id="mwBIU">of</span><span class="p" id="mwBIY">(</span><span class="n" id="mwBIc">left</span><span class="p" id="mwBIg">,</span><span class="w" id="mwBIk"> </span><span class="n" id="mwBIo">right</span><span class="p" id="mwBIs">);</span> <span class="w" id="mwBIw"> </span><span class="p" id="mwBI0">}</span> <span class="p" id="mwBI4">}</span>Remove
- Definition:
Remove(i, j): remove the substring Ci, …, Ci + j − 1, from s to form a new string C1, …, Ci − 1, Ci + j, …, Cm. - Time complexity: .
This operation can be done by two Split() and one Concat() operation. First, split the rope in three, divided by i-th and i+j-th character respectively, which extracts the string to remove in a separate node. Then concatenate the other two nodes.
<span id="mwBKE"></span><span class="kn" id="mwBKI">import</span><span class="w" id="mwBKM"> </span><span class="nn" id="mwBKQ">javafx.util.Pair</span><span class="p" id="mwBKU">;</span> <span class="nd" id="mwBKY">@Override</span> <span class="kd" id="mwBKc">public</span><span class="w" id="mwBKg"> </span><span class="n" id="mwBKk">RopeLike</span><span class="w" id="mwBKo"> </span><span class="nf" id="mwBKs">remove</span><span class="p" id="mwBKw">(</span><span class="kt" id="mwBK0">int</span><span class="w" id="mwBK4"> </span><span class="n" id="mwBK8">start</span><span class="p" id="mwBLA">,</span><span class="w" id="mwBLE"> </span><span class="kt" id="mwBLI">int</span><span class="w" id="mwBLM"> </span><span class="n" id="mwBLQ">length</span><span class="p" id="mwBLU">)</span><span class="w" id="mwBLY"> </span><span class="p" id="mwBLc">{</span> <span class="w" id="mwBLg"> </span><span class="n" id="mwBLk">Pair</span><span class="o" id="mwBLo"><</span><span class="n" id="mwBLs">RopeLike</span><span class="p" id="mwBLw">,</span><span class="w" id="mwBL0"> </span><span class="n" id="mwBL4">RopeLike</span><span class="o" id="mwBL8">></span><span class="w" id="mwBMA"> </span><span class="n" id="mwBME">lhs</span><span class="w" id="mwBMI"> </span><span class="o" id="mwBMM">=</span><span class="w" id="mwBMQ"> </span><span class="n" id="mwBMU">split</span><span class="p" id="mwBMY">(</span><span class="n" id="mwBMc">start</span><span class="p" id="mwBMg">);</span> <span class="w" id="mwBMk"> </span><span class="n" id="mwBMo">Pair</span><span class="o" id="mwBMs"><</span><span class="n" id="mwBMw">RopeLike</span><span class="p" id="mwBM0">,</span><span class="w" id="mwBM4"> </span><span class="n" id="mwBM8">RopeLike</span><span class="o" id="mwBNA">></span><span class="w" id="mwBNE"> </span><span class="n" id="mwBNI">rhs</span><span class="w" id="mwBNM"> </span><span class="o" id="mwBNQ">=</span><span class="w" id="mwBNU"> </span><span class="n" id="mwBNY">split</span><span class="p" id="mwBNc">(</span><span class="n" id="mwBNg">start</span><span class="w" id="mwBNk"> </span><span class="o" id="mwBNo">+</span><span class="w" id="mwBNs"> </span><span class="n" id="mwBNw">length</span><span class="p" id="mwBN0">);</span> <span class="w" id="mwBN4"> </span><span class="k" id="mwBN8">return</span><span class="w" id="mwBOA"> </span><span class="n" id="mwBOE">rebalance</span><span class="p" id="mwBOI">(</span><span class="k" id="mwBOM">new</span><span class="w" id="mwBOQ"> </span><span class="n" id="mwBOU">RopeLikeTree</span><span class="p" id="mwBOY">(</span><span class="n" id="mwBOc">lhs</span><span class="p" id="mwBOg">.</span><span class="na" id="mwBOk">getKey</span><span class="p" id="mwBOo">(),</span><span class="w" id="mwBOs"> </span><span class="n" id="mwBOw">rhs</span><span class="p" id="mwBO0">.</span><span class="na" id="mwBO4">getValue</span><span class="p" id="mwBO8">()));</span> <span class="p" id="mwBPA">}</span>Report
- Definition:
Report(i, j): output the string Ci, …, Ci + j − 1. - Time complexity:
To report the string Ci, …, Ci + j − 1, find the node u that contains Ci and weight(u) >= j, and then traverse T starting at node u. Output Ci, …, Ci + j − 1 by doing an in-order traversal of T starting at node u.
Comparison with monolithic arrays
Advantages:
- Ropes enable much faster insertion and deletion of text than monolithic string arrays, on which operations have time complexity O(n).
- Ropes do not require O(n) extra memory when operated upon (which arrays need for copying operations).
- Ropes do not require large contiguous memory spaces.
- If only nondestructive versions of operations are used, rope is a persistent data structure. For the text editing program example, this leads to an easy support for multiple undo levels.
Disadvantages:
- Greater overall space use when not being operated on, mainly to store parent nodes. There is a trade-off between how much of the total memory is such overhead and how long pieces of data are being processed as strings. The strings in example figures above are unrealistically short for modern architectures. The overhead is always O(n), but the constant can be made arbitrarily small.
- Increase in time to manage the extra storage
- Increased complexity of source code; greater risk of bugs
This table compares the algorithmic traits of string and rope implementations, not their raw speed. Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n). In summary, ropes are preferable when the data is large and modified often.