StructuralTree

com.phasmidsoftware.lascala.tree.StructuralTree
See theStructuralTree companion object
trait StructuralTree[K, +A] extends Tree[A], StructuralNode[K, A]

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

Companion
object
Graph
Supertypes
trait StructuralNode[K, A]
trait Tree[A]
trait Node[A]
class Object
trait Matchable
class Any
Show all
Known subtypes
class KVTree[K, V]
class GeneralKVTree[K, V]

Members list

Value members

Concrete methods

def +:[B >: A](b: B)(implicit evidence$1: TreeBuilder[B], vo: ValueOps[K, B]): StructuralTree[K, B]

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

def +:[B >: A](node: Node[B])(implicit evidence$1: TreeBuilder[B], vo: ValueOps[K, B]): StructuralTree[K, B]

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

def :+[B >: A](b: B)(implicit evidence$1: TreeBuilder[B], vo: ValueOps[K, B]): StructuralTree[K, B]

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

def :+[B >: A](node: Node[B])(implicit evidence$1: TreeBuilder[B], vo: ValueOps[K, B]): StructuralTree[K, B]

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

def findByKey[B >: A](k: K)(implicit vo: ValueOps[K, B]): Option[Node[B]]

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

def findByParentKey[B >: A](k: K)(implicit vo: ValueOps[K, B]): Option[Node[B]]

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

def +[B >: A : TreeBuilder](b: B): Tree[B]

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
def +[B >: A : TreeBuilder](node: Node[B]): Tree[B]

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
def compareValues[B >: A](n: Node[B]): Maybe

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
def depth: Int

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
def filter[B >: A](p: Node[B] => Boolean): Iterator[Node[B]]

Attributes

Inherited from:
Tree
def find[B >: A](p: Node[B] => Boolean): Option[Node[B]]

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
def find[B >: A](b: B): Option[Node[B]]

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
def includes[B >: A](node: Node[B]): Boolean

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
def includes[B >: A](subtree: B, element: B): Boolean

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
def includesValue[B >: A](b: B): Boolean

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
def isLeaf: Boolean

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
def iterator(depthFirst: Boolean = ...): Iterator[A]

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
def key[B >: A](implicit vo: ValueOps[K, B]): Option[K]

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
def like[B >: A](node: Node[B]): Maybe

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
def replaceNode[B >: A : TreeBuilder](x: Node[B], y: Node[B])(f: (Node[B], Node[B]) => Boolean): Tree[B]

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
def size: Int

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
def summary: String

Create a String which represents the value of this Node and the values of its immediate descendants

Create a String which represents the value of this Node and the values of its immediate descendants

Attributes

Returns

an appropriate String

Inherited from:
Tree

Inherited and Abstract methods

def children: List[Node[A]]

Attributes

Returns

the immediate descendants (children) of this branch

Inherited from:
Tree
def get: Option[A]

Attributes

Returns

the value of this node, if any

Inherited from:
Node
def nodeIterator(depthFirst: Boolean = ...): Iterator[Node[A]]

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