CISC 1115 Lecture #12

Overview

Until now, we've created arrays whose size exactly matches the number of elements placed into the array. This is often impractical:

We may not know the number of elements to be placed into the array prior to creating it; for example reading data into an array from a file (or the keyboard) using eof or a trailer value — in both cases the number of elements is not known until after we've read in all the value.
Even if we know the number of initial elements in advance, the logic of the program may call for adding or removing elements, in which case keeping the array at the exact size of the number of elements would mean constantly reallocating and copying (see Resizing an Array below.

There are two basic ways to address the above issues:

Create an array with sufficient unused elements equal to (at least) the expected maximum number of elements we actually expect to use at any point. Such an array is sometimes called a partially populated/filled array.
Add logic so that the array can grow as necessary. An array of any size could then be created and it will dynamically expand as necessary to accommodate the elements needed. Such an array is commonly called a vector (or an ArrayList in Java)

Partially Populated Arrays

If we know in advance the maximum number of elements to be maintained, we can create an array of that maximum size, with the assurance that we will have sufficient room in the array.
If we then fill the array (starting from the beginning and adding values to successive elements), we will typically have empty elements at the right hand side of the array
- For example, if our maximum size is 100, and we only have 30 value (which we assign to locations 0 … 29), there will be 70 empty elements (30 … 99) at the end of the array.
One very important consequence of this is that the .length field of the array doesn't represent the number of elements in the array being used, but rather the number of elements actually allocated at array creation time.
- For example, if one prints out the above array, only the first 30 elements should be printed; the last 70 contain no information of interest to us.
As a result, a variable (let's call it size) needs to be introduced, containing the number of elements in the array actually being used (30 in the above example).
- This variable replaces the .length in the context where the numbers of elements created differs from the number of elements used.

Program 14.1

Write a program that reads in a sequence of numbers (until eof) from the file "numbers.text", and prints out each number together with whether it is above or below the average of the numbers. Assume a maximum of 100 numbers in the file

import java.io.*;
import java.util.*;

public class Program_14_1 {
        public static void main(String [] args) throws Exception {
                Scanner scanner = new Scanner(new File("numbers.text"));

                final int CAPACITY = 100;

                int [] arr = new int[CAPACITY];

                int size = read(scanner, arr, CAPACITY);

                double average = getAverage(arr, size);

                //for (int num : arr)
                for (int i = 0; i < size; i++)
                        System.out.println(arr[i] + " is " + (arr[i] < average ? "below" : "above") + " average");
        }

        public static int read(Scanner scanner, int [] arr, int capacity) {

                int size = 0;

                while (scanner.hasNextInt()) {
                        if (size >= capacity) {
                                System.out.println("Capacity exceeded - increase the size of your arrya");
                                System.exit(1);
                        }
                        arr[size] = scanner.nextInt();
                        size++;
                }

                return size;
        }

        public static double getAverage(int [] arr, int size) {
                return (double)getSum(arr, size)/size;
        }

        public static double getSum(int [] arr, int size) {
                int total = 0;

                for (int i = 0; i < size; i++)
                        total += arr[i];

                return total;
        }
}

Notes

The physical size of the array (see below) is maintained in the final variable CAPACITY
The read method accepts the Scanner, array, and capacity, and returns the logical size of the array (again, see below)
read contains logic to prevent array overflow
- attempting to insert an element when the array is full would cause an ArrayBoundsException
Once the logical size of the array has been obtained, it is used as the 'size' of the array in further processing.
- The length field of the array (the physical size) is inappropriate for most subsequent processing; it includes elements that have not been populated
- This is evident from the additional size parameter of getAverahe and getSum
- The physical size is rarely used once the logical size is obtained

Physical and Logical Size (Capacity vs Size)

capacity/physical size: number of elements the array was created with
size/logical size: number of elements assigned values
We sometime refer to the physical array (the array as created) vs the logical array (the filled portion of the array.
- The former has bounds 0 … arr.length-1; whereas the latter has bounds 0 … size-1

Common Techniques for Logical Arrays

Summarizing … an array with a logical size has bounds 0 … size-1, where size is an integer variable maintaining the number of elements in actual use in the array.
From a coding point of view, the consequence is the size must be passed as an argument to functions working with the array
We'll first present the creation of an array using a logical size, and then present one or two techniques from Lecture 12 to give you the basic idea; the rest are the same.
- The standard way of creating such an array is to read in values from a file, or the keyboard, the quantity of which we are guaranteed to be of a maximum size.

Reading in an array of known maximum size using (eof)

// using eof

final static int CAPACITY = 100;

double [] arr = new double[CAPACITY];
int size = 0;
while (scanner.hasNextInt()) {
	arr[size] = scanner.nextInt();
	size++;
}

// size now contains the actual number of elements read into the array

Reading in an array of known maximum size using a trailer value

// using a trailer of -1

final static int CAPACITY = 100;

double [] arr = new double[CAPACITY];

int size = 0;
arr[size] = scanner.nextInt();	// priming the pump
while (arr[size] >= 0) {
	size++;
	arr[size] = scanner.nextInt();
}

// size now contains the actual number of elements read into the array

Printing an array with a logical size

// Notice the second parameter

void print(double [] arr, int size) {
	System.out.print("{");
	for (int i = 0; i < size; i++)
		System.out.print(arr[i]+ " ");
	System.out.print("}");
}

The Rest of the Techniques

As above, the rest of the techniques are the same as in Lecture 12, except for the presence of a second parameter which is used in place of the .length field

Vector/ArrayList — An Overview

A vector is an array whose size can grow as necessary. While the actual implementation of an actual vector isn't introduced until later (3115 and 3130), we can get already some sense of what they are. Furthermore, the techniques used for implementing vectors can be presented in a more 'low-tech' context — a sequence of elements with a known maximum size.

Vector-Oriented Techniques

Resizing an array

double [] resize(double [] arr) {
	double [] tmpArr = new double[arr.length * 2];
	for (int i = 0; i < arr.length; i++)
		tmpArr[i] = arr[i];
	return tmpArr;
}

Using the above method:

double [] arr = new double[…];
…
arr = resize(arr);

Inserting an element into an array

Deleting an element from an array

Parallel Arrays

As we've seen, our programs often manipulate several pieces of information in performing their task:

A grading program might require a student id, last name, first name, semester average, etc
A payroll program might require an employee id, last and first names, hours worked, hourly rate, etc

Up until now, we simply declared a variable (of the appropriate type) for each of these item if data
However, in many situations, the data must be maintained in an array (for example, if we want to perform searches, or class-wide operations on the data).
In such a situation, we need one array per item of information: i.e., an array for last names, another for first names, etc.
The data for a particular student if then maintained in 'parallel' locations across the arrays, i.e., if a student's last name is at location i of the last name array, the first name is at location i of the first name array, the average at location i of the average array, etc
This technique is called working with parallel arrays
The thing to remember is is any change to the data in one array must be reflected in all of the arrays; i.e., we must always make sure the i'th row across the arrays contains the same student's data
- One important consequence of this is that when we will sort a set of parallel arrays (by moving elements around so they get into a sorted order), we must remember to move all the arrays in the same manner.

Program 14.2

Write a program that reads in student data from a data file (whose name should be obtained from the user) consisting of name, midterm, and final, and prints the data to the console in two sections: first all those students who received a 90 or above on at least one exam, followed by the rest of the class.

The program should define the following methods:

int read(Scanner scanner, String [] names, int [] midterms, int [] finalExams, int capacity);
void print(String [] names, int [] midterms, int [] finalExams, int size);

import java.io.*;
import java.util.*;

public class Program_14_2 {
        public static void main(String [] args) throws Exception {
                Scanner scanner = new Scanner(new File("exams.text"));

                final int CAPACITY = 100;

                String [] names = new String[CAPACITY];

                int [] 
                        midterms = new int[CAPACITY],
                        finalExams = new int[CAPACITY];

                int size = read(scanner, names, midterms, finalExams, CAPACITY);

                print(names, midterms, finalExams, size);
        }

        public static int read(Scanner scanner, String [] names, int [] midterms, int [] finalExams, int capacity) {

                int size = 0;

                while (scanner.hasNext()) {
                        if (size >= capacity) {
                                System.out.println("Capacity exceeded - increase the size of your arrya");
                                System.exit(1);
                        }
                        names[size] = scanner.next();
                        midterms[size] = scanner.nextInt();
                        finalExams[size] = scanner.nextInt();
                        size++;
                }

                return size;
        }

        public static void print(String [] names, int [] midterms, int [] finalExams, int size) {
                System.out.println("Received at least one 90 or above");
                for (int i = 0; i < size; i++)
                        if (midterms[i] >= 90 || finalExams[i] >= 90)
                                System.out.println(names[i] + " " + midterms[i] + " " + finalExams[i]);
                System.out.println();
                System.out.println("Rest of the class");
                for (int i = 0; i < size; i++)
                        if (midterms[i] < 90 && finalExams[i] < 90)
                                System.out.println(names[i] + " " + midterms[i] + " " + finalExams[i]);
        }
}

Program 14.3

Write a program that reads in student data from a data file (whose name should be obtained from the user) consisting of last name, first name, midterm, and final. The program calculates each student's average, and grade, and prints out a roster consisting of all the information, together with whether the student performed above or below the class average.

The program should define the following methods:

int read(String fname, String [] lastNames[], String [] firstNames, int [] midterms, int [] finals, int capacity);
void calcAverages(int [] midterms, int [] finals, double [] averages, int size)
double calcOneAverage(int midterm, int final)
double calcClassAverage(double [] averages, int size)
void calcGrades(double [] averages, char [] grades, int size)
char calcOneGrade(double average)
void printRoster(String [] lastNames, String [] firstNames, int [] midterms, int [] finals, double [] averages, char [] grades, int size, double classAverage)
void printOneStudent(String lastName, String firstName, int midterm, int final, double average, char grade, classAverage)

import java.io.*;
import java.util.*;

public class Program_14_3 {
   public static void main(String [] args) throws Exception {
      Scanner keyboard = new Scanner(System.in);    
      
      System.out.print("roster file? ");
      String filename = keyboard.next();
      
      final int CAPACITY = 100;
      
      String [] 
         lastNames = new String[CAPACITY],
         firstNames = new String[CAPACITY];
      
      int [] 
         midterms = new int[CAPACITY],
         finals = new int[CAPACITY];
      
      double [] averages = new double[CAPACITY];
      
      char [] grades = new char[CAPACITY];
      
      int size = read(filename, lastNames, firstNames, midterms, finals, CAPACITY);
      
      calculateAverages(midterms, finals, averages, size);
      
      double classAverage = calculateClassAverage(averages, size);
      
      calculateGrades(averages, grades, size);
      
      printRoster(lastNames, firstNames, averages, grades, classAverage, size);
   }
   
   public static int read(String filename, String [] lastNames, String [] firstNames,
                          int [] midterms, int [] finals, int capacity) throws Exception {
      Scanner scanner = new Scanner(new File(filename));
      
      int size = 0;
      
      while (scanner.hasNext()) {
         if (size >= capacity) {
            System.out.print("Reached array capacity and still more data. Make the array bigger");
            System.exit(1);
         }
         lastNames[size] = scanner.next();
         firstNames[size] = scanner.next();
         midterms[size] = scanner.nextInt();
         finals[size] = scanner.nextInt();
         size++;
      }
      return size;
   }
      
   public static void calculateAverages(int [] midterms, int [] finals, double [] averages, int size) {
      for (int i = 0; i < size; i++)
         averages[i] = calculateOneAverage(midterms[i], finals[i]);
   }
      
   public static double calculateOneAverage(int midterm, int finalExam) {return (midterm + finalExam)/2.0;}
   
   public static double calculateClassAverage(double [] averages, int size) {
      double total = 0;
      for (int i = 0; i < size; i++)
         total += averages[i];
      return total / size;
   }

   public static void calculateGrades(double [] averages, char [] grades, int size) {
      for (int i = 0; i < size; i++)
         grades[i] = calculateOneGrade(averages[i]);
   }
   
   public static char calculateOneGrade(double average) {
      return average >= 90 ? 'A' : average >= 80 ? 'B' : average >= 70 ? 'C' : average >= 60 ? 'D' : 'F';
   }
   
   public static void printRoster(String [] lastNames, String [] firstNames, double [] averages, 
                                  char [] grades, double classAverage, int size) {
      for (int i = 0; i < size; i++)
         printOneStudent(lastNames[i], firstNames[i], averages[i], grades[i], classAverage);
   }
   
   public static void printOneStudent(String lastName, String firstName, double average, 
                                      char grade, double classAverage) {
      System.out.println(lastName + " " + firstName + " " + average + " " + grade + " " +
                       (average >= classAverage ? "Above" : "Below"));
  }
}

Using a Class

Separate variables vs a class:

Using Arrays:

import java.io.*;
import java.util.*;

public class Program_14_3 {
   public static void main(String [] args) throws Exception {
      Scanner keyboard = new Scanner(System.in);    
      
      System.out.print("roster file? ");
      String filename = keyboard.next();
      
      final int CAPACITY = 100;
      
      Student [] students = new Student[CAPACITY];
      
      int size = read(filename, students, CAPACITY);
      
      double classAverage = calculateClassAverage(students, size);
      
      printRoster(students, size, classAverage);
   }
   
   public static int read(String filename, Student [] students, int capacity) throws IOException {
      Scanner scanner = new Scanner(new File(filename));
      
      int size = 0;
      
      while (scanner.hasNext()) {
         if (size >= capacity) {
            System.out.print("Reached array capacity and still more data. Make the array bigger");
            System.exit(1);
         }
         String lastName = scanner.next();
         String firstName = scanner.next();
         int midterm = scanner.nextInt();
         int finalExam = scanner.nextInt();
            students[size] = new Student(lastName, firstName, midterm, finalExam);
         size++;
      }
      return size;
   }
      
   public static double calculateClassAverage(Student [] students, int size) {
      double total = 0;
      for (int i = 0; i < size; i++)
         total += students[i].average;
      return total / size;
   }
   
   public static void printRoster(Student [] students, int size, double classAverage) {
      for (int i = 0; i < size; i++)
         System.out.println(students[i] + " " + (students[i].average >= classAverage ? "Above" : "Below"));
   }
}

class Student {
        Student(String last, String first, int mid, int fin) {
                lastName = last;
                firstName = first;
                midterm = mid;
                finalExam = fin;
                average = (midterm + finalExam) / 2.0;
                grade = average >= 90 ? 'A' : average >= 80 ? 'B' : average >= 70 ? 'C' : average >= 60 ? 'D' : 'F';
        }
      
        public String toString() {return lastName + " " + firstName + " " + average + " " + grade;}

        String lastName, firstName;
        int midterm, finalExam;
        double average;
        char grade;
}

SubArrays — Subsequences of Arrays

Fully populated arrays have their elements in the range 0 … arr.length-1
Partially populated arrays have their elements in the range 0 … size-1
We often have need to deal with only a portion of an array — a subarray, not necessarily starting from index 0
- For example in the binary search we've alluded to, if the name lies in the last (right) half of the array, we only want to search the portion of the array fro the middle onwards.
- Partially populated arrays to some degree fall into this category, but in that case, they always start at index 0.
For a general subsequence, we specify the beginning and end of the portion of the subarray we are interested in; this is typically done in one of two ways:
1. The starting and ending index of the subsequence;
  - For example, given the array: int [] arr = {10, 20, 30, 40, 50, 60,}; if we wanted to deal with the subarray consisting of the element 30, 40, 50, we would specify 2 as the starting index and 4 as the ending index
    - Specifying the last index in this manner makes the resulting code look a bit different from the 'normal' way of processing an array … i.e., one goes up to and including (<= rather than <) the termination value (see the code for the for loop header in the print method of Program_14.4 below).
    - because of this 'difference', instead of the ending index, it usually proves move convenient to specify the index after the last index we are interested in, in which case for the 20, 30, 40 example, we would specify 2 as the starting index and 5 as the ending index
      - Specifying the last index in this manner makes the resulting code look like the 'normal' way of processing an array … i.e., one goes up to but not including (< rather than <=) the termination value.
2. The starting index and the number of elements
  - For the 20, 30, 40 case, we would specify 2 as the starting index and 3 as the number of elements

Program 14.4

Write a program that reads in an array of integers from the file"numbers.text" (using a header value), prints the entire array, and then prompts the user for the first and last elements of a subarray to be printed.

The program should define and call the following methods:

int [] read(Scanner scanner)
void print(int [] arr);
void print(int [] arr, int first, int end).

import java.io.*;
import java.util.*;

public class Program_14_4 {
        public static void main(String [] args) throws Exception {
                Scanner scanner = new Scanner(new File("numbers.text"));

                int [] arr = read(scanner);

                print(arr);
                System.out.println();

                Scanner keyboard = new Scanner(System.in);

                System.out.print("First index to print: ");
                int first = keyboard.nextInt();
                System.out.print("Last index to print: ");
                int last = keyboard.nextInt();

                print(arr, first, last+1);
                System.out.println();
        }

        public static int [] read(Scanner scanner) {

                int size = scanner.nextInt();

                int [] arr = new int[size];

                for (int i = 0; i < size; i++)
                        arr[i] = scanner.nextInt();

                return arr;
        }

        public static void print(int [] arr) {
                System.out.print("{");
                for (int i = 0; i < arr.length; i++)
                        System.out.print(arr[i] + (i < arr.length-1 ? ", " : ""));
                System.out.print("}");
        }

        public static void print(int [] arr, int first, int end) {
                for (int i = first; i < end; i++)
                        System.out.print(arr[i] + (i < end-1 ? ", " : ""));
        }
}

Notes

All the basic array techniques listed in Lecture 12 and above apply, except that we pass the beginning and ending (or length) specifications (in addition to the array) to the method (in contrast to just the array for simple array processing and the array plus size for partially populated arrays).
Leveraging Functionality
- If we code the method void print(int [] arr, int first, int end) first, we can the easily implement the method void print(int [] arr):
```
				void print(int [] arr) {print(arr, 0, arr.length);}
				
```

CISC 1115
Introduction to Programming Using Java
Lecture #14
Techniques IV — Partially-Populated Arrays, Vectors, Parallel Arrays, Subarrays

Overview

Partially Populated Arrays

Program 14.1

Physical and Logical Size (Capacity vs Size)

Common Techniques for Logical Arrays

Reading in an array of known maximum size using (eof)

Reading in an array of known maximum size using a trailer value

Printing an array with a logical size

The Rest of the Techniques

Vector/ArrayList — An Overview

Vector-Oriented Techniques

Resizing an array

Inserting an element into an array

Deleting an element from an array

Parallel Arrays

Program 14.2

Program 14.3

Using a Class

SubArrays — Subsequences of Arrays

Program 14.4

Files used in this Lecture

CISC 1115 Introduction to Programming Using Java Lecture #14 Techniques IV — Partially-Populated Arrays, Vectors, Parallel Arrays, Subarrays

Overview

Partially Populated Arrays

Program 14.1

Physical and Logical Size (Capacity vs Size)

Common Techniques for Logical Arrays

Reading in an array of known maximum size using (eof)

Reading in an array of known maximum size using a trailer value

Printing an array with a logical size

The Rest of the Techniques

Vector/ArrayList — An Overview

Vector-Oriented Techniques

Resizing an array

Inserting an element into an array

Deleting an element from an array

Parallel Arrays

Program 14.2

Program 14.3

Using a Class

SubArrays — Subsequences of Arrays

Program 14.4

Files used in this Lecture

CISC 1115
Introduction to Programming Using Java
Lecture #14
Techniques IV — Partially-Populated Arrays, Vectors, Parallel Arrays, Subarrays