lesson 7-Arrays & Vectors

7. Arrays and Vectors

To be able to use

arrays and vectors to

collect objects

To implement partially

filled arrays

To be able to pass

arrays to methods

To learn about

common array

algorithms

To build classes

containing arrays and

vectors

To learn how to use

two-dimensional

arrays

Arrays

An array is a collection

of data items of the

same type.

Every element of the

collection can be

accessed separately

by using index.

In Java, array indexing

starts from 0.

Array can be

constructed using

double[ ] data = new

double[10];

An Array Reference

and an Array

Using Arrays to Store

Data

To access the fifth

element in an array,

we use

data[4] = 35.5;

System.out.println

(“The price = ” + data

[4]);

sum = sum + data[4];

double[ ] data; // error :

not initialized

data[0] = 10.5; // assign

a value to data[0]

Bounds Error

double[ ] data = new

double[10];

// we can access data

[0], data[1], … data[9]

data[10] = 35.5; //

cause

ArrayIndexOutOfBound

sException

Size of the array:

arrayRefName.length

double[ ] data = new

double[10];

for (int i = 0; i <
data.length; i++)
if (data[i] < lowest)
lowest = data[i];
Don’t combine array
access and index
increment
x = v[i++]; => x = v[i]; i+

+;

Array Initialization

int[] primes = new int

[5];

primes[0] = 2; primes

[1] = 3; primes[2] = 5;

primes[3] = 7; primes

[4] = 11;

// better to use the

following

int[ ] primes = {2, 3, 5,

7, 11};

Copying Arrays

Reference

double[] data = new

double[10];

// … fill array

double[] prices;

prices = data; // copy

reference of array

Make a true copy of

array

double[] prices = new

double[data.length];

for (int j = 0; j <
data.length; j++)
prices[j] = data[j];
Better if we use the
static
System.arrayCopy
method
System.arrayCopy
(from, fromStart, to,
toStart, count);
System.arrayCopy
(data, 0, prices, 0,
data.length);
Partially Filled Arrays
When we need to set
the size of an array
before you know how
many elements there
are, we can make an
array that is large
enough and partially fill
it.
final int DATA_LENGTH =
1000;
double[] data = new
double[DATA_LENGTH];
then keep a variable
that tells how many
elements are actually
used
int dataSize = 0; // for
collect size of array
and increment this
variable every time
data is added to the
array
double price =
console.readDouble();
data[dataSize] = price;
dataSize++;
Remember! Not to
access the data over
the datasize
for (int j=0; j <
dataSize; j++) // not
data.length
System.out.println(data
[j]);
and not to overfill the
array
if (dataSize <
data.length) // OK
{ data[dataSize] =
price;
dataSize++;
}
else // Array is full
{ System.out.println
(“Sorry, array is full”);
}
If the array fills up, we
can create a new,
larger array; copy all
elements into the new
array; and then attach
the new array to the
old array variable.
if (dataSize >= data.length)

{ //

double[] newData = new

double[2 * data.length];

// copy data

System.arrayCopy(data,

0, newData, 0,

data.length);

//create new reference for

"new data" ่

data = newData;

}

Suppose we want to

write a program that

reads a set of prices

offered by 10 vendors

for a particular product

and then prints them,

marking the lowest

one.

public class BestPrice

{ public static void

main(String[] args)

{ final int DATA_LENGTH =

1000;

double[] data = new

double[DATA_LENGTH];

int dataSize = 0;

// read data

ConsoleReader

console = new

ConsoleReader

(System.in);

boolean done = false;

while (!done)

{ System.out.println

("Enter price, 0 to

quit:");

double price =

console.readDouble();

if (price == 0) // end of

input

done = true;

else if (dataSize <
data.length)
{ // add price to data
array
data[dataSize] = price;
dataSize++;
}
else // array is full
{ System.out.println
("Sorry, the array is
full.");
done = true;
}
}
// compute lowest
price
if (dataSize == 0)
return; // no data
double lowest = data
[0];
for (int i = 1; i <
dataSize; i++)
if (data[i] < lowest)
lowest = data[i];
// print out prices,
marking the lowest
one
for (int i = 0; i <
dataSize; i++)
{ System.out.print(data
[i]);
if (data[i] == lowest)
System.out.print(" <--
lowest price");
System.out.println();
}
}
}
Array Parameters and
Return Values
The method to
compute the average
of an array of floating-
point numbers
public static double
average(double[] data)
{ if (data.length == 0)
return 0;
double sum = 0;
for (int j = 0; j <
data.length; j++)
sum = sum + data[j];
return sum /
data.length;
}
double[] prices =
{ 10.5, 24.5, 30.5, 10.0,
50.4 };
System.out.println
(“Price average = ” +
average(prices));
Array Parameters
When an array is
passed to a method,
the array parameter
contains a copy of the
reference to the
argument array.
A method can modify
the entries of any array
that you pass to it.
The method can return
an array if the returning
result consists of a
collection of values of
the same type.
A method can return an
array
public static int[]
randomData(int length,
int n)
{ Random generator =
new Random();
int[] data = new int
[length];
for (int j = 0; j <
data.length; j++)
data[j] =
generator.nextInt(n);
return data;
}
Array Algorithms
Finding a Value: want
to know the price of
first product that has
price lower or equal
1000
double [] prices;
double targetPrice = 1000;
int j = 0;
boolean found = false;
while (j < prices.length
&& !found)
{ if (prices[j] <=
targetPrice)
found = true;
else
j++;
}
if (found)
System.out.println(“Item”
+ j + “ has a price of” +
prices[j]);
Counting: want to
know the number of
product that has price
lower or equal 1000
double [] prices;
double targetPrice = 1000;
int count = 0;
for (int j = 0; j <
prices.length; j++)
{ if (prices[j] <=
targetPrice)
count++;
}
System.out.println(count
+ “ computers.”);
Removing an Element
from an Unordered
Array
If we want to remove
an element from an
unordered array, we
simply overwrite the
element to be
removed with the last
element of the array.
However, an array
cannot be shrunk to
get rid of the last
element, so we have
to used the technique
of a partially filled
array.
Removing an Element :
Array not sorted
public class Remove1
{ public static void
main(String[] args)
{ ConsoleReader
console = new
ConsoleReader
(System.in);
String[] staff = new
String[5];
staff[0] = "Harry"; staff
[1] = "Romeo"; staff[2]
= "Dick";
staff[3] = "Juliet"; staff
[4] = "Tom";
int staffSize =
staff.length;
print(staff, staffSize);
System.out.println
("Remove which
element? (0 - 4)");
int pos =
console.readInt();
// overwrite the
removed element with
the last element
staff[pos] = staff
[staffSize - 1];
staffSize--;
print(staff, staffSize);
}
/**
Prints an array of
strings
@param s the string
array
@param sSize the
number of strings in
the array
*/
public static void print
(String[] s, int sSize)
{ for (int i = 0; i < sSize;
i++)
System.out.println(i + ":
" + s[i]);
}
}
Remove an Element
from an Ordered Array
After removing an
element, we have to
move all elements
beyond the element to
be removed by one
slot.
Removing from an
Ordered Array
public class Remove2
{ public static void
main(String[] args)
{ ...
int staffSize =
staff.length;
print(staff, staffSize);
System.out.println
("Remove which
element? (0 - 4)");
int pos =
console.readInt();
// shift all elements
above pos down
for (int i = pos; i <
staffSize - 1; i++)
staff[i] = staff[i + 1];
staffSize--;
print(staff, staffSize);
}
}
Inserting an Element
Suppose we want to
insert an element in
the middle of an array,
we must move all
elements beyond the
insertion location by
one slot.
When we insert an
element, we start
moving at the end of
an array, move that
element, then go to
the one before it. This
operation is in reverse
order from removing
operation.
public class Insert
{ public static void
main(String[] args)
{ String[] staff = new
String[6];
staff[0] = “Mary”;
staff[1] = “Ben”;
staff[2] = “Sandy”;
staff[3] = “Janet”;
staff[4] = “Peter”;
int staffSize =
staff.length - 1;
System.out.print
("Insert before which
element? (0 - 4) ");
int pos =
console.readInt();
// shift all element
after pos up by one
for (int i = staffSize; i >

pos; i--)

staff[i] = staff[i - 1];

// insert new element

into freed slot

staff[pos] = "New,

Nina";

staffSize++;

print(staff, staffSize);

}

Parallel Arrays, Arrays

of Objects

and Array as Object

Data

When we want to

analyze a data set that

contains more than

one data item, such as

a data set that contains

the names, prices, and

quality of a collection

of products.

We want to look for

products that give

good quality at low

price.

The problem with this

program is that it

contains three arrays

of the same length.

Bestdata.java

public class BestData

{ public static void

main(String[] args)

{ final int DATA_MAX =

500;

String[] name = new

String[DATA_MAX];

double[] price = new

double[DATA_MAX];

int[] score = new int

[DATA_MAX];

int Size = 0;

// read data from

console

ConsoleReader

console = new

ConsoleReader

(System.in);

Boolean done = false;

while (!done)

{ System.out.println

(“Enter name or leave

blank when done: ”);

String inLine =

console.readLine();

if (inLine == null ||

inLine.equals(“ ”))

done = true;

else if (Size < DATA_
MAX)
{ name[Size] = inLine;
System.out.println
(“Enter price: “);
inLine =
console.readLine();
price[Size] =
Double.parseDouble
(inLine);
System.out.println
(“Enter score: “);
inLine =
console.readLine();
score[Size] =
Integer.parseInt
(inLine);
Size++;
}
else
{ System.out.println
(“Sorry, the array is
full. “);
done = true;
}
}
// compute best buy
if (Size == 0) return; //
no data
double best = score[0]
/ price[0];
for (int j = 0; j < Size; j+
+)
if (score[j] / price[j] >

best)

best = score[j] / price

[j];

final int COLUMN_WIDTH

= 30;

for (int j = 0; j < Size; j+
+)
{ System.out.print
(name[j]);
int pad = COLUMN_
WIDTH - name[j].length();
for (int k = 1; k < = pad; k+
+)
System.out.print(“ “);
System.out.print(“ $” +
price[j] +“ score = “ +
score[j]);
if (score[j] / price[j] ==
best)
System.out.print(“ <--
best buy “);
System.out.println();
}
}
}
Parallel Arrays
The problem with
Bestdata.java is that it
contains three parallel
arrays namely name[j],
price[j], and score[].
We must ensure that
the arrays always have
the same length and
that each slice is filled
with values that
actually belong
together.
We can solve this
problem by turning this
concept into class.
Product.java
class Product
{
private String name;
private double price;
private int score;
public Product(String n,
double p, int s)
{ name = n;
price = p;
score = s;
}
public String getName
()
{ return name;
}
public double getPrice
()
{ return price;
}
public int getScore()
{ return score;
}
}
Bestproduct.java
public class
BestProduct
{ public static void
main(String[] args)
{ final int DATA_MAX =
500;
Product[] data = new
Product[DATA_MAX];
int Size = 0;
// read data from
console
ConsoleReader
console = new
ConsoleReader
(System.in);
Boolean done = false;
while (!done)
{ Product p =
readProduct(console);
if (p == null)
done = true;
else if (Size < DATA_
MAX)
{ data[Size] = p;
Size++;
}
else
{
System.out.println
(“Sorry, the array is
full.”);
done = true;
}
}
// compute best buy
if (Size == 0) return; //
no data
double best = data[0]
.getScore() / data[0]
.getPrice();
for (int j = 1; j < Size; j+
+)
{ double ratio = data[j]
.getScore() / data[j]
.getPrice();
if (ratio > best)

best = ratio;

}

// print out data

for (int j = 0; j < Size; j+

+)

{ printProduct(data[j]);

if (data[j].getScore() /

data[j].getPrice() ==

best)

System.out.print(“ <--

best buy “);

}

}

public static Product

readProduct

(ConsoleReader in)

{ System.out.println

(“Enter name or leave

blank when done:”);

String name =

in.readLine();

if (name == null ||

name.equals(“ “))

return null;

System.out.println

(“Enter price: “);

String inLine =

in.readLine();

double price =

Double.parseDouble

(inLine);

System.out.println

(“Enter score: “);

inLine = in.readLine();

int score =

Integer.parseInt

(inLine);

return new Product

(name, price, score);

}

public static void

printProduct(Product p)

{ final int WIDTH = 30;

System.out.print

(p.getName());

int pad = WIDTH –

p.getName().length;

for (int j = 1; j <= pad; j+

+)

System.out.print(“ “);

System.out.print(“ $” +

p.getPrice() + “ score =

“ +

p.getScore());

}

}

Example:

PolygonTest.java

Arrays as Object Data

import

java.applet.Applet;

import

java.awt.Graphics;

import

java.awt.Graphics2D;

import

java.awt.geom.Line2D;

import

java.awt.geom,Point2D

;

public class

PolygonTest extends

Applet

{ public void paint

(Graphics g)

{ Graphics2D g2 =

(Grahpics2D) g;

Polygon triangle = new

Polygon(3);

triangle.add(new

Point2D.Double(40, 40)

);

triangle.add(new

Point2D.Double(120,

160));

triangle.add( new

Point2D.Double(20,

120));

double x = 200;

double y = 200;

double r = 50;

Polygon pentagon =

new Polygon(5);

for (int j = 0; j < 5; j++)

pentagon.add(new

Point2D.Double(

x + r * Math.cos(2 *

Math.PI * j / 5),

y + r * Math.sin(2 *

Math.PI * j / 5)));

triangle.draw(g2);

pentagon.draw(g2);

}

}

// Polygon class

definition

class Polygon

{ public polygon(int n)

{ corners = new

Point2D.Double[n];

cornerCount = 0;

}

public void add

(Point2D.Double p)

{ if (cornerCount <

corners.length)

{ corners[cornerCount]

= p;

cornerCount++;

}

}

public void draw

(Graphics2D g2)

{ for (int j = 0; j <

cornerCount; j++)

{ Point2D.Double from

= corners[j];

Point2D.Double to =

corners[(j+1) %

corners.length];

g2.draw(new

Line2D.Double(from, to);

}

}

private Point2D.Double

[] corners;

private int

cornerCount;

}

Example

To generate a triangle,

we can use the

following segment of

code:

Polygon triangle = new

Polygon(3);

triangle.add(new

Point2D.Double(40,40))

;

triangle.add(new

Point2D.Double

(120,160));

triangle.add(new

Point2D.Double(20,120)

);

Another kind of

geometric shape is

called a regular

polygon which has all

sides of the same

length.

A regular n-gon with

center (x,y) and radius

r has n corners, c0, c1,

…, cn-1, where

ci = (x+r•cos(2p i/n), y

+r•sin(2p i/n))

A regular polygon can

be generated by:

Polygon pentagon =

new Polygon(5);

for (int j = 0; j < 5; j++)

pentagon.add(new

Point2D.Double(

x +r*Math.cos

(2*Math.PI*j/5),

y+r*Math.sin

(2*Math.PI*j/5)));

PolygonTest.java

import

java.applet.Applet;

import

java.awt.Graphics;

import

java.awt.Graphics2D;

import

java.awt.geom.Line2D;

import

java.awt.geom.Point2D

;

public class

PolygonTest extends

Applet

{ public void paint

(Graphics g)

{ Graphics2D g2 =

(Graphics2D) g;

Polygon triangle = new

Polygon(3);

triangle.add(new

Point2D.Double(40,40))

;

triangle.add(new

Point2D.Double

(120,160));

triangle.add(new

Point2D.Double(20,120)

);

double x = 200;

double y = 200;

double r = 50;

Polygon pentagon =

new Polygon(5);

for (int j = 0; j < 5; j++)

{ pentagon.add(new

Point2D.Double(

x+r*Math.cos

(2*Math.PI*j/5),

y+r*Math.sin

(2*Math.PI*j/5)));

}

triangle.draw(g2);

pentagon.draw(g2);

}

}

// define polygon class

class Polygon

{ public Polygon(int n)

{ corners = new

Point2D.Double[n];

cornersSize = 0;

}

public void add

(Point2D.Double p)

{ if (cornersSize <

corners.length)

{ corners[cornersSize]

= p;

cornersSize++;

}

}

public void draw

(Graphics2D g2)

{ for (int j = 0; j <

cornersSize; j++)

{ Point2D.Double from

= corners[j];

Point2D.Double to =

corners[(j+1) %

corners.length];

g2.draw(new

Line2D.Double(from,

to));

// Line2D.Double line =

new Line2D.Double

(from, to);

// g2.draw(line);

}

}

private Point2D.Double

[] corners;

private int cornersSize;

}

Vector

A Vector is a container

of objects that grows

automatically

A Vector can hold

objects of any types

Internally, the Vector

class keeps an Object

[] array.

There is no limit to the

number of elements

that we add.

We can add new

elements at the end of

the vector with the

add method.

However, vectors are

objects of a class and

not arrays so we

cannot use the []

operator to access

vector.

Instead, we use the

set method to write an

element, and the get

method to read an

element.

products.set(0, p);

Example

// Consider

BestProduct.java

Vector products = new

Vector();

boolean done = false;

while (!done)

{ Product p =

readProduct();

if (p == null) // last

product read

done = true;

else

products.add(p); // add

the object to the end

of the vector

}

Vector positions start

at 0.

The number of

elements stored in a

vector is obtained by

the size method.

int n = products.size();

To read an element

from a vector, we use

the get method:

products.get(i) is the

ith element in the

vector products.

However, because the

return type of the get

method is the class

Object, we must cast

the return value of the

get method to the

correct type.

Product p = (Product)

products.get(i);

An example of a loop

that traverses the

elements of a vector.

for (int j = 0; j <

products.size(); j++)

{ Product p = (Product)

products.get(j);

do something with p;

}

We can also insert an

object in the middle of

a vector by using v.add

(j,p) to add the object

p at position j, move

all elements by one

position, from position

j to the last element in

the vector, and

increase the size of

the vector by 1.

The call v.remove(j)

removes the element

at position j, moves all

elements after the

removed element

down by one position,

and reduce the size of

the vector of the

vector by 1.

Since numbers are not

objects in Java, we

cannot have vectors

of numbers.

To store sequence of

integers, floating-point

numbers, or boolean

values, we must use

wrapper classes.

The classes Integer,

Double, and Boolean

wrap numbers and

truth values inside

objects.

These wrapper

objects can be stored

inside vectors.

The Double class is a

number wrapper.

There is a constructor

that makes a Double

object out of a double

value:

Double d = new Double

(29.74);

Conversely, the

doubleVal method

retrieves the double

value that is stored

inside the Double

object.

double x =

d.doubleValue();

To add a number into a

vector, we first

construct a wrapper

object, then add the

object to the vector:

Vector data = new

Vector();

data.add(new Double

(29.95));

To retrieve the

number, we need to

cast the return value

of the get method to

Double, then call the

doubleValue method:

double x = ((Double)

data.get(0))

.doubleValue();

Converting Vectors to

Arrays

The advantage of

vectors is the dynamic

growth since we need

not know the final size

of the vector.

The disadvantage is

the cumbersome

access syntax.

We can convert a

vector to an array with

the copyInfo method:

// read values into a

vector

vector productVector =

new Vector();

boolean done = false;

while (!done)

{ Product p =

readProduct();

if (p == null)

done = true;

else

productVector.add(p);

}

// allocate an array of

the correct size

Product[] products =

new Product

[productVector.size()];

// copy the elements

from the vector to the

array

productVector.

copyInfo(products);

for (int j = 0; j <

products.length; j++)

do something with

products[j];

Two-Dimensional

Arrays

An arrangement

consisting of rows and

columns of values is

called a two-

dimensional array or

matrix.

To construct a 2D

array, we need to

specify how many ros

and columns we need,

for example

int[][] powers = new

int[10][8];

To access a particular

element in the matrix,

we specify two

subscripts in separate

brackets:

powers[3][4] =

Math.pow(2, 4);

Two-Dimensional

Arrays

In Java, 2D arrays are

stored as arrays of

arrays:

int[][] powers = new

int[10][8];

For example, power is

an array of 10 objects,

each of which is an int

[] array of length 8.

The number of rows is:

int nrows =

powers.length;

The number of

columns is:

int ncols = power[0]

.length;

// See example:

Table2.java

Table2.java

public class Table2

{ public static void

main(String[] agrs)

{ final int COL_WIDTH =

10;

int[][] powers = new

int[10][8];

for (int i = 0; i <

powers.length; i++)

for (int j = 0; j <

powers[i].length; j++)

powers[i][j] = (int)

Math.pow(i+1, j+1);

printTable(powers,

COL_WIDTH);

}

public static void

printTable(int[][] table,

int width)

{ for (int i = 0; i <

table.length; i++)

{ for (int j = 0; j < table

[i].length; j++)

{ System.out.print

(format(table[i][j],

width));

}

System.out.println();

}

}

public static String

format(int n, int width)

{ String nstr = “” + n;

while (nstr.length() <

width)

nstr = “ “ + nstr;

return nstr;

}

}