/**
* This abstract class is intended for objects that can be
* sorted using fixed-range sorting algorithms, such as
* counting sort.
* The class allows one to specify a range of keys that all
* of its instances are allowed to have. It provides methods to check
* if the key is within the specified range.
*
* @author Elena Machkasova, for Data Structures class
*
*/
public abstract class KeyRange {
//lowest and highest are static so that they are they
// are the same for all instances
protected static int lowest;
protected static int highest;
public static void setRange(int low, int high) {
lowest = low;
highest = high;
}
/**
* returns the lowest value of the key range
* @return the lowest value of the key range
*/
public static int getLowest() {
return lowest;
}
/**
* returns the highest value of the key range
* @return the highest value of the key range
*/
public static int getHighest() {
return highest;
}
/**
* The method returns the element's key. It does not
* check if its value is valid.
* @return the key
*/
protected abstract int getKey();
/**
* The method checks if the key is within the valid range
* @return true if the key is within the valid range,
* false otherwise
*/
public boolean verifyKey() {
int key = getKey();
return (! (key < lowest || key > highest));
}
/**
* The method checks the value returned by getKey to make
* sure that it is within the range.
* @return the key if it is within the range
* @throws InvalidKeyException if the key is not within the range
*/
public int getVerifiedKey() {
if (!verifyKey()) throw new InvalidKeyException();
return getKey();
}
/**
* The method sorts an array of KeyRange elements using
* counting sort algorithm.
* @param elements -- the array to be sorted.
*/
public static void countingSort(KeyRange [] elements) {
int [] counts = new int[highest - lowest + 1];
KeyRange [] sorted = new KeyRange[elements.length];
// fill in the code
}
/**
* Checks if the given array of KeyRange elements is sorted
* in non-decreasing order by keys
* @param elements -- the array to be checked
* @return -- true if the array is sorted, false otherwise
*/
public static boolean isSorted(KeyRange [] elements) {
for(int i = 0; i < elements.length - 1; ++i){
if (elements[i].getVerifiedKey() > elements[i + 1].getVerifiedKey()){
return false;
}
}
return true;
}
}
// extending a RuntimeException means that the exception
// doesn't need to be declared or caught
public class InvalidKeyException extends RuntimeException {
}
A modfied Card class that extends KeyRange
public class Card extends KeyRange implements Comparable<Card> {
private String suit;
private int intValue;
private String stringValue;
public Card(String suit, String value){
this.suit = suit;
stringValue = value;
intValue = convertToInt(stringValue);
// checking if the card is in the range
if (!verifyKey()) throw new InvalidKeyException();
}
private int convertToInt(String stringValue) {
String [] faceValues = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
for (int i = 0; i < faceValues.length; i++) {
if (faceValues[i].equals(stringValue)) {
return i + 2;
}
}
System.out.println("Invalid Card Value");
System.exit(0);
return -1;
}
public String getSuit() {
return suit;
}
public String getValue() {
return stringValue;
}
public int getNumericValue() {
return intValue;
}
public int compareTo(Card other){
if (this.intValue < other.intValue) {
return -1;
}else if (this.intValue > other.intValue) {
return 1;
}else {
return 0;
}
}
public String toString() {
return stringValue + " of " + suit;
}
protected int getKey() {
return intValue;
}
}
Testing file for sorting cards.
import java.util.Random;
public class TestKeyRangeCard {
/**
* @param args
*/
public static void main(String[] args) {
KeyRange.setRange(2,14);
// a box of cards fell on the floor at a card factory...
// generate 100 random cards. They *don't* form a deck (some may
// be missing, some repeated).
String [] suits = {"Spades", "Hearts", "Diamonds", "Clubs"};
String [] values = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};
int n = 100; // the number of cards to be sorted
Card [] cards = new Card [n];
Random rand = new Random();
for (int i = 0; i < cards.length; ++i) {
cards[i] = new Card (suits[rand.nextInt(suits.length)],
values[rand.nextInt(values.length)]);
}
System.out.println("Before sorting:");
for (Card card: cards){
System.out.println(card);
}
// sort them using counting sort
KeyRange.countingSort(cards);
System.out.println("After sorting:");
for (Card card: cards){
System.out.println(card);
}
if (KeyRange.isSorted(cards)) {
System.out.println("Congratulations! Your counting sort works");
} else {
System.out.println("Something is wrong with your counting sort");
}
}
}
Another example of a class that extends KeyRange
public class Student extends KeyRange {
private String name;
private int graduationYear;
public Student(String name, int graduationYear) {
this.name = name;
// important: this.graduationYear needs to be set
// before calling verifyKey because
// verifyKey calls getKey that assumes that
// needs graduationYear to be set
this.graduationYear = graduationYear;
if (!verifyKey()) throw new InvalidKeyException();
}
protected int getKey() {
return graduationYear;
}
public String toString() {
return name + " graduating in " + graduationYear;
}
}
Another testing file (more testing code needs to be added)
public class TestKeyRange {
/**
* @param args
*/
public static void main(String [] args) {
KeyRange.setRange(2010,2014);
Student bob = new Student("Bob Smith", 2011);
Student mary = new Student("Mary Andersen", 2012);
System.out.println(bob.getKey());
System.out.println(mary.getKey());
Student [] students = {bob, mary}
KeyRange.countingSort(students);
//Student joe = new Student("Joe Eternal Student", 2050);
//System.out.println(joe.getKey());
}
}