Edit on GitHub

Simple trees

The aim of this module is to represent the standard tree structure in efficiency-non-sensitive cases. Please note that the default implementation of tree methods are far from optimal in efficiency. Therefore, please DO NOT use it if you need an efficient tree for addition, deletion, sort and inquiry. This module of codes apply only when the structure of tree matters but not the efficiency.

AbstractSimpleTree

AbstractSimpleTree{N, D} is the abstract type for all concrete trees. By design, it has two type parameters:

  • N: the type of the tree's node
  • D: the type of the tree's data

To fully utilize the methods designed for a tree structure, in our protocol, a concrete subtype must implement the following methods:

  • inquiry related methods
    • root(tree::AbstractSimpleTree{N}) where N -> Union{N, Nothing}
      Get a tree's root node (nothing for empty trees)
    • haskey(tree::AbstractSimpleTree{N}, node::N) where N -> Bool
      Check whether a node is in a tree.
    • length(tree::AbstractSimpleTree) -> Int
      Get the number of a tree's nodes.
    • parent(tree::AbstractSimpleTree{N},
       node::N,
       superparent::Union{N, Nothing}=nothing
       ) where N -> Union{N, Nothing}
      Get the parent of a tree's node or return superparent when the input node is the tree's root.
    • children(tree::AbstractSimpleTree{N}, node::N) where N -> Vector{N}
      Get the children of a tree's node.
  • structure modification related methods
    • addnode!(tree::AbstractSimpleTree{N},
         parent::Union{N, Nothing},
         node::N
         ) where N -> typeof(tree)
      Update the structure of a tree by adding a node. When the parent is nothing, the input tree must be empty and the input node becomes the tree's root.
    • deletenode!(tree::AbstractSimpleTree{N}, node::N) where N -> typeof(tree)
      Update the structure of a tree by deleting a node.
  • index related methods
    • getindex(tree::AbstractSimpleTree{N, D}, node::N) where {N, D} -> D
      Get the data of a tree's node
    • setindex!(tree::AbstractSimpleTree{N, D}, node::N, data::D) where {N, D}
      Set the data of a tree's node.

Based on these methods, we implement several generic functions for inquiries and manipulations

  • inquiry for type parameters: keytype, valtype, eltype
  • expansion over nodes/data-records: keys, values, pairs
  • inquiry for info of nodes: isleaf, level
  • inquiry for nodes: ancestor, descendants, siblings, leaves
  • modification: push!, append!, delete!, empty!

And optionally, when a subtype implement the following method,

empty(tree::AbstractSimpleTree) -> typeof(tree)

which constructs an empty tree of the same type with the input one, two more methods are supported:

  • subtree: Get a subtree starting from a node.
  • move!: Move a subtree to a new position.

SimpleTreeCore and SimpleTree

To implement all the prerequisites listed above costs a bit efforts. We provide two lazy ways to get over this:

  1. Inheritance AbstractSimpleTree with TREECORE::SimpleTreeCore as one of its attribute
  2. Inclusion an attribute which is an instance of SimpleTree

SimpleTreeCore

SimpleTreeCore{N, D}, as the literal meaning indicates, is the core of a tree. It encapsulates all the data structures needed by the default implementation, which contains 4 attributes:

  • root::N: the tree's root node
  • contents::Dict{N, D}: the tree's (node, data) pairs
  • parent::Dict{N, N}: records of the parent of each of the tree's nodes
  • children::Dict{N, Vector{N}}: records of the children of each of the tree's nodes

As above, the first lazy way is to include this struct with the special name :TREECORE in your concrete subtype one of its attribute.

SimpleTree

SimpleTree{N, D} is the minimum struct that implements all the default tree methods. You can include an instance of it as an attribute in your own type to utilize all the tree methods.

Manual

Base.:== — Method
==(tc1::TC, tc2::TC) where TC<:SimpleTreeCore -> Bool
isequal(tc1::TC, tc2::TC) where TC<:SimpleTreeCore -> Bool

Overloaded equivalent operator.

source
Base.:== — Method
==(t1::T, t2::T) where {T<:AbstractSimpleTree} -> Bool

Overloaded equivalent operator.

source
Base.append! — Method
append!(tree::AbstractSimpleTree{N, D}, subtree::AbstractSimpleTree{N, D}) where {N, D} -> typeof(tree)
append!(tree::AbstractSimpleTree{N, D}, node::Union{N, Nothing}, subtree::AbstractSimpleTree{N, D}) where {N, D} -> typeof(tree)

Append a subtree to a tree.

source
Base.delete! — Method
delete!(tree::AbstractSimpleTree{N}, node::N) where N -> typeof(tree)

Delete a node and all its descendants from a tree.

source
Base.eltype — Method
eltype(tree::AbstractSimpleTree)
eltype(::Type{T}) where {T<:AbstractSimpleTree}

Get the eltype of a tree.

source
Base.empty! — Method
empty!(tree::AbstractSimpleTree) -> typeof(tree)

Empty a tree.

source
Base.empty — Method
empty(tree::AbstractSimpleTree)

Construct an empty tree of the same type with the input one.

source
Base.getindex — Method
getindex(tree::AbstractSimpleTree{N}, node::N) where N -> N

Get the data of a tree's node.

source
Base.haskey — Method
haskey(tree::AbstractSimpleTree{N}, node::N) where N -> Bool

Check whether a node is in a tree.

source
Base.isequal — Method
isequal(t1::T, t2::T) where {T<:AbstractSimpleTree} -> Bool

Overloaded equivalent operator.

source
Base.keys — Method
keys(tree::AbstractSimpleTree{N}, ::SimpleTreeDepth, node::Union{N, Nothing}=root(tree)) where N
keys(tree::AbstractSimpleTree{N}, ::SimpleTreeWidth, node::Union{N, Nothing}=root(tree)) where N

Iterate over a tree's nodes starting from a certain node by depth first search or width first search.

source
Base.keytype — Method
keytype(tree::AbstractSimpleTree)
keytype(::Type{T}) where {T<:AbstractSimpleTree}

Get a tree's node type.

source
Base.length — Method
length(tree::AbstractSimpleTree) -> Int

Get the number of a tree's nodes.

source
Base.pairs — Method
pairs(tree::AbstractSimpleTree{N}, ::SimpleTreeDepth, node::Union{N, Nothing}=root(tree)) where N
pairs(tree::AbstractSimpleTree{N}, ::SimpleTreeWidth, node::Union{N, Nothing}=root(tree)) where N

Iterate over a tree's (node, data) pairs starting from a certain node by depth first search or width first search.

source
Base.push! — Method
push!(tree::AbstractSimpleTree{N, D}, node::N, data::D) where {N, D} -> typeof(tree)
push!(tree::AbstractSimpleTree{N, D}, parent::Union{N, Nothing}, node::N, data::D) where {N, D} -> typeof(tree)

Push a new node to a tree. When parent is nothing, this function set the root node of an empty tree.

source
Base.setindex! — Method
setindex!(tree::AbstractSimpleTree{N, D}, data::D, node::N) where {N, D}

Set the data of a tree's node.

source
Base.valtype — Method
valtype(tree::AbstractSimpleTree)
valtype(::Type{T}) where {T<:AbstractSimpleTree}

Get a tree's data type.

source
Base.values — Method
values(tree::AbstractSimpleTree{N}, ::SimpleTreeDepth, node::Union{N, Nothing}=root(tree)) where N
values(tree::AbstractSimpleTree{N}, ::SimpleTreeWidth, node::Union{N, Nothing}=root(tree)) where N

Iterate over a tree's data starting from a certain node by depth first search or width first search.

source
QuantumLattices.Prerequisites.SimpleTrees.addnode! — Method
addnode!(tree::AbstractSimpleTree{N}, node::N) where N} -> typeof(tree)
addnode!(tree::AbstractSimpleTree{N}, ::Nothing, node::N) where N -> typeof(tree)
addnode!(tree::AbstractSimpleTree{N}, parent::N, node::N) where N -> typeof(tree)

Update the structure of a tree by adding a node. When the parent is nothing, the input tree must be empty and the input node becomes the tree's root.

source
QuantumLattices.Prerequisites.SimpleTrees.children — Method
children(tree::AbstractSimpleTree) -> Vector{keytype(tree)}
children(tree::AbstractSimpleTree, ::Nothing) -> Vector{keytype(tree)}
children(tree::AbstractSimpleTree{N}, node::N) where N -> Vector{N}

Get the children of a tree's node.

source