Rope
A rope is a tree structure for representing strings.
Ropes
A rope provides a tree based scalable way to represent and manipulation strings from small to huge. They provide the following characteristics:
- Immutable (kind of has to be anyway for BEAM)
- Common operations are effecient
- Common oeprations scale
- Should be able to handle alternate representations (ex: IO stream) - we'll see
A rope is build up of leaf and parent/concatenation nodes. Leaf nodes contain the chunks of binary strings that are concatenated or inserted into the rope. The parent/concatentation nodes are purely used to link the various leaf nodes together. The concatentation nodes contain basic tree information.
Ropes as strings
Although they can not be swapped in, this rope implementation supports the Kernel.Inspect and Binary.Chars protocols.
Ropes as enumerations
An implmentation of the Enumerable protocol has been provided to enumerate over the leaf nodes which contain the chunks of binary data. The parent/concat nodes are skipped.
Notes
Current implementation is mostly focused on operations that work well at larger scales. Performance should hopefully improve over time but don't expect a fully String module compatible API.
Links
Functions summary
- balanced?/1
- concat/2
- depth/1
- find/2
- find_all/2
- insert_at/3
- length/1
- new/1
- rebalance/1
- remove_at/3
- replace/4
- slice/3
- to_string/1
Functions
balanced?(rope)
Specs:
- balanced?(rope) :: bool
Checks if the rope is considered balanced based on comparing total length and depth verses the fibanocci sequence.
concat(list1, opts // [])
Specs:
Concatenates the list of ropes or strings together into a single new rope.
Accepts ropes or strings as arguments. Additionally you can override the
auto-rebalancing behavior with a rebalance: false option.
Examples
iex> Rope.concat(["Time is", " an illusion."]) |> Rope.to_string
"Time is an illusion."
iex> Rope.concat([Rope.new("terrible"), " ghastly", " silence"]) |> Rope.to_string
"terrible ghastly silence"
depth(rope)
Specs:
- depth(rope) :: non_neg_integer
Returns the depth of the rope tree. Only particularly of interest to the curious, or those wanting to calculate for themselves when to rebalance.
Concatenation nodes have a depth of 1 and leaf nodes have a depth of 0.
Examples
iex> Rope.depth(Rope.concat([Rope.new("terrible"), " ghastly silence"]))
1
iex> Rope.depth(Rope.concat([Rope.new("terrible"), " ghastly", " silence"]))
2
find(rope, term)
Specs:
Returns the index of the first match or -1 if no match was found.
Examples
iex> Rope.find(Rope.concat(["loathe it", " or ignore it,", " you can't like it"]), "it")
7
iex> Rope.find(Rope.concat(["loathe it", " or ignore it,", " you can't like it"]), "and")
-1
find_all(rope, term)
Specs:
Find all matches in the rope returning a list of indexes, or an empty list if no matches were found. The list is in order from first to last match.
Examples
iex> Rope.find_all(Rope.concat(["loathe it", " or ignore it,", " you can't like it"]), "it")
[7, 20, 39]
iex> Rope.find_all(Rope.concat(["loathe it", " or ignore it,", " you can't like it"]), "and")
[]
insert_at(rope, index, str)
Specs:
Produces a new rope with the string inserted at the index provided. This wraps around so negative indexes will start from the end.
Examples
iex> Rope.insert_at(Rope.concat(["infinite ", "number ", "monkeys"]), 16, "of ") |> Rope.to_string
"infinite number of monkeys"
iex> Rope.insert_at(Rope.concat(["infinite ", "number ", "monkeys"]), -7, "of ") |> Rope.to_string
"infinite number of monkeys"
length(rope)
Specs:
- length(rope) :: non_neg_integer
Retrieve the length in ut8 characters in the rope.
Examples
iex> Rope.length(Rope.concat([Rope.new("terrible"), " ghastly silence"]))
24
new(str)
Specs:
Creates a new rope with the string provided. Not needed since
concat/2 supports strings and ropes as arguments.
Examples
iex> Rope.new("Don't panic") |> Rope.to_string
"Don't panic"
rebalance(rope)
Specs:
Rebalance the rope explicitly to help keep insert, remove, etc efficient. This is a pretty greedy rebalancing and should produce a fully balanced rope.
remove_at(rope, index, len)
Specs:
Produces a new rope with the substr defined by the starting index and the length of characters removed. The advantage of this is it takes full advantage of ropes being optimized for index based operation.
Examples
iex> Rope.remove_at(Rope.concat(["infinite ", "number of ", "monkeys"]), 19, 3) |> Rope.to_string
"infinite number of keys"
iex> Rope.remove_at(Rope.concat(["infinite ", "number of ", "monkeys"]), -7, 3) |> Rope.to_string
"infinite number of keys"
replace(rope, pattern, replacement, opts // [])
Specs:
Replaces the first match with the replacement text and returns the new rope. If not found then the existing rope is returned. By default, it replaces all entries, except if the global option is set to false.
slice(rope, start, len)
Specs:
Returns a sub-rope starting at the offset given by the first, and a length given by the second. If the offset is greater than string length, than it returns nil.
Similar to String.slice/3, check the tests for some examples of usage.