Representation Invariant, Abstraction Function

Recall that an interface specification is a contract between a module's provider and the client programmer, that documents each other's expectations about the module’s operations:

• valid uses of operations (preconditions)
• expected outcomes of operations (postconditions)
• expressed in terms of the module’s abstract values

representation invariants define the sets of valid concrete values of an ADT’s implementation. abstraction functions interpret legal concrete values as an ADT’s abstract values.

Linked List

The Representation Invariants for this linked list are:

• header's data field is a nullptr
• head of list is never nullptr since it points to the header node
• Node has next and prev fields
• given 2 nodes n1 and n2, if n1.next == n2, then n2.prev == n1
• element field of all other entries != nullptr

class LinkedList {
  class Node {
  public:
    Data *element_;
    Node *prev_;
    Node *next_;
    Node(Data *e, Node *p, Node *n) : element_(e), prev_(p), next_(n) {}
  };

public:
  LinkedList();
  … private : Node *header_;
  int size_;
};

LinkedList::LinkedList() : 
  size_(0), 
  header_(new Node(nullptr, nullptr, nullptr)) 
{
  header_->prev = header_->next = header;
}

void LinkedList::insert(Data *o) {
  Node *e = new Node(o, header->prev, header);
  e->prev->next = e;
  e->next->prev = e;
  size++;
}

Guideline: it's better to create an empty ADT whose size is 0 (e.g: initially empty vector) than to always have to check for nullptr.

Q: What if we strengthened the invariant by requiring that all element fields are not nullptr? A: Well, we could dispense with using size to count nodes when traversing the list

Q. What if we weaker invariant on initial values of the header's prev and next, allowing nullptr? A: we would need to reintroduce code for special cases

Representation Invariants of Complex Types

If the representation uses other ADTs, it may refer to themeither by their specification fields of by their operations.

Example:

class Account {
  int balance_;
  vector<Trans> transacitonHistory_;
  ...
};

Suppose the Trans ADT has a specification field ammount that is accessible by the operation ammount()

The Representation Invariant for Account:

• balance >= 0
• a) use specification field for "Trans"
  • balance += transactionHistory_[i].ammount
• b) use the operation for "Trans"
  • balance += transactionHistory_[i].ammount()

Why even use Representation Invariants?

Well, it helps rest, debug, and implement code, since the most common problems are leaving out something (i.e: edge cases)

• you can look for representation values that don't correspond to a valid ADT values