Module rope

Ropes are a high-level representation of text that offers much better performance than strings for common operations, and generally reduce memory allocations and copies, while only entailing a small degradation of less common operations.

More precisely, where a string is represented as a memory buffer, a rope is a tree structure whose leaves are slices of immutable strings. Therefore, concatenation, appending, prepending, substrings, etc. are operations that require only trivial tree manipulation, generally without having to copy memory. In addition, the tree structure of ropes makes them suitable as a form of index to speed-up access to Unicode characters by index in long chunks of text.

Type `rope`

type rope = node::root

The type of ropes.

Function `append_char`

fn append_char(rope: rope, char: char) -> rope

Add one char to the end of the rope

Performance note

this function executes in near-constant time

Function `append_rope`

fn append_rope(left: rope, right: rope) -> rope

Concatenate two ropes

Function `append_str`

fn append_str(rope: rope, str: @str) -> rope

Add one string to the end of the rope

Performance note

this function executes in near-linear time

Function `bal`

fn bal(rope: rope) -> rope

Balance a rope.

Return value

A copy of the rope in which small nodes have been grouped in memory, and with a reduced height.

If you perform numerous rope concatenations, it is generally a good idea to rebalance your rope at some point, before using it for other purposes.

Function `byte_len`

pure fn byte_len(rope: rope) -> uint

The number of bytes in the rope

Performance note

Constant time.

Function `char_at`

fn char_at(rope: rope, pos: uint) -> char

The character at position pos

Arguments

pos - A position in the rope

Safety notes

The function will fail if pos is not a valid position in the rope.

Performance note

This function executes in a time proportional to the height of the rope + the (bounded) length of the largest leaf.

Function `char_len`

pure fn char_len(rope: rope) -> uint

The number of character in the rope

Performance note

Constant time.

Function `cmp`

fn cmp(left: rope, right: rope) -> int

Compare two ropes by Unicode lexicographical order.

This function compares only the contents of the rope, not their structure.

Return value

A negative value if left < right, 0 if eq(left, right) or a positive value if left > right

Function `concat`

fn concat(v: ~[rope]) -> rope

Concatenate many ropes.

If the ropes are balanced initially and have the same height, the resulting rope remains balanced. However, this function does not take any further measure to ensure that the result is balanced.

Function `empty`

fn empty() -> rope

Create an empty rope

Function `eq`

fn eq(left: rope, right: rope) -> bool

Returns true if both ropes have the same content (regardless of their structure), false otherwise

Function `ge`

fn ge(left: rope, right: rope) -> bool

Arguments

left - an arbitrary rope
right - an arbitrary rope

Return value

true if left >= right in lexicographical order (regardless of their structure), false otherwise

Function `gt`

fn gt(left: rope, right: rope) -> bool

Arguments

left - an arbitrary rope
right - an arbitrary rope

Return value

true if left > right in lexicographical order (regardless of their structure), false otherwise

Function `height`

fn height(rope: rope) -> uint

Returns the height of the rope.

The height of the rope is a bound on the number of operations which must be performed during a character access before finding the leaf in which a character is contained.

Performance note

Constant time.

Function `iter_chars`

fn iter_chars(rope: rope, it: fn(char))

Loop through a rope, char by char, until the end.

Arguments

rope - A rope to traverse. It may be empty
it - A block to execute with each consecutive character of the rope.

Function `le`

fn le(left: rope, right: rope) -> bool

Arguments

left - an arbitrary rope
right - an arbitrary rope

Return value

true if left <= right in lexicographical order (regardless of their structure), false otherwise

Function `loop_chars`

fn loop_chars(rope: rope, it: fn(char) -> bool) -> bool

Loop through a rope, char by char

While other mechanisms are available, this is generally the best manner of looping through the contents of a rope char by char. If you prefer a loop that iterates through the contents string by string (e.g. to print the contents of the rope or output it to the system), however, you should rather use traverse_components.

Arguments

rope - A rope to traverse. It may be empty.
it - A block to execute with each consecutive character of the rope. Return true to continue, false to stop.

Return value

true If execution proceeded correctly, false if it was interrupted, that is if it returned false at any point.

Function `loop_leaves`

fn loop_leaves(rope: rope, it: fn(node::leaf) -> bool) -> bool

Loop through a rope, string by string

While other mechanisms are available, this is generally the best manner of looping through the contents of a rope string by string, which may be useful e.g. to print strings as you see them (without having to copy their contents into a new string), to send them to then network, to write them to a file, etc.. If you prefer a loop that iterates through the contents char by char (e.g. to search for a char), however, you should rather use traverse.

Arguments

rope - A rope to traverse. It may be empty
it - A block to execute with each consecutive string component of the rope. Return true to continue, false to stop

Return value

true If execution proceeded correctly, false if it was interrupted, that is if it returned false at any point.

Function `lt`

fn lt(left: rope, right: rope) -> bool

Arguments

left - an arbitrary rope
right - an arbitrary rope

Return value

true if left < right in lexicographical order (regardless of their structure), false otherwise

Function `of_str`

fn of_str(str: @str) -> rope

Adopt a string as a rope.

Arguments

str - A valid string.

Return value

A rope representing the same string as str. Depending of the length of str, this rope may be empty, flat or complex.

Performance notes

this operation does not copy the string;
the function runs in linear time.

Function `of_substr`

fn of_substr(str: @str, byte_offset: uint, byte_len: uint) -> rope

As of_str but for a substring.

Arguments

byte_offset - The offset of str at which the rope starts.
byte_len - The number of bytes of str to use.

Return value

A rope representing the same string as str::substr(str, byte_offset, byte_len). Depending on byte_len, this rope may be empty, flat or complex.

Performance note

This operation does not copy the substring.

Safety notes

this function does not check the validity of the substring;
this function fails if byte_offset or byte_len do not match str.

Function `prepend_char`

fn prepend_char(rope: rope, char: char) -> rope

Add one char to the beginning of the rope

Performance note

this function executes in near-constant time

Function `prepend_str`

fn prepend_str(rope: rope, str: @str) -> rope

Add one string to the beginning of the rope

Performance note

this function executes in near-linear time

Function `sub_bytes`

fn sub_bytes(rope: rope, byte_offset: uint, byte_len: uint) -> rope

Extract a subrope from a rope.

Performance note

on a balanced rope, this operation takes algorithmic time;
this operation does not involve any copying

Safety note

this function fails if byte_offset/byte_len do not represent valid positions in rope

Function `sub_chars`

fn sub_chars(rope: rope, char_offset: uint, char_len: uint) -> rope

Extract a subrope from a rope.

Performance note

on a balanced rope, this operation takes algorithmic time;
this operation does not involve any copying

Safety note

this function fails if char_offset/char_len do not represent valid positions in rope

Module rope

Type rope

Function append_char

Performance note

Function append_rope

Function append_str

Performance note

Function bal

Return value

Function byte_len

Performance note

Function char_at

Arguments

Safety notes

Performance note

Function char_len

Performance note

Function cmp

Return value

Function concat

Function empty

Function eq

Function ge

Arguments

Return value

Function gt

Arguments

Return value

Function height

Performance note

Function iter_chars

Arguments

Function le

Arguments

Return value

Function loop_chars

Arguments

Return value

Function loop_leaves

Arguments

Return value

Function lt

Arguments

Return value

Function of_str

Arguments

Return value

Performance notes

Function of_substr

Arguments

Return value

Performance note

Safety notes

Function prepend_char

Performance note

Function prepend_str

Performance note

Function sub_bytes

Performance note

Safety note

Function sub_chars

Performance note

Safety note

Type `rope`

Function `append_char`

Function `append_rope`

Function `append_str`

Function `bal`

Function `byte_len`

Function `char_at`

Function `char_len`

Function `cmp`

Function `concat`

Function `empty`

Function `eq`

Function `ge`

Function `gt`

Function `height`

Function `iter_chars`

Function `le`

Function `loop_chars`

Function `loop_leaves`

Function `lt`

Function `of_str`

Function `of_substr`

Function `prepend_char`

Function `prepend_str`

Function `sub_bytes`

Function `sub_chars`