ropex

v0.1.2

ropex v0.1.2 Rope View Source

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:

  1. Immutable (kind of has to be anyway for BEAM)
  2. Common operations are effecient
  3. Common oeprations scale
  4. 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.

  • http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf
  • https://en.wikipedia.org/wiki/Rope_(data_structure)

Link to this section Summary

Types

codepoint()
findctxt_t()
grapheme()
str()
t()

Functions

balanced?(rope)

Checks if the rope is considered balanced based on comparing total length and depth verses the fibanocci sequence

concat(arg1, opts \\ [])

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

depth(rope)

Returns the depth of the rope tree. Only particularly of interest to the curious, or those wanting to calculate for themselves when to rebalance

find(rope, term)

Returns the index of the first match or -1 if no match was found

find_all(rope, term)

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

insert_at(rope, index, str)

Produces a new rope with the string inserted at the index provided. This wraps around so negative indexes will start from the end

length(rope)

Retrieve the length in ut8 characters in the rope

new(str)

Creates a new rope with the string provided. Not needed since concat/2 supports strings and ropes as arguments

rebalance(rope)

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)

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

replace(rope, pattern, replacement, opts \\ [])

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(node, start, len)

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

to_string(rope)

Converts the entire rope to a single binary

Link to this section Types

Link to this type codepoint() View Source 
codepoint() :: str
Link to this type findctxt_t() View Source 
findctxt_t() :: {:findctxt, non_neg_integer, non_neg_integer}
Link to this type grapheme() View Source 
grapheme() :: str

Link to this section Functions

Link to this function balanced?(rope) View Source 
balanced?(t) :: boolean

Checks if the rope is considered balanced based on comparing total length and depth verses the fibanocci sequence.

Link to this function concat(arg1, opts \\ []) View Source 
concat([t | str], list) :: t

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"
Link to this function depth(rope) View Source 
depth(t) :: 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
Link to this function find(rope, term) View Source 
find(t, str) :: integer

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
Link to this function find_all(rope, term) View Source 
find_all(t, str) :: [non_neg_integer]

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")
[]
Link to this function insert_at(rope, index, str) View Source 
insert_at(t, integer, str) :: t

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"
Link to this function length(rope) View Source 
length(t) :: non_neg_integer

Retrieve the length in ut8 characters in the rope.

Examples 

iex> Rope.length(Rope.concat([Rope.new("terrible"), " ghastly silence"]))
24
Link to this function new(str) View Source 
new(str | nil) :: t

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"
Link to this function rebalance(rope) View Source 
rebalance(t) :: t

Rebalance the rope explicitly to help keep insert, remove, etc efficient. This is a pretty greedy rebalancing and should produce a fully balanced rope.

Link to this function remove_at(rope, index, len) View Source 
remove_at(t, integer, non_neg_integer) :: t

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"
Link to this function replace(rope, pattern, replacement, opts \\ []) View Source 
replace(t, str, str, list) :: t

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.

Link to this function slice(node, start, len) View Source 
slice(t, integer, integer) :: t

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.

Link to this function to_string(rope) View Source 
to_string(t) :: binary

Converts the entire rope to a single binary.