Back to my web page.
Inheritance, Abstract Classes, and Software Reuse
What are inheritance and abstract classes? And how do these assist with software reuse in Java?
For those of you who are just learning object oriented design and are coming from the world of C, I think the best analogy to inheritance and abstract classes is the qsort function defined in most C libraries. The qsort function takes four parameters: the start of an array; the number of elements in the array; the size of each element in the array; and a pointer to a function that compares two elements of the array.
None of these parameters are specific to any particular array type. The qsort function doesn't know anything about the caller's array; everything about the array to be sorted is described in abstract terms, such as a pointer, a count of elements, and a size in bytes. Even the one component that must know something about the array's internal structure is abstract: it accepts two parameters, and returns an int value that defines the sort relationship between two array elements. In a sense, you might consider qsort to be an "abstract function," and the parameters that the caller passes into qsort are a "subclass" that instantiates the abstract components of qsort.
Now, on to the details of this particular sample. The particular problem I was trying to solve when I wrote this class involved comparing two arrays. Each array consisted of a pair of strings (an object ID and a value, for those of you who are writing SNMP applications). The arrays were stored in the Vector class in Java -- which is an array that stores objects in RAM or temporary disk storage, depending on the number of objects you add or delete, and available RAM.
What I wanted was a method like the diff program under UNIX -- a list of lines that were changed, deleted, or added between the two arrays. The quick and dirty way to do this would be write a method that was specific to Vectors containing string pairs. But there is a better way, using inheritance and abstract classes, that lets you reuse your code again and again.
The smart approach -- and one that requires a bit more forethought -- was to define an abstract class named Diff. As you will see when you start to read the code, Diff is an abstract class because some of the methods required for Diff are not defined in it; the subclass that extends Diff has to define these methods. (Note: I have removed the javadoc information that provides the HTML documentation to simplify reading this code; the full text version has all the javadoc materials included.)
import java.util.*;public abstract class Diff
{
/**
* When returned by more, the Objects on left and right are different.
*/
final public static int CHG = 0;
/**
* When returned by more, the Objects on the left are not present on the right.
*/
final public static int DEL = 1;
/**
* When returned by more, the Objects on the right are not present on the left.
*/
final public static int INS = 2;
/**
* There are no more differences.
*/
final public static int DONE = 3;
final static int MATCH = 4;/**
* These Vectors will contain any differences that are reported to the user.
*
* For CHG, both leftDiff and rightDiff will be populated.
* For DEL, only leftDiff contains Objects.
* For INS, only rightDiff contains Objects.
* For DONE, both leftDiff and rightDiff should be empty.
*/
public Vector leftDiff, rightDiff;/** Constructs a difference object for determining how two groups of similar
objects differ.
*
*/
public Diff()
{
// We have been asked to create a difference object for these two objects.
// These vectors will contain any differences that are reported to the user.
leftDiff = new Vector();
rightDiff = new Vector();
}/**
* Returns the next set of differences between two objects.
*
*/
public int more ()
{
// We clear these Vectors because we are assuming that all differences were
// already grabbed and used on the previous call.
leftDiff.clear();
rightDiff.clear();
int result = MATCH;
while(result == MATCH)
{
// Pick up the next object available on the left side.
Object leftObj = getLeft();
if(leftObj != null)
{
// We haven't run out of objects yet on the left.
// Get one on the right side.
Object rightObj = getRight();
if(rightObj != null)
{
// We haven't run out of objects yet on the right.
if(compare(leftObj, rightObj))
result = MATCH;
else
{
// We may have some lines inserted on the right; let's try to scroll
// through the right until we find another match. In case we have
// to back up, we count the number of right objects we get.
rightDiff.add(rightObj);
int scrolled = 1;
boolean foundMatchAgain = false;
do
{
rightObj = getRight();
if(rightObj != null)
{
scrolled++;
// Add it to the differences list.
rightDiff.add(rightObj);
if(compare(leftObj, rightObj))
foundMatchAgain = true;
}
}
while(!foundMatchAgain && (rightObj != null));
// Now figure out why we stopped getting right objects.
if(rightObj == null)
{
// We ran out of right objects -- this means these were all
// changed objects. Back up scrolled right objects and resume
// getting left objects, seeing if we need to scroll them.
while(scrolled-- > 0)
{
ungetRight();
rightDiff.remove(rightDiff.size()-1);
}
rightObj = getRight();
// It's possible that an object was inserted on the left.
// Let's see if we can scroll forward on the left to get a
// match to the right object.
leftDiff.add(leftObj);
scrolled = 1;
foundMatchAgain = false;
do
{
leftObj = getLeft();
if(leftObj != null)
{
scrolled++;
// Add it to the differences list.
leftDiff.add(leftObj);
if(compare(leftObj, rightObj))
foundMatchAgain = true;
}
}
while(!foundMatchAgain && (leftObj != null));
// Now figure out why we stopped getting left objects.
if(leftObj == null)
{
while(scrolled-- > 0)
{
ungetLeft();
leftDiff.remove(leftDiff.size()-1);
}
// So the next go around will have something in leftObj.
leftObj = getLeft();
// Of course, if scrolling forward on both left and right
// objects didn't get us a match again, it means that we
// need to tag this difference as a change, not an insertion.
leftDiff.add(leftObj);
rightDiff.add(rightObj);
// We have already established that there is no match by
// scrolling forward, so let's continue adding to the diff
// lists until we get a match again.
foundMatchAgain = false;
while(!foundMatchAgain)
{
leftObj = getLeft();
rightObj = getRight();
if(compare(leftObj, rightObj))
{
foundMatchAgain = true;
ungetLeft();
ungetRight();
}
else
{
leftDiff.add(leftObj);
rightDiff.add(rightObj);
}
}
result = CHG;
}
else
{
// We found a match again. This means we are back in
// sync between left and right objects, but we need to
// inform the consumer of the new objects on the left side.
ungetLeft();
leftDiff.remove(leftDiff.size()-1);
ungetRight();
result = DEL;
}
}
else
{
// We found a match again. This means that we are back in
// sync between left and right objects, but we need to inform
// the consumer of the new objects inserted on the right side.
ungetRight();
rightDiff.remove(rightDiff.size()-1);
ungetLeft();
result = INS;
}
}
}
else
{
// Okay, nothing on the right, so this is a left insertion.
leftDiff.add(leftObj);
result = DEL;
}
}
else
{
// Okay nothing, on the left. Is there anything left on the right?
Object rightObj = getRight();
if(rightObj != null)
{
rightDiff.add(rightObj);
// Okay, this is a right insertion.
result = INS;
}
else
result = DONE;
}
}
return(result);
}The following statements define these methods as abstract, meaning that they must be defined by whoever subclasses Diff.
// get/unget the next left object
/**
* The subclass must implement this method to return the next available left Object.
*
* return the next left side Object to compare
*/
public abstract Object getLeft ();/**
* The subclass must implement this method to unget the current left Object.
*
*/
public abstract void ungetLeft ();/**
* The subclass must implement this method to return the next available right Object.
*
* return the next right side Object to compare
*/
public abstract Object getRight ();/**
* The subclass must implement this method to unget the current right Object.
*
*/
public abstract void ungetRight ();/**
* The subclass must implement this method to compare the current left Object and
right Object.
*
* return true means left and right Objects are equal; false means unequal
*/
public abstract boolean compare (Object leftObject, Object rightObject);
}
Here is an example of a subclass, DiffInt, that subclasses Diff to compare two arrays of int. Note that because the Diff class is defined in terms of Object, not int[], the subclass of Diff can use almost any type that is a subclass of Object. We aren't limited to int[], or even an array, because the interface to Diff's methods is defined in terms of Objects. The Diff methods don't really know or care what type its subclasses use:
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;
public class DiffInt extends Diff
{
int i = 0;
int j = 0;
int[] left;
int[] right;
public DiffInt(int[] left, int[] right)
{
super();
i = 0;
j = 0;
this.left = left;
this.right = right;
}
Here we have the methods that instantiate the abstract methods specified in the Diff class.
Note that the ints that we return to the Diff class are cast first to Integer, then to Object. This is because int is a primitive type in Java, and not a subclass of Object. The primitive data types in Java must be cast to a corresponding subclass of Object before you can cast them to an Object. You will notice that the way that int is converted to Integer involves not simply a cast, but calling an Integer constructor:
public Object getLeft ()
{
if(i < (left.length))
return((Object)new Integer(left[i++]));
else
return(null);
}
public Object getRight ()
{
if(j < (right.length))
return((Object)new Integer(right[j++]));
else
return(null);
}
public void ungetLeft ()
{
if(i > 0)
i--;
}
public void ungetRight ()
{
if(j > 0)
j--;
}
public boolean compare (Object leftObj, Object rightObj)
{
return(leftObj.equals(rightObj));
}
}
I debugged the code in Diff entirely using DiffInt. Once I had the code working for this case, I was able to create other subclasses, like DiffString that used the same code in Diff -- and it worked first time.
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;
public class DiffString extends Diff
{
int i = 0;
int j = 0;
String[] left;
String[] right;
public DiffString(String[] left, String[] right)
{
super();
i = 0;
j = 0;
this.left = left;
this.right = right;
}
public Object getLeft ()
{
if(i < (left.length))
return((Object)left[i++]);
else
return(null);
}
public Object getRight ()
{
if(j < (right.length))
return((Object)right[j++]);
else
return(null);
}
public void ungetLeft ()
{
if(i > 0)
i--;
}
public void ungetRight ()
{
if(j > 0)
j--;
}
public boolean compare (Object leftObj, Object
rightObj)
{
if((leftObj == null) && (rightObj
== null))
return(true);
if((leftObj == null) || (rightObj == null))
return(false);
String leftStr = (String)leftObj;
String rightStr = (String)rightObj;
return(leftStr.equals(rightStr));
}
}
Here is the main program that tests DiffInt and DiffString:
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;
public class DiffTest
{
public static void main(String[] args)
{
int[] left = {10, 11, 14, 15, 16, 20, 30,
50, 55, 60, 65, 70, 75};
int[] right = {10, 12, 13, 18, 19, 20, 25,
28, 29, 30, 50, 60, 65, 70};
DiffInt diffObj = new DiffInt(left, right);
boolean moreDiffs = true;
while(moreDiffs)
{
switch(diffObj.more())
{
case Diff.CHG:
System.err.print("chg left:
");
for(int i = 0; i < diffObj.leftDiff.size();
i++)
System.err.print(diffObj.leftDiff.get(i)
+ " ");
System.err.print(" right:
");
for(int i = 0; i < diffObj.rightDiff.size();
i++)
System.err.print(diffObj.rightDiff.get(i)
+ " ");
System.err.println();
break;
case Diff.DEL:
System.err.print("del left:
");
for(int i = 0; i < diffObj.leftDiff.size();
i++)
System.err.print(diffObj.leftDiff.get(i)
+ " ");
System.err.println();
break;
case Diff.INS:
System.err.print("ins right:
");
for(int i = 0; i < diffObj.rightDiff.size();
i++)
System.err.print(diffObj.rightDiff.get(i)
+ " ");
System.err.println();
break;
case Diff.MATCH:
break;
case Diff.DONE:
System.err.println("done");
moreDiffs = false;
break;
}
}
String[] leftStr = {"test", "test2", "another
one", "third string", "ender", "almost ender", "ender again"};
String[] rightStr = {"test", "test3", "another
two", "third string", "fourth string", "ender", "ender again", "not really"};
DiffString diffStrObj = new DiffString(leftStr,
rightStr);
moreDiffs = true;
while(moreDiffs)
{
switch(diffStrObj.more())
{
case Diff.CHG:
System.err.print("chg left:
");
for(int i = 0; i < diffStrObj.leftDiff.size();
i++)
System.err.print("\""
+ diffStrObj.leftDiff.get(i) + "\" ");
System.err.print(" right:
");
for(int i = 0; i < diffStrObj.rightDiff.size();
i++)
System.err.print("\""
+ diffStrObj.rightDiff.get(i) + "\" ");
System.err.println();
break;
case Diff.DEL:
System.err.print("del left:
");
for(int i = 0; i < diffStrObj.leftDiff.size();
i++)
System.err.print("\""
+ diffStrObj.leftDiff.get(i) + "\" ");
System.err.println();
break;
case Diff.INS:
System.err.print("ins right:
");
for(int i = 0; i < diffStrObj.rightDiff.size();
i++)
System.err.print("\""
+ diffStrObj.rightDiff.get(i) + "\" ");
System.err.println();
break;
case Diff.MATCH:
break;
case Diff.DONE:
System.err.println("done");
moreDiffs = false;
break;
}
}
}
}