ch.bfh.algo.example
Class SequencesSortExamples

java.lang.Object
  ch.bfh.algo.example.SequencesSortExamples

public class SequencesSortExamples
extends Object

The class SequencesSortExamples contains samples of the use of a Sequence. This class has no mean of being used, it is only a sample of possible applications of the ch.bfh.algo algorithmic framework.

Version:

1.0

Author:

Emmanuel Benoist

Constructor Summary

SequencesSortExamples()

Method Summary

static void	bubbleSortArrayLike(List<Integer> list) The method bubbleSortArrayLike is a very simple Bubble Sort written for the Java Collection Framework.
static void	bubbleSortExamples() This method bubbleSortExamples is used to run the two other methods: bubbleSortArrayLike and bubbleSortSequence.
static void	bubbleSortSequence(Sequence<Integer> seq) This Bubble sort algorithm has been implemented using a Sequence.
static void	main(String[] args)
static void	mergeSort(Sequence<Integer> seq) The method mergeSort implements the merge sort algorithm using the Sequence interface.
static Sequence<Integer>	mergeUsingPositions(Sequence<Integer> seq1, Sequence<Integer> seq2, Sequence<Integer> result)
void	positionEfficiencyExample() The method positionEfficiencyExample shows the advantage of the Sequence compared to standard structures such as java.util.List.
static void	removeFirstThreeOfL1FromL2(Sequence<ch.bfh.algo.example.SequencesSortExamples.MyString> sequence1, Sequence<ch.bfh.algo.example.SequencesSortExamples.MyString> sequence2) The method removeFirstThreeOfL1FromL2 removes the tree first elements of the sequence1 from the sequence2.
void	run()
static void	splitUsingIterator(List<Integer> seq, List<Integer> res1, List<Integer> res2)
static void	testMerge()
static void	testMergeSort() This method tests if the merge sort algorithm (mergeSort()) works as expected
static void	testSplit() This method tests if the method split (splitUsingIterator()) works as expected

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SequencesSortExamples

public SequencesSortExamples()

Method Detail

bubbleSortArrayLike

public static void bubbleSortArrayLike(List<Integer> list)

The method bubbleSortArrayLike is a very simple Bubble Sort written for the Java Collection Framework. This method does not include any reference to the *ch.bfh.algo framework. However, this works fine *with an ArraySequence since it is fully Java *Collection Framework compatible.

bubbleSortSequence

public static void bubbleSortSequence(Sequence<Integer> seq)

This Bubble sort algorithm has been implemented using a Sequence. It is using also the Positions that are the place-holders of a Sequence

bubbleSortExamples

public static void bubbleSortExamples()

This method bubbleSortExamples is used to run the two other methods: bubbleSortArrayLike and bubbleSortSequence. The first method is using only the standard Collection Framework syntax and interfaces. Whereas the second is using a syntax typical for the ch.bfh.algo framework.

removeFirstThreeOfL1FromL2

public static void removeFirstThreeOfL1FromL2(Sequence<ch.bfh.algo.example.SequencesSortExamples.MyString> sequence1,
                                              Sequence<ch.bfh.algo.example.SequencesSortExamples.MyString> sequence2)

The method removeFirstThreeOfL1FromL2 removes the tree first elements of the sequence1 from the sequence2. This is can not be done efficiently using classes of the java collection framework and is very efficient in our case (regardless of the number of elements in sequence1 or sequence2, this operation is O(1)).

positionEfficiencyExample

public void positionEfficiencyExample()

The method positionEfficiencyExample shows the advantage of the Sequence compared to standard structures such as java.util.List. We create two lists containing the same items. In each Item we save its Position in both of the lists. Afterwhat, it is possible to remove an item from a list in time O(1). Doing the same with java.util.LinkedList requires O(n), since it can not use a way to refere to an item inside a list (there is no place-holder like the Position).

mergeUsingPositions

public static Sequence<Integer> mergeUsingPositions(Sequence<Integer> seq1,
                                                    Sequence<Integer> seq2,
                                                    Sequence<Integer> result)

splitUsingIterator

public static void splitUsingIterator(List<Integer> seq,
                                      List<Integer> res1,
                                      List<Integer> res2)

mergeSort

public static void mergeSort(Sequence<Integer> seq)

The method mergeSort implements the merge sort algorithm using the Sequence interface. It uses on one side the compatibility with the java collection framework in the function splitUsingIterator. The second part, merging is done using Positions

testMerge

public static void testMerge()

testSplit

public static void testSplit()

This method tests if the method split (splitUsingIterator()) works as expected

testMergeSort

public static void testMergeSort()

This method tests if the merge sort algorithm (mergeSort()) works as expected

run

public void run()

main

public static void main(String[] args)