Arrays,

List<E> and Iterator<E>

COMP 401, Spring 2014
Lecture 7
1/30/2014

Array Review
Ordered sequence of elements

Elements must be of the same type

Fixed size once created
Valid indices from 0 to length-1

Arrays are reference types

Have elds and methods like other object types

In parUcular, size of array is available through length
eld

Declaring variables that can hold an array

reference
type[] variable_name

CreaUng Empty Arrays

With new keyword as in:

int[] iarray = new int[10];

Point[] parray = new Point[7];

What do we mean by empty?

For array of value of types

Elements get default value

0 for numeric
false for boolean

For array of reference types

Elements set to null

You need to set each element a`er you create the array to point to either
exisUng or new object.

Can create and iniUalize array with literal syntax as in:

int[] iarray = new int[] {1, 2, 6, 8, 10};

Point[] parray = new Point[] {new Point(0,0), new Point(1,2), new
Point(3,4)};

Arrays as Reference Types

Same reference, same array

ImplicaUon for arrays passed to methods

When an array is passed to a method, any changes that the

method makes to its elements is permanent.

PotenUal danger with object state

If holding object state in an array, easy to accidentally break

encapsulaUon and expose object state to alteraUon.

Array cloning

Easy way to create a shallow copy of an array

Just call clone() method

Result will be a new array of same size with same values or

references

MulUdimensional Arrays
MulUdimension array is simply an array of arrays
Fill out dimensions le` to right.
int[][] marray = new int[5][];!
for(int i=0; i<5; i++) {!
marray[i] = new int[10];!
}!

Each Sub-dimension can have independent size.

SomeUmes known as as a ragged or uneven array

int[][] marray = new int[5][];!
for (int i=0; i<5; i++) {!
marray[i] = new int[i+1];!
}!

If each sub-dimension is same size, can create with a single new statement
int[][] marray = new int[5][10];

Arrays uUlity class

Arrays is a library of useful funcUons for
manipulaUng arrays
Note s in Arrays
Like Math class, all methods are staUc

binarySearch
sort
lling and copying subranges
hnp://docs.oracle.com/javase/7/docs/api/java/uUl/Arrays.html

Java CollecUon Framework

Arrays are not resizeable

O`en need a collecUon of items that acts like an array that can
grow or shrink

Java CollecUon Framework

In package java.uUl
Denes a set of interfaces for resizeable collecUons
List

Ordered by integer index

Set

Unordered, no duplicate elements

Map

Indexed by an arbitrary key

SomeUmes known as a dicUonary

Provides a set of classes that implement these interfaces in

specic ways
Examples for List: ArrayList, LinkedList,

Java CollecUons as Generics

Java CollecUon Framework interfaces and
classes are generic
Interface/class name is modied to specify type in
the collecUon.
ArrayList<E> implements List<E>
E is a placeholder
Must be lled in by an actual type name when used.

For now, just want to have working knowledge of

List as an interface and ArrayList as a collecUon
that implements the interface.

List<E>
boolean add(E val)

Adds val to end of list and returns true

void add(int index, E val)

Inserts val as posiUon index

E get(int index)

Returns element at posiUon index

E set(int index, E val)

Sets element at posiUon index, returns original value for element

E remove(int index)

Removes element at posiUon index, list shrinks

int size()

Returns current size of list

boolean isEmpty()

Same as tesUng size() == 0

E[] toArray(E[] a)

Converts list to an array given current elements

ArrayList<E>
ArrayList<E> is an implementaUon of List<E>
Uses an array internally

lec07.ex1

Design SituaUon
Suppose we have an object that encapsulates
some sort of collecUon.
SongLibrary
A collecUon of songs in an iTunes-like system

PolygonModel
A collecUon of polygons in a 3D modeling system

Design SituaUon
Now suppose we have code outside of this
collecUon object that needs to examine each
element of the underlying collecUon in turn.
SongFilter
A object that represents a search criteria to be applied
to a collecUon of songs

An intersecUon test in which each polygon of a

PolygonModel needs to be evaluated

Strategy 1: Provide access to

underlying collecUon as an array.
SongLibrary
public Song[] getSongs()

PolygonModel
public Polygon[] getPolygons()

Drawbacks?
May have to do a lot of work to create the array
CollecUon may be result of generaUve process
There may be no end to the collecUon.
Or the collecUon may be large so we dont want to provide
the whole thing at once.

Strategy 2: Provide index access to

each underlying item in collecUon
SongLibrary

public int getNumSongs();

public Song getSong(int song_idx);

PolygonModel

public int getNumPolygons();

public Polygon getPolygon(int polygon_idx);

Drawbacks?

Doesnt help with generaUve collecUons

Imposes restricUons on how collecUon is represented
and linearized
Deteriorates encapsulaUon

Strategy 3: Internalize a cursor

SongLibrary
public void resetSongCursor();
public Song getNextSong();
public boolean isCursorAtEnd();

Drawbacks?
Cant have two traversals going at the same Ume.
But, this does come close.

Iterator Design Panern

Provide a way to access the elements of an
aggregate object sequenUally without
exposing its underlying representaUon
Gang of Four, Design Pa8erns

Consider:
for(int i=0; i<slist.size(); i++) {!
Song next_song = slist.get(i);!
// Do something with next_song.!
}!

Iterator Design Panern

Iterator object encapsulates details of item traversal.
Understands details of the underlying collecUon.
Manages order of items

May want a traversal that is not just rst to last.

Underlying collecUon may not have a natural linear order.

Manages state of traversal

Allows traversal to be picked up again later.

AssumpUon: underlying collecUon is not changed or

modied while the traversal is occurring.

Iterator should be able to detect this and signal an error

Variant of panern will have iterator provide methods that
modify underlying collecUon safely

Components of Iterator Panern

CollecUon object is iterable

Provides a method that returns an object that acts as

an iterator.

Iterator object provides access to the elements in

turn.
At the very least:

A method to test whether more items exist.

A method to retrieve the next item.

Other possible features:

Methods that remove an item safely.

Method to peek at the next item.
Method to reset the traversal.

Java Iterator Panern Interfaces

The Java CollecUons Framework denes two
generic interfaces for supporUng the iterable
design panern
Implemented by the various collecUon types such
as List<E>, Map<E>, Set<E>, etc.

Iterable<E>
Interator<E> iterator()

Iterator<E>

Iterator<E>
boolean hasNext()
Are we at the end of the traversal?

E next()
Get the next item of the traversal.
Throws a runUme excepUon if no next item.

void remove()
Not supported by all implementaUons.
Safely removes last item retrieved by next() from
the underlying collecUon.

Iterable examples
lec07.ex2
Main1
Simple use

Main2
Parallel iterators

Main3
Simultaneous iterators

Main4
for each syntacUc sugar

Main1 Visualized (1)

ArrayList<Song> slist

Words and Guitar

Dig Me Out

Jenny

Linle Babies

Buy Her Candy

Main1 Visualized (2)

Iterator<Song> iter

ArrayList<Song> slist

list
next_idx

Words and Guitar

Dig Me Out

Jenny

Linle Babies

Buy Her Candy

Main1 Visualized (3)

Iterator<Song> iter

ArrayList<Song> slist

list
next_idx

public boolean hasNext() {

if (next_idx < list.size()) {

return true;
}
return false;
}
NOTE: This may or may not be how
it is actually implemented, but it is
eec:vely what is going on.

Words and Guitar

Dig Me Out

Jenny

Linle Babies

Buy Her Candy

Main1 Visualized (4)

Iterator<Song> iter

ArrayList<Song> slist

list
next_idx

public Song next() {

Song s = list.get(next_idx);
next_idx++;
return s;
}
NOTE: Real implementaUon would rst
check to see if hasNext() is sUll true and
throw an excepUon otherwise.

Words and Guitar

Dig Me Out

Jenny

Linle Babies

Buy Her Candy

lec07.ex2.Main2
Parallel iteraUon
Processes two dierent lists
Iterator associated with each.
Iterators advance unevenly

lec07.ex2.Main3
Simultaneous iteraUon
2 Iterators, 1 List
Insert your own joke here.

for - each
Java provides syntacUc sugar for a parUcularly
common use of iterators.
for-each loop
Supposing e_coll is Iterable<E>, then these are
equivalent:
Iterator<E> iter = e_coll.iterator();!
while (iter.hasNext()) {!
!E elem = iter.next();!
!// Do something with element!
}!
!

lec07.ex2.Main4

for (E elem : e_coll) {!

!// Do something with elem!
}!

for-each with Array

The for-each construct also works with Arrays
Useful if you need to process the elements of
an array but do not need the index.
String[] names = new String[] {Amy, Mike,!
Cameron, Claire};!
for (String n : names) {!
System.out.println(n);!

}!

lec07.ex3
A more complicated iterator
Can build iterators that do things other than just
go through every item.
Prior examples made use of Iterator<E> built into
List<E>, here we are going to implement our own
specialized version of Iterator<E>