Files for Counting Sort, also include abstract classes


/**
 * 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());
	}

}


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.