hint_max_leaf_char_len - The maximal number of chars that should be permitted in a single nodehint_max_node_height - The maximal height that should be permitted in a tree.Concat - A node obtained from the concatenation of two other nodesLeaf - A text component in a rope.NodeRoot - Implementation of type ropebal - Balance a node.byte_lenchar_at - # Argumentschar_lencmpconcat2flatten - Replace a subtree by a single leaf with the same contents.heightloop_charsloop_leaves - Loop through a node, leaf by leafof_str - Adopt a string as a node.of_substr - Adopt a slice of a string as a node.of_substr_unsafer - Adopt a slice of a string as a node.serialize_nodesub_bytes - Compute the subnode of a node.sub_chars - Compute the subnode of a node.tree_from_forest_destructive - Concatenate a forest of nodes into one tree.rope::node::char_iteratorrope::node::leaf_iteratorhint_max_leaf_char_lenuint
The maximal number of chars that should be permitted in a single node
This is not a strict value
hint_max_node_heightuint
The maximal height that should be permitted in a tree.
This is not a strict value
Concattype Concat = {left: @Node, right: @Node, char_len: uint, byte_len: uint, height: uint,}
A node obtained from the concatenation of two other nodes
byte_len - The number of bytes in the subrope.
Used to pre-allocate the correct amount of storage for serialization.
height - Height of the subrope.
Used for rebalancing and to allocate stacks for traversals.
Leaftype Leaf = {byte_offset: uint, byte_len: uint, char_len: uint, content: @~str,}
A text component in a rope.
This is actually a slice in a rope, so as to ensure maximal sharing.
contentcontent to usecontent - Contents of the leaf.
Note that we can have char_len < str::char_len(content), if this leaf is only a subset of the string. Also note that the string can be shared between several ropes, e.g. for indexing purposes.
NodeLeaf(Leaf) - A leaf consisting in a strConcat(Concat) - The concatenation of two ropesRootImplementation of type rope
Empty - An empty ropeContent(@Node) - A non-empty ropebalfn bal(node: @Node) -> Option<@Node>
Balance a node.
hint_max_node_height, do nothingoption::None if no transformation happenedoption::some(x) otherwise, in which case x has the same contents as node bot lower height and/or fragmentation.byte_lenfn byte_len(node: @Node) -> uint
char_atfn char_at(node: @Node, pos: uint) -> char
The character at position pos
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.
char_lenfn char_len(node: @Node) -> uint
cmpfn cmp(a: @Node, b: @Node) -> int
concat2fn concat2(left: @Node, right: @Node) -> @Node
flattenfn flatten(node: @Node) -> @Node
Replace a subtree by a single leaf with the same contents.
This function executes in linear time.
heightfn height(node: @Node) -> uint
loop_charsfn loop_chars(node: @Node, it: fn&(c: char) -> bool) -> bool
loop_leavesfn loop_leaves(node: @Node, it: fn&(Leaf) -> bool) -> bool
Loop through a node, leaf by leaf
true to continue, false to stoptrue If execution proceeded correctly, false if it was interrupted, that is if it returned false at any point.
of_strfn of_str(str: @~str) -> @Node
Adopt a string as a node.
If the string is longer than max_leaf_char_len, it is logically split between as many leaves as necessary. Regardless, the string itself is not copied.
Performance note: The complexity of this function is linear in the length of str.
of_substrfn of_substr(str: @~str, byte_start: uint, byte_len: uint) -> @Node
Adopt a slice of a string as a node.
If the slice is longer than max_leaf_char_len, it is logically split between as many leaves as necessary. Regardless, the string itself is not copied
str starts.str to use.Behavior is undefined if byte_start or byte_len do not represent valid positions in str
of_substr_unsaferfn of_substr_unsafer(str: @~str, byte_start: uint, byte_len: uint,
char_len: uint) -> @Node
Adopt a slice of a string as a node.
If the slice is longer than max_leaf_char_len, it is logically split between as many leaves as necessary. Regardless, the string itself is not copied
str starts.str to use.str in the interval [byte_start, byte_start+byte_len)byte_start or byte_len do not represent valid positions in strchar_len does not accurately represent the number of chars between byte_start and byte_start+byte_lenserialize_nodefn serialize_node(node: @Node) -> ~str
sub_bytesfn sub_bytes(node: @Node, byte_offset: uint, byte_len: uint) -> @Node
Compute the subnode of a node.
nodenodeThis function fails if byte_offset or byte_len do not represent valid positions in node.
sub_charsfn sub_chars(node: @Node, char_offset: uint, char_len: uint) -> @Node
Compute the subnode of a node.
nodenodeThis function fails if char_offset or char_len do not represent valid positions in node.
tree_from_forest_destructivefn tree_from_forest_destructive(forest: & [mut @Node]) -> @Node
Concatenate a forest of nodes into one tree.