3. Our Specification Of Lists - Details

With the specification of collection complete, let's turn to lists. Our specification of List is a small extension of Collection, taking into account the 2 special properties lists have that ordinary collections don't, namely (refer to handout):

in a list there is a linear order (called followed by, or next) defined on the elements: every element (except for one, called the last element) is followed by one other element, and no two elements are followed by the same element. There is exactly one element in a list (the first element) that does not follow after any element.
It is possible to access individual elements of a list. This access is provided by having a window on the list; when we define the abstract type List we will also have to define Window.

The implications of list is a special kind of collection are two-fold:

Any operation that is applicable to a collection is applicable to a list. A list is a collection.
However, lists are special kinds of collections - they have 2 special properties. We have to add extra postconditions to the operators in order to say how these properties are affected by the operations.

INSERT:: if C is a list: V is the first element in C'.
DELETE:: if C is a list: it is the first occurrence of V in C that is deleted.
JOIN:: if C1 and C2 are both lists: in C1' the elements of C1 and C2 are in their original order, and the elements of C1 are before the elements of C2.
MAP:: if C is a list: if E1 occurs before E2 in C, then the call P(E1) is made before the call P(E2).

To complete our specification we just have to specify what a window is, how windows are affected by the above list operations, and what operations can be performed on windows,

A window is always associated with an individual element of a list; there is no concept of an empty window, or of a window that gives access to several elements. We say that the window is on the element. A window allows us only to look at an element, not to change it.

Unlike the textbook definition we do not specify how many windows there will be for a given list. There could be none, there could be many.

A window is not to be confused with a list element. An element exists whether or not there is a window on it; if we have a window on an element and then we move or destroy the window, the element is unaffected. There can be several distinct windows all on the same element at the same time.

Of course, you shouldn't confuse windows with pointers in C. Window is an abstract type, which we are in the process of specifying. It might be possible to implement this abstract type with C pointers, but it might not; and even if it is possible, it may not be the best way to implement the abstract type. The question of how to implement windows is a separate issue from defining what a window is.

How are windows affected by the list operations? For example, if we create a window on the first element of L and then insert a new value into L, is the window now on the new first element, or does it stay attached to the element it was on before the insert? Our general answer is: if a window is on element E then it stays on element E unless explicitly moved. E.g., when we JOIN two lists, the windows all stay on their elements.

The operations on windows are specified in the handout:

CREATE_WINDOW

input: L (a list), W (a window).
output: W'.
preconditions: L is not empty, W is undefined.
postconditions: W' is on the first element in L. Storage is allocated as needed.

DESTROY_WINDOW

input: W (a window).
output: W'.
preconditions: none.
postconditions: W' is undefined. As much space is reclaimed as is possible.

Destroying a window does not affect the element or list that the window was on. But what about the opposite? Suppose we have a window on element E in list L and we delete E, or destroy L. What happens to the window? This is an important part of the specification. The 2 main possibilities are:

when an element is deleted, or a list destroyed, all the associated windows are destroyed automatically.
deleting an element or destroying a list causes the associated windows to become invalid but the space they consume remains allocated.

Option (1) is the better choice, but it is also the harder to implement: it requires every list element to keep track of all the windows that are on it. This is not difficult, but for simplicity's sake, we will take option (2). What this means is that the user is responsible for destroying the windows he creates, and for keeping track of whether a window is valid or not.

IS_LAST

input: W (a window).
output: boolean.
preconditions: W is defined.
postconditions: true if W is on the last element in a list, false otherwise.

GET_VALUE

input: W (a window).
output: V (a value of a list element).
preconditions: W is defined.
postconditions: V is the value of the element W is on.

MOVE_FORWARD

input: W (a window).
output: W'.
preconditions: W is not on the last element of a list.
postconditions: W' is on the element that follows the element W was on.

This is the only operation the moves a window. There are other useful ones we could have included - MOVE_BACKWARD, for example.

SPLIT

input: L1, L2 (lists), W (a window).
output: L1' and L2'.
preconditions: W is a window into L1, L2 is undefined.
postconditions: L2' = the elements of L1 following the one W is on, their order unchanged. If W is on the last element, L2' is empty. L1' = the elements of L1 up to and including the one W is on, their order unchanged.

Example of SPLIT:

SPLIT(L1,L2,W) would produce:

What about other windows that might be on elements of L1? Following our general rule, SPLIT does not affect them: they are on the same elements after SPLIT as they were before.

We are now finished the specification phase of our design for the abstract data types collection and list. The next design phase addresses the implementation of the datatype. This is a design process, too, and it is concerned almost exclusively concerned with the type definitions:

will something be a record, or an array, or a linked data structure?
how many pointers will there be, where should they point?
etc...

We will not consider in any detail the code that implements the operations. The reason is this: once the C type definitions have been decided upon, the code for the operations is completely determined - the specification tells us what they must do, and the type definitions tell us on what specific data objects they must operate. Filling in the code requires no further decisions, just careful attention to detail. So you see the decisions about the type definitions are very important - it is they determine how simple and efficient our code will be.