Home Previous Next

CSC205AA::Lecture Note::Week 08
Assignments | Handouts | Resources | Email Thurman { compufoo::Twitter | Facebook | YouTube}
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview Assignment(s):  Code [interfaces] InterfaceExample.java | InterfaceEG.java | I_ExitStatus.java | TestI_ExitStatus.java
[interfaces continued] TestSerializable.java | TestClone.java CloneableEG.java | CSC205_Containers
[multi-dimensional arrays] MultiArrays.java | TwoDimensionalArrays.java | BYTES.java | ThreeDimensionalArray.java
[memory/heap/stack/miscellaneous] Memory.java | Main.java


Interfaces

From the The Java Programming Language by Arnold, Gosling, Holmes.

The fundamental unit of programming in Java is the class, but the fundamental unit of object-oriented design is the type. Interfaces define types in an abstract form as a collection of methods or other types that form the contract for that type.

An interface is defined using the keyword interface rather than class.

An interface contains no instance variables, nor does it contain any method implementations. You cannot create instances of an interface.

   interface Foo { ... }

   //! Foo f = new Foo();   // not legal

An interface can declare three kinds of members:

All interface members are implicitly public.

A class guarantees to implement the methods of an interface by using the implements keyword when the class is defined.

   class X implements Y

Any class that implements an interface must define (i.e. implement) the methods, if any, declared in the interface.

A class can implement more that one interface. In addition, a class can extend another class and still implement one or more interfaces.

   class X implements Y, Z { ... }
   class X extends A implements Y, Z { ... }

To an extent, interfaces support the concept of multiple inheritance.

Common interfaces from the java.lang package:

An interface can be used to "tie" together classes that are in separate inheritance trees.

                  Object
                    |
                Assignment               Interface:  Submitable
                    |
            Exam   Program   Homework
            ...    ...       ...



             Object
               |
              Game                       Interface:  Submitable
               |
  Guessing  Yahtzee   Blackjack
  ...       ...       ....

Another example...

An interface can be used to encapsulate a collected of related manifest constants (i.e. simulate an enum in C).

   interface ExitStatus {
      int EXIT_SUCCESS = 0;
      int EXIT_FAILURE = 1;
   }

When an interface declares named constants, then they are implicitly defined to be public, static, and final. [blank finals are not allowed]

Methods declared in an interface are implicitly abstract.

An interface can extend (i.e. inherit) other interfaces.

   interface Sortable { ... }
   interface Searchable { ... }
   interface Container extends Sortable, Searchable { ... }
Any class that implements interface Container must also implement the Sortable and Searchable interfaces.

Although you cannot instantiate an object using an interface, you can use an interface as the type for variable and assign to that variable any object whose class implements the interface. This allows for polymorphic run-time binding.

   interface Container { ... }

   class List implements Container { ... }

   List list = new List();
   ...
   Container c = list;  // list is a container

From a naming convention perspective, many interfaces have a -able suffix applied to them.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Object Serialization

Any object that implements the Serializable interface can be turned into a sequence of bytes that can be restored fully into the original object.

Benefits.

The Serializable interface is used as a flag -- it has no methods. Some objects may not want to be serialized.

To serialize an object you create some sort of OutputStream object and wrap it inside an ObjectOutputStream object. Then, the object can be serialized by calling writeObject(). Reversing the process is accomplished by creating an InputStream inside a ObjectInputStream and calling the readObject() method.

When an object is serialized, so are all the references it may contain to other objects.

- Object Serialization (java1.1)
   * useful for saving the state of an application/applet
   * objects serialized/deserialized with  ObjectOutputStream  and
     ObjectInputStream, respectively, using the  writeObject()  and
     readObject()  methods
   * primitive types written to stream as if using DataOutputStream;
     otherwise,  writeObject() is called recursively to serialize
     other objects (arrays, strings, objects) -- infinite recursion
     is not a problem (so they say); can end up with an entire
     graph object serialized
   * not all objects can or should be serialized
   * a class is serialable iff it implements Serializable 
      (or Externalizable); no methods defined -- it is a
      marker interface
   * Component implements Serializable; thus, all AWT components
     can be serialized
   * transient  indicates that a field should not be serialized
   * custom serialization is accomplished by overriding  writeObject()
     and  readObject(), and by using  defaultWriteObject()  and
     defaultReadObject() -- note: they must be declared  private
   * classes are assigned a version # -- cannot deserialize a
     class that has a different version # than what was used when
     it was serialized;  'serialver'  program
        + static final long serialVersionUID = 19971209L;
   * serialized applets
      + <applet code=appletName.ser ...>
      + applets can be shipped in a pre-initialized state
   * Externalizable
      + ObjectOutputStream and ObjectInputStream use the
         writeExternal() and readInternal() methods instead
         of writeObject() and readObject(); allows the class
         to take complete control over writing/reading their state

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Object Cloning

Objects cannot be cloned unless they are created using a class that implements the Cloneable interface.

For a class to use the default implementation of Object.clone(), it must implement the Cloneable interface.

The Cloneable interface is an empty interface -- it is used as a tag only. In many cases, classes that can be cloned override Object.clone().

Object.clone() does a bit-wise copy, which works fine for primitive types, but not necessarily with references. Only individual classes know how to be cloned (if at all). By default, a shallow copy is done versus a deep copy.

If an attempt is made to clone an object that is not cloneable, then the CloneNotSupportedException exception is thrown. This is a checked exception; therefore, it must be caught.

It is common for cloneable classes to override clone() so as to make it public rather than protected.

   The Population class extends class X (which is cloneable), and it
   contains numerous primitive types and a bunch of object references:

      try {
         Population p = (Population)super.clone();
         p.name = new String(getName());
         p.growthRate = (GrowthRate)growthRate.clone();
         p.density = (Density)density.clone();
         return p;
      } catch (CloneNotSupportedException e) { return null; }

From the CoreJava book.

Why clone? You never want to return a mutable object as the value of a method because this violates encapsulation. As a rule of thumb, always use clone whenever you need to return a copy of a mutable data field.

When you start dealing with objects instantiated from classes that you do not know well, then how they clone becomes an unknown.

Here is an example of a program that will result in the throwing of a CloneNotSupportedException.

   class A {
      int a;
      public A (int i) { a = i; }
      public Object clone() throws CloneNotSupportedException {
         return super.clone();
      }
   }
   public class Main {
      public static void main(String[] arg) {
         A a1 = new A(260);
         try {
            A a2 = (A)(a1.clone());
         } catch (CloneNotSupportedException e) {}
      }
   }

      The execeptions occurs because class A calls Object.clone(),
      but it does not implement the  cloneable  interface.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Multi-dimensional Arrays

Multi-dimensional arrays are arrays-of-arrays. Example: a two-dimensional array is an array of one-dimensional arrays.

   int someArray[][];  // someArray  will reference an array whose elements
                       // are of type:   array-of-int

   someArray = new int[3][];
   for (int i = 0; i < someArray.length; i++)
      someArray[i] = new int[5];

   int[0][0]  int[0][1]   int[0][2]   int[0][3]   int[0][4]
   int[1][0]  int[1][1]   int[1][2]   int[1][3]   int[1][4]
   int[2][0]  int[2][1]   int[2][2]   int[2][3]   int[2][4]

   /*
    * example of a jagged two-dimensional array
    */
   a = new int[4][];
   for (int i = 0; i < a.length; i++)
      a[i] = new int[i + 1];

   int[0][0]
   int[1][0]  int[1][1]
   int[2][0]  int[2][1]  int[2][2]
   int[3][0]  int[3][1]  int[3][2]  int[3][3]

   The EXPR  a[i]  accesses the  i'th   one-dimensional array.

   The following code snippet creates a 2x3 table of Foo objects.

      Foo[][] foo = new Foo[2][3];
      for (int i = 0; i < foo.length; i++) 
         for (int j = 0; j < foo[i].length; j++)
            foo[i][j] = new Foo();

   or

      Foo[][] foo = new Foo[2][];
      for (int i = 0; i < foo.length; i++)  {
         foo[i] = new Foo[3];
         for (int j = 0; j < foo[i].length; j++)
            foo[i][j] = new Foo();
      }

Excluding some mathematical and scientific computing, multi-dimensional arrays rarely exceed two dimensions.

MultiArrays.java

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Lists

A  list  is a linear data structure whose components can only be accessed sequentially, one after another.

The first item is a list is called the  head  or  front  and the last item is called the  tail ,  back  or  end.

Lists have the following features:

List operations include:

GDT::Java::Code::GoofyIntList.java

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Sets

A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).

The objects of a set are called elements (or members).

A set the following properties:

Example of sets:

The following operations are performed on a set:

An array (i.e. vector) can be used to store a set.

A class that is used to represent a set could have the following instance methods:

   Set();
   Set(int capacity);
   boolean isMember(Object element);
   boolean isEmpty();
   boolean isSubset(Set other);
   int size();
   Set union(Set other);
   Set intersection(Set other);
   Set difference(Set other);
   void add(Object element);
   void remove(Object element);
   void clear();

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Stacks

A  stack  is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).

My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and  pushes  them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.

A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called  push ,  pop  and  top .

Elements are inserted onto a stack by using a push operation.

Elements are deleted from a stack by using a pop operation.

The most-recently inserted element can be examined by using a top operation.

Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:

  1. create an empty stack
  2. read symbols until EOF
    1. if the symbol is an opening symbol, push it onto the stack
    2. if the symbol is a closing symbol and the stack is empty, then report an error
    3. otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
  3. at EOF, if stack is *not* empty, then report an error

A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.

Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Queues

A  queue  is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).

Operations are:

Examples of a queue: buffered input and a line printer spooler.

Another queue example: message queues.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Priority Queues

A  priority queue  allows the highest priority element to be removed from a queue even though it may not be the "oldest."

Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.

An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Linked Lists

A linked list is a low-level structure upon which high-level data structures can be built (e.g. stacks and queues can be implemented using a linked-list).

Sometimes the only Abstract Data Type (ADT) available for organizing data is the built-in array; however, this can be problem if the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. It can also be problem when arrays need to grow (i.e. increase in length [capacity]). In these cases a linked-list may be the solution.

A linked-list is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).

If each node contains only one link member, then we have a singly linked list.

Unlike an array, the nodes of a linked-list do not necessarily occupy consecutive memory locations.

The implementation of a linked-list relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linked-list is created, its length (i.e. # of nodes) is unknown.]

Terminology

A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The end-of-list (EOL) is called the rear its link data member has the value NULL (i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.

class Node

Example instance variables.

   some_data_type data   // 1 or more of these
   Node next             // pointer to next node 
   Node prev             // if doubly-linked-list

class LinkedList

Example instance variables.

   head      // handle to the 1st node in the linked-list
   size      // # of nodes in linked-list
   capacity  // maximum nodes allowed
   // maybe more...

Possible instance methods.

   constructors to initial linked-list objects
   add() -- add nodes to the end of linked-list
   insert() -- insert nodes into a linked-list
   delete() -- delete (remove) nodes from a linked-list
   update() -- update (modify) a node in a linked-list
   search() -- search a linked-list for data
   // maybe more...
Bjarne Stroustrup: Why you should avoid Linked Lists
Linked-List notes: Singly | Doubly

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Home Previous Next