Tree.SingleRootTree

Tree.SingleRootTree

SingleRootTree node is a thin wrapper around Tree that helps when you have one root node, and want to be able to reference the root without having to record the node ID yourself. You create it with a root node, and the root can never be removed. It exposes the same functionality as Tree, plus convenience functions for directly operating on the root node, without having to know its ID.

You can still create multiple roots, since a root is simply a node that is not a child of another node. However, this code tracks one very special root node for you.

Use Tree when you need a general-purpose forest (zero or more roots). Use SingleRootTree when your data naturally has a single entry point and you want a more convenient API.

type SingleRootTree node

The SingleRootTree manages a Tree nd keeps track of the ID of the single root node.
new : node -> SingleRootTree node

Create a new tree with a single root node.

tree = SingleRootTree.new "root"
SingleRootTree.nodeCount tree == 1

Functions for the root-node

getRoot : SingleRootTree node -> Maybe node

Get the root node's value.

tree = SingleRootTree.new "root"
SingleRootTree.getRoot tree == Just "root"
getRootChildren : SingleRootTree node -> Array Int

Get the children ids of the root node.

tree = SingleRootTree.new "root"
    |> SingleRootTree.appendRootChild 1
SingleRootTree.getRootChildren tree == [1]
getRootId : SingleRootTree node -> Int

Get the root node's id.

tree = SingleRootTree.new "root"
SingleRootTree.getRootId tree == 0
appendRootChild : Int -> SingleRootTree node -> SingleRootTree node

Append a child id to the root node's children array.

result = SingleRootTree.insert "child" tree
tree2 = SingleRootTree.appendRootChild result.id result.tree
SingleRootTree.children (SingleRootTree.getRootId tree2) tree2 == [1]
appendRootChildren : Array Int -> SingleRootTree node -> SingleRootTree node

Append multiple child ids to the root node's children array.

tree2 = SingleRootTree.appendRootChildren [1, 2, 3] tree
setRootChildren : Array Int -> SingleRootTree node -> SingleRootTree node

Replace the root node's entire children array.

tree2 = SingleRootTree.setRootChildren [2, 3] tree
SingleRootTree.children (SingleRootTree.getRootId tree2) tree2 == [2, 3]
getRootChildrenWithNodes : SingleRootTree node -> Array { id : Int, node : node }

Get the root's children with both id and value for each child.

SingleRootTree.getRootChildrenWithNodes tree
    == [ { id = 1, node = "childA" }, { id = 2, node = "childB" } ]

Wrappers for Tree functions

insert :
node
-> SingleRootTree node
-> { id : Int, tree : SingleRootTree node
}

Insert a node into the tree. Returns the auto-assigned id and the updated tree.

result = SingleRootTree.insert "child" tree
-- result == { id = 1, tree = ... }
remove : Int -> SingleRootTree node -> SingleRootTree node

Remove a single node by id. Cannot remove the root node.

trimmed = SingleRootTree.remove 2 tree
removeRecursive : Int -> SingleRootTree node -> SingleRootTree node

Remove a node and all of its descendants recursively. Cannot remove the root node.

trimmed = SingleRootTree.removeRecursive 1 tree
get :
Int
-> SingleRootTree node
-> Maybe { value : node, children : Array Int
}

Get the full entry for a node: its value and children ids.

SingleRootTree.get 0 tree
    == Just { value = "root", children = [1, 2] }
getNode : Int -> SingleRootTree node -> Maybe node

Get just the value of a node, ignoring its children.

SingleRootTree.getNode 0 tree == Just "root"
children : Int -> SingleRootTree node -> Array Int

Get the children ids of a node.

SingleRootTree.children 0 tree == [1, 2]
childrenNodes : Int -> SingleRootTree node -> Array node

Get the values of a node's children, without ids.

SingleRootTree.childrenNodes 0 tree == ["childA", "childB"]
childrenWithNodes :
Int
-> SingleRootTree node
-> Array { id : Int, node : node
}

Get the children of a node, with both id and value for each child. Returns an empty array if the node does not exist.

-- Given node 0 has children [1, 2]:
SingleRootTree.childrenWithNodes 0 tree
    == [ { id = 1, node = "childA" }, { id = 2, node = "childB" } ]
parent : Int -> SingleRootTree node -> Maybe Int

Find the parent id of a node.

SingleRootTree.parent 1 tree == Just 0
appendChild : Int -> Int -> SingleRootTree node -> SingleRootTree node

Append a child id to a parent's children array.

tree2 = SingleRootTree.appendChild 0 1 tree
setChildren :
Int
-> Array Int
-> SingleRootTree node
-> SingleRootTree node

Replace a node's entire children array.

tree2 = SingleRootTree.setChildren 0 [1, 2] tree
updateNode :
Int
-> (node -> node)
-> SingleRootTree node
-> SingleRootTree node

Update a node's value by applying a function to it.

tree2 = SingleRootTree.updateNode 0 String.toUpper tree
replaceNode : Int -> node -> SingleRootTree node -> SingleRootTree node

Replace a node's value entirely, preserving its children.

tree2 = SingleRootTree.replaceNode 0 "goodbye" tree
map :
(node -> mappedNode)
-> SingleRootTree node
-> SingleRootTree mappedNode

Transform every node value in the tree.

mapped = SingleRootTree.map String.toUpper tree
foldl :
(Int -> node -> Array Int -> acc -> acc)
-> acc
-> SingleRootTree node
-> acc

Fold over every node in the tree.

values =
    SingleRootTree.foldl
        (\id value childIds acc -> Array.pushLast value acc)
        Array.empty
        tree
roots : SingleRootTree node -> Array Int

Get the ids of all root nodes.

SingleRootTree.roots tree == [0]
descendants : Int -> SingleRootTree node -> Array Int

Get all descendant ids of a node, recursively.

SingleRootTree.descendants 0 tree == [1, 2, 3]
depthFirst :
Int
-> SingleRootTree node
-> Array { id : Int, value : node , depth : Int
}

Depth-first traversal starting from a given node.

SingleRootTree.depthFirst 0 tree
    == [ { id = 0, value = "root", depth = 0 }, ... ]
toArray :
SingleRootTree node
-> Array { id : Int, value : node , children : Array Int
}

Flatten the entire tree into an array of records.

SingleRootTree.toArray tree
    == [ { id = 0, value = "root", children = [1] }, ... ]
ids : SingleRootTree node -> Array Int

Get all node ids in the tree.

SingleRootTree.ids tree == [0, 1, 2]
isMember : Int -> SingleRootTree node -> Bool

Check whether a node id exists in the tree.

SingleRootTree.isMember 0 tree == True
nodeCount : SingleRootTree node -> Int

Get the total number of nodes in the tree.

SingleRootTree.nodeCount tree == 3
prettyPrint : (node -> String) -> SingleRootTree node -> String

Return a hierarchical representation of the Tree for debugging purposes. It needs a helper function to convert a node to a String.

SingleRootTree.prettyPrint identity tree
-- "(0) root\n  (1) child"