Transcript Generics and the ArrayList Class

Review Generics and the
ArrayList Class
Generics




Added to Java v5.0
Generics = class and method definitions
may include parameters for types
Generic program – type parameter
allows one to write code that applies to
any class
Ex. list of items of type T

When T=Double, it’s a list of Doubles, etc.
ArrayList
Advantage:




Can grow or shrink (arrays can’t)
import java.util.ArrayList;
See
http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html
ArrayList

Disadvantage:
1.
2.
3.
Less efficient than arrays
Lacks familiar [] syntax (Java limitation,
supported by C++)
Base type must be an object (not
primitive) type

Can have ArrayList of Integer but can’t have
an ArrayList of int.


Less of a problem w/ automatic boxing and
unboxing
Java limitation, supported by C++
ArrayList class

Define an ArrayList of Strings:


ArrayList<String> list = new ArrayList<String>();
Define an ArrayList of Employees:

ArrayList<Employee> empList
= new ArrayList<Employee>( 20 );

Initial capacity is specified as 20.
ArrayList class

Set an element:


list.set( 12, “Hi, Mom.” );
Get an element:


System.out.println( list.get( 12 ) );
String s = list.get( 5 );
ArrayList class

Add an element: add( value ) form




list.add( “One” );
list.add( “Two” );
list.add( “Three” );
“One” is at position 0, “Two” is at position
1, and “Three” is at position 2.
ArrayList class

Add an element: add( i, value ) form






i must be a used position or the first
unused position
list.add( “One” );
list.add( “Two” );
list.add( “Three” );
list.add( 1, “Fred” );
“One” is at position 0, “Fred is at position
1, “Two” is at position 2, and “Three” is at
position 3.
ArrayList class

size() method
for (int i=0; i<list.size(); i++) {
System.out.println( list.get(i) );
}
ArrayList class methods
ArrayList class methods

public ArrayList<Base_Type>( int initialCapacity )

public ArrayList<Base_Type>()

initial capacity is 10
ArrayList class methods

Array-like methods

public Base_Type set ( int index, Base_Type newElement )


where 0<=index<size() (or exception)
public Base_Type get ( int index )

where 0<=index<size() (or exception)
ArrayList class methods

Methods to add elements

public boolean add ( Base_Type newElement )
 adds the new element to the end
 size() increases by 1
 capacity increases if necessary
ArrayList class methods

Methods to add elements

public void add ( int index, Base_Type newElement )





0<=index<=size()
when index==size(), inserts at end
size() increases by 1
capacity increases if necessary
when 0<=index<size(), current elements at
index move to index+1, at index+1 move to
index+2, …, at size()-1 move to size()
ArrayList class methods

Methods to remove elements

public Base_Type remove ( int index )



0<=index<size() (or exception)
Removes element at index; shifts to the left
remaining elements at index+1 … size()-1.
protected void removeRange ( int fromIndex, int toIndex )

Removes elements with index i s.t.
fromIndex<=i<toIndex; shifts to the left
remaining elements at toIndex … size()-1
ArrayList class methods

Methods to remove elements

public boolean remove( Object theElement )



if found then removes the first occurrence of
theElement; shifts the remaining elements to the
left; size() becomes size()-1; returns true.
if not found then returns false.
public void clear ( )

Removes all elements; size() becomes 0
ArrayList class methods

Search methods

public boolean contains ( Object target )



public int indexOf ( Object target )



Uses equals() method of target
True if ArrayList contains target; false otherwise.
Uses equals() method of target
Returns index of first occurrence of target in ArrayList; -1
otherwise.
public int lastIndexOf ( Object target )

Same as above except index of last occurrence is
returned.
ArrayList class methods

Memory management (size & capacity)

public boolean isEmpty ( )

True if empty; false otherwise.

public int size ( )

Returns number of elements in ArrayList
public void ensureCapacity ( int newCapacity )
 Increases the capacity (if necessary)

public void trimToSize ( )


Reduces capacity to current size
ArrayList class methods

Make a copy

public Object[] toArray ( )


Public<Type> Type[] toArray ( Type[] a )




Returns an array of list elements (in order).
Returns an array of list elements (in order).
If list will fit in array a, it will be used;
remaining elements of a will be null.
If list won’t fit in array a, a new array will be
created and used.
public Object clone ( )

Returns a shallow copy of the ArrayList.
ArrayList class methods

Equality

public boolean equals ( Object other )

True only when both are of the same size, and
both have the same elements (in the same
order).
for-each loop
for (Array_Base_Type var : Collection_Object)
Statement;

Let myList be an ArrayList of Strings.
for (String element : myList)
System.out.println( element );
for-each loop

The for-each loop also works with
arrays:
// Returns the sum of the elements of a
int sum ( int[] a ) {
int result = 0;
for (int item : a)
result += item;
return result;
}
Generics
Generics




Classes and methods can have a type
parameter (actually, more than one).
The type parameter can be any
reference (class) type.
(started with Java version 5.0; in C++
as well but much restricted in Java)
Generic class = parameterized class =
class with a parameter for a type
Generic methods
public class Utility {
…
public static<T> T getMidpoint ( T[] a ) {
return a[ a.length/2 ];
}
public static<T> T getFirst ( T[] a ) {
return a[0];
}
…
}
Generic methods
public class Utility {
public static<T> T getMidpoint ( T[] a ) {
return a[ a.length/2 ];
}
public static<T> T getFirst ( T[] a ) {
return a[0];
}
}
//usage:
String midString = Utility.<String>getMidPoint( b );
double firstNumber = Utility.<Double>getFirst( c );
Generic (parameterized)
classes
public class Sample<T> {
private T data;
public void setData ( T newData ) {
data = newData;
}
public T getData ( ) {
return data;
}
}
Generic (parameterized)
classes
public class Sample<T> {
private T data;
public void setData ( T newData ) {
data = newData;
}
public T getData ( ) {
return data;
}
}
//usage:
Sample<String> object = new Sample<String>();
object.setData( “Hello” );
Generic class for ordered pairs
Pair<String> secretPair
= new Pair<String>( “Happy”, “Day” );
Pair<Integer> rollOfDice
= new Pair<Integer>( new Integer(2),
new Integer(3) );
Pet male = new Pet();
Pet female = new Pet();
Pair<Pet> breedingPair
= new Pair<Pet>( male, female );
Defining the ordered pair class
public class Pair<T> {
private T first;
private T second;
public Pair ( ) {
first = null;
second = null;
}
public Pair ( T f, T s ) {
first = f;
second = s;
}
…
}
Defining the ordered pair class
public class Pair<T> {
private T first;
private T second;
…
//These are suggested by our author.
//Why are they bad?
public T getFirst ( ) { return first; }
public T getSecond ( ) { return second; }
…
}
Defining the ordered pair class
public class Pair<T> {
private T first;
private T second;
…
//These are suggested by our author.
//Why are they bad?
//potential privacy leaks!
public T getFirst ( ) { return first; }
public T getSecond ( ) { return second; }
…
}
Defining the ordered pair class
public class Pair<T> {
private T first;
private T second;
…
public boolean equals ( Object other ) {
if (other==null)
return false;
if (getClass() != other.getClass())
return false;
Pair<T> o = (Pair<T>)other;
return first.equals(o.first) && second.equals(o.second);
}
…
}
More then one type parameter
can be specified
Pair<String,Integer>
p = new Pair<String,Integer>( “Kyle Jones”,
new Integer(123456789) );
Defining the ordered pair class
public class Pair<T1,T2> {
private T1 first;
private T2 second;
public Pair ( ) {
first = null;
second = null;
}
public Pair ( T1 f, T2 s ) {
first = f;
second = s;
}
…
}
Defining the ordered pair class
public class Pair<T1,T2> {
private T1 first;
private T2 second;
…
public T1 getFirst ( ) { return first; }
public T2 getSecond ( ) { return second; }
…
}
Defining the ordered pair class
public class Pair<T1,T2> {
private T1 first;
private T2 second;
…
public boolean equals ( Object other ) {
if (other==null)
return false;
if (getClass() != other.getClass())
return false;
Pair<T1,T2> o = (Pair<T1,T2>)other;
return first.equals(o.first) && second.equals(o.second);
}
…
}
Bounds for type parameters

Say I wish to restrict my type
parameter T to only those things that
implement the Comparable interface.


Can I do this?
What happens if I use the compareTo()
method without stating this restriction?
Bounds for type parameters

Say I wish to restrict my type
parameter T to only those things that
implement the Comparable interface.

Can I do this?


Yes.
What happens if I use the compareTo()
method without stating this restriction?

A compiler error occurs.
Bounds for type parameters

Example of stating this restriction:
public class Pair<T extends Comparable> {
…
}
The keyword extends is used rather
than implements because T must be
a class (not an interface).
Multiple bounds


Multiple bounds may also be specified.
For example,
public class AnotherGeneric<
T1 extends Employee & Comparable,
T2 extends Comparable> {
…
}

But only 1 may be a class. The rest
must be interfaces. Why?
Problem 1



In the sport of diving, seven judges award a
score between [0.0,10.0]. The highest and
lowest scores are discarded. The remaining
scores are added together. The sum is then
multiplied by the degree of difficulty [1.2,3.8]
for that dive. The result is then multiplied by
0.6 to determine the diver’s score.
Write a program that inputs the degree of
difficulty and the 7 judges’ score, and outputs
the diver’s score.
You are required to use an ArrayList of
Double for the judges’ scores.
Problem 2




Write a program that uses an ArrayList of parameter type
Contact to store a database of contracts.
The Contract class should store the contact’s first and last
name, phone number, and email address. Add appropriate
accessor and mutator methods.
Your program should present a textual menu that allows the
user to add a contact, display all contacts, search for a specific
contact and displays it, or search for a specific contact and give
the user the option to delete it. The searches should find any
contact where any member variable contains a target search
string. For example, if “elmore” is the search target then any
contact where the first name, last name, phone number, or
email address contains “elmore” should be returned for display
or deletion.
Use the “for-each” loop to iterate through the ArrayList.
Problem 3



Many GPS’ can record waypoints. The waypoint
marks the coordinates of a location on a map along
with a timestamp. Our GPS stores waypoints in
terms of an (X,Y) coordinate on a map together with
a timestamp t that records the number of seconds
that have elapsed since the unit was turned on.
Write a program that allows the user to enter as
many waypoints as desired, storing each in an
ArrayList of a class that you design.
As waypoints are entered, calculate the average
speed of the trip so far. (The distance between (0,0)
to (1,0) is 0.1 miles.)
Problem 4





Write a generic class, MyMathClass, with a type
parameter T where T is a numeric object type (e.g.,
Integer, Double, or any class that extends
java.lang.Number).
Add a method named standardDeviation that takes
an ArrayList of type T and returns as a double the
standard deviation of the values in the ArrayList.
Use the doubleValue() method in the Number class to
retrieve the value of each number as a double.
Your program should generate a compile-time error if
your standard deviation method is invoked on an
ArrayList that is defined for non-numeric elements
(e.g., String).
Additionally, use the for-each in the
standardDeviation method.
Problem 5





Create a generic class with a type parameter that simulates
drawing an item at random out of a box. This class could be
used for simulating a random drawing.
For example the box might contain Strings representing names
written on a slip of paper, or the box might contain Integers
representing a random drawing for a lottery based on numeric
lottery picks.
Create an add method that allows the user of the class to add
an object of the specified type along with an isEmpty method
that determines whether or not the box is empty.
Finally, your class should have a drawItem method that
randomly selects an object from the box and returns it. If the
user attempts to draw an item out of an empty box, return null.
Write a main method that tests your class. To generate a
random number x, where 0<=x<=1, use x = Math.random();.