An implementation of the Rope data structure.
This is based on the original rope data structure paper, which you can find in the wayback machine. I also was watching the Swift Talk sessions on fold (see episodes 150 through 152), and used those concepts extensively.
You can create a Rope in a variety of ways:
var intRope = Rope([1, 2, 3])
let strRope: Rope<String> = ["Hello", "World", "!"]
let incrementedRope: Rope<Int> = intRope.map { $0 + 1 }
let reversedRope: Rope<String> = strRope.reversed()And interact and manipulate it like any other Collection:
intRope.append(4)
intRope.append(contentsOf: [5, 6, 7])
for element in intRope {
print(element)
}
let big = intRope.reduce(0, +)To retain decent performance, you may need to rebalance after a lot of manipulation, though:
var intRope = Rope([1, 2, 3])
intRope.append(4)
(4..<100).forEach { i in intRope.append(i) }
print(intRope.height) // --> 97
var balancedRope = intRope.balanced(minLeafSize: 5, maxLeafSize: 10)!
print(balancedRope.height) // --> 5