Java 2 API: java.util: Collections

The "Object" superclass

Before we discuss collections, it is important to note that all classes in Java eventually inherit from the Object class (located in the java.lang package). If you declare a class without specifying that it extends another class, Java automatically makes your class a sublass of Object behing the scenes. So the following two declarations are in fact identical:

public class HappyClass {
    //...stuff goes here
}

public class HappyClass extends Object {
    //...stuff goes here
}

The Object super class offers some methods with default implementations that can be overriden by subclasses. Some important ones are clone, equals, hashCode, and toString. The object superclass also provides support for multi-threading with the wait and notify methods.

This feature that everything is an Object is used in the Java collections framework to allow you to put any kind of object type into a collection, since they all inherit from Object at some point, be it directly or indirectly. Now, the only things you can't put into Java collections are primitive types. Since primitive types (e.g. byte, char, int, short, long, float, double, bool) are not classes, they can't be added to collections directly. Instead, you have to wrap them using their corresponding object type. See the example below:

public class PuttingPrimitiveTypesIntoCollectionsDemo {
    public void addIntToCollection(a, List collection) {
        //example of adding a primitive int to a collection
        Integer intA = new Integer(a); //convert the primitive int to an Integer object first
        collection.add(intA); //now you can add the Integer object to the list
    }

    public int retrieveIntFromCollection(List collection, int index) {
        //example of extracting a primitive int from a collection
        Integer intX = (Integer) collection.get(index);
        int x = 0;      
        if (intX != null)
            x = intX.intValue();
        return x;
    } 
}

Note: JDK 1.5 is the first release of Java to support automatic boxing and unboxing of primitive types, so in this version of Java you don't have to go through the trouble of manually doing the conversion shown above. As I'm writing this set of notes, JDK 1.4 and 1.3 are still probably more widely  used than 1.5, so it's worthwhile knowing how this works in these earlier versions of Java.

Java Collections

Most of the classes in the java.util package have to do with managing collections. In this regard, there are a few classes that one uses often:
ArrayList acts as a List and is implemented internally as a dynamically resizable array (size increases geometrically when you run out of space). This means you get roughly O(1) access to any particular index of the array. However, inserting to the start of the array, or iterating over an ArrayList while deleting elements is  O(n). In that case consider using LinkedList instead. When using lists, it's a good idea to hold on to a reference instead of the implementation. That way you can remain open to use a different implementation of that interface later on. To wit:
public class MyBookCollection {
    private List books = new ArrayList(); //better than ArrayList books = new ArrayList()

    public void addBook(Book book) {
        books.add(book);
    }

}
HashMap implements the Map interface. Basically it allows you to store key-value pairs. A map, by its very definition, cannot store the same key twice, but the same value can be associated with multiple keys. Retrieval by key is O(1), but you do waste a fair amount of memory as HashMap uses a hash table internally to represent the data. Also, iterating over all of they key-value pairs in a HashMap is relatively slow. TreeMap is also a reasonable solution. Retrieval is O(log n) and insertion/deletion is O(nlog n). Also, TreeMap implements the SortedMap interface, so if it's important to read the data in sorted order, use TreeMap.
HashSet and TreeSet implement the Set interface. TreeSet, since it is implemented using a balanced tree just like TreeMap, also supports the SortedSet inteface. Sets are generally used less often than the other collections in Java. Sets guarantee that the same object reference will not be added twice, and they provide union and intersection capabilities. Note: There is a difference between two references pointing to the same object and two distinct objects that have the same value. See the "equals" method in the Object class.

Deck Of Cards Example

package ca.ucalgary.conted.introjava.cardgames.utils;

public class Card {
    //suit constants
    public static final int CLUBS = 0;
    public static final int DIAMONDS = 1;
    public static final int HEARTS = 2;
    public static final int SPADES = 3;

    //rank constants
    public static final int TWO = 2;
    public static final int THREE = 3;
    public static final int FOUR = 4;
    public static final int FIVE = 5;
    public static final int SIX = 6;
    public static final int SEVEN = 7;
    public static final int EIGHT = 8;
    public static final int NINE = 9;
    public static final int TEN = 10;
    public static final int JACK = 11;
    public static final int QUEEN = 12;
    public static final int KING = 13;
    public static final int ACE = 14;

    //face constants
    public static final boolean FACE_UP = true;
    public static final boolean FACE_DOWN = false;

    private int suit;
    private int rank;
    private boolean isFaceUp = FACE_DOWN;

    public Card(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    public Card(int suit, int rank, boolean isFaceUp) {
        this(suit, rank);
        this.isFaceUp = isFaceUp;
    }

    public int getSuit() {
        return suit;
    }

    public int getRank() {
        return rank;
    }

    public boolean isFaceUp() {
        return isFaceUp;
    }

    public void setFaceUp() {
        isFaceUp = true;
    }

    public void setFaceDown() {
        isFaceUp = false;
    }

    public String toString() {
        if (!isFaceUp)
            return "*";

        String[] suitsAsStrings = new String[4];
        suitsAsStrings[CLUBS] = "C";
        suitsAsStrings[DIAMONDS] = "D";
        suitsAsStrings[HEARTS] = "H";
        suitsAsStrings[SPADES] = "S";

        String rankAsString = String.valueOf(rank);
        switch (rank) {
            case (11):
                rankAsString = "J";
                break;
            case (12):
                rankAsString = "Q";
                break;
            case (13):
                rankAsString = "K";
                break;
            case (14):
                rankAsString = "A";
                break;
        }

        return rankAsString + suitsAsStrings[suit];
    }

    //when you override the equals method, you should also override hashCode
    public boolean equals(Object obj) {
        Card anotherCard = (Card) obj;

        if (getSuit() == anotherCard.getSuit()
                && getRank() == anotherCard.getRank())
            return  true;
        else
            return false;
    }

    public int hashCode() {
        String cardValue = String.valueOf(getSuit()) + getRank();
        return cardValue.hashCode();
    }
}

//-------------------------------------------------------
package ca.ucalgary.conted.introjava.cardgames.gameofwar;

import ca.ucalgary.conted.introjava.cardgames.utils.Card;
import java.util.Comparator;

public class WarCardComparator implements Comparator {

    //compare imposes a total ordering on collections of Cards.
    public int compare(Object obj1, Object obj2) {
        Card firstCard = (Card) obj1;
        Card secondCard = (Card) obj2;

        if (firstCard.getRank() > secondCard.getRank())
            return 1;
        else if (firstCard.getRank() < secondCard.getRank())
            return -1;
        else
            return 0;
    }
}

//------------------------------------------------------
package ca.ucalgary.conted.introjava.cardgames.gameofwar;

import ca.ucalgary.conted.introjava.cardgames.utils.Card;

import java.util.Stack;
import java.util.Collections;

public class GameOfWar {
    public static void main(String[] args) {
        Card fiveHearts = new Card(Card.HEARTS, Card.FIVE, Card.FACE_UP);
        Card queenDiamonds = new Card(Card.DIAMONDS, Card.QUEEN, Card.FACE_UP);
        Card eightSpades = new Card(Card.SPADES, Card.EIGHT, Card.FACE_UP);
        Card tenClubs = new Card(Card.CLUBS, Card.TEN, Card.FACE_UP);

        Stack deck = new Stack();
        deck.push(fiveHearts);
        deck.push(queenDiamonds);
        deck.push(eightSpades);
        deck.push(tenClubs);

        System.out.print("Original deck: ");
        System.out.println(deck);

        System.out.print("Sorted deck:   ");
        Collections.sort(deck, new WarCardComparator());
        System.out.println(deck);

        System.out.print("Shuffled deck: ");
        Collections.shuffle(deck);
        System.out.println(deck);

        System.out.print("Shuffled deck: ");
        Collections.shuffle(deck);
        System.out.println(deck);

        System.out.print("Shuffled deck: ");
        Collections.shuffle(deck);
        System.out.println(deck);
    }
}