INTRODUCTION TO PROGRAMMING IN JAVA: CONSTRAINED AND UNCONSTRAINED ARRAYS


CONTENTS

1. Overview
2. The this object
3. Example problem - set intersection
3.1. Requirements
 
3.2. Analysis
3.3. Design
3.4. Implementation
3.5. Testing

The "setIO" code presented here refers back to code introduced in the previous lecture.




1. OVERVIEW

A constrained array is an array where the index is specified (and hence the number of components is specified), we say that the bounds are static, hence constrained arrays are sometimes referred to as static arrays. So far we have only looked at such constrained arrays. Most programming languages (including Java) support the concept of unconstrained arrays. When an unconstrained array is declared the number of elements is not supplied untill run time --- typically by user input.

In a previous example we considered a class SetIO which included methods to allow us to input the values making up a set of integers (ensuring that duplicates were not accepted) and output those values. However, because a set was represented as an 8 element static array, the class could only be used in relation to sets comprising 8 elements. The class and the methods within it would be much more useful if it operated with respect to sets (arrays) of any size from 0 (the empty set) up to some maximum. This would make the class much more general (generic) and therefore much more useful.

 

To do this we must amend the code so that the upper bound constant becomes a variable so that a value can be supplied (using the constructor) for this data item at run time. The proposed changes are presented in Table 1. Code for an application test class to exercise the revised SetIO class is presented in Table 2.

Consider the code fragment given in Table 1. This is the start of the implementation for the SetIO class but this time we have included a constructor which allows the user to "load" values into sets of any size (in the previous version a default constructor was used). In this case, although the lower bound will remain constant, the set length will vary for each instance of SetIO thus it cannot be a (static) class field. Similarly it cannot be a (final) constant field because we will not know the value till run time.

We also need to make an adjustment to the SetIOtestApp class with which we tested the SetIO class as shown in Table 2. Here we have included some lines of code to allow the user the opportunity to input an appropriate upper bound. Note that the constant ARRAY_LENGTHarrayLength.

 
// SET IO, VERSION 2
// Frans Coenen
// 7 July 1999
// Revised: Tuesday 30 august 2005
// Dept Computer Science, University of Liverpool

import java.util.*;

class SetIOver2 {

    // ------------------ FIELDS ------------------------

    private static Scanner keyboardInput = new Scanner(System.in);
    private static final int LOWER_BOUND = 0;
    private int arrayLength;   
    private int[] integerSet;

    // ------------------ CONSTRUCTOR ------------------------
    
    public SetIOver2(int numElements) {
        arrayLength = numElements;
    	integerSet = new int[arrayLength];
	}
	
    // 	------------------ METHODS ------------------------
< AND SO ON AS BEFORE EXCEPT THAT THE ARRAY_LENGTH CONSTANT IS NOW A VARIABLE>

Table 1: Version 2 of SetIO class with constructor to allow definition of set of any size

 
// SET IO VERSDION 2 TEST APPLICATION 
// Frans Coenen
// 7 July 1999
// Revised: Tuesday 30 august 2005
// Dept Computer Science, University of Liverpool

import java.util.*;

class SetIOver2testApp{

    // ------------------- FIELDS ------------------------ 
        
    // Create Scanner class instance
    private static Scanner keyboardInput = new Scanner(System.in);
    
    
    // ------------------ METHODS ------------------------  
    
    /* Main method */    
    public static void main(String[] args) {
	
	// Input number of elements in set and then create instance of 
	// set IO class.	
	System.out.println("Input number of elements in set");
	int setSize = keyboardInput.nextInt();
	SetIOver2 newSet = new SetIOver2(setSize);
	
        // Input for set 
	System.out.println("Input values for set.");
	newSet.inputSet();
	
	// Output values for set	
	newSet.outputSet();
	}
    }

Table 2: Version 2 of SetIOver2 test application class




2. THE THIS OBJECT

We have seen that we call an instance method by linking it (using the '.' operator) to a particular instance of the class to which the method belongs:

myInstance.myMethod()

In this manner the method has access to all the instance fields peculiar to the "calling instance". In addition the method may have some arguments (formal parameters) associated with it. In some cases these arguments are instances. Let us assume we have a method, lets call it myMethod, which is an instance method of the class myClass. To use this method we would create an instance of the class, (say) myInstance, and then call the method in the normal way as shown above. Now, suppose that embedded within this method there is a call to another method, anotherMethod, that requires as its argument the current instance:

public void myMethod() {
   anotherMethod
         (< The Current Instance >);
   }
 

How does Java know what this instance is? The answer is that we have to tell it, but how? One option is to "hard code" the desired instance name into the method:

public void myMethod() {
    anotherMethod(myInstance);
    }

But what if we wish to call myMethod with a different instance in which case we would want the anotherMethod to be also called with this alternative instance and not the one that we have "hard coded" in. To do this we must use the keyword this which refers to the current object. Thus:

public void myMethod() {
    anotherMethod(this);
    }

Consequently we often refer to the this keyword as the this object.

In the following unconstrained array handling example problem we will make use of the this keyword to pass the current object/instance.



3. EXAMPLE PROBLEM - SET INTERSECTION


3.1. Requirements

Develop a Java program which, given two sets of integers, determines the intersection of these two sets and stores this in a third set. For example Given:

set1 = {2  4  6  8 10 12 14 18 20}
set2 = {3  6  9 12 15 18}
set1 intersection set2 = set3 = {6 12 18}
SET

Figure 1: Venn diagram


3.2. Analysis

We will make use of the SetIO class introduced earlier and ammended above, and extend this by adding two new methods (numIntersectingElements and setIntersection) which, given two sets, determine:

The size of the intersection so that we can dynamically create a third array in which to store the result, and
The intersection elements to be contained in the new array.

respectively. The extended class diagram for the SetIO class, is given in Figure 2. Note that the the three methods inputSet, noDuplicates and outputSet are identical to methods of the same name developed for the SetIO class; except that, in the case given here, the upper bound constant (ARRAY_LENGTH)used previously has been replaced by an instance variable --- arrayLength.


3.3 Design

From Figure 2 we can identify the following methods.

 
CLASS DIAGRAM FOR SET OPERATIONS PROBLEM

Figure 2: Class diagram for extended SetIOver2 class

3.3.1 Extended SetIOver2 Class

Field Summary
private static Scanner keyboardInput
           A private class instance to facilitate input from the input stream.
private static final int LOWER_BOUND
           A class constant, set to 0, to mark the lower bound of an array.
private int arrayLength
           An instance variable to store the length of the set (array).
private int[] integerSet
           An instance variable to store the set in the form of an integer array.

Constructor Summary
SetIOver2(int numElements)
           Constructor to create an instance of the class SetIOver2 with a given set size.

Method Summary
public void inputSet()
           Method to allow user to input values for an N element set. To ensure that no duplicates are included the method includes a call to the noDuplicates method (see below). Input is carried out using a while loop which will continue iterating until eight distinct values have been entered. Method behaves in a similar manner to method of same name developed for the SetIO class.
private boolean noDuplicates(int newElement, int currentEnd)
           Method (similar to method of same name in SetIO class) to check whether a new user supplied value is already contained in the set so far. If so method returns false, otherwise true.
public void outputSet()
           Method (similar to method in SetIO class) to loop through set (using a for loop) and output the values of the set.
public static int numIntersectingElements(SetIOver2 set1, SetIOver2 set2)
           Private class method to determine and return the number of intersecting elements given a pair of sets. This method is required so that we can create an appropriately sized set to hold the desired intersection set. Called from the setIntersection method as the argument to the
public SetIOver2 setIntersection(SetIOver2 set2)
           Method to loop through two sets (that associated with the calling instance and the given argument) and produce a third set that represents the intersection of the two sets. At the end of the method the new set is returned. The third set is a field of a new instance of the class SetIOver2 created using the SetIOver2 constructor with a call to the numIntersectingElements class method as its argument.

Remenber that a private method can only be accessed from within a class (in the same way that a private field can only be accessed from within a class).

Nassi Shneiderman charts for the above methods are presented in Figure 3.

NASSI SHNEIDERMAN CHARTS FOR SET OPERATIONS PROBLEM NASSI SHNEIDERMAN CHARTS FOR SET OPERATIONS PROBLEM

Figure 3: Nassi Shneiderman charts for set operations class methods


3.3.2 SetIOver2testApp Class

Field Summary
private static Scanner KeyboardInput()
           A class instance to facilitate input from the input stream.

Method Summary
public static void main(String[] args)
           Main method to test set operations.
private static SetIOver2 createNewSetIOver2()
           Method that invokes the inputSet instance method and returns a reference to the newly created set.

A series of Nassi Shneiderman Tables describing the above methods are given in Figure 4.

NASSI SHNEIDERMAN CHARTS FOR SET OPERATIONS PROBLEM

Figure 4: Nassi Shneiderman charts for set operations class methods


3.4. Implementation

The implementation for the rctended SetIOver2 class (in its entirety is given in Table 3. The code for the application class to address the particular problem described here is given in Table 4.

// SET IO, Version 2
// Frans Coenen
// 7 July 1999
// Revised: Tuesday 30 august 2005
// Dept Computer Science, University of Liverpool

import java.util.*;

class SetIOver2 {

    // ------------------ FIELDS ------------------------

    private static Scanner keyboardInput = new Scanner(System.in);
    private static final int LOWER_BOUND = 0;
    private int arrayLength;   
    private int[] integerSet;

    // ------------------ CONSTRUCTOR ------------------------
    
    public SetIOver2(int numElements) {
        arrayLength = numElements;
    	integerSet = new int[arrayLength];
	}
	
    // 	------------------ METHODS ------------------------

    /* Input a set of elements */

    public void inputSet() {
	int loopParameter = LOWER_BOUND;
	int newElement;
	
	// Loop till set instantiated
	
	System.out.println("Enter " + arrayLength + " elements.");
	while (loopParameter < arrayLength) {
	    newElement = keyboardInput.nextInt();
	    if (noDuplicates(newElement,loopParameter)) {
	    	integerSet[loopParameter] = newElement;
		loopParameter++;
		}
	    else System.out.println("Duplicate element " + newElement);
	    }
	}
	    
    /* ------ NO DUPLICATES ------ */
    
    /* Check for duplicates, return true if non found, false otherwise. */
    
    private boolean noDuplicates(int newElement, int currentEnd) {
        boolean noDuplicatesFound = true;
	
	// Loop through array so far
	    
	for (int index=LOWER_BOUND;index < currentEnd;index++) {
	    if (integerSet[index] == newElement) return(!noDuplicatesFound);
	    }
	
	// Return
	
	return(noDuplicatesFound);
	}
    
    /* OUTPUT CONTENTS OF SET */
    
    public void outputSet() {
    	
	// Commence output
	
	System.out.print("{" + integerSet[0]);
	
	// Loop through rest of set outputting on each iteration 
	
	for(int index=LOWER_BOUND+1;index < arrayLength;index++) {
	    System.out.print("," + integerSet[index]);
	    }
	    
	// End output
	   
    	System.out.print("}");
	}
    
    /* ----- NUMBER OF INTERSECTING ELEMENTS ------ */
    
    /* Determine number of intersecting elements in a set */
    
    private static int numIntersectingElements(SetIOver2 set1,
    					SetIOver2 set2) {
    	int index1, index2;
	int numElements=0;
	
	/* Determine number of intersecting elements. */
	
	for(index1=LOWER_BOUND;index1 < set1.arrayLength;index1++) {
	    for(index2=LOWER_BOUND;index2 < set2.arrayLength;index2++) {
	    	if (set1.integerSet[index1] == set2.integerSet[index2]) {
		    numElements++;
		    break;
		    }
	    	}
	    }
	    
	/* Return. */
	
	return(numElements);    
	}
	
    /* ------ IDENTIFY SET INTERSECTION ------ */
    
    public SetIOver2 setIntersection(SetIOver2 set2) {
    	int index1, index2, index3=LOWER_BOUND;
	
	/* Create a new instance of the class SetIOver2 */
	
	SetIOver2 set3 = new 
			SetIOver2(numIntersectingElements(this,set2));
	
	/* Load intersecting set */
	
	for(index1=LOWER_BOUND;index1 < arrayLength;index1++) {
	    for(index2=LOWER_BOUND;index2 < set2.arrayLength;index2++) {
	        if (integerSet[index1] == set2.integerSet[index2]) {
		    set3.integerSet[index3] = integerSet[index1];
		    index3++;
		    break;
		    }
	    	}
	    }
	    
	/* Return new set */
	 
	return(set3);  
    	}
    }

Table 3: Extended Set IO version 2 class implementation

// SET INTERSECTION 2 TEST APPLICATION 
// Frans Coenen
// 7 July 1999
// Revised: Tuesday 30 august 2005
// Dept Computer Science, University of Liverpool

import java.util.*;

class SetIOintersectionTestApp{

    // ------------------- FIELDS ------------------------ 
        
    // Create Scanner class instance
    private static Scanner keyboardInput = new Scanner(System.in);
    
    
    // ------------------ METHODS ------------------------  
    
    /* Main method */
    
    public static void main(String[] args) {
	
	// Create and input values for two sets.	
	SetIOver2 set1 = createNewSetIOver2();
	SetIOver2 set2 = createNewSetIOver2();
	
	// Determine intersection	
	SetIOver2 set3 = set1.setIntersection(set2);
	
	// Output 	
	set1.outputSet();
	System.out.print(" intersection ");
	set2.outputSet();
	System.out.print(" = ");
	set3.outputSet();
	System.out.println("\n");
	}
	
    /* CREATE NEW SET IO VERSION 2: Method to allow input of set size  
    and cause the creation of an instance of the class SetIOver2 */
    
    private static SetIOver2 createNewSetIOver2() {
	
	// Input number of elements in set and then create instance  
	// of set IO class.	
	System.out.println("Input number of elements in set");
	int setSize = keyboardInput.nextInt();
	SetIOver2 newSet = new SetIOver2(setSize);
	
        // Input for set 	
	if (setSize != 0) {
	    System.out.println("Input values for set.");
	    newSet.inputSet();
	    }
	else System.out.println();
	    
	// Return	
	return(newSet);
	}
    }

Table 4: Set IO version 2 test application class implementation


3.5. Testing


3.5.1. Black Box Testing

BVA, Limit and Arithmetic Testing: As with the SetIO example problem, inputs may range from the maximum to the minimum default range for the integer type. We should also include a zero test value. A set of test cases similar to that specified for the SetIO class will therefore suffice.

3.5.2. White Box Testing

Path Testing: We should test each path through the code. More particularly we should test where an element of one set is and is not a member of the other set.

Loop Testing: To exercise the loops we should test where one or both sets are empty, and where one or both sets have only one element. Instinctively it also seems appropriate to test for cases where there is no intersection (disjoint sets) and where both sets are identical.

A suitable set of white box test cases is presented below. Some sample output generated by running the last of these two test cases is given in Table 5.

TEST CASEEXPECTED RESULT
Set1Set 2Intersection
{}{}{}
{}{1}{}
{1}{}{}
{1}{1}{1}
{1}{2,3,4,5}{}
{1,2,3,4}{5}{}
{1,2,3,4}{1,3,5}{1,3}
{1,2,3}{1,2,3}{1,2,3}
{1,2,3}{4,5,6}{}
$ java SetOpsTestApp
Input a value for the array length
3
Input values for set.
Enter 3 elements.
1
2
3
Input a value for the array length
3
Input values for set.
Enter 3 elements.
1
2
3
{1,2,3} intersection {1,2,3} = {1,2,3}

$ java SetOpsTestApp
Input a value for the array length
3
Input values for set.
Enter 3 elements.
1
2
3
Input a value for the array length
3
Input values for set.
Enter 3 elements.
4
5
6
{1,2,3} intersection {4,5,6} = {}    

Table 5: Sample output

3.5.3. Data validation testing

This should also be done.




Created and maintained by Frans Coenen. Last updated 30 August 2005