CSci 581: Obj.-Oriented Design & Programming
Spring Semester 1999
Lecture Notes

A method declared in a class may be either a class method or instance method.

• A class method is associated with the class as a whole, not with any specific instance.
• An instance method is associated with an instance of the class.

We declare a method as a class method by giving the keyword static in the header of its definition. For example, a main method of a program is a class method of the class in which it is defined.

    public static void main(String[] args) 
    {   //  beginning code for the program
    }

If we do not include the keyword static in the header of a method definition, the method is an instance method. For example, consider methods to implement the push and top operations of a class that implements a stack.

    public void pop()
    {   // code for pop operation
    }

    public Object top()
    {   // code for top operation
    }

Note that pop() is a procedure (i.e., it has return type void) method and top is a function method.

Class and Instance Variables

In a similar fashion, the variables (data fields) declared in a class may be either class variables or instance variables.

• A class variable is associated with the class as a whole; there is only one copy of the variable for the entire class. As with methods, the keyword static is used to declare a class variable.

• An instance variable is associated with an instance of the class; each instance has its own instance of the variable. As with methods, the absence of the keyword static denotes an instance variable.

An instance method has access to the instance variables of the class instance (object) to which it is applied. The instance's variables are implicit arguments of the method calls. The instance methods also have access to the class variables (if any).

Class methods only have access to the class variables. The methods do not have any implicit arguments. In fact, class methods can be called without any instances of the class being in existence.

Public and Private Accessibility

The components of a class can be designated as public or private.

• The public components of the class are accessible from anywhere in the program.

• The private components are only accessible from inside the class.

As a general rule, the data fields of a class should be private instance variables, meaning that they are associated with a specific instance and are only accessible by the instance methods. This hides, or encapsulates, the data fields within the class instance.

Note: Actually, the instance methods of a class can access the instance variables of any instance of that class, not just the current instance.

In general, avoid public instance variables. They break the principle of information hiding, leading to potential entanglements among modules.

A public method of a class is a service provided by that instance to other parts of a program. The private methods of a class can be used in implementing the public methods.

Class methods and variables should be used sparingly. These are more or less the types of subprograms and global variables found in languages like Pascal and C. Their excessive use can greatly reduce the potential benefits that can be realized from object-oriented techniques.

Note: There are two other types of accessability, "friendly" and protected, but public and private are sufficient for our purposes in discussion of ADT implementations.

Primitive or Reference Variables

A Java variable is a strongly typed "container" in memory that is declared to hold either:

• a value of the associated primitive data type such as integers (int), booleans (boolean), and single characters (char).

• a reference (i.e., memory address) to an instance of the associated class (or other reference) type.

The class instances themselves are stored in the dynamically managed heap memory area. Java allocates memory from the heap to hold newly constructed instances of a class. Java's garbage collector reclaims the memory for instances that are no longer needed by the program.

Implementing ADTs as Java Classes

One way to implement an ADT in Java is to do the following:

1. Use the Java class construct to represent the entire ADT. If we want to allow access to the class from anywhere in the program, we will make the class public.

   For the StackB ADT, we can use the following structure for the class:

       public class StackB
       {   // implementation of instance methods and data here
       }
   

2. Use an instance of the Java class to represent an instance of the ADT and, hence, variables of the class type to hold references to instances.

   For example, to declare a variable that can hold a reference to a StackB instance, we can use the following declaration:

       StackB stk;
   

3. Represent the ADT's constructor by Java constructor methods.

   A Java constructor is a method with the same name as the class. It does not have a return type specified. Upon creation of an instance of the class, the constructor initializes the instance's state.

   A constructor is normally invoked by the Java operator new. The operator new allocates memory on the heap for the instance, calls the constructor to initialize the new instance, and then returns a reference to the new instance.

   For example, we can represent the ADT operation create by the constructor method StackB.

       public class StackB
       {   public StackB(int size)
           {   // initialization code
           }
   
           // rest of StackB methods and data ...
       }
   

   A user of the StackB class can then declare a variable and initialize it to hold a reference to a new stack with a capacity of 100 items as follows:

       StackB stk = new StackB(100);
   

   The expression new StackB(100) allocates a StackB instance in the heap storage and calls the constructor above to initialize the data fields encapsulated within the instance.

4. Represent the ADT operations by instance methods of the class. Thus the state of the ADT instance, which is given explicitly in the ADT signatures, becomes an implicit argument of all method calls. Mutators also have the state as an implicit return.

   We can apply a method to a class instance by using the selector (i.e., "dot") notation. This notation is similar to the notation for accessing record components in Pascal.

   For example, in the case of the StackB ADT we can represent the operations as instance methods of class StackB. The explicit StackB parameters and return values of the operations thus become implicit.

   Suppose we want to push an item x onto the stk created above. We can do that with the following code:

       if (!stk.full())
           stk.push(x); 
   

   We can then examine the top item and remove it:

       if (!stk.empty())
       {   it = stk.top();
           stk.pop(); 
       }
   

5. Make the constructors, mutators, accessors, and destructors public methods of the class. That is, precede the method's definition by the keyword public.

6. Represent the ADT mutator operations by Java procedure (i.e., void) methods, except those mutator operations that explicitly require new instances to be generated (e.g., a copy operation). These methods modify the encapsulated state of the class instance (which is the implicit argument of the methods).

       public void pop()
       {   //  code to implement operation
       }
   

   Comment: Implementing mutator operations as procedure calls that modify the stored state is really an optimization. All mutators can be implemented in the applicative style, returning a modified copy of the instance. This implementation might, however, be quite inefficient in use of processor time and memory.

7. As appropriate, implement some of the ADT mutator operations (e.g., a copy method) to return a new instance of the ADT's class rather than modify the instance itself (i.e., the implicit parameter).

8. Represent the ADT accessor operations by Java function methods of the proper return type. These functions can access the encapsulated state of the class instance (which is the implicit argument of these methods) and compute a value to be returned.

       public boolean empty()
       {   //  code to implement operation
       }
   

9. If necessary for deallocation of internal resources, represent the ADT destructor methods by explicit Java procedures; otherwise, just allow the automatic garbage collection to reclaim instances that are no longer being used.

       public void destroy()
       {   //  code to free resources
       }
   

10. Use private data fields of the Java class to represent the encapsulated state of the instance needed for a particular implementation. By making the data fields private they are still available to the instance's methods, but are not visible outside the class.

        public class StackB
        {   //  public operations of class instance
        
            //  encapsulated data fields of class instance
            private int topItem;   // Pointer to next index for insertion
            private int capacity;  // Maximum number of items in stack
            private Object[] stk;  // the stack
        }
    

11. Do not use public data fields in the class. They violate the principle of information hiding. Instead introduce appropriate accessor and mutator methods to allow manipulation of the hidden state.

12. Include, as appropriate, private methods to aid in implementation. Functionality common to several methods can be placed in separate functions and procedures as needed. However, since these are private, they can only be accessed from within the class and thus can be changed without affecting the public interface of the class.

13. Add any other methods needed to make the ADT fit into the Java environment. For example, it is frequently useful to add a public toString() method to convert an instance of the ADT's class to an appropriately valued Java String for printing.

Java does not currently have a parameterized class facility (like the C++ template or Ada generic mechanisms). We must handle the type parameters of the ADT in other ways.

For example, in the next section we represent the set Item of the StackB ADT by the class Object. As we will see when we discuss inheritance, the Object type will allow us to store an instance of any class on the StackB. With this definition, any data of a reference type can appear in the stack, but values of the primitive types cannot.

Java Implementation of the Bounded Stack

In this section, we give an implementation of the StackB ADT that uses an array of objects and an integer "pointer" to represent the stack.

This implementation is not robust; each operation assumes that its precondition holds. A more robust implementation might check whether the precondition holds and throw an exception if it does not.

Remember that the invariants are implicitly pre- and postconditions of all mutator and accessor methods, postconditions of the constructor, and preconditions of the destructor.

// A Bounded Stack ADT
public class StackB {
    // Interface Invariant:  Once created and until destroyed, this
    //     stack instance has a valid and consistent internal state 

    public StackB(int size)
    // Pre:   size >= 0
    // Post:  initialized new instance with capacity size && empty()
    {   stk = new Object[size];
        capacity = size;
	topItem = 0;
    }

    Public void push(Object I)
    // Pre:   not full()
    // Post:  I added as the new top of this instance's stack
    {   stk[topItem] = I;
        topItem++;
    }

    public void pop()
    // Pre:   not empty()
    // Post:  item at top of stack removed from this instance
    {   topItem--;
        stk[topItem] = null;
    }

    public Object top()
    // Pre:   not empty()
    // Post:  return item at top of this instance's stack
    {   return stk[topItem-1];
    }

    public boolean empty()
    // Pre:   true
    // Post:  return true iff this instance's stack has no elements
    {   return (topItem <= 0);
    }

    public boolean full()
    // Pre:   true
    // Post:  return true iff this instance's stack is at full capacity
    {  return (topItem >= capacity);
    }

    public void destroy()
    // Pre:   true
    // Post:  internal resources released;  stack effectively deleted
    {   stk = null;
	capacity = 0;
        topItem = 0;
    } 

    // Implementation Invariants:  0 <= topItem <= capacity
    //     stack is in array section stk[0..topItem-1]
    //         with the top at stk[topItem-1], etc.

    private int topItem;   // Pointer to next index for insertion
    private int capacity;  // Maximum number of items in stack
    private Object[] stk;  // the stack
}

A Date (Day) ADT

Consider an ADT for storing and manipulating calendar dates. We will call the ADT Day to avoid confusion with the Date class in the Java API. This ADT is based on the Day class defined in Chapter 4 of the first edition of the book Core Java.

Logically, a calendar date consists of three pieces of information: a year designator, a month designator, and a day of the month designator. A secondary piece of information is the day of the week. In this ADT interface definition, we use integers (i.e., Java int) to designate these pieces of information.

Constructor

create(int y, int m, int d) -> Day D'

Precondition:

y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month m &&

(y,m,d) does not fall in the gap formed by the change to the modern (Gregorian) calendar

Postcondition:

D' is a valid new instance of Day with year y, month m, and day d

Mutators

setDay(Day D, int y, int m, int d) -> Day D'

Precondition:

D is a valid instance of Day &&

y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month &&

(y,m,d) does not fall in the gap formed by the change to the modern (Gregorian) calendar

Postcondition:

D' is a valid instance of Day &&

D'= D except with year y, month m, and day d

Question: Should we include setDay, setMonth, and setYear operations? What problems might arise?

advance(Day D, int n) -> Day D'

Precondition:

D is a valid instance of Day

Postcondition:

D' is a valid instance of Day &&

D' = D with the date moved n days later (Negative n moves to an earlier date.)

Accessors

getDay(Day D) -> int d

Precondition:

D is a valid instance of Day

Postcondition:

d is day of the month from D, where 1 <= d <= #days in month getMonth(D)

(D is unchanged.)

getMonth(Day D) -> int m

Precondition:

D is a valid instance of Day

Postcondition:

m is the month from D, where 1 <= m <= 12

(D is unchanged.)

getYear(Day D) -> int y

Precondition:

D is a valid instance of Day

Postcondition:

y is the year from D, where y != 0

(D is unchanged.)

getWeekday(Day D) -> int wd

Precondition:

D is a valid instance of Day

Postcondition:

wd is the day of the week upon which D falls: 0 = Sunday, 1 = Monday, ..., 6 = Saturday

(D is unchanged.)

equals(Day D, Day D1) -> boolean eq

Precondition:

D and D' are valid instances of Day

Postcondition:

eq is true if and only if D and D' denote the same calendar date

(D and D' are unchanged.)

daysBetween(Day D, Day D1) -> int d

Precondition:

D and D' are valid instances of Day

Postcondition:

d is the number of calendar days from D1 to D, i.e., equals(D,advance(D1,d)) would be true

(D is unchanged.)

toString(Day D) -> String s

Precondition:

D is a valid instance of Day

Postcondition:

s is the date D expressed in the format "Day[getYear(D),getMonth(D),getDay(D)]".

(D is unchanged.)

Destructor

destroy(Day D) ->

Precondition:

D is a valid instance of Day

Postcondition:

D no longer exists

Java Class Implementation for Day

// Parts of this come unmodified from _Core_Java_ (First Edition).
// Not all the commenting has been made consistent.

import java.util.*;

public class Day 
{
    // Interface Invariant:  Once created and until destroyed, this
    //    instance contains a valid date.  getYear() != 0 && 
    //    1 <= getMonth() <= 12 && 1 <= getDay() <= #days in getMonth().  
    //    Also calendar date getMonth()/getDay()/getYear() does not
    //    fall in the gap formed by the change to the modern
    //    (Gregorian) calendar.  

  // Constructors

    public Day()
    //  Pre:   true
    //  Post:  the new instance's day, month, and year set to today's
    //             date (i.e., the date of creation of the instance)
    {   java.util.Date today = new java.util.Date();
        year  = today.getYear() + 1900;
        month = today.getMonth() + 1;
        day   = today.getDay();
    }
 
    public Day(int y, int m, int d) throws IllegalArgumentException
    //  Pre:   y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month m
    //         (y,m,d) does not fall in the gap formed by the change
    //            to the modern (Gregorian) calendar.
    //  Post:  the new instance's day, month, and year set to y, m,
    //             and d, respectively  
    //  Exception:  IllegalArgumentException if y m d not a valid date
    {   year  = y;
        month = m;
        day   = d;
        if (!isValid())
            throw new IllegalArgumentException();
    }


  // Mutators

    public void setDay(int y, int m, int d)  
                throws IllegalArgumentException
    //  Pre:   y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month m
    //         (y,m,d) does not fall in the gap formed by the
    //             change to the modern (Gregorian) calendar.
    //  Post:  this instance's day, month, and year set to year, month
    //             and day set to y, m, and d, respectively 
    //  Exception:  IllegalArgumentException if y m d not a valid date
    {   year  = y;
        month = m;
        day   = d;
        if (!isValid())
            throw new IllegalArgumentException();
    }

    public void advance(int n)
    //  Pre:   true
    //  Post:  this instance's date moved n days later.  (Negative n
    //             moves to an earlier date.) 
    {   fromJulian(toJulian() + n);
    }

  // Accessors

    public int getDay()
    //  Pre:   true
    //  Post:  returns the day from this instance, where 
    //             1 <= getDay() <= #days in this instance's month
    {   return day;
    }

    public int getMonth()
    //  Pre:   true
    //  Post:  returns the month from this instance's date, where
    //             1 <= getMonth() <= 12
    {   return month;
    }

    public int getYear()
    //  Pre:   true
    //  Post:  returns the year from this instance's date, where 
    //             getYear() != 0
    {   return year;
    }

    public int getWeekday()
    // Pre:   true
    // Post:  returns the day of the week upon which this instance
    //            falls, where 0 <= getWeekday() <= 6;
    //            0 == Sunday, 1 == Monday, ..., 6 == Saturday
    {   //  calculate day of week
        return (toJulian() + 1)% 7;
    }

    public boolean equals(Day dd)
    //  Pre:   dd is a valid instance of Day
    //  Post:  returns true if and only if this instance and instance
    //             dd denote the same calendar date
    {   return (year == dd.getYear() && month == dd.getMonth()
                && day == dd.getDay());
    }

    public int daysBetween(Day dd)
    //  Pre:   dd is a valid instance of Day
    //  Post:  returns the number of calendar days from the dd
    //             instance's date to this instance's date, where
    //             equals(dd.advance(n)) would hold
    {   //  implementation code
        return toJulian() - dd.toJulian();
    }

    public String toString()
    //  Pre:   true
    //  Post:  returns this instance's date expressed in the format
    //             "Day[year,month,day]"
    {   //  implementation code
        return "Day[" + year + "," + month + "," + day + "]";
    }

  //  Destructors -- None needed

  //  Private Methods -- Mostly borrowed from _Core_Java_

 
   /**
    * Computes the number of days between two dates
    * @return true iff this is a valid date
    */
   private boolean isValid()
   {  Day t = new Day();
      t.fromJulian(this.toJulian());
      return t.day == day && t.month == month 
         && t.year == year;
   }

   private int toJulian()
   /**
    * @return The Julian day number that begins at noon of 
    * this day
    * Positive year signifies A.D., negative year B.C. 
    * Remember that the year after 1 B.C. was 1 A.D.
    *
    * A convenient reference point is that May 23, 1968 noon
    * is Julian day 2440000.
    *
    * Julian day 0 is a Monday.
    *
    * This algorithm is from Press et al., Numerical Recipes
    * in C, 2nd ed., Cambridge University Press 1992
    */
    {   int jy = year;
        if (year < 0) 
	    jy++;
        int jm = month;
	if (month > 2) 
	    jm++;
        else
        {   jy--;
            jm += 13;
        }
        int jul = (int) (java.lang.Math.floor(365.25 * jy) 
          + java.lang.Math.floor(30.6001*jm) + day + 1720995.0); 

        int IGREG = 15 + 31*(10+12*1582);
            // Gregorian Calendar adopted Oct. 15, 1582

        if (day + 31 * (month + 12 * year) >= IGREG)
            // change over to Gregorian calendar
        {   int ja = (int)(0.01 * jy);
            jul += 2 - ja + (int)(0.25 * ja);
        }
        return jul;
    }

    private void fromJulian(int j)
    /**
     * Converts a Julian day to a calendar date
     * @param j  the Julian date
     * This algorithm is from Press et al., Numerical Recipes
     * in C, 2nd ed., Cambridge University Press 1992
     */
    {   int ja = j;
   
        int JGREG = 2299161;
            /* the Julian date of the adoption of the Gregorian
               calendar  
             */ 

        if (j >= JGREG)
        /* cross-over to Gregorian Calendar produces this
           correction
         */ 
        {   int jalpha = (int)(((float)(j - 1867216) - 0.25)
                / 36524.25);
            ja += 1 + jalpha - (int)(0.25 * jalpha);
        }
        int jb = ja + 1524;
        int jc = (int)(6680.0 + ((float)(jb-2439870) - 122.1)/365.25);
        int jd = (int)(365 * jc + (0.25 * jc));
        int je = (int)((jb - jd)/30.6001);
        day = jb - jd - (int)(30.6001 * je);
        month = je - 1;
        if (month > 12) 
	    month -= 12;
        year = jc - 4715;
        if (month > 2) 
	    year--;
        if (year <= 0) 
	    year--;
    }

    //  Implementation Invariants:
    //      year != 0 && 1 <= month <= 12 && 1 <= day <= #days in month
    //      (year,month,day) not in gap formed by the change to the
    //      modern (Gregorian) calendar

    private int year;
    private int month;
    private int day; 
}

Client-Supplier Relationship

The design and implementation of ADTs (i.e., classes) must be approached from two points of view simultaneously:

supplier

the developers of the ADT -- the providers of the services.

client

the users of the ADT -- the users of the services (e.g., the designers of other ADTs).

Client-supplier relationship:

   ________________             ________________ 
  |                |           |                |
  |     Client     |===USES===>|    Supplier    |
  |________________|           |________________|

     (ADT user)                    (ADT)

The supplier's concerns include:

• efficient and reliable algorithms and data structures,
• convenient implementation,
• easy maintenance.

The clients' concerns include:

• accomplishing their own tasks,
• using the supplier ADT without effort to understand its internal details,
• having a sufficient, but not overwhelming, set of operations.

As we have noted previously, the interface of an ADT is the set of features (i.e., public operations) provided by a supplier to clients.

A precise description of a supplier's interface forms a contract between clients and supplier.

The client-supplier contract:

1. gives the responsibilities of the client. These are the conditions under which the supplier must deliver results -- when the preconditions of the operations are satisfied (i.e., the operations are called correctly).
2. gives the responsibilities of the supplier. These are the benefits the supplier must deliver -- make the postconditions hold at the end of the operation (i.e., the operations deliver the correct results).

The contract

• protects the client by specifying how much must be done by the supplier.
• protects the supplier by specifying how little is acceptable to the client.

  If we are both the clients and suppliers in a design situation, we should consciously attempt to separate the two different areas of concern, switching back and forth between our supplier and client "hats".

  Design Criteria for ADT (Class) Interfaces

  We can use the following design criteria for evaluating ADT (class) interfaces. Of course, some of these criteria conflict with one another; a designer must carefully balance the criteria to achieve a good interface design.

  Cohesion:

  All operations must logically fit together to support a single, coherent purpose. The ADT (class) should describe a single abstraction.

  Simplicity:

  Avoid needless features. The smaller the interface the easier it is to use the ADT (class).

  No redundancy:

  Avoid offering the same service in more than one way; eliminate redundant features.

  Atomicity:

  Do not combine several operations if they are needed individually. Keep independent features separate. All operations should be primitive, that is, not be decomposable into other operations also in the public interface.

  Completeness:

  All primitive operations that make sense for the abstraction should be supported by the ADT (class).

  Consistency:

  Provide a set of operations that are internally consistent in

  • naming convention (e.g., in use of prefixes like "set" or "get", in capitalization, in use of verbs/nouns/adjectives),
  • use of arguments and return values (e.g., order and type of arguments),
  • behavior (i.e., make operations work similarly).

  Avoid surprises and misunderstandings. Consistent interfaces make it easier to understand the rest of a system if part of it is already known.

  Reusability:

  Do not customize ADTs (classes) to specific clients, but make them general enough to be reusable in other contexts.

  Robustness with respect to modifications:

  Design the interface of an ADT (class) so that it remains stable even if the implementation of the ADT changes.

  Convenience:

  Where appropriate, provide additional operations (e.g., beyond the complete primitive set) for the convenience of users of the ADT (class). Add convenience operations only for frequently used combinations after careful study.

  Acknowledgments

  Some of the material here is based on the presentation in the following books:

  • Gary Cornell and Cay S. Horstmann. Core Java (First Edition), Sun Microsystems Press (Prentice-Hall), 1996.
  • Nell Dale and Henry M. Walker. Abstract Data Types: Specifications, Implementations, and Applications, D. C. Heath, 1996.
  • Cay S. Horstmann. Mastering Object-Oriented Design in C++, Wiley, New York, 1995.
  • Bertrand Meyer. Object-Oriented Program Construction, Second Edition, Prentice Hall PTR, Upper Saddle River, NJ, 1997.
  • Hanspeter Mossenbock. Object-Oriented Programming in Oberon-2, Springer-Verlag, Berlin, 1995.
  • Pete Thomas and Ray Weedom. Object-Oriented Programming in Eiffel, Addison-Wesley, Workingham, UK, 1995.

  The first version of these lecture notes were written for use in the first Java-based version of CSCI 211 (File Systems) during the fall semester of 1996. It was subsequently modified for use in the CSCI 581, Object-Oriented Design and Programming, classes in the fall of 1997 and spring of 1999.

  ---

  UP to CSCI 581 Lecture Notes root document?

  ---

  Copyright © 1999, H. Conrad Cunningham
  Last modified: Wed May 12 08:46:57 CDT