Ordering and Priority Queue
There are many computing tasks that require performing some sort of comparison between data objects. A few data types are endowed with a "natural" ordering of their values. The integers have a natural ordering "less or equal to", labeled "<=", defined as follows.
n <= m iff m = n + k, for some non-negative integer k (Note: a rigorous mathematical definition of the set of non-negative integers is beyond the scope of this lecture).
The above natural order of the integers is a concrete instance of an abstract concept called an order relation. An order relation on a set S is a boolean function R on S x S that is
reflexive: R(x, x) is true for all x in S,
anti-symmetric: R(x,y) and R(y,x) implies x = y, for all x, y in S, and
transitive: R(x, y) and R(y, z) implies R(x, z), for all x, y, z in S.
To model order relations that are naturally endowed in certain types of data objects, Java provides an interface called Comparable, which has exactly one method called
int compareTo(T lhs), defined abstractly as
x.compareTo(y) < 0 means x is "less than" y,
x.compareTo(y) == 0 means x is "equal to" y, and
x.compareTo(y) > 0 means y is "less than" x.
For example, the Integer class implements the Comparable interface as follows. If x and y are Integer objects then,
x.compareTo(y) < 0 means x.intValue() < y.intValue(),
x.compareTo(y) == 0 means x.intValue() == y.intValue(), and
x.compareTo(y) > 0 means y.intValue() < x.intValue().
Common data types that have a natural ordering among their values, such as Double, String, Character, all implement Comparable.
Most of the time, the ordering among the data objects is an extrinsic operation imposed on the objects by the user of the objects. For example, the Pizza objects in lecture 2 and homework 1 have no concepts of comparing among themselves, however, the user can impose an ordering on them by comparing their price/area ratios or their profits. To model extrinsic ordering relation, Java provides an interface in the java.util package called Comparator, which has exactly two methods:
int compare(T x, T y), to model the ordering
compare(x, y) < 0 means x is "less than" y,
compare(x, y) == 0 means x is "equal to" y, and
compare(x, y) > 0 means y is "less than" x, and
boolean equals(Object x) to model equality.
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 Comparator to compare the Integer objects.
Implement Comparator to compare the Pizza deal in lecture 2.
Implement Comparator to compare the Pizza profit in homework 1.
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. The column on the left is a visitor on the non-generic version of LRStruct. The column on the right uses Comparator and the generic version of LRStruct..
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 n[0] is 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 n[0] is an Integer to be inserted in order into host. * @return LRStruct */ public Object nonEmptyCase(LRStruct host, Object... n) { int nv = (Integer)n[0]; int fv = (Integer)host.getFirst(); if (nv < fv) { return host.insertFront(n[0]); } else { return host.getRest().execute(this, n[0]); } } } |
import genLRS.*; import java.util.*; public class InsertInOrder<T> implements IAlgo<T, LRStruct<T>, T> { private Comparator<T> _order; public InsertInOrder(Comparator<T> ord) { _order = ord; } /** * Simply inserts the given parameter n at the front. * @param host an empty LRStruct. * @param n n[0] is an Object to be inserted in order into host, * based on the given Comparator. * @return LRStruct<T> */ public LRStruct<T> emptyCase(LRStruct<? extends T> host, T... n) { return ((LRStruct<T>)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 n[0] is an Object to be inserted in order into host, * based on the given Comparator. * @return LRStruct<T> */ public LRStruct<T> nonEmptyCase(LRStruct<? extends T> host, T... n) { if (_order.compare(n[0], host.getFirst()) < 0) { return ((LRStruct<T>)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 RAC called priority queue.
package genRac; import genLRS.*; import genLRS.visitor.*; import java.util.*; /* * Implements a factory for restricted access containers that * return the "highest priority" item. */ public class PQComparatorRACFactory<T> extends ALRSRACFactory<T> { private Comparator<T> _comp; /** * Used when the items in the container are Comparable objects. */ public PQComparatorRACFactory() { _comp = new Comparator<T>() { public int compare(T x, T y) { /* * Intentionally reverse the ordering so that the * largest item will be first. */ return ((Comparable<T>)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<T> comp) { _comp = comp; } /** * Create a container that returns the item with the highest priority * according to a given Comparator. */ public IRAContainer<T> makeRAC() { return new LRSRAContainer<T>(new InsertInOrder<T>(_comp)); } }