Algorithmic Concepts

In this framework, some interesting algorithmic concepts are used rather frequently. Hereafter, the most important ones are presented.

Sequences and Positions

Principle

In their series of books (Algorithms in Java, ...) Goodrich and Tamassia presented the interesting concept of a Sequence using Postions (see java.datastructures.net and algorithmdesign.net to learn more).
In algorithmics, we have essentially two sort of flat datastructures. On the one hand so-called Linked Lists and on the other hand Arrays. In an Array, one can access items using their rank in constant time (i.e. O(1)), but it is difficult (i.e. not O(1)) to insert an element inside an existing array (as one has to shift all the elements). In a Linked list one can insert an element after or before a cell in time O(1) even if this cell is right in the middle, but accesing elements by rank is difficult.
So if we want to implement these two datastructures, we will have two different Interfaces. On one hand, the Array will have some methods using mainly the rank (or index) to access its elements. On the other hand, the Linked List will have to give the user access to its internal nodes to allow the most efficient methods. Yet this second interface can not be used as is, because it is a very big hazard to allow access to an internal structure of an object.
In the Java Collection Framework, the java.util.List and even java.util.LinkedList do use the first type of interface, i.e. not giving the user acces to internal nodes directly. It is therefor not possible to directly insert or remove an element in the middle of the structure using this interface. The only possibility is to use an Iterator to visit the structure in a iterative way, which then allows the operation.
Goodrich and Tamassia developped a new concept they call the Sequence that is an interface using methods of both types. Some methods use the rank to access elements, and some use the new concept of Position to access elements.
The main Idea is to have an object called Position playing the role of both the rank of the element in an array and the cell in a linked list. The methods will refer to this very position item, to access elements, insert and remove elements in a sequence, etc. The Position does -- from the users perspective -- nothing. The only thing it knows is the element it contains, it has therefore only one method element(). (Note that sofar we have not spoken about the implementation of such a sequence.)

Example

In the following example, there is a loop for visiting the elements of a Sequence. This piece of code is independent of the way the Sequence is implemented (using an array or a linked list).
This code is very close to a pseudocode

pos1 = seq.first();
while(pos1!=seq.last()){
  pos2=seq.after(pos1);
  if( pos1.element()> pos2.element()){
      Integer tmp = pos1.element();
      seq.replace(pos1,pos2.element());
      seq.replace(pos2,tmp);
  }
}

Advantages

The main advantage of this concept is to have the possibility to insert and remove elements inside a linked list with complexity of O(1), i.e. in constant time. And we have nevertheless the possibility to write an object oriented code that can use both linked lists and arrays.

Forest vs Tree

Principle

The ch.bfh.algo frame work does'nt have any class for storing a single tree, yet the framework does provide an extensive support for forests. In real algorithms, such a forest will most of the time contain only one arborescence, or one single tree in the classical sense. Nevertheless, inside the algorithm, one could separate "temporarly" some branches from the tree (they become new trees in the forest). Afterwhile, these trees can be inserted back anywhere in the original tree. The structure "Forest" does not limit the functionality, but rather expands the possibilities of the structure.

Example

In the following example, we create a new node and then visit all the existing nodes in order for them to become children of the new node. This way, we have transformed a forest into a regular tree.

public static void branchAllRoots(Forest f, String root){
    Position<String> newRoot = f.insert(root);
    for(Position<String> oldRoot : f.roots()){
        if(oldRoot!= newRoot){
    	f.link(newRoot,oldRoot);
        }
    }
    return;
}

Advantages

We believe that this structure, where the tree is not the centeral datastructure, is very interesting when dealing with subtree that change their location. Using some other data-structure, such a movement obliges to notify all the nodes that they belong to another datastructure which typically cannot be done in constant time O(1). The structures of a forest allows to implement the cut and link features in time O(1).