Transcript Chapter 2: Using Objects

Chapter 6: Arrays and Vectors
Presentation slides for
Java Software Solutions
Foundations of Program Design
Second Edition
by John Lewis and William Loftus
Java Software Solutions is published by Addison-Wesley
Presentation slides are copyright 2000 by John Lewis and William Loftus. All rights reserved.
Instructors using the textbook may use and modify these slides for pedagogical purposes.
Arrays and Vectors

Arrays and vectors are objects that help us organize large
amounts of information

Chapter 6 focuses on:
•
•
•
•
•
array declaration and use
arrays of objects
sorting elements in an array
multidimensional arrays
the Vector class
• using arrays to manage graphics
2
Arrays

An array is an ordered list of values
The entire array
has a single name
0
scores
Each value has a numeric index
1
2
3
4
5
6
7
8
9
79 87 94 82 67 98 87 81 74 91
An array of size N is indexed from zero to N-1
This array holds 10 values that are indexed from 0 to 9
3
Arrays


A particular value in an array is referenced using the array
name followed by the index in brackets
For example, the expression
scores[2]
refers to the value 94 (which is the 3rd value in the array)

That expression represents a place to store a single integer,
and can be used wherever an integer variable can

For example, it can be assigned a value, printed, or used in
a calculation
4
Arrays

An array stores multiple values of the same type

That type can be primitive types or objects

Therefore, we can create an array of integers, or an array
of characters, or an array of String objects, etc.

In Java, the array itself is an object

Therefore the name of the array is a object reference
variable, and the array itself is instantiated separately
5
Declaring Arrays

The scores array could be declared as follows:
int[] scores = new int[10];

Note that the type of the array does not specify its size, but
each object of that type has a specific size

The type of the variable scores is int[] (an array of
integers)

It is set to a new array object that can hold 10 integers

See BasicArray.java (page 270)
6
BasicArray
int[] list = new int[LIMIT];
// Initialize the array values
for (int index = 0; index < LIMIT; index++)
list[index] = index * MULTIPLE;
list[5] = 999; // change one array value
for (int index = 0; index < LIMIT; index++)
System.out.print (list[index] + " ");
Declaring Arrays

Some examples of array declarations:
float[] prices = new float[500];
boolean[] flags;
flags = new boolean[20];
char[] codes = new char[1750];
8
Bounds Checking

Once an array is created, it has a fixed size

An index used in an array reference must specify a valid
element

That is, the index value must be in bounds (0 to N-1)

The Java interpreter will throw an exception if an array
index is out of bounds

This is called automatic bounds checking
9
Bounds Checking


For example, if the array codes can hold 100 values, it can
only be indexed using the numbers 0 to 99
If count has the value 100, then the following reference
will cause an ArrayOutOfBoundsException:
System.out.println (codes[count]);

It’s common to introduce off-by-one errors when using
arrays
problem
for (int index=0; index <= 100; index++)
codes[index] = index*50 + epsilon;
Bounds Checking

Each array object has a public constant called length that
stores the size of the array

It is referenced using the array name (just like any other
object):
scores.length

Note that length holds the number of elements, not the
largest index

See ReverseNumbers.java (page 272)
See LetterCount.java (page 274)

11
ReverseNumbers
double[] numbers = new double[10];
System.out.println ("The size of the array: " + numbers.length);
for (int index = 0; index < numbers.length; index++)
{
System.out.print ("Enter number " + (index+1) + ": ");
numbers[index] = Keyboard.readDouble();
}
System.out.println ("The numbers in reverse:");
for (int index = numbers.length-1; index >= 0; index--)
System.out.print (numbers[index] + " ");
LetterCount
int[] upper = new int[NUMCHARS];
int[] lower = new int[NUMCHARS];
char current;
// the current character being processed
int other = 0; // counter for non-alphabetics
System.out.println ("Enter a sentence:");
String line = Keyboard.readString();
// Count the number of each letter occurance
for (int ch = 0; ch < line.length(); ch++) {
current = line.charAt(ch);
if (current >= 'A' && current <= 'Z')
upper[current-'A']++;
else
if (current >= 'a' && current <= 'z')
lower[current-'a']++;
else
other++;
}
LetterCount
// Print the results
System.out.println ();
for (int letter=0; letter < upper.length; letter++)
{
System.out.print ( (char) (letter + 'A') );
System.out.print (": " + upper[letter]);
System.out.print ("\t\t" + (char) (letter + 'a') );
System.out.println (": " + lower[letter]);
}
System.out.println ();
System.out.println ("Non-alphabetic characters: " +
other);
Initializer Lists

An initializer list can be used to instantiate and initialize an
array in one step

The values are delimited by braces and separated by
commas

Examples:
int[] units = {147, 323, 89, 933, 540,
269, 97, 114, 298, 476};
char[] letterGrades = {'A', 'B', 'C', 'D', 'F'};
15
Initializer Lists

Note that when an initializer list is used:
• the new operator is not used
• no size value is specified

The size of the array is determined by the number of items
in the initializer list

An initializer list can only be used in the declaration of an
array

See Primes.java (page 278)
16
Primes
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
System.out.println ("Array length: " + primes.length);
System.out.println ("The first few prime numbers are:");
for (int prime = 0; prime < primes.length; prime++)
System.out.print (primes[prime] + " ");
Arrays as Parameters

An entire array can be passed to a method as a parameter

Like any other object, the reference to the array is passed,
making the formal and actual parameters aliases of each
other

Changing an array element in the method changes the
original

An array element can be passed to a method as well, and
will follow the parameter passing rules of that element's
type
18
Arrays of Objects

The elements of an array can be object references

The following declaration reserves space to store 25
references to String objects
String[] words = new String[25];

It does NOT create the String objects themselves

Each object stored in an array must be instantiated
separately

See GradeRange.java (page 280)
19
GradeRange
String[] grades = {"A", "A-", "B+", "B", "B-", "C+", "C",
"C-", "D+", "D", "D-", "F"};
int[] cutoff = {95, 90, 87, 83, 80, 77, 73, 70, 67, 63, 60, 0};
for (int level = 0; level < cutoff.length; level++)
System.out.println (grades[level] + "\t" + cutoff[level]);
Command-Line Arguments



The signature of the main method indicates that it takes an
array of String objects as a parameter
These values come from command-line arguments that are
provided when the interpreter is invoked
For example, the following invocation of the interpreter
passes an array of three String objects into main:
> java DoIt pennsylvania texas california

These strings are stored at indexes 0-2 of the parameter

See NameTag.java (page 281)
NameTag
public static void main (String[] args)
{
System.out.println ();
System.out.println (" " + args[0]);
System.out.println ("My name is " + args[1]);
System.out.println ();
}
Arrays of Objects

Objects can have arrays as instance variables

Therefore, fairly complex structures can be created simply
with arrays and objects

The software designer must carefully determine an
organization of data and objects that makes sense for the
situation

See Tunes.java (page 282)
See CDCollection.java (page 284)
See CD.java (page 286)


23
Tunes
CDCollection music = new CDCollection ();
music.addCD ("Storm Front", "Billy Joel", 14.95, 10);
music.addCD ("Come On Over", "Shania Twain", 14.95, 16);
music.addCD ("Soundtrack", "Les Miserables", 17.95, 33);
music.addCD ("Graceland", "Paul Simon", 13.90, 11);
System.out.println (music);
music.addCD ("Double Live", "Garth Brooks", 19.99, 26);
music.addCD ("Greatest Hits", "Jimmy Buffet", 15.95, 13);
System.out.println (music);
CD.java
public class CD {
private String title, artist;
private double value;
private int tracks;
public CD (String theTitle, String theArtist, double theValue,
int theTracks) {
title = theTitle;
artist = theArtist;
value = theValue;
tracks = theTracks;
}
public String toString() {
}
}
CDCollection.java
public class CDCollection {
private CD[] collection;
private int count;
private double totalValue;
private int currentSize;
//----------------------------------------------------------------// Creates an initially empty collection.
//----------------------------------------------------------------public CDCollection () {
currentSize = 100;
collection = new CD[currentSize];
count = 0;
totalValue = 0.0;
}
CDCollection cont.
public void addCD (String title, String artist,
double value, int tracks) {
if (count == currentSize)
increaseSize();
collection[count] = new CD (title, artist, value, tracks);
totalValue += value;
count++;
}
private void increaseSize () {
currentSize *= 2;
CD[] temp = new CD[currentSize];
for (int cd = 0; cd < collection.length; cd++)
temp[cd] = collection[cd];
collection = temp;
}
CDCollection cont.
// Returns a report describing the CD collection.
public String toString() {
NumberFormat fmt = NumberFormat.getCurrencyInstance();
String report = "&&&&&&&&&&&&&&&&&&&&&&&&&&&\n";
report += "My CD Collection\n\n";
report += "Number of CDs: " + count + "\n";
report += "Total value: " + fmt.format(totalValue) + "\n";
report += "Average cost: " + fmt.format(totalValue/count);
report += "\n\nCD List:\n\n";
for (int cd = 0; cd < count; cd++)
report += collection[cd].toString() + "\n";
return report;
}
Sorting

Sorting is the process of arranging a list of items into a
particular order

There must be some value on which the order is based

There are many algorithms for sorting a list of items

These algorithms vary in efficiency

We will examine two specific algorithms:
• Selection Sort
• Insertion Sort
29
Selection Sort
Given an array numbers of size length,
1 For index = 0 to length - 1 do
1.1 find min, index of smallest element from index to length - 1
1.2 switch elements at locations index and min
expand 1.1
1.1.1 min = index
1.1.2 for scan = index+1 to length do
1.1.2.1
if (numbers[scan] < numbers[min])
1.1.2.1.1
min = scan;
30
Selection Sort

An example:
original:
smallest is
smallest is
smallest is
smallest is


1:
2:
3:
6:
3
1
1
1
1
9
9
2
2
2
6
6
6
3
3
1
3
3
6
6
2
2
9
9
9
See SortGrades.java (page 289)
See Sorts.java (page 290) -- the selectionSort
method
31
SortGrades
int[] grades = {89, 94, 69, 80, 97, 85, 73, 91, 77, 85, 93};
Sorts.selectionSort (grades);
for (int index = 0; index < grades.length; index++)
System.out.print (grades[index] + " ");
Sorts.java
public class Sorts {
// Sorts the specified array of integers using the selection
// sort algorithm.
public static void selectionSort (int[] numbers) {
int min, temp;
for (int index = 0; index < numbers.length-1; index++) {
min = index;
for (int scan = index+1; scan < numbers.length; scan++)
if (numbers[scan] < numbers[min])
min = scan;
// Swap the values
temp = numbers[min];
numbers[min] = numbers[index];
numbers[index] = temp;
}
}
Insertion Sort

The approach of Insertion Sort:
• Pick any item and insert it into its proper place in a sorted sublist
• repeat until all items have been inserted

In more detail:
• consider the first item to be a sorted sublist (of one item)
• insert the second item into the sorted sublist, shifting items as
necessary to make room to insert the new addition
• insert the third item into the sorted sublist (of two items), shifting as
necessary
• repeat until all values are inserted into their proper position
34
Insertion Sort

An example:
original:
insert 9:
insert 6:
insert 1:
insert 2:

3
3
3
1
1
9
9
6
3
2
6
6
9
6
3
1
1
1
9
6
2
2
2
2
9
See Sorts.java (page 290) -- the insertionSort
method
35
Insertion Sort Code
public static void insertionSort (int[] numbers) {
for (int index = 1; index < numbers.length; index++) {
int key = numbers[index];
int position = index;
// shift larger values to the right
while (position > 0 && numbers[position-1] > key)
{
numbers[position] = numbers[position-1];
position--;
}
numbers[position] = key;
}
}
Sorting Objects

Integers have an inherent order, but the order of a set of
objects must be defined by the person defining the class

Recall that a Java interface can be used as a type name and
guarantees that a particular class has implemented
particular methods

We can use the Comparable interface to develop a generic
sort for a set of objects

See SortPhoneList.java (page 294)
See Contact.java (page 295)
See Sorts.java (page 290)


37
Comparing Sorts

Both Selection and Insertion sorts are similar in efficiency

The both have outer loops that scan all elements, and inner
loops that compare the value of the outer loop with almost
all values in the list

Therefore approximately n2 number of comparisons are
made to sort a list of size n

We therefore say that these sorts are of order n2

Other sorts are more efficient: order n log2 n
38
Two-Dimensional Arrays

A one-dimensional array stores a simple list of values

A two-dimensional array can be thought of as a table of
values, with rows and columns

A two-dimensional array element is referenced using two
index values

To be precise, a two-dimensional array in Java is an array
of arrays

See TwoDArray.java (page 299)
39
TwoDArray
public static void main (String[] args) {
int[][] table = new int[5][10];
// Load the table with values
for (int row=0; row < table.length; row++)
for (int col=0; col < table[row].length; col++)
table[row][col] = row * 10 + col;
// Print the table
for (int row=0; row < table.length; row++) {
for (int col=0; col < table[row].length; col++)
System.out.print (table[row][col] + "\t");
System.out.println();
}
}
Output
0
10
20
30
40
1
11
21
31
41
2
12
22
32
42
3
13
23
33
43
4
14
24
34
44
5
15
25
35
45
6
16
26
36
46
7
17
27
37
47
8
18
28
38
48
9
19
29
39
49
Debugger View
Multidimensional Arrays

An array can have as many dimensions as needed, creating
a multidimensional array

Each dimension subdivides the previous one into the
specified number of elements

Each array dimension has its own length constant

Because each dimension is an array of array references, the
arrays within one dimension could be of different lengths
43
3 dimensional array
int [][][] table3 = { { {1,2}, {3,4} },
{ {5,6,7} , {8}, {9,10} }
};
The Vector Class

An object of class ArrayList is similar to an array in that
it stores multiple values

However, an ArrayList
• only stores objects
• does not have the indexing syntax that arrays have

The methods of the ArrayList class are used to interact
with the elements of a vector

The ArrayList class is part of the java.util package

See Beatles.java (page 304)
45
Beatles
ArrayList band = new ArrayList();
band.add ("Paul");
band.add ("John");
band.add ("Pete");
band.add ("George");
System.out.println (band);
int location = band.indexOf ("Pete");
band.remove (location);
System.out.println (band);
System.out.println ("At index 1: " + band.get(1));
band.add (2, "Ringo");
System.out.println (band);
System.out.println ("Size : " + band.size());
Some ArrayList methods
Boolean add(Object o) : Appends the specified element to the end of this
Vector.
Object get(int index)
Returns the element at the specified position in this Vector.
String toString() :Returns a string representation of this Vector, containing
the String representation of each element
Int indexOf(Object elem) : Searches for the first occurence of the given
argument, testing for equality using the equals method.
Object remove(int index) :
Removes the element at the specified position in this Vector.
int size() : Returns the number of components in this vector.
The ArrayList Class

An important difference between an array and a vector is
that a vector can be thought of as a dynamic, able to change
its size as needed

Each vector initially has a certain amount of memory space
reserved for storing elements

If an element is added that doesn't fit in the existing space,
more room is automatically acquired
48
The ArrayList/Vector Class

The Vector class is implemented using an array

Whenever new space is required, a new, larger array is
created, and the values are copied from the original to the
new array

To insert an element, existing elements are first copied, one
by one, to another position in the array

Therefore, the implementation of Vector in the API is not
very efficient for inserting elements
49
CDCollection using ArrayList
import java.util.*;
public class CDCollection {
private ArrayList collection;
public CDCollection () {
collection = new ArrayList(100);
}
public void addCD (String title, String artist, double value, int tracks) {
CD newcd = new CD (title, artist, value, tracks);
collection.add (newcd);
}
…
public String toString() {
String report = "";
for (int cd = 0; cd < collection.size (); cd++) {
CD currentcd = (CD) collection.get (cd);
report += currentcd.toString() + "\n";
}
// or ….
Iterator it = collection.iterator ();
while (it.hasNext ()) {
CD currentcd = (CD) it.next ();
report += currentcd.toString() + "\n";
}
return report;
}
PhoneBook example


Implement a class that will act like a phone book: it will
contain phone numbers along with their owners
Typical use of the class will look like:
PhoneBook pb = new PhoneBook(10);
pb.add(“cengiz”, “312-290 3395”);
pb.add(“maintenance”, “555 2323 ext 43”);
…..
System.out.println(pb);
String deptNumber = pb.getNumber(“department”);
pb.remove(“nofutur”);
Parallel Array Implementation

Each phone entry consists of a key, the name or owner of
the phone number, and the value, the phone number itself.

We can create two arrays, names and numbers, to store
these two pieces of information, such that numbers[i] is the
phone number corresponding to names[i].

Very similar to CDCollection example

Need sequential scan to find a phone number
// parallel array implementation
class PhoneBook0 {
String[] names;
String[] numbers;
int count;
public PhoneBook0(int initialCapacity) {
names = new String[initialCapacity];
numbers = new String[initialCapacity];
count = 0;
}
public void add(String name, String number) {
if (count == names.length) {
String [] newNames = new String[2 * names.length];
String [] newNumbers = new String[2 * numbers.length];
for(int i =0; i < names.length; i++) {
newNames[i] = names[i];
newNumbers[i] = numbers[i];
}
names = newNames;
numbers = newNumbers;
}
names[count] = name;
numbers[count] = number;
count++;
}
public boolean remove(String name) {
int loc = findName(name);
if (loc != -1) {
names[loc] = names[count - 1];
numbers[loc] = numbers[count - 1];
count--;
return true;
}
else
return false;
}
public String getNumber(String name) {
int loc = findName(name);
if (loc != -1)
return numbers[loc];
else
return null;
}
public String toString() {
String report = "";
for(int i = 0; i < count; i++)
report += names[i] + " : " + numbers[i] + "\n";
return report;
}
private int findName(String name)
{
int loc = count - 1;
while (loc >= 0) {
String currName = names[loc];
if (currName.equals(name))
break;
loc --;
}
return loc;
}
ArrayList Implementation
class PhoneBook1 {
ArrayList names;
ArrayList numbers;
public PhoneBook1(int initialCapacity) {
names = new ArrayList(initialCapacity);
numbers = new ArrayList(initialCapacity);
}
public void add(String name, String number) {
names.add (name);
numbers.add(number);
}
public boolean remove(String name) {
int loc = names.indexOf (name);
if (loc != -1) {
names.remove(loc);
numbers.remove(loc);
return true;
}
else
return false;
}
public String getNumber(String name) {
int loc = names.indexOf (name);
if (loc != -1)
return (String) numbers.get(loc);
else
return null;
}
public String toString() {
String report = "";
Iterator nameit = names.iterator ();
Iterator numberit = numbers.iterator ();
while (nameit.hasNext ()) {
String name = (String) nameit.next();
String number = (String) numberit.next();
report += name + " : " + number + "\n";
}
return report;
}
Parallel Array Implementation Overview


Two separate collection to maintain
Prone to error

What if we want to extend our solution so that there is not
only one phone number, but several variation like home
number, work number, mobile number? What changes do
you need to do?

It would be better if we wrap up all the phone related
information to a separate class : --
class PhoneRecord {
private String name;
private String number;
public PhoneRecord(String name, String number) {
this.name = name;
this.number = number;
}
public String getName() {
return name;
}
public String getNumber() {
return number;
}
public String toString() {
return name + " : " + number;
}
}
// PhoneRecord implementation
class PhoneBook2 {
ArrayList records;
public PhoneBook2(int initialCapacity) {
records = new ArrayList(initialCapacity);
}
public void add(String name, String number) {
records.add( new PhoneRecord(name, number));
}
public boolean remove(String name) {
int loc = findName(name);
if (loc != -1) {
records.remove(loc);
return true;
}
else
return false;
}
public String getNumber(String name) {
int loc = findName(name);
if (loc != -1)
return ((PhoneRecord) records.get(loc)).getNumber();
else
return null;
}
public String toString() {
String report = "";
Iterator it = records.iterator ();
while (it.hasNext()) {
PhoneRecord record = (PhoneRecord) it.next();
report += record.toString () + "\n";
}
return report;
}
private int findName(String name)
{
int loc = records.size () - 1;
while (loc >= 0) {
PhoneRecord currRecord =
(PhoneRecord) records.get(loc);
if (currRecord.getName().equals(name))
break;
loc --;
}
return loc;
}
Array Implementations Overview





Relatively fast insertions
Iterating over the records simple
Records are sorted by their insertion time
If order needs to be preserved, removal is a difficult
process, otherwise deletions are fast, too.
Finding an item needs sequential search, therefore not very
efficient
HashMap implementation


In our implementations, what we really have is just a
mapping from a key to a value.
Unfortunately, our arrays can only map an integer value to
a value :
• Names[i] ~ i  element at location I
It would be nice if arrays could be indexed by other types as
well :
numbers[“cengiz”] ~ “cengiz”  “312-290 3395”
HashMap Methods

public Object put(Object key, Object value)
• Associates the specified value with the specified key in this map. If
the map previously contained a mapping for this key, the old value
is replaced.

public Object get(Object key)
• Returns the value to which the specified key is mapped in this
identity hash map, or null if the map contains no mapping for this
key.
HashMap map = new HashMap();
Map.put(“cengiz”, “312-290 3395”);
….
String cengizNo = (String) map.get(“cengiz”);
//hashmap implementation
class PhoneBook3 {
public HashMap records;
public PhoneBook3(int initialCapacity) {
records = new HashMap(initialCapacity);
}
public void add(String name, String number) {
records.put (name, number);
}
public boolean remove(String name) {
String number = (String) records.remove (name);
return number != null;
}
public String getNumber(String name) {
String number = (String) records.get(name);
return number;
}
public String toString() {
String report = "";
Set entrySet = records.entrySet();
Iterator it = entrySet.iterator ();
while (it.hasNext()) {
Map.Entry entry = (Map.Entry) it.next();
report += (String) entry.getKey() + " : " +
(String)entry.getValue() + "\n";
}
return report;
}
Alternative Iteration
public String toString() {
String report = "";
Set keys = records.keySet();
Iterator it = keys.iterator ();
while (it.hasNext()) {
String key = (String) it.next();
String value = (String) records.get(key);
report += (String) key + " : " + value + "\n";
}
return report;
}