Tutorial - Sequence and Position Interfaces

Principle

There exists basically two ways to represent flat data structures in algorithmic literature: arrays and linked lists.
Arrays are used since one can access (and change) any element in time O(1) if one has its corresponding index.
Linked lists are also interesting since, if a pointer to the cell is provided, one can insert, remove or change any element in the middle of a list in constant time O(1).
Unfortunately, there is no implementation using the linked list advantages in the java collection framework. We use the concept privided by Goodrich and Tamassia Data Structures and Algorithms in Java (it is also implemented in the net.datastructure and the JDSL frameworks).
We want interfaces to be identical for programs using linked lists or arrays. This interface should be efficient for methods using indices if the undelying data structure is an array, but it should also provide a way to insert and remove elements inside a linked list efficiently.
The solution is that we use an other interface called Position that intuitively plays the role of the "cell" in the linked list. This means that we can add an item after a given Position, we can remove a Position, we can get the first and the last Position of a sequence and get the Position that is positionned after a given Position. This interface has only two features: it knows which element it contains and also knows which collection it belongs to. It has no possibility to know its successor (i.e. no method getNext()) or predecessor. Only the sequence knows this information. It is possible to implement such an interface using a sequence implemented with a doubly linked list (in this case, the Position is implemented by the cell class). As an option, we provide also an implementation of this interface using an underlying array. In this case, the Position contains the element plus the index where it is stored, the array contains only Positions.

Example using the Position

In this first example, we have a sequence seq (we do not know how it was implemented).
We let two Positions pos1 and pos2 visit the sequence. We swap elements if they are in the wrong order. (this piece of code comes from bubble sort algorithm).

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);
  }
}

This example has the same efficiency for both of the possible implementations of the framework.

Using the efficiency of the Position interface

Assume that there are two different lists containing some elements, and we want to sort one of them and remove the first three elements of that list from the other list. There is no way to do this efficiently using standard data structure. We use here the advantage of storing the two positions in both of the lists, such that we can remove the elements in time O(1). Suppose we have a class MyString that extends a String and has two properties positionInList1 and positionInList2.

public static void removeFirstThreeOfL1FromL2(Sequence sequence1,
						  Sequence sequence2){
	Position pos=sequence1.first();
	for(int i=0;i<3;i++){
	    MyString s=sequence1.element(pos);
	    sequence2.delete(s.getPositionInList2());
	    pos=sequence1.after(pos);
	}
	
}


public void positionEfficiencyExample(){
	MyString s1=new MyString("1");
	MyString s2=new MyString("2");
	MyString s3=new MyString("3");
	MyString s4=new MyString("4");
	MyString s5=new MyString("5");
	MyString s6=new MyString("6");
	Sequence seq1 = new ArraySequence();
	s1.setPositionInList1(seq1.insert(s1));
	s2.setPositionInList1(seq1.insert(s2));
	s3.setPositionInList1(seq1.insert(s3));
	s4.setPositionInList1(seq1.insert(s4));
	s5.setPositionInList1(seq1.insert(s5));
	s6.setPositionInList1(seq1.insert(s6));
	
	Sequence seq2 = new LinkedSequence();
	s1.setPositionInList2(seq2.insert(s1));
	s6.setPositionInList2(seq2.insert(s6));
	s5.setPositionInList2(seq2.insert(s5));
	s4.setPositionInList2(seq2.insert(s4));
	s2.setPositionInList2(seq2.insert(s2));
	s3.setPositionInList2(seq2.insert(s3));
     
	removeFirstThreeOfL1FromL2(seq1,seq2);

}

Fully compatible with the java collection framework

Suppose we have written the following algorithm for bubble sort using the java.util.List interface.

    public static void bubbleSortArrayLike(List list){
	int size = list.size();
	for (int pass=0; pass < size ; pass++){
	    for(int index = 0; index< size-(pass+1);index++){
		if(list.get(index)>list.get(index+1)){
		    Integer tmp = list.get(index);
		    list.set(index,list.get(index+1));
		    list.set(index+1,tmp);
		}
	    }
	}

    }

We can without any problem use our data structure, since it implements this interface.

List seq1 = new ArraySequence();
seq1.add(10);
seq1.add(20);
seq1.add(30);
seq1.add(40);
seq1.add(1);
bubbleSortArrayLike(seq1);

Iterators and Iterable

Sequences are iterable. So each method that returns a Sequence can be iterated. For instance, the method g.vertices():

List> vertices = g.vertices();
for(Position v : vertices){
    if(! bufferedVertices.contains(v)){
	buffer.add(v);

Previous Tutorial Next