Using abstract classes and interfaces: introducing tables

The Abstract Data Type Table

A table is a collection of records where a record from the collection can be accessed using a key. This leads on to the whole idea of databases, but in this course we shall consider only very simple tables. Detailed consideration of databases is left for another course.

A record is a bundle of information, and maintaining and using collections of such bundles of information is one of the most common applications of computers. If we have a collection of records, a key is a value associated with each record that can be used to access the record from the collection in is in. Generally, a key is an aspect of a record we know has a unique value for each record in the collection. For example, the registration number of a car would be a good key to for use with a collection of records of cars. We may have a computer system storing records of cars, and if we give it the registration number of a car, it will provide the complete record for the particular car with that registration number, containing other information on the car.

The abstract data type Table formalises the idea of keeping a collection of records accessible with a key. It is similar to the set abstract data type we have considered extensively previously: there is an operation to add a member, to delete a member and to check on membership. However, with tables, to delete an item from the table we give only the key and then the item with that key will be deleted. Rather than just check whether there is an item with a given key as a member of the collection, with a table there is an operation called "retrieve" in which a key is given, and the item from the collection with that key is returned.

Objects with keys, and abstract classes

For simplicity we considered sets of integers, but our tables must contain more complex objects. We can generalise this, and think of the aspects an object to be stored in a table must have. It must have a key, and we could have a method getKey which returns the key associated with the object the method is called on. For convenience, we will also want a number of operations that enable us to comape objects using their keys. We need a method to tell us whether the key of an object is equal to a given key, and a method that enables us to put objects in order, saying whether one object comes before another in alphabetical ordering of their keys (we will assume keys are always strings). We can express a general type for objects to go in collections as an abstract class. Here is the code for it: 
abstract class KeyObject
{
 public abstract String getKey();

 public boolean equalKey(String key)
 {
  return getKey().equals(key);
 }

 public boolean equalKey(KeyObject kobj)
 {
  return getKey().equals(kobj.getKey());
 }

 public boolean lessThan(String key)
 {
  return getKey().compareTo(key)<0;
 }

 public boolean lessThan(KeyObject kobj)
 {
  return getKey().compareTo(kobj.getKey())<0;
 }
}
Note that only the signature of the method getKey is given, and it is declared as abstract. What this means is that all objects of type KeyObject must have a method getKey with the signature as given, but we don't here specify how that method should work. It is expected that other classes will be introduced that use inheritance to extend the class KeyObject. These subclasses will provide the method getKey. They won't have to provide the other methods given in KeyObject as they will inherit these and the code from KeyObject.

KeyObject is itself declared as abstract as it contains an abstract method. This means that you cannot directly create a KeyObject object. But you can create an object of one of the classes that extends KeyObject. You can have variables and method parameters of type KeyObject and they can be set to refer to objects of any type that extends KeyObject. It is a general type, but not as general as the type Object which can be used to refer to objects of any type. The advantage of the KeyObject type is that we can write code which uses objects given this type, including making use of the methods defined within class KeyObject. This code is general and can be used in conjunction with any type of object so long as that type extends KeyObject.

For convenience, in class KeyObject we have given two versions of the methods equalKey and lessThan, one of which compares the object it is called on with the key passed as the argument to the method, the other of which has a whole KeyObject object as its argument, and we know we can call getKey on this argument object to get its key. When these methods are called, the version of the method that is used depends on the type of the argument given to the method.

The Table interface

Now we can introduce a class that defines tables. Here it is: 
import java.io.*;


interface Table
{
 public boolean delete(String key);
 public void add(KeyObject obj);
 public KeyObject retrieve(String key);
 public void print(PrintStream out);
}
Here we are using the idea of a Java interface. An interface is like a class where all the methods are abstract. You don't have to declare them as abstract since that is taken for granted, you cannot have anything in an interface except method signatures. Where a Java class extends another Java class, it implements a Java interface, meaning it gives code for each of the methods whose signatures are in the interface. The reason for having this separate concept of an interface in Java is that whereas a Java class can only directly extend one other Java class, it can implement any number of Java interfaces, a limited form of multiple inheritance. In other languages, for example, C++, a class can extend any number of any other classes.

This specific use of the keyword interface in Java to mean "a purely abstract class" should not be confused with the more general use of "interface" in programming to mean "the mechanism which enables one thing to interact with another". In particular, another use of the term "interface" is what is more correctly termed the "user interface", meaning what is seen when the program runs and interacts with its human user.

When we were considering different ways of implementing the general concept of "set of integers" we could have had a general interface called IntSet which gave the signatures of the methods any correct implementation should have (there would need to be a separate interface for destructive and constructive implementations of the set concept, however). Here is such an interface: 

interface IntSet
{
 public void delete(int n);
 public void add(int n);
 public boolean member(int n);
}
One advantage of this is that it is a way of checking that different implementations of the concept contain the correct classes for the concept. If we had defined this interface, then we should have written the code for set as before but with the first line: 
class IntSet1 implements IntSet
The Java compiler would then have checked that the code IntSet1 has methods delete with an int argument and return type void, add with an int argument and return type void, and member with int argument and return type boolean. The same would have applied for the other destructive implementations of sets of integers.

Note that our interface for tables has its delete method return a boolean. This is set to true if an item with its key equal to the argument is found and deleted from the table, to false if no such item is found. That contrasts with sets where we decided not to indicate whether the integer that was given as the parameter to the delete method was in the set.

Our interface for tables has an extra method called print which takes as its argument an object of the type PrintStream. This type is part of Java's java.io package. This method is intended to be used to display the entire contents of the table both onto the screen and onto files. The line import java.io.*; is needed because of this use of a type which comes from the java.io package. Only types which are in the java.lang package are made available automatically without the need of an import statement. Note that import statements are the only things in Java which appear outside classes and interfaces.

Two implementations of Table using arrays

Our simplest implementation of sets used an "array and count" representation. Each set object had an array field of the maximum size thought necessary for sets, and an int field saying how much of the array was actually used for the set.

Here is code for a Table class implemented in a similar way: 

import java.io.*;

class Table1 implements Table
{
// Table class, data stored in unordered partly-filled arrays

 private KeyObject[] array;
 private int count;
 final static int MAX=100;

 public Table1()
 {
  array = new KeyObject[MAX];
 }

 public boolean delete(String key)
 {
  int i;
  for(i=0; i<count&&!array[i].equalKey(key); i++) {}
  if(i<count)
     {
      array[i]= array[count-1];
      count--;
      return true;
     }
  else
     return false;
 }

 public void add(KeyObject obj)
 {
  int i;
  for(i=0; i<count&&!array[i].equalKey(obj); i++);
  if(i==count)
     array[count++] = obj;
 }

 public KeyObject retrieve(String key)
 {
  int i;
  for(i=0; i<count&&!array[i].equalKey(key); i++);
  if(i==count)
     return null;
  else
     return array[i];
 }

 public void print(PrintStream out)
 {
  for(int i=0;i<count;i++)
     out.println(array[i]);
 }
}
Note the similarity with the code that implemented sets in the same way which you can view here. In the place of testing whether an array item is equal to the integer given as a parameter, here the test is whether the key of the array item is equal to the key given as a parameter. The test is done using the equalKey method from class KeyObject. When a new item is added using the add method, a test is made to see if the item is already in the array, and this uses the equalKey method that takes a KeyObject rather than a string as its argument. Nothing is done if an item with the same key is found, otherwise the new item is added at the end of the used portion of the array, and the count field increased by one showing the increase in the size by one of the portion of the array that is in use. If an item is to be deleted, as with sets of integers previously, the "hole" left by the deletion of the item is covered by copying into it the last item from the array, and then the count is reduced by one so the original reference to it is no longer counted as part of the data.

In the case of retrieve the code is similar to that of member with sets, but in the place of returning true if the integer is found in the set, false otherwise, the item with the given key is returned if one is found, and null otherwise. Note that it is always possible to return the value null where the return type is any object type. This is one way of showing that an exceptional condition has been met (in this case, no object with the given key in the table) such that an object could not be returned. The other way of doing that would be to throw a Java exception. As with delete we know an item is not in the table if we look through all the items in the portion of the array used to store data (that is, up to but not the item indexed by count) and don't find one whose key is equal to the key given as the method's argument.

In the case of print, note that PrintStream is the type of System.out. We have been using System.out.print and System.out.println to print things onto the command window, but in fact System.out is an object that is available in all programs that has methods print and Println. So we can attach calls to print and println to any PrintStream object.

For comparison, let us now consider another implementation of tables using arrays, but this time with the data in the arrays ordered, and the array only of size equal to the number of items in the table. We gave an implementation of sets in this way here. As we noted then, the advantage of using arrays in which the data is ordered is that we can use binary search to test whether a particular item is in the array, and this is the more efficient O(n log n) rather than O(n). Using fully-filled arrays is efficient in memory usage terms, since it means that no more space than is necessary is used. But it is inefficient in terms of time, since it means that each time an item is added or deleted, a new array has to be created of the size of the new collection, and references to objects in the old array (or the actual values with arrays of integers or other primitive types) copied into the new array.

Here is the code: 

import java.io.*;

class Table2 implements Table
{
// Table class, data stored in ordered fully-filled arrays

 protected KeyObject[] array;

 public Table2()
 {
  array = new KeyObject[0];
 }

 public boolean delete(String key)
 {
  int i;
  for(i=0; i<array.length&&array[i].lessThan(key); i++) {}
  if(i<array.length&&array[i].equalKey(key))
     {
      KeyObject[] array1 = new KeyObject[array.length-1];
      for(int j=0; j<i; j++)
         array1[j]=array[j];
      for(i++;i<array.length; i++)
         array1[i-1]=array[i];
      array=array1;
      return true;
     }
  else
     return false;
 }

 public void add(KeyObject obj)
 {
  int i;
  for(i=0; i<array.length&&array[i].lessThan(obj); i++) {}
  KeyObject[] array1 = new KeyObject[array.length+1];
  for(int j=0; j<i; j++)
     array1[j]=array[j];
  array1[i]=obj;
  for(int j=array.length; j>i; j--)
     array1[j]=array[j-1];
  array=array1;
 }

 public KeyObject retrieve(String key)
 {
  int from=0, to=array.length;
  int mid=(from+to)/2;
  while(from!=to&&!array[mid].equalKey(key))
     {
      if(!array[mid].lessThan(key))
         to=mid;
      else
         from=mid+1;
      mid=(from+to)/2;
     }
  if(from==to)
     return null;
  else
     return array[mid];
 }

 public void print(PrintStream out)
 {
  for(int i=0;i<array.length;i++)
     out.println(array[i]);
 }

}
Note the use of binary search in retrieve. The midpoint of the array is looked at initially to see if its key is equal to the key given as an argument to the method. If not, it is looked at to see if it is less than or greater than the key given as the argument to the method. This uses the method lessThan from the KeyObject class. Search then goes to the cells on one or other side of the midpoint, unless the midpoint cell happened to be the one with the given key.

Two implementations of Table using linked structures

Now let us consider implementations of the interface Table using linked structures. As with the implementations using arrays, they resemble closely the implementations of sets we have already see. We saw an implementation of sets using unordered linked lists, now below is an implementation of tables using unordered linked lists: 
import java.io.*;

class Table3 implements Table
{
// Table class, data stored in unordered linked lists

 Cell list;

 public boolean delete(String key)
 {
  if(list!=null)
     if(list.first.equalKey(key))
        {
         list=list.next;
         return true;
        }
     else
        {
         Cell ptr;
         for(ptr=list; 
             ptr.next!=null&&!ptr.next.first.equalKey(key); 
             ptr=ptr.next)
           {}
         if(ptr.next!=null)
            {
             ptr.next=ptr.next.next;
             return true;
            }
         else
            return false;
        }
  else
     return false;
 }

 public void add(KeyObject obj)
 {
  list = new Cell(obj,list);
 }

 public KeyObject retrieve(String key)
 {
  Cell ptr;
  for(ptr=list; ptr!=null&&!ptr.first.equalKey(key); ptr=ptr.next) {}
  if(ptr==null)
     return null;
  else
     return ptr.first;
 }

 public void print(PrintStream out)
 {
  Cell ptr;
  for(ptr=list; ptr!=null; ptr=ptr.next)
     out.println(ptr.first);
 }

 private static class Cell
 {
  KeyObject first;
  Cell next;

  Cell(KeyObject f,Cell n)
  {
   first=f;
   next=n;
  }
 }

}
In this case, unlike the above implementation using unordered arrays, there is no check to see when an item is added that there is not already an item with the same key, the new item is always just put at the front of the linked list. As we had with sets, there is an inner class called Cell to give the nodes of the linked list, though the first field of Cell is of type KeyObject so each cell can store a reference to a KeyObject object. The method equalKey is used where we used arithmetic equality (using ==) with sets of integers. Note the modifications to the delete method required so that it returns true if an item with the given key is found and deleted, and false otherwise, whereas with our sets nothing happened if the item being deleted wasn't found.

Finally, let us consider an implementation using ordered trees. Again, this can be obtained fairly easily from the equivalent implementation of sets. Here is the code: 

import java.io.*;

class Table4 implements Table
{
// Table class, data stored in ordered trees

 Cell tree;

 public boolean delete(String key)
 {
  if(tree!=null)
     if(tree.left==null&&tree.right==null)
        {
         if(tree.item.equalKey(key))
            {
             tree=null;
             return true;
            }
         else
            return false;
        }
     else
        return delete(key,tree);
  else
     return false;
 }

 private static boolean delete(String key,Cell t)
 {
  if(t.item.lessThan(key))
     if(t.right==null)
        return false;
     else if(t.right.left==null&&t.right.right==null)
         if(t.right.item.equalKey(key))
            {
             t.right=null;
             return true;
            }
         else
            return false;
     else
        return delete(key,t.right);
  else if(!t.item.equalKey(key))
     if(t.left==null)
        return false;
     else if(t.left.left==null&&t.left.right==null)
        if(t.left.item.equalKey(key))
           {
            t.left=null;
            return true;
           }
        else
           return false;
    else
       return delete(key,t.left);
  else
     {
      if(t.left==null)
         {
          t.item=t.right.item;
          t.left=t.right.left;
          t.right=t.right.right;
         }
      else if(t.left.right==null)
         {
          t.item=t.left.item;
          t.left=t.left.left;
         }
      else
         t.item = removeRightmost(t.left);
      return true;
     }
 }

 private static KeyObject removeRightmost(Cell t)
 {
  if(t.right.right==null)
     {
      KeyObject rightmost = t.right.item;
      t.right = t.right.left;
      return rightmost;
     }
  else
     return removeRightmost(t.right);
 }

 public void add(KeyObject obj)
 {
  if(tree==null)
     tree = new Cell(obj,null,null);
  else
     add(obj,tree);
 }

 private static void add(KeyObject obj,Cell t)
 {
  if(t.item.lessThan(obj))
     if(t.right==null)
        t.right = new Cell(obj,null,null);
     else
        add(obj,t.right);
  else
     if(t.left==null)
        t.left = new Cell(obj,null,null);
     else
        add(obj,t.left);
 }

 public KeyObject retrieve(String key)
 {
  return retrieve(key,tree);
 }

 private static KeyObject retrieve(String key,Cell t)
 {
  if(t==null)
     return null;
  else if(t.item.equalKey(key))
     return t.item;
  else if(t.item.lessThan(key))
     return retrieve(key,t.right);
  else
     return retrieve(key,t.left);
 }

 public void print(PrintStream out)
 {
  print(out,tree);
 }

 private void print(PrintStream out,Cell tree)
 {
  if(tree!=null)
     {
      out.println(tree.item);
      print(out,tree.left);
      print(out,tree.right);
     }
 }

 public void orderedPrint(PrintStream out)
 {
  orderedPrint(out,tree);
 }
 
 private void orderedPrint(PrintStream out,Cell tree)
 {
  if(tree!=null)
     {
      orderedPrint(out,tree.left);
      out.println(tree.item);
      orderedPrint(out,tree.right);
     }
 }

 private static class Cell
 {
  KeyObject item;
  Cell left,right;
  
  Cell(KeyObject n,Cell l,Cell r)
  {
   item=n;
   left=l;
   right=r;
  }
 }
}
Here the print method writes the file to a printStream using an preorder tree traversal. This means that if a table is read from the file created here it will re-create the same tree structure. A second printing method orderedPrint is given which prints the tree using inorder tree traversal. This results in the items in the tree being printed in order of their key.
Matthew Huntbach

Last modified: 28 March 2003