Assignment 8

Generic Algorithms

Objectives:generics algorithms, interfaces.A computer science archaeologist has unearthed a high-quality Java algorithm library from themid 1990s. Unfortunately, Java did not support generics at that time. Before the library can be released to the wild, it is your task to improve type-safety by converting the code to use generics. The algorithm library is implemented in class edu.uab.cis.util.Algos(see attached code).

Tasks

Migrate the library to use Java generics (create a new class edu.uab.cs.util.Algos).

Add a tester class edu.uab.cs.util.AlgoTester using the provided Vehicle hierarchy.

Add a class edu.uab.cis.util.AlgoTester, illustrating some tests that compile with the old library, but that would fail to compile with the new library.

Algo.java

package edu.uab.cis;

import java.util.ArrayList; import java.util.List; import java.util.Iterator; import java.util.Comparator;

/** * Implements frequently used algorithms. */ public class Algo { /** * returns a comparator object that uses compareTo of Comparable objects. * * @return a comparator object */ static private Comparator defaultComparator() { return new Comparator() { public int compare(Object one, Object two) { assert one instanceof Comparable;

return ((Comparable)one).compareTo(two); } }; }

/** * Copies all objects from src to tgt, for which the predicate pred holds. * * @param src source list * @param tgt target list * @param pred unary predicate */ static public void copyIf(List src, List tgt, UnaryPredicate pred) { for (Object obj : src) { if (pred.test(obj)) tgt.add(obj); } }

/** * Copies all objects from src to tgt that are greater than yardstick. * * @param src source * @param tgt target * @param yardstick determines if objects in src should be copied to tgt. */ static public void copyIfGreaterThan(List src, List tgt, final Comparable yardstick) { copyIf(src, tgt, new UnaryPredicate() { public boolean test(Object o) { return yardstick.compareTo(o) < 0; } }); }

/** * Finds a maximum object in lst. * * @param lst a list containing non-null references * @param comp comparator defines order between two objects in lst * @return a maximum object in lst; null if the lst is empty */ static public Object findMax(List lst, Comparator comp) { assert lst != null; assert comp != null;

Object max = null; Iterator iter = lst.iterator();

// handle first element if (iter.hasNext()) max = iter.next();

// handle remaining elements while (iter.hasNext()) { assert max != null;

Object cand = iter.next();

if (comp.compare(max, cand) < 0) max = cand; }

return max; }

/** * Finds a maximum object in lst. * * @param lst a list containing non-null references * @return a maximum object in lst; null if the lst is empty */ static public Comparable findMax(List lst) { return (Comparable) findMax(lst, defaultComparator()); }

/** * Adds the smaller of lhs and rhs to dst. * * @param lhs left hand side object * @param rhs right hand side object * @param dst destination list */ static public void storeMin(Comparable lhs, Comparable rhs, List dst) { Comparable min = lhs;

if (min.compareTo(rhs) > 0) min = rhs;

dst.add(min); }

/** * swaps the elements at a and b in lst. * * @param lst a list * @param a first location in lst * @param b second location in lst */ static private void swap(ArrayList objs, int a, int b) { Object tmp = objs.get(a);

objs.set(a, objs.get(b)); objs.set(b, tmp); }

/** * Sorts the elements in lst according to criteria specified in comp. * * @param lst an array list containing non-null references * @param comp comparator defines order between two objects in lst */ static public void selectionSort(ArrayList lst, Comparator comp) { for (int i = 0; i < lst.size(); ++i) { int min = i;

for (int j = i+1; j < lst.size(); ++j) { if (comp.compare(lst.get(min), lst.get(j)) > 0) min = j; }

swap(lst, min, i); } }

/** * Sorts the elements in lst. * * @param lst an array list containing non-null references */ static public void selectionSort(ArrayList lst) { // call selection sort with built-in comparison selectionSort(lst, defaultComparator()); } }

Bike.java

package edu.uab.cis;

public class Bike extends Vehicle { /** * Creates a new Vehicle object. * * @param desc description * @param seats max. number of people * @param gears number of gears */ public Bike(String desc, int seats, int gears) { super(desc, seats);

this.gears = gears; }

/** * Compares this to other. * * @param other some other Bike * @return negative iff this < other * 0 iff this == other * positive iff this > other */ public int compareTo(Object other) { int res = super.compareTo(other);

if (res != 0) return res;

if (other instanceof Bike) { Bike that = (Bike) other;

res = this.gears - that.gears; }

return res; }

/** * Returns a textual description. * * @return a text */ public String toString() { return super.toString() + " " + gears; }

/** gears. */ private int gears; }

MotorVehicle.java

package edu.uab.cis;

public class MotorVehicle extends Vehicle { /** * Creates a new Vehicle object. * * @param desc description * @param seats max. number of people * @param mpg gas mileage */ public MotorVehicle(String desc, int seats, double mpg) { super(desc, seats);

this.mpg = mpg; }

/** * Compares this to other. * * @param other some other MotorVehicle * @return negative iff this < other * 0 iff this == other * positive iff this > other */ public int compareTo(Object other) { int res = super.compareTo(other);

if (res != 0) return res;

if (other instanceof MotorVehicle) { MotorVehicle that = (MotorVehicle) other;

res = this.mpg.compareTo(that.mpg); }

return res; }

/** * Returns a textual description. * * @return a text */ public String toString() { return super.toString() + " " + mpg; }

/** mpg. */ private Double mpg; }

UnaryPredicate.java

package edu.uab.cis;

interface UnaryPredicate { boolean test(Object obj); }

Vehicle.java

package edu.uab.cis;

public class Vehicle implements Comparable { /** secret constructor. */ private Vehicle() {}

/** * Creates a new Vehicle object. * * @param desc description * @param seats max. number of people */ public Vehicle(String desc, int seats) { description = desc; capacity = seats; }

/** * Compares this to other. * * @param other some other Vehicle * @return negative iff this < other * 0 iff this == other * positive iff this > other */ public int compareTo(Object other) { // if the real type is different, just compare the real type Vehicle that = (Vehicle) other; int res = this.capacity - that.capacity;

if (res != 0) return res;

return this.description.compareTo(that.description); }

/** * Returns a textual description. * * @return a text */ public String toString() { return description + " " + capacity; }

/** capacity. */ private int capacity;

/** description. */ private String description; }

Car.java

package edu.uab.cis;

public class Car extends MotorVehicle { /** * Creates a new Vehicle object. * * @param desc description * @param seats max. number of people * @param mpg gas mileage * @param make name of make */ public Car(String desc, int seats, double mpg, String make) { super(desc, seats, mpg);

this.make = make; }

/** * Compares this to other. * * @param other some other Car * @return negative iff this < other * 0 iff this == other * positive iff this > other */ public int compareTo(Object other) { int res = super.compareTo(other);

if (res != 0) return res;

if (other instanceof Car) { Car that = (Car) other;

res = this.make.compareTo(that.make); }

return res; }

/** * Returns a textual description. * * @return a text */ public String toString() { return super.toString() + " " + make; }

/** make. */ private String make; }