You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
Sean Copenhaver 5da9cafd26 Merge pull request #2 from ijcd/master 7 years ago
config Update for Elixir 1.5.1 7 years ago
lib Update for Elixir 1.5.1 7 years ago
test Update for Elixir 1.5.1 7 years ago
.gitignore Update for Elixir 1.5.1 7 years ago
LICENSE.txt oops forgot to update license info 11 years ago
Makefile swapped in the parallel find_all for the default implementation 11 years ago
README.md updating image text 11 years ago
mix.exs Update for Elixir 1.5.1 7 years ago
mix.lock Update for Elixir 1.5.1 7 years ago
ttb_last_config Update for Elixir 1.5.1 7 years ago

README.md

Rope

Implemention of a rope data structure in Elixir. It provides faster index based operations, especially at scale, then plain binary based strings. One of the basic building block of this is the slice/3 operation which is roughly 3x faster at 2kb of text and up to 50x faster at 880kb of text. The other is concat/2 operation which runs in constant time but as it stands so does the BEAM (how about that). concat/2 does suffer roughly double the overhead of the <> operator on plain binary based strings. The combination of slice/3 and concat/2 allows efficient insert_at/3 and remove_at/3.

So what does this look like?

The following images where genereated with GraphViz. The green oval represent the variables who point to a rope. The squares represent the internal record data structure for the rope. 'concat' nodes are purely for connecting the leaves together, while the leaves actually contain the text.

Straight concatenation with an auto-rebalance triggered part way:

Worst case

The same rope explicitly rebalanced for better slice based operations:

Worst case rebalanced

Also existing leafs should be reused in new ropes. The operations performed where creating a new rope (original), inserting 'hello world' (insert), a subrope sliced out (slice), then concatenated back in (concat), then finally a series of concatenations (multiconcat).

Rope with manipulations

That same rope rebalanced:

Rope with manipulations rebalanced