• An Array:
  • A fixed-size collection of homogeneous objects that are indexed by an integer
• 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 array" with an integer index
• Important Methods:
  • void add(int index, Object element)
  • Object get(int index)
  • int size()

javaexamples/collections/basics/TextFormatter.java

import java.util.ArrayList;
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 1.0
 */
public class TextFormatter
{

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


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

       // Construct a new ArrayList
       message = new ArrayList();


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


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

       // Format the message so that it fits in
       // a fixed-width display
       width = displayWidth;
       for (i=0; i < message.size(); i++) 
       {
          // The generic Object must be cast as a String
          word = (String)(message.get(i));

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

}
        

• Some Convenient Methods:
  • void add(Object element)
  • void clear()
• Some Methods to Avoid For Now:
  • boolean contains(int index, Object element)
  • int indexOf(Object element)

• Purpose:
  • A "growable array" that can use an object as an index/key
• Important Methods:
  • Object get(Object key)
  • Object put(Object key, Object element)
  • int size()
• What Does put() Return:
  • The previous value associated with the key (or null) if there was no such value

javaexamples/collections/basics/CallerID.java

import java.util.HashMap;
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 1.0
 */
public class CallerID
{

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



        scanner = new Scanner(System.in);
        
        // Construct a new HashMap
        names = new HashMap();


        // Fill the Hashtable
        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, H.");
        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.printf("Phone Number: ");
            number = scanner.nextLine();

            id = (String)(names.get(number));

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

}
        

• Parameters of add() (in ArrayList) and put() (in HashMap):
  • A Object
• Implication:
  • An ArrayList and a HashMap can only contain objects
  • They can't contain an int, double, etc...

• Integer:
  • Constructor: Integer(int value)
  • Accessor: int intValue()
• Double:
  • Constructor: Double(double value)
  • Accessor: double doubleValue()

javaexamples/collections/basics/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 1.0
 */
public class StatisticsCalculator
{
    private ArrayList        values;
    

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

       // Initialize the ArrayList
       values = new ArrayList();
       
       // Read the data
       in = new Scanner(new File(name));
       while (in.hasNext())
       {
          value        = in.nextDouble();
          System.out.println(value);
          
          wrappedValue = new Double(value);          
          values.add(wrappedValue);          
       }
    }
    

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

       total = 0.0;
       
       for (int i=0; i<values.size(); i++)
       {
          wrappedValue = (Double)values.get(i);
          value        = wrappedValue.doubleValue();
          
          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;
       Double        wrappedValue;

       mean  = mean();
       
       sum   = 0.0;
       
       for (int i=0; i<values.size(); i++)
       {
          wrappedValue = (Double)values.get(i);
          value        = wrappedValue.doubleValue();
          
          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();       
    }
    
}
        

• Some Observations:
  • Wrapper classes are inconvenient
  • It seems like the process could be handled by the compiler
• The Solution:
  • Autoboxing - the Java compiler will automatically box and unbox in many situations

• The Motivation:
  • They key is normally an Object that uniquely identifies the value Object
  • Sometimes the value Object does not have an attribute (or attributes) that can be used for this purpose
• Some Observations:
  • The Java interpreter has a way of uniquely identifying each object - its address
  • Each Object also has a Object.hashCode() method that can be used for this purpose (which can be based on the address but needn't be)

• The Result:
  • Sometimes the key and the value are the same
• An Example:
  • A "paint" application in which you add a bunch of different shapes to the canvas
• What To Do?
  • You can use a HashMap, but you can also use a HashSet

javaexamples/collections/basics/ShapeCanvas.java (Fragment: 0)

/**
 * A simple GUI component that contains a collection of Shape objects
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class ShapeCanvas extends JComponent
{
    private HashSet       shapes;
    
    /**
     * Default Constructor
     */
    public ShapeCanvas()
    {
       shapes = new HashSet();       
    }

    /**
     * Add a Shape to this canvas
     *
     * @param s   The Shape to add
     */
    public void addShape(Shape s)
    {
       // The Shape is used as the key and the value
       shapes.add(s);
    }
    

    /**
     * Remove a Shape from this canvas
     *
     * @param s   The Shape to remove
     */
    public void removeShape(Shape s)
    {
       shapes.remove(s);       
    }

}
        

• Computers vs. Calculators:
  • Computers can perform the same operation many times
• Programming Languages:
  • Harness this power using loops
• A Problem:
  • Traditional looping requires an understanding of the structure of the collection/aggregate

javaexamples/iterator/ArrayExample.java (Fragment: 1)

       String    city;

       for (int i=0; i < cities.length; i++)
       {
          city = cities[i];
          System.out.println(city);
       }
        

javaexamples/iterator/ArrayListExample.java (Fragment: 1)

       String    city;

       for (int i=0; i < cities.size(); i++)
       {
          city = cities.get(i);
          System.out.println(city);
       }
        

We don't know all of the keys unless we keep them in another collection

• Applications often "loop" over the same collection/aggregate object in many classes and methods
• Changing from one colelction/aggregate to another is, as a result, very inconvenient
• The Iterator design pattern enables us to access the elements of an aggregate object while hiding its internal structure

• Reset its "pointer" (or cursor) to the first element.
• Determine if there are any more elements in the sequence.
• Move its "pointer" to the next element.
• Retrieve the "current" element.

• The Iterator:
  • Iterator
• Some Aggregates:
  • ArrayList
  • HashSet

javaexamples/collections/basics/IteratorExample.java

import java.util.*;

public class IteratorExample
{
    ArrayList         employees;
    //HashSet           employees;    

    public IteratorExample()
    {
       employees = new ArrayList();
       //employees = new HashSet();

       // Populate the collection
    }
    

    public void printEmployees(Collection c)
    {
       Iterator      i;
       
       i = c.iterator();
       while (i.hasNext())
       {
          System.out.println(i.next());          
       }
    }
    
}