| << Chapter < Page | Chapter >> Page > |
In most applications, when we implement a
Comparator interface, we only need to override the
compare(...) method and simply inherit the
equals(...) method from
Object .
Implement a
Comparator class that will compare
Integer objects.
Recall the problem of inserting an
Integer object in order into a sorted list of
Integers . Instead of writing an algorithm that only works for
Integer , we can write an algorithm that will work for any
Object that can be compared by some
Comparator . The table below contrasts the insert in order algorithm for Integer and the insert in order algorithm that uses a
Comparator as a strategy (as in strategy pattern) for comparison. Both are algorithms for
LRStruct , the mutable list.
First, let's look at a regular in-order insertion algorithm that works only on
Integer objects because the comparison technique is hard-coded in:
InsertInOrderLRS Visitor class
import lrs.*;
public class InsertInOrderLRS implements IAlgo {public static final InsertInOrderLRS Singleton = new InsertInOrderLRS();
private InsertInOrderLRS() {}
/*** Simply inserts the given parameter n at the front.
* @param host an empty LRStruct.* @param n an Integer to be inserted in order into host.
* @return LRStruct*/
public Object emptyCase(LRStruct host, Object... n) {return host.insertFront(n[0]);}
/*** Based on the comparison between first and n,
* inserts at the front or recurs!* @param host a non-empty LRStruct.
* @param n an Integer to be inserted in order into host.* @return LRStruct
*/public Object nonEmptyCase(LRStruct host, Object... n) {
if (n[0]<(Integer)host.getFirst();) { // could use Integer.compareTo()
return host.insertFront(n[0]);
}else {
return host.getRest().execute(this, n[0]);
}}
}
A visitor to an
LRStruct that performs an in-order insertion, but only for
Integer objects.
Now let's look at how the simple substitution of a
Comparator for the hard-coded comparison allows the otherwise identical code to be used for any objects. All one has to do is to supply the desired
Comparator instance that matches the type of objects stored in the
LRStruct . Here is the implementation of a visitor to an
LRStruct that performs an in-order insertion, for any objects that are comparable with the given
Comparator :
InsertInOrder Visitor class
import lrs.*;
import java.util.*;public class InsertInOrder implements IAlgo {
private Comparator _order;public InsertInOrder(Comparator ord) {
_order = ord;}
/*** Simply inserts the given parameter n at the front.
* @param host an empty LRStruct.* @param n an Object to be inserted in order into host,
* based on the given Comparator.* @return LRStruct
*/public Object emptyCase(LRStruct host, Object... n) {
return host.insertFront(n[0]);
}/**
* Based on the comparison between first and n,* inserts at the front or recurs!
* @param host a non-empty LRStruct.* @param n an Object to be inserted in order into host,
* based on the given Comparator.* @return LRStruct
*/public Object nonEmptyCase(LRStruct host, Object... n) {
if (_order.compare(n[0], host.getFirst())<0) {
return host.insertFront(n[0]);
}else {
return host.getRest().execute(this, n[0]);
}}
}
The
InsertInOrder algorithm given in the above can be used as part of a strategy for a
Restricted Access Container ("RAC") called
priority queue . In the code below, it is assumed that "smaller" objects have higher priority, i.e. will be retrieved from the RAC before "larger" objects. The code also shows how, if the RAC elements are
Comparable objects, that a
Comparator could be used to provide their ordering in the RAC, even to the point of reversing their order if desired.
PQComparatorRACFactory Priority queue implementation
package rac;
import lrs.*;import lrs.visitor.*;
import java.util.*;/*
* Implements a factory for restricted access containers that* return the ``highest priority'' item.
*/public class PQComparatorRACFactory extends ALRSRACFactory {
private Comparator _comp;/**
* Used when the items in the container are Comparable objects.*/
public PQComparatorRACFactory() {_comp = new Comparator() {
public int compare(Object x, Object y) {/*
* Intentionally reverse the ordering so that the* largest item will be first, just to show that it can be done.
*/return ((Comparable)y).compareTo(x);
}};
}/**
* Used when we want to prioritize the items according to a given Comparator.* @param comp the item that is smallest according to comp has the highest
* priority.*/
public PQComparatorRACFactory(Comparator comp) {_comp = comp;
}/**
* Create a container that returns the item with the highest priority* according to a given Comparator.
*/public IRAContainer makeRAC() {
return new LRSRAContainer(new InsertInOrder(_comp));}
}
A priority queue can easily be implemented from a RAC by using a
Comparator .
Notification Switch
Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|