Trait which models the tree-like aspects of a structural tree. This kind of tree is distinguishable from an ordinary Tree by the fact that the methods take an implicit parameter of type ValueOps. This parameter allows for the values themselves to imply a position within the tree, in other words a tree which could be faithfully rebuilt from itself.
CONSIDER requiring that the ValueOps parameter be a property of the StructuralTree itself.
Type parameters
- A
-
the underlying type of the tree/node
- K
-
the key type
Attributes
Members list
Value members
Concrete methods
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
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
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
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
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
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 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 determine if this Node's value is equal to node n's value WITHOUT any recursion.
Method to determine if this Node's value is equal to node n's value WITHOUT any recursion.
Type parameters
- B
-
the underlying type of n
Value parameters
- n
-
the node to be compared
Attributes
- Returns
-
true if this is "like" n
- Inherited from:
- Node
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
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
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
Inherited and Abstract methods
Attributes
- Returns
-
the immediate descendants (children) of this branch
- Inherited from:
- Tree
Iterate on the nodes which are the descendants of this node (including this node at start or end of result)
Iterate on the nodes which are the descendants of this node (including this node at start or end of result)
Value parameters
- depthFirst
-
if true then we iterate depth-first, else breadth-first (defaults to true)
Attributes
- Returns
-
an iterator of nodes
- Inherited from:
- Node