Enumerations: the student database examples, part 3

Avoiding overspecialisation

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);
}

The print method seems a bit of an anomaly, too specific for a general type like Table, but it was introduced for convenience.

However, it is a good example of how a poor design decision may limit us later. If we consider extending our student database program, we might think of various operations which involve going through each of the student records in the database one by one. But in the interface Table In general, we need to avoid as much as possible being too specific in how we define anything we may wish to modify later. It is much easier to modify something that has been defined generally. If we had a general way of going through the items in a table, we could make use of it for printing the items out, but also for other things, such as our case of adding a new mark to all student records. In the implementations of Table we have given, however, there is no way of going through all the items in the table unless we do that inside the class implementing Table since it requires accessing the actual data structure of the table. Doing this, however, would break the careful distinction we have made between the code implementing an abstract data type and the code whia uses it.

The Enumeration interface

An object of type Enumeration has methods nextElement and hasMoreElements that can be called on it. The object is formed with reference to some collection of objects. Each time nextElement is called on it, an item from the collection is returned. No item from the collection is returned more than once, and if nextElement is called enough times, eventually all the items in the collection will get returned. If there are no more items that can be returned from calls of nextElement, a call of hasMoreElements on the enumeration object will return false, otherwise it will return true. Although it is not defined exactly what will happen if nextElement is called when there are no more items to return, that will usually cause an exception to be thrown. The type Enumeration can be defined by the Java interface:

interface Enumeration
{
 boolean hasMoreElements();
 Object nextElement();
}

Using an Enumeration from a Table

import java.util.*;

interface ETable
{
 public boolean delete(String key);
 public void add(KeyObject obj);
 public KeyObject retrieve(String key);
 public Enumeration getEnumeration();
}                                                                              

Now we can consider a version of our student database program that makes use of objects of type ETable:

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

class StudentDatabase8
{
// Database implemented with unordered partly-filled array
// Uses Enumerations

 public static void main(String[] args)
 throws IOException
 {
  ETable table = new ETable1();
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  BufferedReader file;
  Enumeration enum;
  Student student;
  String name;
  int mark;
  char ch;
  do {
      System.out.print(": ");
      StringTokenizer toks = new StringTokenizer(in.readLine());
      ch = toks.nextToken().charAt(0);
      switch(ch)   
         {
          case 'a' :
            table.add(new Student(in));
            break;
          case 'c' :
            enum = table.getEnumeration();
            while(enum.hasMoreElements())
               {
                student = (Student) enum.nextElement();
                System.out.print("Enter mark for "+student.getKey()+": ");
                student.addMark(Integer.parseInt(in.readLine()));
               }
            break;
          case 'd' :
            name = toks.nextToken();
            if(!table.delete(name))
               System.out.println("No student named "+name);
            break;
          case 'f' :
            file = new BufferedReader(new FileReader(toks.nextToken()));
            try {
                 while(true)
                    table.add(new Student(file));
                }
            catch(Exception e) {}
            file.close();
            break;     
          case 'm':
            name = toks.nextToken();
            mark = Integer.parseInt(toks.nextToken());
            student = (Student) table.retrieve(name);
            if(student==null)
               System.out.println("No student named "+name);
            else
               student.addMark(mark);
            break;
          case 'p':
            enum = table.getEnumeration();
            while(enum.hasMoreElements())
               System.out.println(enum.nextElement());
            break;
          case 'q':
            break;
          case 'r':
            name = toks.nextToken();
            student = (Student) table.retrieve(name);
            if(student==null)
               System.out.println("No student named "+name);
            else
               System.out.println(student);
            break;
          case 'w':
            enum = table.getEnumeration();
            name = toks.nextToken();
            PrintStream out = new PrintStream(new FileOutputStream(name));
            while(enum.hasMoreElements())
               out.println(enum.nextElement());
            out.close();
            break;
          default:
            System.out.println(" a - add, c - class mark, d - delete,");
            System.out.println(" f - file read, m - add mark, p - print,"); 
            System.out.println(" q - quit, r - retrieve, w - file write ");
         }
     }
  while(ch!='q');
 }
}

     enum = table.getEnumeration();
     while(enum.hasMoreElements())
        System.out.println(enum.nextElement());

We have added the new command c to the database program to show further use of enumerations. This command goes through all the students in the database prompting the user for a new mark for each. Here is the code which gives it:

     enum = table.getEnumeration();
     while(enum.hasMoreElements())
        {
         student = (Student) enum.nextElement();
         System.out.print("Enter mark for "+student.getKey()+": ");
         student.addMark(Integer.parseInt(in.readLine()));
        }                                                               

Constructing an Enumeration from a table implemented using an array

import java.util.*;

class ETable1 implements ETable
{
// Table class with Enumeration, 
// data stored in unordered partly-filled arrays

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

 public ETable1()
 {
  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 Enumeration getEnumeration()
 {
  return new MyEnumeration();
 }

 private class MyEnumeration implements Enumeration
 {
  int current;

  MyEnumeration()
  {
   current=0;
  }

  public boolean hasMoreElements()
  {
   return current<count;
  }

  public Object nextElement()
  {
   return array[current++];
  }
 }
}

A call of getEnumeration on an object of type ETable1 returns an object of type MyEnumeration as defined inside ETable1 (another way of referring to this type is ETable1.MyEnumeration. At first this may seem odd, because how can the world outside the ETable1 class make use of an object defined by the class MyEnumeration which is private to ETable1. It can do so because MyEnumeration implements the public class Enumeration and the outside world sees it as object of type Enumeration.

In this example, if an Enumeration object is returned from an ETable1 object, and then the ETable1 object is altered by calling add or delete on it, the contents of the enumeration are changed. This would not be observed in the above example, because on each time when an enumeration is created, it is always gone right through before any other command on the database is made.

Constructing an Enumeration from a table implemented using an ordered tree

 public Enumeration getEnumeration()
 {
  return new MyEnumeration();
 }

 private class MyEnumeration implements Enumeration
 {
  ECell list;

  MyEnumeration()
  {
   list=flatten(tree,null);
  }

  public boolean hasMoreElements()
  {
   return list!=null;
  }

  public Object nextElement()
  {
   Object obj = list.first;
   list = list.next;
   return obj;
  }

  private ECell flatten(Cell t,ECell l)
  {
   if(t==null)
     return l;
   else
      {
       l = flatten(t.right,l);
       l = flatten(t.left,l);
       l = new ECell(t.item,l);
       return l;
      }
  }

  private class ECell
  {
   KeyObject first;
   ECell next;

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

So a MyEnumeration object here has inside it a linked list of KeyObjects, and each time nextElement is called on it, it returns the head of the list and sets the list to its tail.

The method flatten which produces the linked list from the tree uses a similar idea to that we used to gain a more efficient quick sort of lists: passing in an accumulator list parameter and then joining the new items to its front. The tree is traversed right-to-left, so the items from the right branch of the tree are joined first to the accumulator before the items from the left branch. Joining the node-value in between makes it right-to-left inorder traversal, although since we made no guarantee that our enumeration would return the items in the table in any particular order, it does not really matter.

In this case, since the linked list which is used in the enumeration is constructed completely at the time the enumeration is constructed, the enumeration would not be affected by any later calls to add or delete items from the table. The calls of nextElement on it will always return the elememnts as they existed in the table at the time the enumeration was created.

An alternative way of dealing with the enumeration would be to use a stack of trees, in the way we showed previously for recursion elimination. Here is the code for doing it this way:

 private class MyEnumeration implements Enumeration
 {
  ECell stack;

  MyEnumeration()
  {
   if(tree==null)
     stack=null;
   else
     stack = new ECell(tree,null);
  }

  public boolean hasMoreElements()
  {
   return stack!=null;
  }

  public Object nextElement()
  {
   Cell t = stack.first;
   stack = stack.next;
   if(t.left!=null)
     stack = new ECell(t.left,stack);
   if(t.right!=null)
     stack = new ECell(t.right,stack);
   return t.item;
  }

  private class ECell
  {
   Cell first;
   ECell next;

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

This also has the advantage that the enumeration does not do any unnecessary work. It traverses the tree piecemeal as each call to nextElement is made rather than completely when the enumeration is created. If the enumeration is never used up completely to go through the whole tree, then it has not wasted any effort traversing those parts of the tree which were never asked for with a nextElement call. The idea of evaluating a structure (in this case the list of items from the tree) only as and when needed rather than in advance of its need is developed further and more formally in functional programming under the name lazy evaluation.

Constructing an Enumeration from a hash table

import java.util.*;

class ETable4 implements ETable
{
// Table class, data stored in hash table
// Handles collisions with linear probing
// Returns an Enumeration

 private KeyObject[] array;
 final static int SIZE=41;

 public ETable4()
 {
  array = new KeyObject[SIZE];
 }

 public boolean delete(String key)
 {
  int i = hash(key);
  while(array[i]!=null&&!array[i].equalKey(key))
     i=(i+1)%SIZE;
  if(array[i]==null)
     return false;
  else
     {
      array[i] = new Deleted();
      return true;
     }
 }

 public void add(KeyObject obj)
 {
  int i = hash(obj.getKey());
  while(array[i]!=null && !(array[i] instanceof Deleted))
     i=(i+1)%SIZE;
  array[i]=obj;
 }

 public KeyObject retrieve(String key)
 {
  int i = hash(key);
  while(array[i]!=null&&!array[i].equalKey(key))
     i=(i+1)%SIZE;
  return array[i];
 }

 public Enumeration getEnumeration()
 {
  return new MyEnumeration();
 }

 private static int hash(String key)
 {
  int val=0;
  key = key.toLowerCase();
  for(int i=0; i<key.length(); i++)
     if(Character.isLetter(key.charAt(i)))
        val=(val*32+key.charAt(i)-'a')%SIZE;
  return val;
 }

 private static class Deleted extends KeyObject
 {
  public String getKey()
  {
   return "";
  }
 }

 private class MyEnumeration implements Enumeration
 {
  int current;

  MyEnumeration()
  {
   current=-1;
   moveCurrent();
  }

  public boolean hasMoreElements()
  {
   return current<SIZE;
  }

  public Object nextElement()
  {
   Object obj = array[current];
   moveCurrent();
   return obj;
  }

  private void moveCurrent()
  {
   current++;
   while(current<SIZE&&
         (array[current]==null||array[current] instanceof Deleted))
      current++;
  }
 }
}

The code for creating an enumeration from a hash table which uses separate chaining is slightly more complicated. Here is its MyEnumeration inner class:

 private class MyEnumeration implements Enumeration
 {
  Cell ptr;
  int current;

  MyEnumeration()
  {
   current=0;
   while(current<SIZE&&array[current]==null)
      current++;
   if(current<SIZE)
      ptr=array[current];
  }

  public boolean hasMoreElements()
  {
   return current<SIZE;
  }

  public Object nextElement()
  {
   Object obj=ptr.first;
   ptr=ptr.next;
   if(ptr==null)
      {
       current++;
       while(current<SIZE&&array[current]==null)
          current++;
       if(current<SIZE)
          ptr=array[current];
      }
   return obj;
  }
 }

Last modified: 20 March 2003