Interfaces

Interfaces

Java’s interface is a useful language mechanism for expressing an abstract data type. An interface in Java is a list of method signatures, but no method bodies. A class implements an interface if it declares the interface in its implements clause, and provides method bodies for all of the interface’s methods. So one way to define an abstract data type in Java is as an interface, with its implementation as a class implementing that interface.

One advantage of this approach is that the interface specifies the contract for the client and nothing more. The interface is all a client programmer needs to read to understand the ADT. The client can’t create inadvertent dependencies on the ADT’s rep, because instance variables can’t be put in an interface at all. The implementation is kept well and truly separated, in a different class altogether.

Another advantage is that multiple different representations of the abstract data type can co-exist in the same program, as different classes implementing the interface. When an abstract data type is represented just as a single class, without an interface, it’s harder to have multiple representations. In the [MyString example from Abstract Data Types][1], MyString was a single class. We explored two different representations for MyString, but we couldn’t have both representations for the ADT in the same program.

Java’s static type checking allows the compiler to catch many mistakes in implementing an ADT’s contract. For instance, it is a compile-time error to omit one of the required methods, or to give a method the wrong return type. Unfortunately, the compiler doesn’t check for us that the code adheres to the specs of those methods that are written in documentation comments.

Example: MyString

Let’s revisit [MyString][1]. Using an interface instead of a class for the ADT, we can support multiple implementations: ```java /** MyString represents an immutable sequence of characters. */ public interface MyString {

 1 /** @return number of characters in this string */
 2 public int length();
 3 
 4 /** @param i character position (requires 0 <= i < string length)
 5  *  @return character at position i */
 6 public char charAt(int i);
 7 
 8 /** Get the substring between start (inclusive) and end (exclusive).
 9  *  @param start starting index
10  *  @param end ending index.  Requires 0 <= start <= end <= string length.
11  *  @return string consisting of charAt(start)...charAt(end-1) */
12 public MyString substring(int start, int end);

} ```

We’ll skip the static valueOf method and come back to it in a minute. Instead, let’s go ahead using a different technique from our [toolbox of ADT concepts in Java][2]: constructors.

Here’s our first implementation: ```java public class SimpleMyString implements MyString { private char[] a; private SimpleMyString() {}

 1 /** Create a string representation of b, either "true" or "false".
 2  *  @param b a boolean value */
 3 public SimpleMyString(boolean b) {
 4 	a = b ? new char[] { 't', 'r', 'u', 'e' }
 5 		: new char[] { 'f', 'a', 'l', 's', 'e' };
 6 }
 7 
 8 @Override 
 9 public int length() { return a.length; }
10 
11 @Override 
12 public char charAt(int i) { return a[i]; }
13 
14 @Override 
15 public MyString substring(int start, int end) {
16 	SimpleMyString that = new SimpleMyString();
17 	that.a = new char[end - start];
18 	System.arraycopy(this.a, start, that.a, 0, end - start);
19 	return that;
20 }

} ```

And here’s the optimized implementation:

 1 public class FastMyString implements MyString {
 2 
 3 	private char[] a;
 4 	private int start;
 5 	private int end;
 6 
 7 	private FastMyString() {}
 8 
 9 	/** Create a string representation of b, either "true" or "false".
10 	 *  @param b a boolean value */
11 	public FastMyString(boolean b) {
12 		a = b ? new char[] { 't', 'r', 'u', 'e' }
13 			: new char[] { 'f', 'a', 'l', 's', 'e' };
14 		start = 0;
15 		end = a.length;
16 	}
17 
18 	@Override 
19 	public int length() { return end - start; }
20 
21 	@Override 
22 	public char charAt(int i) { return a[start + i]; }
23 
24 	@Override 
25 	public MyString substring(int start, int end) {
26 		FastMyString that = new FastMyString();
27 		that.a = this.a;
28 		that.start = this.start + start;
29 		that.end = this.start + end;
30 		return that;
31     }
32 }

• Compare these classes to the [implementations of MyString in Abstract Data Types][1]. Notice how the code that previously appeared in static valueOf methods now appears in the constructors, slightly changed to refer to the rep of this.
• Also notice the use of [@Override][3]. This annotation informs the compiler that the method must have the same signature as one of the methods in the interface we’re implementing. But since the compiler already checks that we’ve implemented all of the interface methods, the primary value of @Override here is for readers of the code: it tells us to look for the spec of that method in the interface. Repeating the spec wouldn’t be DRY, but saying nothing at all makes the code harder to understand.
• And notice the private empty constructors we use to make new instances in substring(..) before we fill in their reps with data. We didn’t have to write these empty constructors before because Java provided them by default; adding the constructors that take boolean b means we have to declare the other constructors explicitly.

Now that we know good ADTs scrupulously [preserve their own invariants][4], these do-nothing constructors are a bad pattern: they don’t assign any values to the rep, and they certainly don’t establish any invariants. We should strongly consider revising the implementation. Since MyString is immutable, a starting point would be making all the fields final.

How will clients use this ADT? Here’s an example:

1 MyString s = new FastMyString(true);
2 System.out.println("The first character is: " + s.charAt(0));

This code looks very similar to the code we write to use the Java collections classes:

 1 List<string> s = new ArrayList<string>();
 2 ...
 3 
 4 Unfortunately, this pattern **breaks the abstraction barrier** we've worked so h\
 5 ard to build between the abstract type and its concrete representations. Clients\
 6  must know the name of the concrete representation class. Because interfaces in \
 7 Java cannot contain constructors, they must directly call one of the concrete cl\
 8 ass' constructors. The spec of that constructor won't appear anywhere in the int\
 9 erface, so there's no static guarantee that different implementations will even \
10 provide the same constructors.
11 
12 Fortunately, (as of Java 8) interfaces _are_ allowed to contain static methods, \
13 so we can implement the creator operation `valueOf` as a static factory method i\
14 n the interface `MyString`:
15 
16 ```java
17 public interface MyString {
18 
19 /** @param b a boolean value
20  *  @return string representation of b, either "true" or "false" */
21 public static MyString valueOf(boolean b) {
22 	return new FastMyString(true);
23 }

Now a client can use the ADT without breaking the abstraction barrier:

1 MyString s = MyString.valueOf(true);
2 System.out.println("The first character is: " + s.charAt(0));

Example: Set

Java’s collection classes provide a good example of the idea of separating interface and implementation.

Let’s consider as an example one of the ADTs from the Java collections library, Set. Set is the ADT of finite sets of elements of some other type E. Here is a simplified version of the Set interface:

1 /** A mutable set.
2  *  @param <e> type of elements in the set */
3 public interface Set<e> {

Set is an example of a generic type: a type whose specification is in terms of a placeholder type to be filled in later. Instead of writing separate specifications and implementations for Set<string>, Set<integer>, and so on, we design and implement one Set<e>.

We can match Java interfaces with our classification of ADT operations, starting with a creator:

1 /** Make an empty set.
2  *  @param <e> type of elements in the set
3  *  @return a new set instance, initially empty */
4 	public static <e> Set<e> make() { ... }

The make operation is implemented as a static factory method. Clients will write code like Set<string> strings = Set.make(); and the compiler will understand that the new Set is a set of String objects.

1 /** Get size of the set.
2  *  @return the number of elements in this set */
3 public int size();
4 
5 /** Test for membership.
6  *  @param e an element
7  *  @return true iff this set contains e */
8 public boolean contains(E e);

Next we have two observer methods. Notice how the specs are in terms of our abstract notion of a set; it would be malformed to mention the details of any particular implementation of sets with particular private fields. These specs should apply to any valid implementation of the set ADT.

1 /** Modifies this set by adding e to the set.
2  *  @param e element to add */
3 public void add(E e);
4 
5 /** Modifies this set by removing e, if found.
6  *  If e is not found in the set, has no effect.
7  *  @param e element to remove */
8 public void remove(E e);

The story for these mutators is basically the same as for the observers. We still write specs at the level of our abstract model of sets.

<p style=”background:#eaeaea; padding:10px; margin-top:20px; text-align:right”> In the Java Tutorials, read these pages:<br /> <a href=”http://docs.oracle.com/javase/tutorial/collections/interfaces/”> Lesson: Interfaces</a><br /> <a href=”http://docs.oracle.com/javase/tutorial/collections/interfaces/set.html”>The Set Interface</a><br /> <a href=”http://docs.oracle.com/javase/tutorial/collections/implementations/set.html”>Set Implementations</a><br /> <a href=”http://docs.oracle.com/javase/tutorial/collections/interfaces/list.html”>The List Interface</a><br /> <a href=”http://docs.oracle.com/javase/tutorial/collections/implementations/list.html”>List Implementations</a></p>

Why Interfaces?

Interfaces are used pervasively in real Java code. Not every class is associated with an interface, but there are a few good reasons to bring an interface into the picture.

• Documentation for both the compiler and for humans. Not only does an interface help the compiler catch ADT implementation bugs, but it is also much more useful for a human to read than the code for a concrete implementation. Such an implementation intersperses ADT-level types and specs with implementation details.
• Allowing performance trade-offs. Different implementations of the ADT can provide methods with very different performance characteristics. Different applications may work better with different choices, but we would like to code these applications in a way that is representation-independent. From a correctness standpoint, it should be possible to drop in any new implementation of a key ADT with simple, localized code changes.
• Optional methods. List from the Java standard library marks all mutator methods as optional. By building an implementation that does not support these methods, we can provide immutable lists. Some operations are hard to implement with good enough performance on immutable lists, so we want mutable implementations, too. Code that doesn’t call mutators can be written to work automatically with either kind of list.
• Methods with intentionally underdetermined specifications. An ADT for finite sets could leave unspecified the element order one gets when converting to a list. Some implementations might use slower method implementations that manage to keep the set representation in some sorted order, allowing quick conversion to a sorted list. Other implementations might make many methods faster by not bothering to support conversion to sorted lists.
• Multiple views of one class. A Java class may implement multiple methods. For instance, a user interface widget displaying a drop-down list is natural to view as both a widget and a list. The class for this widget could implement both interfaces. In other words, we don’t implement an ADT multiple times just because we are choosing different data structures; we may make multiple implementations because many different sorts of objects may also be seen as special cases of the ADT, among other useful perspectives.
• More and less trustworthy implementations. Another reason to implement an interface multiple times might be that it is easy to build a simple implementation that you believe is correct, while you can work harder to build a fancier version that is more likely to contain bugs. You can choose implementations for applications based on how bad it would be to get bitten by a bug.

Realizing ADT Concepts in Java

This table summarizes how some key ADT ideas can be implemented in Java.

Summary

Java interfaces help us formalize the idea of an abstract data type as a set of operations that must be supported by a type.

This helps make our code…

• Safe from bugs. An ADT is defined by its operations, and interfaces do just that. When clients use an interface type, static checking ensures that they only use methods defined by the interface. If the implementation class exposes other methods — or worse, has visible representation — the client can’t accidentally see or depend on them. When we have multiple implementations of a data type, interfaces provide static checking of the method signatures.
• Easy to understand. Clients and maintainers know exactly where to look for the specification of the ADT. Since the interface doesn’t contain instance fields or implementations of instance methods, it’s easier to keep details of the implementation out of the specifications.
• Ready for change. We can easily add new implementations of a type by adding classes that implement interface. If we avoid constructors in favor of static factory methods, clients will only see the interface. That means we can switch which implementation class clients are using without changing their code at all.

Test Yourself

Java interfaces

Consider this Java interface and Java class, which are intended to implement an immutable set data type: ```java /** Represents an immutable set of elements of type E. / interface Set<e> { /** make an empty set */ /A*/ public Set();

1    /** @return true if this set contains e as a member */
2    public boolean contains(E e);
3         
4    /** @return a set which is the union of this and that */

/B/ public ArraySet union(Set<e> that); }

/** Implementation of Set<e>. */ class ArraySet<e> implements Set<e> { /** make an empty set */ public ArraySet() { … }

1 /** @return a set which is the union of this and that */
2 public ArraySet union(Set<e> that) { ... }
3 
4 /** add e to this set */
5 public void add(E e) { ... }

} ```

Which of the following statements are true about Set<e> and ArraySet<e>?

• [ ] The line labeled A is a problem because Java interfaces can’t have constructors.
• [ ] The line labeled B is a problem because Set mentions ArraySet, but ArraySet also mentions Set, which is circular.
• [ ] The line labeled B is a problem because it isn’t representation-independent.
• [ ] ArraySet doesn’t correctly implement Set because it’s missing the contains() method.
• [ ] ArraySet doesn’t correctly implement Set because it includes a method that Set doesn’t have.
• [ ] ArraySet doesn’t correctly implement Set because
• [ ] ArraySet is mutable while Set is immutable.

Code review

Let’s review the code for FastMyString. Which of these are useful criticisms:

• [ ] I wish the abstraction function was documented
• [ ] I wish the representation invariant was documented
• [ ] I wish the rep fields were final so they could not be reassigned
• [ ] I wish the private constructor was public so clients could use it to construct empty strings
• [ ] I wish the charAt specification did not expose that the rep contains individual characters
• [ ] I wish the charAt implementation behaved more helpfully when i is greater than the length of the string

Collection interfaces & implementations

Assume the following lines of code are run in sequence, and that any lines of code that don’t compile are simply commented out so that the rest of the code can compile.

The code uses two methods from Collections, so you might need to consult their documentation.

Choose the most specific answer to each question. java Set<string> set = new HashSet<string>();

set now points to:

• [ ] a HashSet object
• [ ] an object that implements the Set interface
• [ ] null
• [ ] this line won’t compile

1 set = Collections.unmodifiableSet(set);

set now points to:

• [ ] a HashSet object
• [ ] a Collections object
• [ ] an object that implements the Set interface
• [ ] null
• [ ] line 2 won’t compile

1 set = Collections.singleton("glorp");

set now points to:

• [ ] a HashSet object
• [ ] a Collections object
• [ ] an object that implements the Set interface
• [ ] null
• [ ] line 3 won’t compile

1 set = new Set<string>();

set now points to: - [ ] a HashSet object - [ ] a Collections object - [ ] an object that implements the Set interface - [ ] null - [ ] line 4 won’t compile

1 List<string> list = set;

set now points to: - [ ] a HashSet object - [ ] a Collections object - [ ] an object that implements the Set interface - [ ] null - [ ] line 5 won’t compile

Answers to the Test Yourself questions.