CISC 3130 INterfaces & Implementations

Modelling Social Security Numbers

Let us introduce a class that represents social security numbers.

We'll keep it simple: a social security number is a 9 digit value separated into 3 sections by dashes (-).
The three sections are known as the area, group, and serial respectively, and are 3, 2, and 4 digits respectively as well.
In line with keeping things simple, we'll restrict the behavior of the class to printing an ssnum, and retrieving any of its three sections

Specification of Behavior

class SSNum {
	…

	public int getArea() {…}
	public int getGroup() {…}
	public int getSerial() {…}

	public String toString() {…}
	…
}

Notes

The (public) methods are referred to as the behavior of the class
The (private) instance variables are referred to as the state of the class
Initially, we are interested in the behavior of the class, i.e., how the user (the client) of the class interacts with objects of the class.
Strictly speaking, it is only after we have determined the behavior that we flesh out the state (variables)
- It does turn out however, that the fleshing out of details may form feedback that in turn may influence the behavior somewhat
In the above code, we have specified the interface of the class (i.e., the manner in which users of the class interact/interface with objects of the class), but not its implementation (its internal representation).

Choosing the Internal Representation

We decide to represent the ssnum as a String, complete with the separating '-'s.

The choice of state (i.e., the variables; the way we intend to represent the information maintained by the class) drives the logic (bodies/implementation) of the methods.
We decide on the '-'-separated string as the input to our constructor.
- We could add additional constructors to allow the creation of an ssnum using alternative formats (e.g., a simple integer)
Similarly we choose the '-'-separated string for toString.
- This is probably a bit more obvious; regardless of how we maintain the social security number internally, we in all likelihood want to print it 'as a social security number', i.e., with the '-'s in the usual places.

class SSNum {
	SSNum(String ssnum) {this.ssnum = ssnum;}

	public int getArea() {return Integer.parseInt(ssnum.substring(0, 3));}
	public int getGroup() {return Integer.parseInt(ssnum.substring(4, 6));}
	public int getSerial() {return Integer.parseInt(ssnum.substring(7));}

	public String toString() {return ssnum;}
	
	private String ssnum;
}

Notes

As can be seen above, once we choose the internal representation of the class' state, the logic of the behavior (methods) becomes to some extent a given.
- that should not be a surprise; one usually chooses a internal representation because of its impact on the implementation of the methods
Integer.valueOf is an acceptable alternative to parseInt
- the former returns an Integer, the latter an int, but with autoboxing, the result is basically the same (at least here)

Coding a Demo App for our Class

Just a short application to demonstrate the behavior of the class

class SSNumApp {
	public static void main(String [] args) {
		SSNum sSNum = new SSNum("123-45-6789");

		System.out.println(sSNum);
		System.out.println(sSNum.getArea());
		System.out.println(sSNum.getGroup());
		System.out.println(sSNum.getSerial());
	}
}

A Change of Implementation (Representation)

We decide we'd like to change our implementation (i.e., internal representation) to an int (e.g., it takes up less space than the 11-byte string).

class SSNum {
	SSNum(String ssnum) {
		this.ssnum = Integer.parseInt(ssnum.substring(0, 3)) * 1000000  + Integer.parseInt(ssnum.substring(4, 6)) * 10000 + Integer.parseInt(ssnum.substring(7));}

	public int getArea() {return ssnum / 1000000;}
	public int getGroup() {return (ssnum / 10000) % 100;}
	public int getSerial() {return ssnum % 10000;}

	public String toString() {return String.format("%03d-%02d-%04d", getArea(), getGroup(), getSerial());}
	
	private int ssnum;
}

Notes

The behavior (specification/signatures of the public methods) remains the same.
As before, the logic details of the methods are irrelevant to our discussion, but notice that they ARE quite different due to the change in representation — both the public methods as well as the constructor and toString
- This all makes sense, and is in keeping with our discussion above … while the behavior remains the same, the means of achieving them is heavily dependent on the internal representation
- The constructor has to transform the parameter into the internal format
- Similarly, toString has to transform the internal representation into a String
- It is often (usually?) the case that a change in implementation will affect the constructors, which accept arguments and transform them into the internal representation; and the toString which takes the internal representation and transforms it into a string suitable for human viewing.

The Demo App Remains Unchanged

We used the same name for the new class (i.e., we replaced the old implementation with the new)
The behavior (public methods) is the same, and we are constrained to work with those methods

Some Issues

The following may not be compelling arguments just yet, but they help set the stage for what is coming.

Suppose we had named our original class StringSSNum. When we shift to an int-based implementation, that name would no longer be appropriate.
On the other hand, using the same name for the change of implementation, means you can't have both classes in the same application
- There's not much reason to do so in the above example, but there are other situations where you might want to have them both around (see the Sorting example below for a bit more elaboration)
Using different names for the two classes also means that any application code (i.e., code that uses this class) would have to change to refer to the new class name.
- All code that creates an object of one of the classes has to be changed when moving to the other implementation; for example, assuming we started off with StringSSNum, the app would read:
```
StringSSNum sSNum = new StringSSNum("123-45-6789");
			
```
  would have to be changed to:
```
IntSSNum sSNum = new IntSSNum("123-45-6789");
			
```
  (note that I've left the variable name the same 'vanilla' name (ssNum); changing it from stringSSNum to intSSNum just introduces even more name changing.)
  - One of the objectives of object-oriented programming (OOP) (and to an extent, programming in general) is to minimize changes to code that isn't directly affected by a change. In our situation, the application code is changing even though we're employing the exact same behavior.
Finally, it will often be the case that a particular implementation class may have methods that are specific to the implementation; changing to a different implementation that doesn't provide those methods can break the application
- To some extent this is the most important issue, though it cannot be made compelling with our simple example; it will have to wait for later situations
- A weak example might be if there was a convertToInt method in our StringSSNum implementation:
```
int convertToInt() {…}
				
```
  - Even though, the internal representation should be of no concern to the outside, the naive programmer who designed and coded StringSSNum may have thought it a good idea to have such a method; and furthermore, made heavy use of this method
  - If we now change implementations (to IntSSNum) — which justifiably would not have such a method, the application code would break wherever that method was called.
    - We can repair this easily enough (simply add the method to IntSSNum) but that then involves making changes to our tested class.
    - The name of the method is inappropriate as well; if anything, a method named asInt would be less egregious, and could be argued to be appropriate under all implementations.

The upshot is that in situations where there is a clear set of behavior, and potentially more than one implementation, we should strive to limit ourselves to the common behavior.

Interfaces

The following is a standard approach to coding robust and flexible software, and, in particular the sort of coding we will be doing in this course.

Java's interface construct allows us to specify a set of behavior in the form of method specifications. The interface forms a data type, i.e., a specification of a set of values and the valid operations on those values. Any class that implements the interface is said to belong to the data type of the interface, i.e., an object of the implementation class is-a object of the interface type as well, and can appear in any context interface reference variables appear.

This is identical to the data type relationship of a subclass and superclass, where we say that the subclass object is-a superclass object as well; i.e., the subclass object may appear in any context legal for a superclass object.

Here is an interface for our social security number:

interface SSNum {
	int getArea();
	int getGroup();
	int getSerial();
}

Notes

The interface construct consists of a sequence of method headers.
- As you can see, they correspond to our original behavior for our class.
Any class implementing this interface must supply implementations (i.e., method bodies) for all of the specified header.
- If any methods are not implementing, the class remains abstract
No constructors are specified … an interface cannot be created (it has all this unspecified behavior); only an implementing class can be created
In a similar fashion, toString is typically not specified in the interface
- There's not much point; all classes inherit a toString method from Object so the method has already been specified and a (default) implementation is already provided

Implementations of the Interface

We now restate our two implementations in terms of the interface:

class StringSSNum implements SSNum {
	StringSSNum(String ssnum) {this.ssnum = ssnum;}

	public int getArea() {return Integer.parseInt(ssnum.substring(0, 3));}
	public int getGroup() {return Integer.parseInt(ssnum.substring(4, 6));}
	public int getSerial() {return Integer.parseInt(ssnum.substring(7));}

	public String toString() {return ssnum;}
	
	private String ssnum;
}

class IntSSNum implements SSNum {
	IntSSNum(String ssnum) {this.ssnum = Integer.parseInt(ssnum.substring(0, 3)) * 1000000 + 
										Integer.parseInt(ssnum.substring(4, 6)) * 10000 + Integer.parseInt(ssnum.substring(7));}

	public int getArea() {return ssnum / 1000000;}
	public int getGroup() {return (ssnum / 10000) % 100;}
	public int getSerial() {return ssnum % 10000;}

	public String toString() {return String.format("%03d-%02d-%04d", getArea(), getGroup(), getSerial());}
	
	private int ssnum;
}

The Apps

class StringSSNumApp {
	public static void main(String [] args) {
		StringSSNum stringSSNum = new StringSSNum("123-45-6789");

		System.out.println(stringSSNum);
		System.out.println(stringSSNum.getArea());
		System.out.println(stringSSNum.getGroup());
		System.out.println(stringSSNum.getSerial());
	}
}

class IntSSNumApp {
	public static void main(String [] args) {
		IntSSNum intSSNum = new IntSSNum("123-45-6789");

		System.out.println(intSSNum);
		System.out.println(intSSNum.getArea());
		System.out.println(intSSNum.getGroup());
		System.out.println(intSSNum.getSerial());
	}
}

Notes

The two apps are identical, modulo:
- The names of the type (StringSSNum vs IntSSNum). This is used in
  - declaring the reference variables of the objects (e.g., IntSSNum intSSNum).
    - We'll see how to solve this in the next section
  - creation of the object (e.g., new StringSSNum(…);).
    - This will take a touch more work; but its solution will introduce a powerful OOP technique
- The names of the variables (stringSSNum vs intSSNum)
  - These are 'arbitrary' … there's no reason we don't use the variable name ssNum in both apps.

Programming to the Interface

An interface specifies the required/recommended behavior (set of methods) via which one interacts with any class implementing the interface.

An application restricting itself to the interface is impervious to implementation changes (i.e., a change of implementation or a change within the currently used implementation).
Each implementation may have (non-private) methods outside of the interface; using such methods opens up the application to breaking in the event of a change to the implementation.
The alternative to programming to the interface is called programming to the implementation or programming to classes

Revisiting our Apps

As we mentioned, the apps for the two ssnum implementations are identical except for the creation of the objects and the variable names.

The latter is trivial to rectify; simply name them the same, i.e., ssNum.
- and this would be in keeping with your notion of concentrating on the interface; we're not interested in intSSNums or stringSSNum's; from the interface POV, they're both simply ssNums
The creation of the object is a bit more challenging, to create an IntSSNum one must write new IntSSNum, (clearly one wouldn't write new StringSSNum and you can't create an SSNum (it's an interface, not a concrete class).
- The solution is to isolate the common code from the implementation-specific stuff. The common code goes into an SSNum app
  - Rather than creating the ssNum object (which would require stating what sort of implementing object we're creating, i.e., newIntSSNum or new String SSNum), we pass the object in as a parameter, allowing the caller to be responsible for which to use.
    - this works since both implementations is-a SSNum by virtue of their having implemented the SSNum interface.
  - By placing the common stuff in the SSNum app, we are also making sure we are only using those methods of the interface, i.e., we are indeed 'programming to the interface'.
- This technique is an elegant and fairly advanced modern object-oriented programming approach called dependency injection
  - Dependency injection is the process of an external entity supplying dependencies (i.e., the objects to be used for which there are various choices as to their selection). This is a technique of a design principle known as inversion of control in which (loosely speaking) responsibility for decisions are shifted from a piece of code to its caller.

class SSNumApp {
	public static void demo(SSNum sSNum) {
		System.out.println(sSNum);
		System.out.println(sSNum.getArea());
		System.out.println(sSNum.getGroup());
		System.out.println(sSNum.getSerial());
	}
}

class StringSSNumApp {
        public static void main(String [] args) {
                SSNumApp.demo(new StringSSNum("123-45-6789"));
        }
}

class IntSSNumApp {
        public static void main(String [] args) {
                SSNumApp.demo(new IntSSNum("123-45-6789"));
        }
}

Abstract Data Type (ADT) vs Data Structure

An abstract data type (ADT) is a specification of a set of values, the operations on these values, and the semantics of those operations. For example, our notion of a vector was:

a set of homogeneous elements (e.g. integers, strings, etc)
operations get, set, add, and size
the semantics (behavior) of the above four operations

As we mentioned at the very beginning, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data.

In other words, the ADT is the abstraction of a type, while the data structure is the implementation representation of the type.

ADT and Data Structures in Java

Java's interface construct acts as a mechanism for the specification of an ADT. Taking our Vector as an example, we could abstract our notion of a vector int the following interface:

interface Vector<E> {
	E get(int index);
	void set(int index, E value);
	void add(E value);
	int getCapacity();
	int size();
}

Notes

The primary role of a Java interface in the specification of an ADT is in the listing of the operations and their interface to the user (i.e., their signatures).
- actual semantics would have to be specified mathematically; any Java code would be more in the realm of an implementation
In a sense, we might say that the above is the abstraction or essence of a vector.

A vector data structure would then be a concrete class implementing the above interface.

class ArrayVector implements Vector {
	// Our Version 5 Vector class
	Vector() {…}
	E get(int index) {…}	
	void set(int index, E value) {…}	
	void add(E value) {…}
	int getCapacity() {…}return capacity;}
	int size() {…}return size;}

	public String toString() {…}

	private void checkCapacity() {…}

	E [] arr;
	int capacity, size = 0;
	static final int INITIAL_CAPACITY = 10;
}

Given that the interface is now named Vector we need a new name for our concrete class
- The convention in Java, particularly in the context of container ADT's is to include the underlying container type in the name of the implementing class. Since we are using an array as our underlying container, we name the class ArrayVector.
The class:
- provides state for the class (the instance and class variables)
- implements all the methods in the interface (in order to be able to state that it implements Vector), using those variables
- adds constructors to initialize the state
- provides any additional methods:
  - toString: not specified in the interface as it's already inherited from Object and overridden in this class
  - getCapacity: as we'll see shortly capacity is part of the implementation, i,e. typically not seen by the user. We've placed it in the set of public methods until now for the purposes of illustrating the capacity-related behavior of the class, but strictly speaking it;s not part of the interface, and I've left it out of the current version
  - checkCapacity: regardless of whether we want to display capacity info and thus add getCapacity to the interface, checkCapacity should definitely be private

Programming to the Interface Again — `List`, `ArrayList`, and `LinkedList`

The vector class/type we introduced is a restricted version of a more general vector ADT, also known as a list We will now present this interface as well as two implementations and apply the above approach of programminf to the interface in that context.

We will investigate the list ADT in more detail shortly; for the moment, we will simply think of it as the Java version of our Vector class.
As discussed above, Java specifies its list ADT using an interface named List
There are also two implementations (data structures) named ArrayList and LinkedList
- In keeping with its container's interface/implementation naming conventions, ArrayList uses and array as the underlying implementation container, while LinkedList uses something called a linked represntation
  - we will be covering linked lists in a bit; they are the alternative to arrays as the fundamental underlying container.
  - for the moment we need not concern ourselves with how or why they work; we will simply work with them knowing they implement the List interface, i.e., we will program to the interface
    - This is the power of the interface: we are able to work with the LinkedList class without its details; all we are concerned with is the fact that it implements the List interface.

The Interface-Specific App

import java.util.List;
import java.util.ArrayList;

public class ListApp {
	static void doIt(List<Integer>  basicList, List<String> exceptionList, List<Double> listDouble, List<String> listString) {
		System.out.println("===== ListApp =====");
		basics(basicList);
		exceptions(exceptionList);
		generics(listDouble, listString);
	}

	static void basics(List<Integer> list) {
		System.out.println("=== Basic Functionality ===");
		System.out.println("--- Printing and initial stats ---");
		System.out.println(list + " (" + list.size() + ")");
		System.out.println();

		System.out.println("--- Loading it up to capacity; add ---");
		for (int i = 0; i < 10; i++) {
			list.add(i * 10);
			System.out.println(list + " (" + list.size() + ")");
		}
		System.out.println();

		System.out.println("--- Incrementing each element; get and set ---");
		for (int i = 0; i < list.size(); i++)
			list.set(i, list.get(i)+1);
		System.out.println(list);
		System.out.println();
	}

	static void exceptions(List<String> list) {
		System.out.println("=== Exceptions ===");
		try {
			System.out.println(list.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			list.set(0, "");
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}
		System.out.println();
	}

	static void generics(List<Double> listDouble, List<String> listString) {
		System.out.println("--- Generics");
		System.out.println();

		System.out.println("--- A List of doubles");
		for (int i = 0; i < 10; i++)
			listDouble.add((double)i);
		System.out.println(listDouble);
		System.out.println();

		System.out.println("--- A List of Strings");
		for (int i = 0; i < 7; i++)
			listString.add("Str" + i);
		System.out.println(listString);
		for (int i = 1; i < listString.size(); i++)
			System.out.println(listString.get(i).substring(1));
		System.out.println();
	}
}

Notes

Recall that programming to the interface, i.e., writing code that relies solely on the methods of the interface (rather than those of the concrete class) typically involves dependency injection; i.e., having the called send the implementing object to the app (which is written from the perspective of the interface).
- In the SSNum example above, the implementing classes (IntSSNum and StringSSNum created an instance of themselves in their own app, and passed it on to the (common) interface-based app (SSNumApp).
- Our current situation is a bit more complicated: there are several methods, each using one or more of its own lists, as well as the lists having different elements types.
  - I've used the brute force method of having the implementation class apps create all of the necessary List objects and send them along to the above app. This does lead to a bit of a mess in the parameter lists of the app.
    - Having the app send already-created objects to the app also prevents the app from working with any situation in which the objects are to be dynamically created as needed. This is mentioned below.
  - There is a better way of resolving this, but it's a bit beyond the scope of this class.
Capacity-management is totally hidden in Java lists: some of the implementations might not even have a notion of capacity (we'll discuss that later). As such:
- The entire capacity-management method is gone
- The initial loading up of the list to capacity in our original VectorApp has been replaced with a load of 10 elements (no particular reason, and although I should have declared a constant for that value and used it, it would have been more of a distraction than simply stating 'putting 10 elements into the list').
- The capacity is no longer displayed when displaying the list and its size
The Vector<Vector<Integer>> example in the generic method has been removed. The reason for this is a touch involved:
- When loading up that vector, each element is itself a vector which had to be created.
```
System.out.println("--- A List of List");
???<???<Integer>> ??Integer = new ???<>();
for (int i = 0; i < 5; i++) {
	???List<Integer> ???Integer = new ???<>();
	for (int j = 0; j < i; j++)
		???Integer.add(j);
	listListInteger.add(???Integer);
}
				
```
  In keeping with the whole notion of injection, we don't know what type of list to create
  - This was not a problem originally, as we were not using injection, and furthermore, there was only one type of Vector. But now, there are at least to implementations of List (ArrayList and LinkedList and furthermore, in the above app, we are in the context of simply a List, the question becomes what sort of List do we create for the elements of our List<List<Integer>>

The Apps for the Implementing Classes

import java.util.List;
import java.util.ArrayList;

public class ArrayListApp {
	public static void main(String [] args) {
		ListApp.doIt(new ArrayList<Integer>(), new ArrayList<String>(), new ArrayList<Double>(), new ArrayList<String>());
	}
}

import java.util.List;
import java.util.LinkedList;

public class LinkedListApp {
	public static void main(String [] args) {
		ListApp.doIt(new LinkedList<Integer>(), new LinkedList<String>(), new LinkedList<Double>(), new LinkedList<String>());
	}
}

Notes

Just setting up the injection objects and calling the List interface app

CISC 3130 Data Structures Interfaces & Implementations

Modelling Social Security Numbers

Specification of Behavior

Choosing the Internal Representation

Coding a Demo App for our Class

A Change of Implementation (Representation)

The Demo App Remains Unchanged

Some Issues

Interfaces

Implementations of the Interface

The Apps

Programming to the Interface

Revisiting our Apps

Abstract Data Type (ADT) vs Data Structure

ADT and Data Structures in Java

Programming to the Interface Again — List, ArrayList, and LinkedList

The Interface-Specific App

The Apps for the Implementing Classes

CISC 3130
Data Structures
Interfaces & Implementations

Programming to the Interface Again — `List`, `ArrayList`, and `LinkedList`