Trait which models the tree-like aspects of a tree
Type parameters
- K
-
the Key type
- V
-
the underlying type of the tree/node values
Value parameters
- vo
-
the (implicit) ValueOps
Attributes
Members list
Value members
Concrete methods
Method to determine if this Node's value is like node n's value WITHOUT any recursion. NOTE: This implementation uses the key for comparison, not the value.
Method to determine if this Node's value is like node n's value WITHOUT any recursion. NOTE: This implementation uses the key for comparison, not the value.
Type parameters
- B
-
the underlying type of n
Value parameters
- n
-
the node to be compared
Attributes
- Returns
-
true if this is "like" n
- Definition Classes
Inherited methods
Method to add the given node to this node
Method to add the given node to this node
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- b
-
the value to add, as a Leaf
Attributes
- Returns
-
the resulting tree
- Inherited from:
- Tree
Method to add the given node to this node.
Method to add the given node to this node.
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- node
-
the node to add
Attributes
- Returns
-
the resulting tree
- Inherited from:
- Tree
Method to add a node to this tree: because the addition of nodes is not order-dependent this method simply invokes :+
Method to add a node to this tree: because the addition of nodes is not order-dependent this method simply invokes :+
NOTE the implementation of this method assumes that the order of the operands is not important.
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- node
-
the node to add
Attributes
- Returns
-
the resulting tree
- Inherited from:
- StructuralTree
Method to add a value to this tree: because the addition of values is not order-dependent this method simply invokes :+
Method to add a value to this tree: because the addition of values is not order-dependent this method simply invokes :+
NOTE the implementation of this method assumes that the order of the operands is not important.
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- b
-
the value to add
Attributes
- Returns
-
the resulting tree
- Inherited from:
- StructuralTree
Method to add a node to this tree
Method to add a node to this tree
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- node
-
the node to add
Attributes
- Returns
-
the resulting tree
- Inherited from:
- StructuralTree
Method to add a value to this tree by simply creating a leaf and calling :+(Node[B])
Method to add a value to this tree by simply creating a leaf and calling :+(Node[B])
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- b
-
the value to add
Attributes
- Returns
-
the resulting tree
- Inherited from:
- StructuralTree
NOTE: that this is NOT tail-recursive
NOTE: that this is NOT tail-recursive
NOTE: I don't think we can use Parent.traverse for depth. Could be wrong.
Attributes
- Returns
-
the depth of the subtree
- Inherited from:
- Tree
Type parameters
- B
-
the type of b
Value parameters
- p
-
the predicate to be applied to the value of each node in turn (depth first)
Attributes
- Returns
-
Some(node) where node is the first node to be found that satisfies the predicate p
- Inherited from:
- Tree
Type parameters
- B
-
the type of b
Value parameters
- b
-
value to be found, looking at the value of each node in turn (depth first)
Attributes
- Returns
-
Some(node) where node is the first node to be found with value b
- Inherited from:
- Tree
Non tail-recursive method to find a Node in a tree by its key
Non tail-recursive method to find a Node in a tree by its key
Type parameters
- B
-
the value type
Value parameters
- k
-
the key
- vo
-
(implicit) ValueOps
Attributes
- Returns
-
optionally the node found
- Inherited from:
- StructuralTree
CONSIDER making this tail-recursive, given that the parent key is structure-based
CONSIDER making this tail-recursive, given that the parent key is structure-based
Method to find a Node in a tree by its structural key. NOTE: this method is not tail-recursive.
FIXME: this must be made much more efficient because building an N-node tree is currently an O(N2) problem ... we can reduce that to N log N
Type parameters
- B
-
the value type
Value parameters
- k
-
the (structural) key for the desired node
- vo
-
(implicit) ValueOps
Attributes
- Returns
-
optionally the node found
- Inherited from:
- StructuralTree
Method to determine if this Tree includes the given node
Method to determine if this Tree includes the given node
Type parameters
- B
-
the underlying type of n
Value parameters
- node
-
the node to be searched for
Attributes
- Returns
-
true if node n is found in the sub-tree defined by this
- Inherited from:
- Tree
Determine if this tree has a subtree matching b which includes c
Determine if this tree has a subtree matching b which includes c
Type parameters
- B
-
the type of subtree and element
Value parameters
- element
-
the value of the element to be found in the subtree
- subtree
-
the value of the subtree to be searched
Attributes
- Returns
-
true if value element is found in the sub-tree defined by subtree
- Inherited from:
- Tree
Determine if this subtree includes a value equal to b
Determine if this subtree includes a value equal to b
CONSIDER renaming this back to just includes (as it was previously)
Type parameters
- B
-
the type of b
Value parameters
- b
-
the value to be searched
Attributes
- Returns
-
true if value b is found in the sub-tree defined by this
- Inherited from:
- Tree
Method to determine if this Node is a leaf or a branch node
Method to determine if this Node is a leaf or a branch node
Attributes
- Returns
-
true if this Node is a leaf
- Inherited from:
- Node
Iterate on the values of this tree
Iterate on the values of this tree
Value parameters
- depthFirst
-
if true then we iterate depth-first, else breadth-first (defaults to true)
Attributes
- Returns
-
an iterator of values
- Inherited from:
- Tree
Method to get the key for this StructuralNode
Method to get the key for this StructuralNode
Type parameters
- B
-
the underlying type of the node to be added (and the tree to be returned)
Value parameters
- vo
-
the (implicit) ValueOps that is used to determine the proper tree position of this node
Attributes
- Returns
-
the key based on value rather than tree position
- Inherited from:
- StructuralNode
Method to determine if this subtree is "like" the given node (without recursion)
Method to determine if this subtree is "like" the given node (without recursion)
Type parameters
- B
-
the underlying type of n
Value parameters
- node
-
the node to be searched for
Attributes
- Returns
-
true if node n is found in the sub-tree defined by this
- Inherited from:
- Tree
Iterate on the nodes of this branch
Iterate on the nodes of this branch
NOTE: this method is not currently implemented in a tail-recursive manner.
Value parameters
- depthFirst
-
if true then we iterate depth-first, else breadth-first
Attributes
- Returns
-
an iterator of nodes
- Inherited from:
- Branch
Method to replace a particular node in this tree with another node, but otherwise return a copy of this tree.
Method to replace a particular node in this tree with another node, but otherwise return a copy of this tree.
CONSIDER moving this into Tree since it isn't really a Node method
Type parameters
- B
-
the underlying type of the new node (and the resulting tree)
Value parameters
- f
-
function to determine if two nodes are the same
- x
-
the node to be replaced with y
- y
-
the node to replace x
Attributes
- Returns
-
the resulting tree
- Inherited from:
- Node
Calculate the size of this node's subtree
Calculate the size of this node's subtree
Attributes
- Returns
-
the size of the subtree
- Inherited from:
- Tree