Struct DblTree

pub struct DblTree<E, ProE, Sq>(pub Tree<DblNode<E, ProE, Sq>>);

A double tree, or pasting diagram in a virtual double category.

As the name suggests, the underlying data structure of a double tree is a [Tree] whose nodes represent cells (or occasionally arrows) in the pasting diagram. Not just any underlying tree constitutes a valid pasting. For example, the domains/codomains and sources/targets of the cells must compatible, and spines can only appear in certain configurations. Moreover, among the valid trees, invariants are maintained to ensure a normal form among equivalent representations of the same pasting.

TODO: Enforce invariant with identities when graft-ing.

Tuple Fields

0: Tree<DblNode<E, ProE, Sq>>

Implementations

impl<E, ProE, Sq> DblTree<E, ProE, Sq>

pub fn empty(p: ProE) -> Self

Constructs the empty or identity tree.

pub fn single(sq: Sq) -> Self

Constructs a tree with a single square, its root.

pub fn linear(iter: impl IntoIterator<Item = Sq>) -> Option<Self>

Constructs a linear tree from a sequence of squares.

pub fn spine(e: E) -> Self

Constructs a tree with a single spine node.

pub fn spines<V>(path: Path<V, E>) -> Option<Self>

Constructs a tree from a non-empty path of edges.

pub fn from_nodes( iter: impl IntoIterator<Item = DblNode<E, ProE, Sq>>, ) -> Option<Self>

Constructs a linear tree from a sequence of node values.

pub fn two_level(leaves: impl IntoIterator<Item = Sq>, base: Sq) -> Self

Constructs a tree of a height two.

pub fn graft(subtrees: impl IntoIterator<Item = Self>, base: Sq) -> Self

Constructs a tree by grafting trees as subtrees onto a base cell.

pub fn size(&self) -> usize

The size of the tree.

The size of a double tree is the number of non-identity nodes in it.

pub fn is_empty(&self) -> bool

Is the tree empty?

A double tree is empty if its sole node, the root, is an identity.

pub fn root(&self) -> &DblNode<E, ProE, Sq>

Gets the root of the double tree.

pub fn leaves(&self) -> impl Iterator<Item = &DblNode<E, ProE, Sq>>

Iterates over the leaves of the double tree.

pub fn src_nodes(&self) -> impl Iterator<Item = &DblNode<E, ProE, Sq>>

Iterates over nodes along the source (left) boundary of the double tree.

Warning: iteration proceeds from the tree’s root to its left-most leaf, which is the opposite order of the path of edges.

pub fn tgt_nodes(&self) -> impl Iterator<Item = &DblNode<E, ProE, Sq>>

Iterates over nodes along the target (right) boundary of the double tree.

Warning: iteration proceeds from the tree’s root to its right-most leaf, which is the opposite order of the path of edges.

pub fn dom<V>( &self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>, ) -> Path<V, ProE>

where ProE: Clone,

Domain of the tree in the given virtual double graph.

pub fn cod(&self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> ProE

where ProE: Clone,

Codomain of the tree in the given virtual double graph.

pub fn src<V>( &self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>, ) -> Path<V, E>

where E: Clone,

Source of the tree in the given virtual double graph.

pub fn tgt<V>( &self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>, ) -> Path<V, E>

where E: Clone,

Target of the tree in the given virtual double graph.

pub fn arity( &self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>, ) -> usize

Arity of the composite cell specified by the tree.

pub fn contained_in( &self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>, ) -> bool

where E: Eq + Clone, ProE: Eq + Clone,

Is the double tree contained in the given virtual double graph?

This includes checking whether the double tree is well-typed, i.e., that the domains and codomains, and sources and targets, of the cells are compatible.

pub fn is_isomorphic_to(&self, other: &Self) -> bool

where E: Eq, ProE: Eq, Sq: Eq,

Is the double tree isomorphic to another?

pub fn map<CodE, CodSq>( self, fn_e: impl FnMut(E) -> CodE, fn_sq: impl FnMut(Sq) -> CodSq, ) -> DblTree<CodE, ProE, CodSq>

Maps over the edges and squares of the tree.

impl<V, E, ProE, Sq> DblTree<Path<V, E>, ProE, DblTree<E, ProE, Sq>>

where V: Clone, E: Clone, ProE: Clone + Eq + Debug, Sq: Clone,

pub fn flatten_in( &self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>, ) -> DblTree<E, ProE, Sq>

Flattens a tree of trees into a single tree.

Trait Implementations

impl<E: Clone, ProE: Clone, Sq: Clone> Clone for DblTree<E, ProE, Sq>

fn clone(&self) -> DblTree<E, ProE, Sq>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<E: Debug, ProE: Debug, Sq: Debug> Debug for DblTree<E, ProE, Sq>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<E, ProE, Sq> From<Tree<DblNode<E, ProE, Sq>>> for DblTree<E, ProE, Sq>

fn from(value: Tree<DblNode<E, ProE, Sq>>) -> Self

Converts to this type from the input type.

impl<E: PartialEq, ProE: PartialEq, Sq: PartialEq> PartialEq for DblTree<E, ProE, Sq>

fn eq(&self, other: &DblTree<E, ProE, Sq>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<E: Eq, ProE: Eq, Sq: Eq> Eq for DblTree<E, ProE, Sq>

impl<E, ProE, Sq> StructuralPartialEq for DblTree<E, ProE, Sq>