Data Structures & Algorithms Lecture Notes

17 September 2009 • Interfaces

---

Outline

• Types and operations.

• Interfaces.

• Traits.

Types and Operations

• A value v’s type determines the allowable operations on v.

• A value v’s type doesn’t matter if nothing operates on v.

  • v’s type may as well be Object.

• Two extremes:

  • perform no operations on v, or

  • perform every possible operation on v.

Example

• Consider a VotingList data structure, the list of everybody able to vote in a district.

• The constituent-value type is Citizen.

• A VotingList performs a few Citizen operations.

  bool sameName(String name)
  bool isVotingAge()
  Date lastVotedOn()
  

• Citizen has many operations not needed by VotingLists.

A Middle Ground

• Some data structures perform some but not all operations on constituent values.

• What is the type of the constituent values?

  • Object doesn’t allow the necessary operations.

  • The values’ dynamic type is too specific.

• Is there a middle ground where the constituent values’ type allows the required operations and ignores the rest?

Interfaces

• An interface specifies a type’s allowable operations.

  • Specifies, not defines.

  • All methods are non-static and public.

• An interface can also contain variables, classes, and other interfaces.

Example Interfaces

interface Voter {
  bool sameName(String name);
  bool isVotingAge();
  Date lastVotedOn();
  }

interface Dictionary<K, V> {
  public void put(K key, V value);
  public void delete(K key);
  public V find(K key);
  }  

Interfaces and Classes

• A class implements one or more interfaces.

  class Citizen
  implements Voter
  extends Person {
  
    bool sameName(String name) { ... }
    bool isVotingAge() { ... }
    Date lastVotedOn() { ... }
  
    bool isNaturalized() { ... }
    // and so on
    }
  

Classes and Interfaces

• A class may implement

  • more than one interface.

  • interfaces and extend a class.

  • its own methods.

• An interface may extend another interface.

  interface RichVoter
  extends Voter
    BigInteger campainContributions();
  

Interface and Class Types

• An interface defines a type.

• A class implementing an interface can considered to be of the interface’s type.

  • A value of type Citizen can also be of type Voter.

  This is the interface style of pseudo-multiple inheritance.

Interface Advantages

• An interface precisely specifies the constituent type required by a data structure.

  • The VotingList accepts constituent values of type Voter.

• The interface defines exactly the operations needed by the data structure.

• All other constituent-value operations are ignored (and are inaccessible).

Trait-Defining Interfaces

• Use interfaces to define traits: small, well-defined collections of behavior.

  interface Comparable
    int compareTo(Object o);
  
  public interface Destroyable
    void destroy();
    boolean isDestroyed();
  
  public interface Readable
    int read(CharBuffer cb);
  

Trait Behaviors

• Mix and match traits to give desired behaviors to classes.

  class Card
  implements Comparable
    int compareTo(Object o) { ... }
    // and so on.
  
  class SecurityCertificate
  implements Destroyable, Readable
    void destroy() { ... }
    boolean isDestroyed() { ... }
    int read(CharBuffer cb) { ... }
    // and so on.
  

Trait Specifications

• Use traits to specify exactly and minimally what behavior class instances should have.

  boolean beats(Comparable x) { ... }
  void validate(Destroyable tag) { ... }
  Message read(Readable input) { ... }
  

• The same class instance may have several roles based on traits.

  SecurityCertificate ticket = 
    new SecurityCertificate()
  validate(ticket)
  Message m = read(ticket)
  

Summary

• Interfaces specify expected class behavior.

• Specify a data structure’s constituent types in terms of interfaces.

• Think in terms of traits when defining interfaces.

References

• Item 17 (Use interfaces only to define types) from Effective Java by Joshua Bloch, Addison-Wesley, 2001.