Tutorial 3      Lecturer: Ray Reiter          Tutor: Andria Hunter
==========                                  990120 Wed@1pm (PA105)

CSC148, Spring 1999                            Tutorial notes,  T3
==================================================================

Topics:
------------------------------

  - last chance for questions on A0
  - interfaces and implementations

Notes:
------------------------------

  - finished Abstraction & ADTs, up through slide 102 in lecture.
  - read the course web page, including the A0 Announcements
       and Advice page, for recent announcements.
  - do the online homework (unmarked) on parameters and references.

Assignment 0 [10 minutes]
------------------------------

  - Answer questions arising from assnt 0.  Note that commonly asked
     questions have probably already been answered on the web page.

  - A0 is due next Friday

Understanding interfaces
------------------------------

  - In this tutorial you will develop an interface and implement it
    in two different ways.

  - You will redesign Element from the lecture notes; currently
    Element is a class, but that's limited since it can contain
    only ints.

  - It's much like the Comparator ADT defined on page 210 of the
    text.  (We will define something called ComparisonKey later
    this term which has the same functionality of Comparator.)

Solution code [15 minutes]
-------------

Here are two interfaces.  You should have already seen the OSet
interface in class, and a class Element that had the same methods.

Notice that we are using 0..size-1 as the ranks, not 1..size as
the lecture notes have them.


public interface OSet {
    // init: Make me empty.
    // ------------------------------------------------------------------
    public void init();

    // size: Return the number of elements that I contain.
    // ------------------------------------------------------------------
    public int size();

    // insert: Ensure exactly one copy of element e is in me.
    // ------------------------------------------------------------------
    public void insert(Element e);

    // retrieve: Return my element whose position is rank.
    // Pre: 0 <= rank && rank < this.size()
    // ------------------------------------------------------------------
    public Element retrieve(int rank);

    // delete: Ensure the element at position rank is no longer there.
    // Pre: 0 <= rank && rank < this.size()
    // ------------------------------------------------------------------
    public void delete(int rank);
}


public interface Element {
    // equals
    // ------------------------------------------------------------------
    // Return true iff e has the same value that I do.
    public boolean equals(Element e);

    // lessThan
    // ------------------------------------------------------------------
    // Return true iff my value is less than e's value.
    public boolean lessThan(Element e);
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Given the two previous interfaces, and the fact that ALL classes
inherit all features of Object, including toString(), we are now in
a position to write code to manipulate an OSet.  Write a class that
contains a method to print each element in an OSet, and a method
to save an OSet to a file (the filename is passed to this method).

Note that for the RandomAccessFile, you only need to know about the
constructor and RandomAccessFile.writeChars() method.  The "rw" is
for a file with read and write privileges.

The saveToFile method includes exception handling code, in case
an Exception is generated by the code that writes to the file.

import java.io.*;
public class OSetManipulator {

    // Print all the values in o.
    // ------------------------------------------------------------------
    public static void print( OSet o ) {
        for (int r = 0; r < o.size(); r++) {
            Element el = o.retrieve(r);
            System.out.println("Element " + r +
                               " by rank is: " + el.toString());
        }
    }

    // Save all the elements of theOSet to file named filename.
    // ------------------------------------------------------------------
    public static void saveToFile( OSet theOSet, String filename ) {
        RandomAccessFile output;
        try {
            output = new RandomAccessFile(filename, "rw");
            for (int r = 0; r < theOSet.size(); r++) {
                Element el = theOSet.retrieve( r );
                output.writeChars( (el.toString() + "\n") );
            }
        } catch( IOException e ) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Implementation of Element interface [20 minutes]

- Next, we actually implement Element.  This one will store ints.
  Notice the toString() method; it redefines the way Object.toString()
  works.  (We will go over this sort of thing in more detail in class
  in a week or two.)

- Notice the type casting.  We know that, in equals(), e had better
  be an IntElement, since any particular OSet should only store one
  type.  But Java currently only knows that it's an Element.  So we
  *cast* it as an IntElement, so that Java lets us look at the myInt
  instance variable.  And yes, all the parentheses are necessary.

public class IntElement implements Element {
    protected int myInt;

    // Constructor.  Create me with value val.
    // ------------------------------------------------------------------
    public IntElement( int val ) {
        myInt = val;
    }

    // Return me as a String.
    // ------------------------------------------------------------------
    public String toString() {
        return String.valueOf(myInt);
    }

    // Return true iff e has the same value that I do.
    // ------------------------------------------------------------------
    public boolean equals(Element e) {
        return myInt == ((IntElement)e).myInt;
    }

    // Return true iff my value is less than e's value.
    // ------------------------------------------------------------------
    public boolean lessThan(Element e) {
        return myInt < ((IntElement)e).myInt;
    }
}

class OSetIntDriver {
    public static void main(String[] args) {
        int r;

        OSet o = new OSetArray();
        System.out.println("Set size = " + o.size());

        o.insert(new IntElement(10));
        o.insert(new IntElement(11));
        o.insert(new IntElement(5));
        o.insert(new IntElement(20));
        o.insert(new IntElement(8));

        System.out.println("Set size = " + o.size());

        OSetManipulator.print( o );

        System.out.println("\nDeleting element 1" +
                           " by rank");
        o.delete(1);

        OSetManipulator.print( o );
        OSetManipulator.saveToFile( o, "IntFile" );
    }
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Implementation of Element interface [10 minutes]

- You don't need to change OSetManipulator to handle StringElements.
  This strategy saves tons of time later on in software projects when
  you need to do almost the same thing as something that's already
  done; if that other thing was written in a general way, you'd just
  be able to plug into it.

public class StringElement implements Element {
    private String value;

    // Constructor.  Create me with value val.
    // ------------------------------------------------------------------
    public StringElement( String val ) {
        value = val;
    }

    // Return me as a String.
    // ------------------------------------------------------------------
    public String toString() {
        return value;
    }

    // Return true iff e has the same value that I do.
    // ------------------------------------------------------------------
    public boolean equals(Element e) {
        return value.equals( ((StringElement)e).value );
    }

    // Return true iff my value is less than e's value.
    // ------------------------------------------------------------------
    public boolean lessThan(Element e) {
        return ( value.compareTo( ((StringElement)e).value ) < 0 );
    }
}

class OSetStringDriver {
    public static void main(String[] args) {
        int r;
        OSet o = new OSetArray();
        System.out.println("Set size = " + o.size());

        o.insert(new StringElement("Wombat"));
        o.insert(new StringElement("Kangaroo"));
        o.insert(new StringElement("Emu"));
        o.insert(new StringElement("RoadPizza"));
        o.insert(new StringElement(""));

        System.out.println("Set size = " + o.size());
        OSetManipulator.print( o );

        System.out.println("\nDeleting element 1" +
                 " by rank");
        o.delete(1);

        OSetManipulator.print( o );
        OSetManipulator.saveToFile( o, "StringFile" );
    }
}
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

// This is included ONLY for your reference.  Don't write any
// of this on the board, it will take way too long.

class OSetArray implements OSet {

    // The maximum number of Elements I can store.
    private final int MAXSIZE = 500;

    // The number of elements I actually store right now.
    private int numElements;

    // Maintain my contents in a sorted array.
    private Element[] contents;

    // OSetArray Constructor.  Create a new empty OSet.
    // ------------------------------------------------------------------
    public OSetArray() {
        contents = new Element[MAXSIZE];
        numElements = 0;
    }

    // init: Make me empty.
    // ------------------------------------------------------------------
    public void init() {
        numElements = 0;
    }

    // size: Return the number of elements that I contain.
    // ------------------------------------------------------------------
    public int size() {
        return numElements;
    }

    // insert: Ensure exactly one copy of element e is in me.
    // ------------------------------------------------------------------
    public void insert(Element e) {
        int position = binarySearch(e);

        // If contents[position] is not e, insert it.
        if (position == size() || !contents[position].equals(e)) {
            insertAt(position, e);
        }
    }

    // retrieve: Return my element whose position is rank.
    // Pre: 0 <= rank && rank < this.size()
    // ------------------------------------------------------------------
    public Element retrieve(int rank) {
        return contents[rank];
    }

    // delete: Ensure the element at position rank is no longer there.
    // Pre: 0 <= rank && rank < this.size()
    // ------------------------------------------------------------------
    public void delete(int rank) {
        for(int i = rank; i < numElements - 1; i++) {
            contents[i] = contents[i + 1];
        }

        numElements--;
    }

    // binarySearch: Return the index of the first element greater
    // than or equal to e, or size() if all of my elements are less
    // than e.
    // ------------------------------------------------------------------
    private int binarySearch(Element e) {

        int i = 0;
        int j = size()-1;

        // Inv: contents[0 .. i-1] < e && contents[j+1 .. size()-1] >= e
        // Post: contents[0 .. i-1] < e && contents[i .. size()-1] >= e

        while (i != j+1) {
            int mid = (i + j) / 2;
            if (contents[mid].lessThan(e)) {
                i = mid+1;
            } else {
                j = mid-1;
            }
        }

        // Now i is the index of the first item whose value is >= e.
        return i;
    }

    // insertAt: Insert element e at position pos in my set.
    // Pre: 0 <= position && position <= size() && size() < MAXSIZE - 1
    // ------------------------------------------------------------------
    private void insertAt(int pos, Element e) {

        // Make room for the new element by shifting everything
        // from position p and up one to the right.
        for (int i = numElements - 1; i >= pos; i--) {
            contents[i+1] = contents[i];
        }

        contents[pos] = e;
        numElements++;
    }
}

Program Output:
------------------------------

% java OSetIntDriver

Set size = 0
Set size = 5
Element 0 by rank is: 5
Element 1 by rank is: 8
Element 2 by rank is: 10
Element 3 by rank is: 11
Element 4 by rank is: 20

Deleting element 1 by rank
Element 0 by rank is: 5
Element 1 by rank is: 10
Element 2 by rank is: 11
Element 3 by rank is: 20



% java OSetStringDriver

Set size = 0
Set size = 5
Element 0 by rank is:
Element 1 by rank is: Emu
Element 2 by rank is: Kangaroo
Element 3 by rank is: RoadPizza
Element 4 by rank is: Wombat

Deleting element 1 by rank
Element 0 by rank is:
Element 1 by rank is: Kangaroo
Element 2 by rank is: RoadPizza
Element 3 by rank is: Wombat