SC ADT

• R10: abstraction data types
  • access control
  • What abstraction means
  • classifying types and operations
  • What and how: what is ADT and how to design
  • representation independence
  • Testing
• R11: abstraction function & rep invariants
  • invariants
  • Rep invariants and abstract function
  • Beneficent mutation
  • Documenting the AF, RI, and safety from rep exposure
  • ADT invariants replace preconditions
• R12:defining ADTs
  • Interface
  • subclassing
  • Generic types
  • enumerations
  • ADTs in non-OOP languages

R10: abstraction data types¶

access control¶

Private(only in the same class), public, no modifiers(only in the same package), protected(only in the same parentage)

• Scope: same class, same package, subclass of other package, different class of other package

• 区分： instance variable vs. class name

What abstraction means¶

• fancy words? Not that fancy.
  • Abstraction/modularity/encapsulation/information hiding/separation of concerns
• User-defined types
  • type is characterized by the operations you can perform on it.
  • abstract away from the details of data structure, memory storage, implementation

classifying types and operations¶

• Types: mutable / immutable

• Operations:

  • Creator, create new objects of the type. Input: values
    • constructor
    • implemented as a static method called a factory method
  • Producers. Input: existing objects
  • Observer
  • Mutators, change objects

What and how: what is ADT and how to design¶

• Representation
• Implementation

representation independence¶

Testing¶

R11: abstraction function & rep invariants¶

invariants¶

good ADTs preserve its own invariants.

• mutable objects

• public and private in access control

• Immutable wrappers around mutable data types, get exception at runtime not at compile time.

  • avoid representation exposure

Rep invariants and abstract function¶

abstract type can be divided into abstract value space and representation value space.

• every abstract value is mapped to by some rep value.
• Some abstract values are mapped to by more than one rep value.
• Not all rep values are mapped.

1. Abstract function

AF: R -> A

2. Rep invariant

RI: R->boolean //subset of rep values on which AF is defined

Implementations of an ADT means not only choosing the two spaces, but alse deciding which rep values are legal, and how to interpret them as abstract values.

Beneficent mutation¶

• beneficent mutation: 改变rep value, 不改变abstract value

  The rep value has changed to another that still maps to the same abstract value.

Documenting the AF, RI, and safety from rep exposure¶

• Rep exposure safety argument
• What an ADT spec
  • may talk about
    • Things that are visible to the client: parameters, return values, exceptions thrown by its operations
    • Abstract values
  • should not talk about
    • details of the representation
    • AF and RI should hide within the body of the class

ADT invariants replace preconditions¶

• Encapsulate preconditions in ADTs

• How to establish invariants

  if an invariant of an ADT is

  1. established by creators and producers
  2. preserved by mutators, observers, and producers; and
  3. no representation exposure occurs
  

  then the invariant is true of all instances of the ADT.

R12:defining ADTs¶

Objectives:implement interfaces, generic types, enumerations and global functions operating on opaque type of ADT, determine subtyping relationship

Interface¶

> interfaces:¶

• advantage:

  1. Interface specifies the contract for the client.
  2. Support multiple different representations

• Java’s interfaces: do not include info about the representations

  所以不需要提供有关interface的额外信息，比如：instance variables, instance method bodies, constructors

> subtypes:¶

• 编译器能检查子类型有无实现其父类的所有类型，但不能检查是否符合其规范。我们需要保证子类型的规范至少要和其父类一样的强劲。

“B is a subtype of A” means “every B is an A.” In terms of specifications: “every B satisfies the specification for A.

• Declare subtypes in java

  • declare that a class B is a subtype of an interface A, use implements:

  class ArrayList<E> implements List<E> {
      ...
  }

  • declare that an interface is a subtype of another interface, using extends:

  interface SortedSet<E> extends Set<E> {
      ...
  }

> Example:mystring¶

需要注意的地方：

1. Constructor: valueOf(). The difference between concrete class’s static method and interface’s constructor

2. Inheritance: @override

3. Private constructors are allowed

4. abstraction barrier between ADT and its concrete representations

   • How clients use ADT?

     MyString s = new FastMyString(true);
     MyString s = MyString.valueOf(true); //better

     • implement the creator operation valueOf as a static factory method in the interface MyString

/**
 * MyString represents an immutable sequence of characters.
 */
public interface MyString { 
    // public static MyString valueOf(boolean b) { ... }
    public static MyString valueOf(boolean b) {return new FastMyString(b);} //notice 4
    public int length();
    public char charAt(int i);
    public MyString substring(int start, int end);
}

public class SimpleMyString implements MyString {
    private char[] a;
    /**
     * Create a string representation of b, either "true" or "false".
     * @param b a boolean value
     */
    public SimpleMyString(boolean b) {
        a = b ? new char[] { 't', 'r', 'u', 'e' } 
              : new char[] { 'f', 'a', 'l', 's', 'e' };
    }
  
    // private constructor, used internally by producer operations
    private SimpleMyString(char[] a) {
        this.a = a;
    }
  
    @Override public int length() { return a.length; }
    @Override public char charAt(int i) { return a[i]; }
    @Override public MyString substring(int start, int end) {
        char[] subArray = new char[end - start];
        System.arraycopy(this.a, start, subArray, 0, end - start);
        return new SimpleMyString(subArray);
    }
}

public class FastMyString implements MyString {

    private char[] a;
    private int start;
    private int end;

    /**
     * Create a string representation of b, either "true" or "false".
     * @param b a boolean value
     */
    public FastMyString(boolean b) {
        a = b ? new char[] { 't', 'r', 'u', 'e' } 
              : new char[] { 'f', 'a', 'l', 's', 'e' };
        start = 0;
        end = a.length;
    }

    // private constructor, used internally by producer operations.
    private FastMyString(char[] a, int start, int end) {
        this.a = a;
        this.start = start;
        this.end = end;
    }

    @Override public int length() { return end - start; }
    @Override public char charAt(int i) { return a[start + i]; }
    @Override public MyString substring(int start, int end) {
        return new FastMyString(this.a, this.start + start, this.start + end);
    }
}

> Why interfaces？¶

1. 使用界面能为编译器和人们增加可读性。
2. 从最开始抽象出独立的实现，然后再修正具体细节。能够在不同方式实现间权衡性能。
3. 有意未明确的方法规范，在之后更具体的实现
4. multiple view of one class. A java class may implement multiple interfaces.
5. 通过从简单的实现到更复杂/严格的实现，一步步构建可信的方法实现

subclassing¶

和界面实现的区别在于：subclass 可以继承superclass的method bodies, fields；包含spec 和rep,而interface只包含spec。

Problem: what inheriting the rep means?

• answer: 一个安全的subclass需要遵循两个合同，和用户的以及和其subclass的，而这导致了rep独立性被破坏的问题。

  • rep exposure between the superclass and all its subclasses
  • rep dependence between superclass and subclasses
  • superclass and subclass can inadvertently break each other’s rep invariants

Static type vs. dynamic type:

• Dispatching to the method

  Java’s dynamic dispatch: it uses the implementation appropriate to the dynamic type of the object, not the static type of the reference that points to the object.

FastMyString fms = new FastMyString(true); // recall that this represents the 4-character string "true"
fms.toString() → "FastMyString@504bae78" // not useful! just the class name followed by the object's address in memory
  
public class FastMyString {
    ...
    @Override
    public String toString() {
        String s = "";
        for (int i = 0; i < this.length(); ++i) {
            s += this.charAt(i);
        }
        return s;
    }
}
Object obj = new FastMyString(true);
obj.toString() → "true"

Object is static type known at compile time, while FastMyString is the typpe unknown until runtime.

Generic types¶

generic type: a type whose specification is in terms of a placeholder type to be filled in later. -> generic programming

Implementations:

• Generic interface, non-generic implementation

  public interface Set<E> {)
  public class CharSet implements Set<Character> {}                      

• Generic interface, generic implementation

  public interface Set<E> {}
  public class HashSet<E> implements Set<E> {}

enumerations¶

enumeration: a small and finite values which can be defined as named constants.

和c struct相像。

• Java 中.equals 和 == 的额外细节：equals在运行时间检查是否在意义上相同，而==检查两个对象是否是同一个reference。这在一般的比较中是有差异的，而在enum中由于只有唯一的reference，equals和==反而没什么区别，同时==符合fail fast的特点因为我们检查的正是它们是否是相同的reference指向唯一的enum中的值。

• java中有内置的enum类型，自动提供一些操作：

  • ordinal() is the index of the value in the enumeration, so JANUARY.ordinal() returns 0.
  • compareTo() compares two values based on their ordinal numbers.
  • name() returns the name of the value’s constant as a string, e.g. JANUARY.name() returns "JANUARY".
  • toString() has the same behavior as name()

• 可以自定义需要的enum

  • An enum declaration can contain all the usual fields and methods that a class can. (Rep, methods, constants)
  • Example

  public enum Month {
      // the values of the enumeration, written as calls to the private constructor below
      JANUARY(31),
      FEBRUARY(28),
      MARCH(31),
      APRIL(30),
      MAY(31),
      JUNE(30),
      JULY(31),
      AUGUST(31),
      SEPTEMBER(30),
      OCTOBER(31),
      NOVEMBER(30),
      DECEMBER(31);
  
      // rep
      private final int daysInMonth;
  
      // enums also have an automatic, invisible rep field:
      //   private final int ordinal;
      // which takes on values 0, 1, ... for each value in the enumeration.
  
      // rep invariant:
      //   daysInMonth is the number of days in this month in a non-leap year
      // abstraction function:
      //   AF(ordinal,daysInMonth) = the (ordinal+1)th month of the Gregorian calendar
      // safety from rep exposure:
      //   all fields are private, final, and have immutable types
  
      // Make a Month value. Not visible to clients, only used to initialize the
      // constants above.
      private Month(int daysInMonth) {
          this.daysInMonth = daysInMonth;
      }
  
      /**
       * @param isLeapYear true iff the year under consideration is a leap year
       * @return number of days in this month in a normal year (if !isLeapYear) 
       *                                           or leap year (if isLeapYear)
       */
      public int getDaysInMonth(boolean isLeapYear) {
          if (this == FEBRUARY && isLeapYear) {
              return daysInMonth+1;
          } else {
              return daysInMonth;
          }
      }
  
      /**
       * @return first month of the semester after this month
       */
      public Month startOfNextSemester() {
          switch (this) {
              case JANUARY:
                  return FEBRUARY;
              case FEBRUARY:   // cases with no break or return
              case MARCH:      // fall through to the next case
              case APRIL:
              case MAY:
                  return JUNE;
              case JUNE:
              case JULY:
              case AUGUST:
                  return SEPTEMBER;
              case SEPTEMBER:
              case OCTOBER:
              case NOVEMBER:
              case DECEMBER:
                  return JANUARY;
              default:
                  throw new RuntimeException("can't get here");
          }
      }
  }

ADTs in non-OOP languages¶

define ADT in non-oop languages like C: a group of globally-accessible functions that operate on an opaque data type.

(data abstraction)

FILE* f = fopen("out.txt", "w"); // open a file for writing
fputs("hello", f); // write to the file
fclose(f);  // close the file

The notion of an abstract data type does not depend on language features like classes, or interfaces, or public/private access control. Data abstraction is a powerful design pattern that is ubiquitous in software engineering.