Sort
This example presents different concepts, especially generics, and the design patterns Adapter, Decorator and Observer.
- We dispose in this first version of two classes composed of
static methods which allow to sort arrays of elements implementing the
inteface java.util.Comparable. The class QuickSort et InsertionSort, implement respectivly the algorithm Quicksort and Sorting using insertion. A testing class TestSort completes the program.
Because we don't want to use generics in this first version, this
program is compiled using the version 1.4 of Java. In Eclispe, you must
select the project, then do a right click and choose the item
"Properties". In the dialog, select the item "Java Compiler", then
click on the check button "Enable project specific settings" and then
select the value "1.4" in the list "Compiler compliance level".
- This version proposes a new interface Sort which allows to use any kind of sort. QuickSort and InsertionSort are modified to implement this interface, and TestSort to use it.
- This version adds a useful class Sorts which allows to get an yet existing instance of QuickSort or InsertionSort, and to sort an array without having to choose which kind of sort would be used. TestSort is updated to use this new class. Sort, QuickSort and InsertionSort remain unchanged.
- This version add an interface SortableData, typing sortable data. Two implementations are given : SortableArray and SortableList which adapt arrays and java.util.List to the interface SortableData. Classes Sort, QuickSort, InsertionSort, Sorts and TestSort are modified to use SortableData.
- This version adds a functionnality for tracing the sort, by the way of a "decorator" on the instances of SortableData : SortableDataWithTracer. The class TestSort is updated and the other classes SortableData, SortableArray, SortableList, Sort, QuickSort, InsertionSort and Sorts and TestSort remain unchanged.
- This version add generics, in particular to SortableData. Note that the classes SortableArray and SortableList use elements of generic type T where T is a subtype of java.util.Comparable<? super T>. Sort, InsertionSort and QuickSort are updated using wildcards. Sorts , SortableDataWithTracer and TestSort are also updated.
- This version allows to modify the order on comparable elements,
or to add a compare method on objects which was not comparable at
first, using an instance of java.util.Comparator.
Classes Sort, InsertionSort and QuickSort remain unchanged.
Instead, the architecture around SortableData has been deeply modified. Now, we find a new interface SwapableData which declares the same methods from SortableData but int compare(int i, int j). The classes SortableComparableData and SortableDataWithComparator allow to transform instances of SwapableData to instances of SortableData by adding the lacking method compare(int, int), respectivly using the natural order on comparable objects or using an external comparator. SortableArray and SortableList have been replaced respectivly by SwapableArray and SwapableList.
Sorts and TestSort have been updated with small changes. SortableDataWithTracer remains unchanged.
- This version add a new package comparator which contains classes helpful for manipulating comparators. The class LexicographicComparator allows to combine two comparators in a lexicographic way, the class ReverseComparator to reverse the order given by a comparator, and the class TrivialComparator to obtain a trivial comparator on comparable objects. The class TestSort has been modified and two other classes TestLexicographic and People have been added in the default package in order to test the lexicographic comparaison.
Classes from the package sort have not been changes.
- This version implements the model Observer on instances of SortableData. To obtain that an instance of SortableData become observable, we use the class SortableDataObservable which extends java.util.Observable and implements, using delegation, SortableData. Now, a sort is traced by two ways : printing on the standard output using AsciiTracer or using an GUI with WindowTracer. Those tracers both implement java.util.Observer. The class TestSort has been modified. The other classes remain unchanged.
Note the use of an internal class in SortableDataObservable :
SortableDataObservable.Operation which represents the different kind of
operations made on SortableData during a sort.