• An Array:
  • A fixed-size "group" of homogeneous objects each of which is identified by an integer index
• Limitations of Arrays:
  • Fixed size
  • Must be indexed by an integer

• Fixed Size:
  • When we don't know even the maximum number of elements in the collection beforehand
• Integer Index:
  • When the indices aren't numbers (e.g., names)
  • When the "important" integers are sparse (e.g., phone numbers)

• Collection:
  • An object that "groups" multiple elements into a single unit
• Examples in Java:
  • List
  • Map

• Aggregation:
  • An object of class A "has-an" object of class B if B is a part of A.
• Obvious Applications to Collections:
  • 
• Less Obvious Applications:
  • 

• Purpose:
  • A "growable" collection with an integer index
• Important Methods:
  • void add(int index, E element)
  • E get(int index)
  • E set(int index, E element)
  • int size()

• Purpose:
  • A "growable" collection that can use any Object as an index/key
• Important Methods:
  • V get(K key)
  • V put(K key, V value)
  • int size()

• An Observation:
  • It must be possible to uniquely identify an Object (since it can be used as the key in a Map)
• Some Internals:
  • Each Object has a hashCode() method that can be used for this purpose (which can be based on the object's address, but needn't be)

• List:
  • ArrayList
  • LinkedList
• Map:
  • HashMap
  • TreeMap

• What Are the Differences?
  • The data structures used (i.e., the way memory is organized)
  • The algorithms used
• Can You Be More Specific?
  • If you want to know more, take CS240 (Data Structures and Algorithms)

• Elements in a Collection:
  • In Java, one can put Object objects in a collection
  • Effectively, this means that you can put any reference type in a collection
• A Shortcoming of this Approach:
  • You are forced to cast the Object to the appropriate type when you retrieve it
  • You may cast it incorrectly and this mistake will only be caught at run-time
• Overcoming this Shortcoming:
  • Use parameterized classes/interfaces

• The Raw ArrayList Class:
  • Contains Object objects
  • An Example:

    	List       a;
    
    	a = new ArrayList();
    	

• Parameterizing an ArrayList :
  • Contains objects of a specified type
  • An Example:

    	List<String>       a;
    
    	a = new ArrayList<String>();
    	

javaexamples/collections/typesafe/TextFormatter.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * A simple class for formatting text messages.
 *
 * This class illustrates the use of the ArrayList
 * class.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 2.0 (Using a type-safe parameterized class)
 */
public class TextFormatter
{

    /**
     * The entry point of the program
     *
     * @param args  The command-line arguments
     */
    public static void main(String[] args)
    {
       int           displayWidth, i, width;
       Scanner       scanner;       
       String        word;
       List<String>  message;          // v2.0


       // Initialization
       displayWidth = 20;
       scanner      = new Scanner(System.in);       

       // Construct a new ArrayList
       message = new ArrayList<String>();  // v2.0


       // Prompt the user to enter the message
       // one word at a time
       do 
       {
          System.out.print("Next word: ");
          word = scanner.nextLine();
          message.add(message.size(), word);
       } 
       while (!word.equals(""));


       System.out.print("\n\n\n");

       // Format the message so that it fits in
       // a fixed-width display
       width = displayWidth;
       for (i=0; i < message.size(); i++) 
       {
          word = message.get(i);         // v2.0

          if (width+word.length()+1 > displayWidth) 
          {
             width = word.length();
             System.out.print("\n");
             System.out.print(word);
          } 
          else 
          {
             width = width + word.length() + 1;
             System.out.print(" "+word+" ");
          }
       }
    }
}
        

• The Raw HashMap Class:
  • Uses Object objects as both the key and the value
  • An Example:

    	Map          h;
    
    	h = new HashMap();
    	

• Parameterizing a HashMap :
  • Uses keys and values with specified types
  • An Example:

    	Map<String, Robot>       h;
    
    	h = new HashMap<String, Robot>();
    	

javaexamples/collections/typesafe/CallerID.java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * A simple class for performing a "Caller ID"
 * (i.e., look up a person's name given their
 * phone number)
 *
 * This class illustrates the use of the HashMap
 * class.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 2.0 (Using a type-safe parameterized class)
 */
public class CallerID
{

    /**
     * The entry point of the program
     *
     * @param args  The command-line arguments
     */
    public static void main(String[] args)
    {
        Scanner                    scanner;        
        Map<String, String>        names;       // v2.0
        String                     id, number;

        scanner = new Scanner(System.in);        

        // Construct a new HashMap
        names = new HashMap<String, String>();     // v2.0


        // Fill the HashMap
        names.put("540-568-1671","Bernstein, D.");
        names.put("540-568-2773","Fox, C.");
        names.put("540-568-6288","Grove, R.");
        names.put("540-568-2774","Harris, A.");
        names.put("540-568-8771","Harris, N.");
        names.put("540-568-8745","Heydari, N.");
        names.put("540-568-2772","Lane, M.");
        names.put("540-568-2727","Marchal, J.");
        names.put("540-568-2775","Mata-Toledo, R.");
        names.put("540-568-2777","Norton, M.");


        // Prompt the user to enter a phone number
        // and then display the appropriate name
        do 
        {
           System.out.print("Phone Number: ");
           number = scanner.nextLine();
           
           id = names.get(number);          // v2.0

           if (id != null) System.out.printf("%s\n", id);
        } 
        while (!number.equals(""));
    }

}
        

• The Issue:
  • Sometimes the key and the value are the same
• Examples:
  • A "paint" application in which you add a bunch of different shapes to the canvas
  • A course-requirements application that needs to keep track of the courses you've taken
• What To Do?
  • You could use a Map but it is better (i.e., clearer) to use a Set (like the HashSet )

The parameters for the class are listed (in order) in the dotted rectangle and are used as types elsewhere.

Note that parameters are not explicitly included in constructors. Note also that bound parameters are included in arguments or return types (e.g., the keySet() method returns a Set of K so it is written as Set<K>). Note finally that Map is not "officially" a Collection (for reasons we will discuss later).

• Parameters of add() (in List) and put() (in Map):
  • Must be an (extension of) Object
• Implication:
  • A List and a Map can only contain class types
  • They can't contain an int, double, etc...

• Integer:
  • Deprecated Constructor: Integer(int value)
  • Factory: Integer.valueOf(int value)
  • Accessor: int intValue()
• Double:
  • Deprecated Constructor: Double(double value)
  • Factory: Double.valueOf(double value)
  • Accessor: double doubleValue()

• Some Observations:
  • Wrapper classes are inconvenient
  • It seems like the process could be handled by the compiler
• The Solution:
  • The compiler will automatically box (i.e., wrap) and unbox (unwrap) values when you use parameterized collections

javaexamples/collections/typesafe/StatisticsCalculator.java

import java.io.*;
import java.util.*;

/**
 * A simple calculator that can be used to calculate
 * descriptive statistics from a sample contained in a file
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 2.0 (Using type-safe generics)
 */
public class StatisticsCalculator
{
    private List<Double>        values;   // v2.0
    

    /**
     * Explicit Value Constructor
     *
     * @param name   The name of the file containing the sample
     */
    public StatisticsCalculator(String name) throws IOException
    {
       double        value;       
       Scanner       in;
    

       // Initialize the ArrayList
       values = new ArrayList<Double>();
       
       // Read the data
       in = new Scanner(new File(name));
       while (in.hasNext())
       {
          value = in.nextDouble();
          values.add(value);          // v2.0 (boxing)
       }
    }
    

    /**
     * Calculates the mean of a sample
     *
     * @return    The mean
     */
    public double mean()
    {
       double        total, value;
       

       total = 0.0;
       
       for (int i=0; i<values.size(); i++)
       {
          value =  values.get(i);    // v2.0 (unboxing)
          total += value;          
       }
       
       return total/((double)values.size());
    }
    

    /**
     * Calculates the sum of the squared residuals [i.e., the
     * sum of (x_i - xbar)^2 ]
     */
    private double ssr()
    {
       double        mean, sum, value;

       mean  = mean();
       
       sum   = 0.0;
       
       for (int i=0; i<values.size(); i++)
       {
          value = values.get(i);     // v2.0  (unboxing)
          sum   += Math.pow((value - mean), 2);
       }
       
       return sum;
    }


    /**
     * Calculates the (biased) variance of a sample
     *
     * @return  The (biased) variance
     */
    public double variance()
    {
       return (1.0/(double)(values.size())) * ssr();       
    }
    
}
        

• OptionalInt and OptionalDouble:
  • May or may not contain a value
• Methods:
  • boolean isPresent()
  • int orElse(int default) and double orElse(double default) return the value if present and the default otherwise

• An Example:

  • 	Map           offerings;
    	List         cs139, cs159;
    
    	offerings = new HashMap();
    
    	cs139 = new ArrayList();
    	cs139.add("Harris, J.A.");
    	cs139.add("Harris, N.L.");
            offerings.put("CS139", cs139);
    
    
    	cs159 = new ArrayList();
            cs159.add("Bernstein");
            cs159.add("Harris, N.L.");
            offerings.put("CS159", cs159);
    	

• An Observation:
  • This is not type safe

javaexamples/collections/typesafe/Courses.java

import java.util.*;


/**
 * An example that uses a parameterized collection of a parameterized
 * collection
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class Courses
{
    /**
     * The entry point
     *
     * @param args    The command line arguments (ignored)
     */
    public static void main(String[] args)
    {
       Map<String, List<String>>    offerings;
       List<String>                 course;
       

       offerings = new HashMap<String, List<String>>();


       
       // Sections of CS139
       course = new ArrayList<String>();
       course.add("Harris, J.A.");
       course.add("Harris, N.L.");
       
       offerings.put("CS139", course);


       
       // Sections of CS159
       course = new ArrayList<String>();
       course.add("Bernstein");
       course.add("Harris, N.L.");
       
       offerings.put("CS159", course);
       

       
       // Sections of CS446
       course = new ArrayList<String>();
       course.add("Bernstein");
       course.add("Fox");
       
       offerings.put("CS446", course);
    }
    
}
        

• Recall:
  • When we discussed specialization we considered an example in which there was an (abstract) SecurityQuotation class and two subclasses, StockQuotation and FutureQuotation
• Two Questions:
  • Should we be able to create a type-safe collection (e.g., an ArrayList) that contains children of both types?
  • Can we (in Java)?

javaexamples/collections/typesafe/SecurityDriver.java (Fragment: 1)

       ArrayList<SecurityQuotation>  quotes;
       

       quotes = new ArrayList<SecurityQuotation>();
       quotes.add(new StockQuotation());
       quotes.add(new FutureQuotation());
        

• Recall:
  • We can assign a StockQuotation object to a variable that is declared to be a SecurityQuotation (because a StockQuotation "is a" SecurityQuotation)
• A Question:
  • Can we assign an ArrayList<StockQuotation> to a variable of type ArrayList<SecurityQuotation>?

javaexamples/collections/typesafe/SecurityDriver.java (Fragment: 2)

       ArrayList<SecurityQuotation>  securities;
       ArrayList<StockQuotation>     stocks;
       

       stocks = new ArrayList<StockQuotation>();

       // This assignment involves incompatible types
       securities = stocks;
        

• Another Part of the Java Lexicon:
  • The ? is called the wildcard character
• Java Syntax for Unbounded Wildcards:
  • Collection<?> variable
• Java Syntax for Bounded Wildcards:
  • Collection<? extends Parent> variable

javaexamples/collections/typesafe/SecurityDriver.java (Fragment: 3)

       ArrayList<? extends SecurityQuotation>  nyse;
       ArrayList<StockQuotation>               temp;
       

       temp = new ArrayList<StockQuotation>();

       nyse = temp;