KVTree

com.phasmidsoftware.lascala.tree.KVTree
See theKVTree companion object
abstract class KVTree[K, +V]()(implicit vo: ValueOps[K, V]) extends Branch[V], StructuralTree[K, V]

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

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

Members list

Value members

Concrete methods

def asTree[W >: V](n: Node[W])(implicit treeBuilder: TreeBuilder[W]): KVTree[K, W]
override def compareValues[B >: V](n: Node[B]): Maybe

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

def +[B >: V : 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 >: V : 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 +:[B >: V](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

Inherited from:
StructuralTree
def +:[B >: V](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

Inherited from:
StructuralTree
def :+[B >: V](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

Inherited from:
StructuralTree
def :+[B >: V](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

Inherited from:
StructuralTree
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 >: V](p: Node[B] => Boolean): Iterator[Node[B]]

Attributes

Inherited from:
Tree
def find[B >: V](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 >: V](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 findByKey[B >: V](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

Inherited from:
StructuralTree
def findByParentKey[B >: V](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 from:
StructuralTree
def includes[B >: V](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 >: V](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 >: V](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[V]

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 >: V](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 >: V](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 nodeIterator(depthFirst: Boolean): Iterator[Node[V]]

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
def replaceNode[B >: V : 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[V]]

Attributes

Returns

the immediate descendants (children) of this branch

Inherited from:
Tree
def get: Option[V]

Attributes

Returns

the value of this node, if any

Inherited from:
Node