stau.space
Rope data structure implementation in Hare.
1# Hare Rope Implementation.
2A Rope is a data structure that manages an ordered set of characters. Just like
3a string!
4
5You can read more about it on its [Wikipedia article.](https://en.wikipedia.org/wiki/Rope_(data_structure))
6
7Some of the key Big-O differences are the following:
8| Operation | Rope | String |
9| --- | --- | --- |
10| Index | O(log n) | **O(1)** |
11| Split | O(log n) | **O(1)** |
12| Concatenate | **O(1)** amort., **O(log n)** worst | O(n) |
13| Iterate over each character | *O(n)* | *O(n)* |
14| Insert | **O(log n)** | O(n) |
15| Append | **O(1)** amort., **O(log n)** worst | O(1) amort., O(n) worst |
16| Delete | **O(log n)** | O(n) |
17| Report | O(j + log n) | **O(j)** |
18| Build | *O(n)* | *O(n)* |
19
20*Table taken from [Comparison with monolithic arrays](https://en.wikipedia.org/wiki/Rope_(data_structure)#Comparison_with_monolithic_arrays)*