Transcript ArrayList, Iterator

CS 340
CS 340 DATA
STRUCTURES
Lecture: ArrayList, Iterator
1
CS 340
2
Containers Illustration
import java.util.*;
public class PrintingContainers {
static Collection fill(Collection c) {
c.add(“dog”); c.add(“dog”); c.add(“cat”);
return c;
}
static Map fill(Map m) {
m.put(“dog”, “Bosco”); m.put(“dog”, “Spot”); m.put(“cat”, “Rags”);
return m;
}
public static void main(String[] args) {
System.out.println(fill(new ArrayList())); // toString() used
System.out.println(fill(new HashSet()));
System.out.println(fill(new HashMap()));
}
}
CS 340
3
Containers Illustration
• The arguments and return types of fill() are the
general interface types, for generality.
• The results look like this:
[dog, dog, cat]
[cat, dog]
{cat=Rags, dog=Spot}
• Elements of Sets and keys of Maps are unique,
and ordered (here, lexicographically).
• Lists hold things in the order in which you enter
them.
CS 340
4
Java Containers Hold “Objects”
• All the container classes are defined (by Sun) to hold
(references to) Objects.
• So, the exact type of an object is lost.
• This is far less safe than ordinary arrays, but is more
powerful.
• If you know what type of thing went into the container, you
can cast it to the correct type.
CS 340
Eckel’s Cats’n’Dogs
public class Cat {
private int catNumber;
Cat(int i) { catNumber = i; }
void print() {
System.out.println(“Cat #” + catNumber);
}
}
public class Dog {
private int dogNumber;
Dog(int i) { dogNumber = i; }
void print() {
System.out.println(“Dog #” + dogNumber);
}
}
5
CS 340
Cats’n’Dogs (cont.)
import java.util.*;
public class CatsAndDogs {
public static void main(String[] args) {
ArrayList cats = new ArrayList();
for (int i = 0; i < 7; i++)
cats.add(new Cat(i));
// here’s trouble
cats.add(new Dog(8));
for(int i = 0; i < cats.size(); i++)
( (Cat) cats.get(i) ).print();
}
}
6
CS 340
7
Cats’n’Dogs (cont.)
• A Dog in the cats ArrayList is perfectly legal.
• The compiler has no way of knowing this is wrong.
• At runtime, when the Dog is cast to a Cat, trouble occurs
(giving an exception).
• (Note the extra set of parentheses in the cast.)
CS 340
A Type-Conscious ArrayList
import java.util.*;
public class CatList { // no Dogs allowed
private ArrayList list = new ArrayList();
public void add(Cat c) {
list.add(c);
}
public Cat get(int index) {
return (Cat) list.get(index);
}
public int size() { return list.size(); }
}
8
CS 340
Iterators For Collections
• The Iterator interface specifies
• boolean hasNext()
• Object next()
• void remove()
• You just have to be careful
• to check hasNext() before using next()
• to not modify the Collection while iterating, except by using
remove()
9
CS 340
10
Simple Iterator Example
ArrayList cats = new ArrayList();
for (int i = 0; i < 7; i++)
cats.add(new Cat(i));
Iterator e = cats.iterator();
while (e.hasNext())
( (Cat)e.next()).print();
• We get the iterator by asking the ArrayList for one.
• On creation, it is positioned “just before the beginning” of
the ArrayList.
CS 340
11
Let’s Be Clear On This!
Iterator e = cats.iterator();
while (e.hasNext())
( (Cat)e.next()).print();
ArrayList cats
When e is here,
hasNext() returns
false.
CS 340
12
Another Example
class Printer {
static void printAll(Iterator e) {
while(e.hasNext())
System.out.println(e.next());
}
• There is no knowledge about the type of thing being
iterated over.
• This also shows the power of the “toString() idea”.
CS 340
13
Collection Interface Methods
• boolean add(Object)
• boolean addAll(Collection)
• void clear()
• boolean contains(Object)
• boolean containsAll(Collection)
• boolean isEmpty()
• Iterator iterator()
“optional”
CS 340
14
Collection Interface Methods
• boolean remove(Object)
• boolean removeAll(Collection)
• boolean retainAll(Collection)
• int size()
• Object[] toArray()
• Object[] toArray(Object[] a)
“optional”
CS 340
15
What’s Missing?
• All the methods that use indexes:
• boolean add(int, Object)
• boolean addAll(int, Collection)
• Object get(int)
• int indexOf(Object)
• Object set(int, Object)
• Why? Sets (HashSet, TreeSet) have their own
way of ordering their contents. But ArrayList and
LinkedList have these methods, since they
are…lists.
CS 340
Collections Example
public class AABattery {
public String toString() { return "AABattery"; }
}
public class NineVoltBattery {
public String toString() { return "NineVoltBattery"; }
}
public class RollOfRibbon {
public String toString() { return "RollOfRibbon"; }
}
public class PaperClip {
int i;
PaperClip(int i) { this.i = i; }
public String toString() { return "PaperClip(" + i + ")"; }
}
16
CS 340
Collections Example (cont.)
public class BandAid {
public String toString() { return "BandAid"; }
}
public class Box {
ArrayList moreStuff = new ArrayList();
public String toString() {
String s = new String("Box");
s += moreStuff;
return s;
}
}
17
CS 340
Collections Example (cont.)
public class BoxOfPaperClips {
ArrayList clips = new ArrayList();
public String toString() {
String s = new String("BoxOfPaperClips");
s += clips;
return s;
}
}
18
CS 340
Collections Example (cont.)
public class JunkDrawer {
ArrayList contents = new ArrayList();
public void fillDrawer() {
contents.add(new RollOfRibbon());
contents.add(new AABattery());
contents.add(new NineVoltBattery());
BoxOfPaperClips boxOfClips = new BoxOfPaperClips();
for (int i = 0; i < 3; i++)
boxOfClips.clips.add(new PaperClip(i));
contents.add(boxOfClips);
Box box = new Box();
box.moreStuff.add(new AABattery());
box.moreStuff.add(new BandAid());
contents.add(box);
contents.add(new AABattery());
}
19
CS 340
20
Collections Example (cont.)
public static void main(String[] args) {
JunkDrawer kitchenDrawer = new JunkDrawer();
kitchenDrawer.fillDrawer();
System.out.println(kitchenDrawer.contents);
}
}
This prints
[RollOfRibbon, AABattery, NineVoltBattery,
BoxOfPaperClips[PaperClip(0), PaperClip(1), PaperClip(2)],
Box[AABattery, BandAid], AABattery]
CS 340
21
Removing Stuff
void takeAnAABattery() {
boolean b = contents.remove(new AABattery());
if (b)
System.out.println("One AABattery removed");
}
• This doesn’t work at all!
• You need to have a reference to a battery actually
in the drawer.
• How do you figure out if something is an
AABattery?
CS 340
22
Using RTTI
boolean takeAnAABattery() {
Iterator i = contents.iterator();
Object aa = null;
// initialize, or compiler complains
while(i.hasNext()) {
if ( (aa = i.next()) instanceof AABattery ) {
contents.remove(aa);
return true;
}
}
return false;
}
CS 340
23
Containers Are Good, But…
• Everything in a container is “just an Object.”
• If you aren’t sure what’s in there, and its location, then
finding what you want can be tedious.
• Can we do better?
CS 340
A “More Organized” Drawer
public class MarthaStewartDrawer {
ArrayList contents = new ArrayList();
ArrayList aaBatteries = new ArrayList();
public void fillDrawer() {
contents.add(new RollOfRibbon());
AABattery a1 = new AABattery();
AABattery a2 = new AABattery();
contents.add(a1);
aaBatteries.add(a1);
//add all the rest…
contents.add(a2);
aaBatteries.add(a2);
}
24
CS 340
Remove An Entire Collection
boolean takeAllAABatteries() {
return contents.removeAll(aaBatteries);
}
public static void main(String[] args) {
MarthaStewartDrawer kitchenDrawer
= new MarthaStewartDrawer();
kitchenDrawer.fillDrawer();
System.out.println(kitchenDrawer.contents);
if (kitchenDrawer.takeAllAABatteries())
System.out.println("All AABatteries removed");
System.out.println(kitchenDrawer.contents);
}
}
25
CS 340
26
Or, Remove Everything Except...
boolean leaveOnlyAABatteries() {
return contents.retainAll(aaBatteries);
}
• This is actually the “set intersection” of contents with
aaBatteries.
• Note, however, that this removes the AABatterys in the
Box…
CS 340
27
Specialized Collections
• The List interface:
• Gives you the Collection interface, plus more
• Insertion order is preserved
• You can “index into” a List
• The concrete types are ArrayList and LinkedList.
• The Set interface:
• Just the Collection interface, but with specialized
behavior
• Insertion order isn’t preserved.
• The concrete types are HashSet and TreeSet.
28
CS 340
Lists Produce ListIterators
interface
Iterator
AbstractCollection
interface
ListIterator
interface
List
interface
Set
<<instantiate>>
AbstractList
ArrayList
interface
Collection
<<instantiate>>
AbstractSequentialList
LinkedList
AbstractSet
HashSet
interface
SortedSet
TreeSet
CS 340
Operational Efficiencies
• ArrayList
• Holds data internally as an array (duh!)
• Random access is fast, just “index into” the array
• Insertion (except at the end) is very slow
• LinkedList
• Random access is slow (but provided for)
• Insertion anywhere is fast (once you are there!)
29
CS 340
30
GENERIC COLLECTIONS
CS 340
31
Generic Collections
 The statement
List<String> myList = new
ArrayList<String>();
uses a language feature called generic collections or
generics
 The statement creates a List of String; only
references of type String can be stored in the list
 String in this statement is called a type parameter
 The type parameter sets the data type of all objects
stored in a collection
CS 340
32
Generic Collections (cont.)
 The general declaration for generic collection is
CollectionClassName<E> variable =
new CollectionClassName<E>();
 The <E> indicates a type parameter
 Adding a noncompatible type to a generic collection will
generate an error during compile time
 However, primitive types will be autoboxed:
ArrayList<Integer> myList = new ArrayList<Integer>();
myList.add(new Integer(3)); // ok
myList.add(3); // also ok! 3 is automatically wrapped
in an Integer object
myList.add(new String("Hello")); // generates a type
incompatability
error
CS 340
33
Why Use Generic Collections?
• Better type-checking: catch more errors, catch them
earlier
• Documents intent
• Avoids the need to downcast from Object
CS 340
34
ARRAYLIST APPLICATIONS
Slides adopted from: CS 146: Data Structures and
Algorithms © R. Mak
35
Primitive Types and Reference Types
• Java has primitive types and reference types.
• Primitive types are int, short, long, byte , float, double,
char, and boolean.
36
Primitive Types and Reference Types
• Reference types (AKA object types) are for objects that
are created with the new operator.
• Java objects are always referred to by pointers.
Object, Integer,
Float, Date, System, ArrayList,
Hashtable
• Built-in reference types include
• Object is the root of all reference types
in the Java type hierarchy.
• An array is a reference type.
• You can define custom reference types.
_
37
Array1: Sort an Array of Integers
• Main:
public static void main(String[] args)
{
int numbers[] = new int[] {5, 1, 9, 4, 5, 0, 7, 6};
Primitive int data.
System.out.print("Before sorting:"); print(numbers);
sort(numbers);
System.out.print(" After sorting:"); print(numbers);
}
• Print:
private static void print(int elements[])
{
for (int elmt : elements) {
System.out.print(" " + elmt);
}
System.out.println();
}
38
Array2: Use an ArrayList
• Main:
public static void main(String[] args)
{
ArrayList numbers = new ArrayList();
numbers.add(new Integer(5));
numbers.add(new Integer(1));
numbers.add(new Integer(9));
numbers.add(new Integer(4));
numbers.add(new Integer(5));
numbers.add(new Integer(0));
numbers.add(new Integer(7));
numbers.add(new Integer(6));
Integer objects.
System.out.print("Before sorting:"); print(numbers);
sort(numbers);
System.out.print(" After sorting:"); print(numbers);
}
• An ArrayList can only store instances (objects) of a
reference type such as Integer, not primitive type data
such as int.
39
Array2: Use an ArrayList
• Print:
private static void print(ArrayList elements)
{
for (Object elmt : elements) {
System.out.print(" " + ((Integer) elmt).intValue());
}
System.out.println();
}
• A “raw” ArrayList stores Object data.
• Object is the base of all Java reference types.
• Therefore, we must coerce each Object element to Integer with
a type cast: (Integer) elmt
• Class Integer has an intValue() method:
((Integer) elmt).intValue()
40
Dangers of Using Raw ArrayList
• Since a raw ArrayList holds Object data, and Object
is the root of all Java reference types, nothing prevents us
from doing this:
ArrayList numbers = new ArrayList();
numbers.add(new Integer(5));
numbers.add(new Integer(1));
numbers.add(new Integer(9));
numbers.add(new Integer(4));
numbers.add(new Date());
numbers.add(new Integer(0));
numbers.add(new Integer(7));
numbers.add(new Integer(6));
• What happens at run time?
CS 146: Data Structures and Algorithms
© R. Mak
41
Array3: Use ArrayList<Integer>
public static void main(String[] args)
{
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(new Integer(5));
numbers.add(new Integer(1));
Now the compiler will prevent us
numbers.add(new Integer(9));
from adding anything other than
numbers.add(new Integer(4));
Integer data to the array list.
numbers.add(new Integer(5));
numbers.add(new Integer(0));
numbers.add(new Integer(7));
numbers.add(new Integer(6));
System.out.print("Before sorting:"); print(numbers);
sort(numbers);
System.out.print(" After sorting:"); print(numbers);
}
42
Array3: Use ArrayList<Integer>
private static void print(ArrayList<Integer> elements)
{
for (Integer elmt : elements) {
System.out.print(" " + elmt.intValue());
}
System.out.println();
}
We no longer need to coerce
element data to Integer
because that’s the only allowable
data type in ArrayList<Integer>.
43
Boxing and Unboxing
• Boxing
• We “wrap” an int value in an Integer object:
Integer obj = new Integer(3);
• Unboxing
• We “unwrap” an int value from an Integer object:
int i = int obj.intValue()
• Java does autoboxing/unboxing as necessary, so we don’t
have to explicitly do it in our code.
_
44
Array4: Autobox/Unbox
public static void main(String[] args)
{
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(1);
Java will autobox each int value
numbers.add(9);
to an Integer object before
numbers.add(4);
adding it to the array list.
numbers.add(5);
numbers.add(0);
numbers.add(7);
numbers.add(6);
System.out.print("Before sorting:"); print(numbers);
sort(numbers);
System.out.print(" After sorting:"); print(numbers);
}
45
Array4: Autobox/Unbox
private static void print(ArrayList<Integer> elements)
{
for (Integer elmt : elements) {
System.out.print(" " + elmt);
}
System.out.println();
Auto-unbox the int value
}
from an Integer object.
46
Comparisons Among Other Object Types
• If a reference class implements the Comparable
interface, then you can compare instances (objects) of
that class to each other.
• You have to write (implement)
the interface’s compareTo() method.
• For example, we can define shape objects such as
squares, rectangles, and circles and compare their areas.
_
47
Abstract Class SimpleShape
public abstract class SimpleShape implements Comparable
{
public abstract float area();
public int compareTo(Object other)
{
return (int) (this.area() - ((SimpleShape) other).area());
}
}
Comparable is a raw interface. Type casting needed.
• Implements the Comparable interface.
• It implements the interface’s compareTo() method.
• Returns a negative, zero, or positive
int value
if the comparison is less than, equal to,
or greater than, respectively.
• Subclasses will implement method area().
48
Subclass Square
• Subclass Square implements method area().
public class Square extends SimpleShape
{
private float width;
public Square(float width)
{
this.width = width;
}
public float area()
{
return width*width;
}
}
49
Subclass Rectangle
• Subclass Rectangle has its implementation
of method area().
public class Rectangle extends SimpleShape
{
private float width, height;
public Rectangle(int width, int height)
{
this.width = width;
this.height = height;
}
public float area()
{
return width*height;
}
}
50
Subclass Circle
• Subclass Circle has its implementation
of method area().
public class Circle extends SimpleShape
{
private static final float PI = 3.1415926f;
private float radius;
public Circle(float radius)
{
this.radius = radius;
}
public float area()
{
return PI*radius*radius;
}
}
51
Array5: SimpleShape Objects
public static void main(String[] args)
{
ArrayList<SimpleShape> shapes = new ArrayList<>();
shapes.add(new Square(5));
shapes.add(new Rectangle(3, 4));
shapes.add(new Circle(2));
System.out.print("Before sorting:"); print(shapes);
sort(shapes);
System.out.print(" After sorting:"); print(shapes);
}
52
Array5: SimpleShape Objects
private static void print(ArrayList<SimpleShape> elements)
{
for (SimpleShape elmt : elements) {
System.out.print(" " + elmt);
}
System.out.println();
}
53
Array6: Comparable<SimpleShape>
• Type casting no longer needed!
public abstract class SimpleShape implements Comparable<SimpleShape>
{
public abstract float area();
public int compareTo(SimpleShape other)
{
return (int) (this.area() - other.area());
}
}
54
Arrays are Covariant
• Square is a subclass of class SimpleShape, therefore
Square objects are type compatible with SimpleShape
objects.
• Java arrays are covariant, which means that in this case,
a Square[] array is type compatible with a
SimpleShape[] array.
_
55
Array7: Covariant Arrays
public static void main(String[] args)
{
SimpleShape shapes[] = new SimpleShape[] {
new Square(5),
new Rectangle(3, 4),
new Circle(2)
};
System.out.println("Total area: " + totalArea(shapes));
Square squares[] = new Square[] {
new Square(5),
new Square(3),
new Square(2)
};
We can pass a Square[].
System.out.println("Total area: " + totalArea(squares));
}
Array8: ArrayList Types are Not
Covariant
56
• This will not compile.
private static float totalArea(ArrayList<SimpleShape> elements)
{
float total = 0;
for (SimpleShape elmt : elements) {
total += elmt.area();
}
return total;
}
public static void main(String[] args)
{
ArrayList<Square> squares = new ArrayList<>();
squares.add(new Square(5));
squares.add(new Square(3));
Cannot pass an ArrayList<Square>
squares.add(new Square(2));
to an ArrayList<SimpleShape>.
System.out.println("Total area: " + totalArea(squares));
}
57
Array9: Fix the Noncovariance Problem
private static float totalArea(ArrayList<? extends SimpleShape> elements)
{
float total = 0;
for (SimpleShape elmt : elements) {
total += elmt.area();
}
return total;
}
public static void main(String[] args)
{
ArrayList<Square> squares = new ArrayList<>();
squares.add(new Square(5));
squares.add(new Square(3));
squares.add(new Square(2));
System.out.println("Total area: " + totalArea(squares));
}
58
Arrays are not good enough
int [ ] arr = new int[ 10 ];
...
// Later on we decide arr needs to be larger.
int [ ] newArr = new int[ arr.length * 2 ];
for( int i = 0; i < arr.length; i++ )
newArr[ i ] = arr[ i ];
arr = newArr;
CS 340
59
Implementing ArrayList.add(E)(cont.)
If size is less than capacity, then to append a new item
1.
2.
3.
insert the new item at the position indicated by the value of
size
increment the value of size
return true to indicate successful insertion
CS 340
60
Implementing ArrayList.add(int index,E
anEntry)
To insert into the middle of the array, the values at the
insertion point are shifted over to make room, beginning at
the end of the array and proceeding in the indicated order
CS 340
61
remove Method
• When an item is removed, the items that follow it must be
moved forward to close the gap
• Begin with the item closest to the removed element and
proceed in the indicated order
CS 340
Collection interface
1 public interface Collection<AnyType>
extends Iterable<AnyType>
2 {
3
int size( );
4
boolean isEmpty( );
5
void clear( );
6
boolean contains( AnyType x );
7
boolean add( AnyType x );
8
boolean remove( AnyType x );
9
java.util.Iterator<AnyType> iterator( );
10 }
62
CS 340
Iterator interface
1 public interface Iterator<AnyType>
2 {
3
boolean hasNext( );
4
AnyType next( );
5
void remove( );
6 }
63
CS 340
64
Printing a collection BI (Before Iterators )
1 public static <AnyType> void print( Collection<AnyType>
coll )
2 {
3
for( AnyType item : coll )
4
System.out.println( item );
5 }
CS 340
65
Printing a collection AI (After Iterators )
1 public static <AnyType> void print( Collection<AnyType>
coll )
2 {
3
Iterator<AnyType> itr = coll.iterator( );
4
while( itr.hasNext( ) )
5
{
6
AnyType item = itr.next( );
7
System.out.println( item );
8
}
9 }