ch.bfh.algo
Interface Forest<E>

All Superinterfaces:

Collection<E>, Container<E>, Iterable<E>

All Known Subinterfaces:

BinaryForest<E>, GenericBinaryForest<E,P>, GenericForest<E,P>

All Known Implementing Classes:

DefaultBinaryForest, DefaultForest, GenericBinaryForestGraph, GenericForestGraph

public interface Forest<E>
extends Container<E>

The Forest interface is used to store any type of arborescence. A forest contains many nodes. Some of them have one parent. They are internal nodes if they have at least one child and are leaves if they do not have any child. The nodes without parents are the roots. A forest (unlike a tree) can have many roots. The nodes of the trees can be handled using Positions. The following example presents a program for displaying the content of a given forest.

    public static void displayForest(Forest f){
        LinkedSequence> s =
            new LinkedSequence>();
        LinkedSequence depthList = new LinkedSequence();
        int depth=0;
        for(Position root : f.roots()){
            depth=0;
            s.add(root);
            depthList.add(depth);
            while(!s.isEmpty()){
                Position tmpNode = s.delete(s.last());
                depth = depthList.delete(depthList.last());
                System.out.println(createXSpaces(depth)+tmpNode.element());
                for(Position child : f.children(tmpNode)){
                    s.add(child);
                    depthList.add(depth+1);

                }
            }
        }
    }
 

Version:

1.0

Author:

Juerg Kraehenbuehl (code) and Emmanuel Benoist (Javadoc)

Method Summary

List<Position<E>>	children(Position<?> parent) Returns the list of the children of a given node.
void	cut(Position<?> child) Removes the relation between the given node (child) and its parent.
void	link(Position<?> parent, Position<?> child) Creates a link between parent and child.
void	linkAfter(Position<?> sibling, Position<?> node) Inserts node in the list of children of the parent of sibling.
void	linkBefore(Position<?> sibling, Position<?> node) Inserts node in the list of children of the parent of sibling.
Position<E>	parent(Position<?> child) Returns the parent of the given node.
List<Position<E>>	roots() Returns the list of the roots contained in the forest.

Methods inherited from interface ch.bfh.algo.Container

delete, element, encloses, insert, positionIterator, replace, swap

Methods inherited from interface java.util.Collection

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

roots

List<Position<E>> roots()

Returns the list of the roots contained in the forest. I.e. all the nodes without parent.

Returns:

the list containing all roots.

parent

Position<E> parent(Position<?> child)
                   throws InvalidAccessorException

Returns the parent of the given node. We get a child and return its parent

Parameters:

child - the node we are looking at

Returns:

the parent of child.

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.

children

List<Position<E>> children(Position<?> parent)
                           throws InvalidAccessorException

Returns the list of the children of a given node. We receive a parent node and return the list of its children.

Parameters:

parent - the node we are looking at

Returns:

the list of all the children of parent.

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.

link

void link(Position<?> parent,
          Position<?> child)
          throws InvalidAccessorException

Creates a link between parent and child. child is inserted in the list of children of parent and parent becomes its parent.

Parameters:

parent - the node that will be the parent

child - the node that will be the child

Throws:

InvalidAccessorException - if the positions are not valid nodes of this forest.

linkAfter

void linkAfter(Position<?> sibling,
               Position<?> node)
               throws BoundaryViolationException,
                      InvalidAccessorException

Inserts node in the list of children of the parent of sibling. node is inserted just after sibling in the list. The parent of sibling becomes the new parent of node.

Parameters:

sibling - the future sibling of node

node - the node that will be inserted

Throws:

InvalidAccessorException - if the positions are not valid nodes of this forest.

BoundaryViolationException

linkBefore

void linkBefore(Position<?> sibling,
                Position<?> node)
                throws BoundaryViolationException,
                       InvalidAccessorException

Inserts node in the list of children of the parent of sibling. node is inserted just before sibling in the list. The parent of sibling becomes the new parent of node.

Parameters:

sibling - the future sibling of node

node - the node that will be inserted

Throws:

InvalidAccessorException - if the positions are not valid nodes of this forest.

BoundaryViolationException

cut

void cut(Position<?> child)
         throws InvalidAccessorException

Removes the relation between the given node (child) and its parent. child becomes a new root of the forest.

Parameters:

child - the node to be transformed into a root.

Throws:

InvalidAccessorException - if the position is not valid node of this forest.