in scala.collection.immutable
class Tree

abstract `class` Tree [ A , B ]
  `extends` java.lang.Object
  `with` scala.ScalaObject

  General Balanced Trees - highly efficient functional dictionaries. An efficient implementation of Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to plain unbalanced binary trees, and their performance is in general better than AVL trees.

  This implementation does not balance the trees after deletions. Since deletions don't increase the height of a tree, this should be OK in most applications. A balance method is provided for those cases where rebalancing is needed.

  The tree consists of entries conatining a key with an order.

  When instanciating the tree an order for the keys has to be supplied.

author:
  Erik Stenman
author:
  Michel Schinz
version:
  1.1, 2005-01-20

Constructor Summary
| `def` this ( ) ( view$0 : (A) => scala.Ordered[A] )

Type Summary
`protected` | `type` aNode The type of nodes that the tree is build from.

Def Summary
`protected` | `def` New ( sz : scala.Int , t : scala.collection.immutable.GBTree[A,B] ) : Tree.this.This This abstract method should be defined by a concrete implementation C[T] as something like:
           override def New(sz:Int,t:aNode):This {
             new C[T](order) {
              override def size=sz;
              override protected def tree:aNode=t;
           }
The concrete implementation should also override the def of This `override type This = C[T];`
`protected` | `def` add ( key : A , entry : B ) : Tree.this.This A new tree with the entry added is returned, assuming that key is not in the tree.
| `def` balance : Tree.this.This Create a new balanced tree from the tree. Might be useful to call after many deletions, since deletion does not rebalance the tree.
`protected` | `def` deleteAny ( key : A ) : Tree.this.This Removes the key from the tree.
`protected` | `def` entries : scala.Iterator[B] Gives you an iterator over all elements in the tree. The iterator structure corresponds to the call stack of an in-order traversal. Note: The iterator itself has a state, i.e., it is not functional.
`protected` | `def` findValue ( key : A ) : scala.Option[B] Check if this map maps `key` to a value and return the value if it exists.
`protected` | `def` getThis : Tree.this.This
| `def` size : scala.Int The size of the tree, returns 0 (zero) if the tree is empty.
`protected` | `def` tree : scala.collection.immutable.GBTree[A,B] The nodes in the tree.
`protected` | `def` updateOrAdd ( key : A , entry : B ) : Tree.this.This A new tree with the entry added is returned, if key is not in the tree, otherwise the key is updated with the new entry.

Constructor Detail

`def` this ( ) ( view$0 : (A) => scala.Ordered[A] )

Type Detail

protected `type` aNode

  The type of nodes that the tree is build from.

Def Detail

protected `def` New ( sz : scala.Int , t : scala.collection.immutable.GBTree[A,B] ) : Tree.this.This

  This abstract method should be defined by a concrete implementation C[T] as something like:

             override def New(sz:Int,t:aNode):This {
               new C[T](order) {
                override def size=sz;
                override protected def tree:aNode=t;
             }

  The concrete implementation should also override the def of This `override type This = C[T];`

protected `def` add ( key : A , entry : B ) : Tree.this.This

  A new tree with the entry added is returned, assuming that key is not in the tree.

`def` balance : Tree.this.This

  Create a new balanced tree from the tree. Might be useful to call after many deletions, since deletion does not rebalance the tree.

protected `def` deleteAny ( key : A ) : Tree.this.This

  Removes the key from the tree.

protected `def` entries : scala.Iterator[B]

  Gives you an iterator over all elements in the tree. The iterator structure corresponds to the call stack of an in-order traversal. Note: The iterator itself has a state, i.e., it is not functional.

protected `def` findValue ( key : A ) : scala.Option[B]

  Check if this map maps `key` to a value and return the value if it exists.

param:
  key the key of the mapping of interest
return:
  the value of the mapping, if it exists

protected `def` getThis : Tree.this.This

`def` size : scala.Int

  The size of the tree, returns 0 (zero) if the tree is empty.

Returns:
  The number of nodes in the tree as an integer.

protected `def` tree : scala.collection.immutable.GBTree[A,B]

  The nodes in the tree.

protected `def` updateOrAdd ( key : A , entry : B ) : Tree.this.This

  A new tree with the entry added is returned, if key is not in the tree, otherwise the key is updated with the new entry.