stau.space
Rope data structure implementation in Hare.
Hare Rope Implementation.#
A Rope is a data structure that manages an ordered set of characters. Just like a string!
You can read more about it on its Wikipedia article.
Some of the key Big-O differences are the following:
| Operation | Rope | String |
|---|---|---|
| Index | O(log n) | O(1) |
| Split | O(log n) | O(1) |
| Concatenate | O(1) amort., O(log n) worst | O(n) |
| Iterate over each character | O(n) | O(n) |
| Insert | O(log n) | O(n) |
| Append | O(1) amort., O(log n) worst | O(1) amort., O(n) worst |
| Delete | O(log n) | O(n) |
| Report | O(j + log n) | O(j) |
| Build | O(n) | O(n) |
Table taken from Comparison with monolithic arrays