GAMES and SOFTS

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;
}
}