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 ArrayIndexOutOfBoundsException
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;
}
}
by Pizzler contact us at Pizzler@gmail.com