Trait Ramify 

pub trait Ramify<V> {
    // Required methods
    fn ramify(&mut self, vtx: V) -> impl IntoIterator<Item = V>;
    fn sort_key(&self, vtx: &V) -> impl Ord;
    fn marker(&self, vtx: &V) -> char;

    // Provided methods
    fn annotate(&self, vtx: &V, buf: &mut String) { ... }
    fn is_identical(&self, vtx: &V, other: &V) -> bool { ... }
}

A trait representing hierarchical data structures with efficient iteration of children.

For a version of this trait in which iteration of children might fail, see TryRamify.

This trait includes provided methods and default methods.

Also see the Generator documentation for more information, particularly concerning the sequence of method calls and resource mangement.

Required Methods

fn ramify(&mut self, vtx: V) -> impl IntoIterator<Item = V>

Iterate over the children of the vertex.

This method is called exactly once for each vertex immediately before writing the corresponding branch diagram row.

Iteration order

The iteration order is used to determine the horizontal order in which the vertices are drawn in the tree. This need not correspond to the precise column in which the node is actually drawn.

The below diagram shows the impact of various orders on how the nodes are laid out, for a node with key 0, which has children with keys 1 2 3 iterated in various orders.

123  132  213  231  312  321

0    0    0    0    0    0
├╮   ├╮   ├┬╮  ├╮   ├┬╮  ├╮
1│   1│   │1│  │1   │1│  │1
╭┤   ╭┤   2╭╯  ├╮   │ 2  ├╮
2│   │2    3   2│   3    │2
 3   3          3        3

Iterating in sorted order (either increasing or decreasing) or otherwise guaranteeing that the minimal element is first or last tends to produce narrower trees since this avoids 3-way forks.

fn sort_key(&self, vtx: &V) -> impl Ord

Get the sort key associated with a vertex.

This key is used for the vertical render order; that is, to decide which vertex should be rendered next. This is different than the iteration order of the children. See the documentation for Ramify::ramify to compare.

The active vertices are passed to Iterator::min_by_key when deciding which vertex should be rendered next on each iteration. In particular, the first element is returned if several elements are equally minimal.

The key is used ephemerally for sorting purposes and is not stored within the branch diagram. In particular, this method could be called many times for a given vertex.

Key order

The keys are drawn in increasing order. Use Reverse or a custom Ord implementation if the vertices in your tree should be arranged in decreasing order.

In many standard use-cases, the children of a vertex are greater than the vertex itself. However, failing to guarantee this will not corrupt the branch diagram. The next vertex which is drawn is simply the minimal vertex out of the active vertices (the vertices with an immediate parent already drawn to the diagram).

fn marker(&self, vtx: &V) -> char

The vertex marker in the branch diagram.

The marker is the character written inside the branch diagram. In the below diagrams, the vertex markers are the chars 0, 1, 2, and 3.

0
├┬╮
│1│
2╭╯
 3

Char width

This should be a char with width exactly 1 when displayed to the terminal. Other characters, such as control characters or double-width characters (mainly those described in Unicode Annex #11) will corrupt the tree drawing.

Here are some characters which might be useful:

• * (\u{002a})
• ◊ (\u{25ca})
• ✕ (\u{2715})
• ◈ (\u{25c8})
• ◉ (\u{25c9})

Provided Methods

fn annotate(&self, vtx: &V, buf: &mut String)

An annotation to write alongside a vertex.

The buffer is cleared before it is passed to this method.

This will be called exactly once per vertex. The lines in the buffer are written sequentially with each line on a separate row. The order in which the lines are rendered and the placement relative to the vertex marker is controled by the generator configuration.

Implementation details

Implementations of this method should write the annotation directly into the buffer, including newlines for annotations spanning multiple lines. The annotations are automatically line-broken and aligned with the branch diagram when rendered.

Like the standard library implementation of str::lines, the final trailing newline is optional and ignored if present. If you want extra space between consecutive annotations, it is best to use the row_padding option of the Config struct since this will allow the layout algorithm to generate a more compact diagram.

Example

The presence of the annotation influences the drawing of the tree, in that subsequent vertices are delayed in order to make space for the entire annotation followed by the margin.

0   An annotation occupying two lines
├┬╮ followed by one line of margin
│││
│1│ An annotation with one line and no margin.
2╭╯
 3  The annotation for vertex 2 is empty.

fn is_identical(&self, vtx: &V, other: &V) -> bool

Return if two vertices are identical and therefore should be merged.

The first argument is the current minimal vertex and the second argument is a different active vertex. This method is called once for other active vertex after computing the new minimal vertex.

The default implementation always returns false, so vertices will never be merged.

Difference from sort_key

Unlike sort_key, this method should check that the vertices are exactly the same. What this means depends on the vertex type, but this might look like Rc::ptr_eq, or like comparison of a usize index for flattened graph-like structures, or comparison of uniquely-defining metadata (like a Git commit hash).

Implementation requirements

This method must be compatible with Ramify::sort_key: if two vertices are identical, then their sort keys must also be equal. The converse need not hold (the sort keys can be equal even if the keys are not identical). Failure to uphold this invariant will result in otherwise identical vertices not being merged.

Note that this only checks active vertices. If there is an identical vertex but it is an offspring of a vertex which has yet to be written, this vertex will not be merged.

If every child of a vertex is strictly larger than the vertex itself (as ordered by sort_key) and the above compatibility requirement is upheld, it is guaranteed that identical vertices will not be missed.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors