11 COLLECTIONS
11.1 Stacks
11.2 Exceptional Conditions
11.3 Queues
11.4 Matrices
11.5 Summary
In daily life there are many examples of collections. Collections of match boxes, stamps, paintings, horses are all examples of intentional collections. The concept of collection is also present in less obvious cases. For example, a forest as a collection of trees, a library as a collection of books, a book as a collection of chapters.
Collections are playing prominent roles in various applications. In many situations, the elements of a collection are of the same type. We will call such a collection a homogeneous collection.
If a collection contains elements of different types we are talking about a heterogeneous collection. The objects in a warehouse, the pieces of a chess game, the things in your pocket, are all examples of heterogeneous collections.
A collection may also contain other collections. A company is a collection of departments which contains collections of employees. A city may be considered as a collection of streets, a collection of houses, and a collection of people.
As we discussed earlier, there are two basic types of collections predefined in the language: arrays, and lists. Based on these two collection types other types of collections can be constructed as will be discussed in this chapter.
We will start with a stack as a small, but interesting example of a collection. We are all familiar with stacks of dishes, stacks of books, or stacks of notes. Characteristic for a stack is that an element which has been last put on a stack, is the first which will be taken off the stack. This principle is sometimes called: Last-In-First-Out or First-In-Last-Out. Let us assume that we want to simulate a stack of books and that the type of Book has already been defined. The operations on such a stack can be defined in a component (see Figure 11-1).
component Stacks; type Stack; Stack (MaxSize = integer) -> Stack; Empty (Stack ) -> boolean; Full (Stack ) -> boolean; Push (Stack, Book) -> nothing; Pull (Stack ) -> Book; begin Stack (MaxSize ) = Stack:[ MaxSize; index:=0; area= array (Book, MaxSize) ];Empty (stack ) = (stack.index <= 0);Full (stack ) = (stack.index >= stack.MaxSize);Push (stack, element ) = [ stack.index:=stack.index + 1; stack.area[ stack.index ]:=element ];Pull (stack) = [ stack.index:=stack.index - 1; stack.area [stack.index + 1 ] ]; end component Stacks;
Figure 11-1: An example of a Stack component.
This component supports one constructor operation ( Stack ), two accessor operations (Empty and Full), and two mutator operations (Push and Pull).
The Stack definition as given in the implementation-section defines the lay-out of the Stack-descriptor. There are three descriptor-elements defined: the maximum size of the stack, the index pointing to the most recent pushed element on the stack, and the area for the stack. The initial value of the index is zero, indicating that the new stack is empty. The stack-area is defined as an array with a maximum number of elements as specified by MaxSize. The array-function is the standard, pre-defined function which creates an array with space for the required number of elements. The first element of the array corresponds with the index-value 1, the second with 2, and so on. The last element corresponds with the maximum number.
The Empty operation is used to test if the stack is empty. If so, it returns the boolean value true; if not, it returns false. The test is performed by comparing the current value of the stack index with zero.
The Full operation tests if the stack is full, by comparing the current value of the stack-index with the maximum number.
The Push operation will put a new element on the current top of the stack. It first increases the index and then uses the new value of the index to store at the proper location in the stack-area the new element. The Push definition returns nothing.
The Pull operation will return the most recent element from the top of the stack. It first decreases the index and then uses the new value of the index to obtain the top-element.
We can now use the Stacks component in the following session:
type Book = text; S = Stack (5); S?
The system responds with:
Stack:[ MaxSize = 5;
index = 0;
area = array([],
[],
[],
[],
[] )]
The Stack-descriptor contains an empty array, representing the stack area. We will now use some Stack operations:
Push (S, "Peter Pan"); Push (S, "Alice in Wonderland"); S?
The system returns the following Stack-descriptor:
Stack:[ MaxSize = 5;
index = 2;
area = array("Peter Pan",
"Alice in Wonderland",
[],
[],
[] )]
We can now use some Pull operations:
Pull (S)? "Alice in Wonderland"Pull (S)? "Peter Pan"
As expected, we see that the stack of books works in a last-in-first-out manner.
Exercise:
- 11.1 Use the Stacks component to create two stacks of books. Move all the books from one stack to the other in a last-in-first-out manner.
Let us assume that we want to continue the previous session by asking for another book from the stack, what would be the result? In this case, the system will respond with an error message indicating that an array index is out of bound. And this is because there are no books on the stack anymore; in the implementation of the Pull definition the array index will be decreased below its minimum value and an attempt is made to access a non-existing array element.
To avoid this kind of undesirable situation the client of the Stacks component should be constantly aware that the Stack as defined here, has a limited capacity. Therefore he should avoid to push an entity on the stack when the stack is full or to pull an entity from the stack when the stack is empty. He can do that by using constructs like:
if not Full (S) then Push (S, "New Book")if not Empty (S) then Pull (S)
In every situation where the client is not sure of the actual number of entities on the stack, he should use these kinds of constructs.
However, the problem with this approach is that if the client is not performing in all cases the necessary tests, some operations may produce wrong results without notifying the client, or the system will give an error message which will be difficult to understand. To avoid these situations we prefer more robust components, which are performing well under normal conditions but are notifying the user of exceptional situations which cannot be handled by the component. That means we will need to define some kind of exception handling. To illustrate the handling of exceptions we will rework our Stacks component (see Figure 11-2).
component Stacks; type Stack; Stack (MaxSize = integer) -> Stack; Empty (Stack ) -> boolean; Full (Stack ) -> boolean; Push (Stack, Book) -> nothing; Pull (Stack ) -> Book; begin Stack (MaxSize ) = Stack:[ MaxSize; index:=0; area= array (Book, MaxSize) ];Empty (stack ) = (stack.index <= 0);Full (stack ) = (stack.index >= stack.MaxSize);Push (stack, element ) = [ exception ( Full (stack), "Stack Overflow"); stack.index:=stack.index + 1; stack.area[ stack.index ]:=element ];Pull (stack) = [ exception (Empty (stack), "Stack Underflow"); stack.index:=stack.index - 1; stack.area [stack.index + 1 ] ]; end component Stacks;
Figure 11-2: An example of a Stack component with exceptions.
In the definitions for the Push and Pull operations, tests on the conditions of Full and Empty stack have been included by using the exception statement. If an exceptional condition occurs, the result of the operation will be undefined, the execution of the definition will be interrupted and the user will be informed with the specified message.
In the previous section we have seen how an elementary collection as an array can be used to build more application-oriented collections such as stacks. In this section we will use the same principles for another type of collection, named queues. Queues are familiar to us in real life: we meet them as waiting lines of persons for a ticket-window, or of vehicles for a traffic-light. In computers we use them for messages or commands destined for users, processes or other systems. The elements of a queue follow the principle of: First-In-First-Out and Last-In-Last-Out. Queues may be implemented in a number of ways. We have chosen to base the collection type Queue on lists. And we will have queues of vehicles assuming that the type Vehicle is already defined. A component for queues of Vehicles is defined in Figure 11-3.
component Queues; type Queue; Queue (MaxSize = integer ) -> Queue; Empty ( Queue ) -> boolean; Full ( Queue ) -> boolean; Append ( Queue, Vehicle ) -> nothing; Remove ( Queue ) -> Vehicle; begin Queue (MaxSize) = Queue:[ MaxSize; count:=0; List=alist (Vehicle)];Empty ( queue ) = (queue.count <= 0);Full ( queue ) = (queue.count >= queue.MaxSize);Append ( queue, element ) = [ exception ( Full (queue), "Queue Overflow"); queue.count:=queue.count + 1; add (element, queue.List) ];Remove ( queue ) = [ exception ( Empty (queue), "Queue Underflow"); queue.count:=queue.count - 1; remove ( last (queue.List) ) ]; end component Queues;
Figure 11-3: An example of a Queue component.
This Queues component is very similar in structure to the Stacks component. The main difference is that it is using the list type.
The Append operation appends a new element to one end of the queue, while the Remove operation deletes an element at the other end of the queue. Both operations are making use of operations defined for lists.
There are some fundamental differences of the Queue component here with the Enqueue and Dequeue functions we discussed in Section 8.7 about "Lists and Functions". First, in this chapter, Queue is a separate type in contrast to the example of list functions. Second, queues here are limited in size, while the example of list functions have unlimited queues.
Exercise:
- 11.2 Use the Queues component in a session to simulate vehicles waiting for a traffic light. Assume that vehicles are identified by their registration numbers.
Matrices are used in various application areas. A matrix is a rectangular array of elements that can be combined to form sums and products with similar matrices having an appropriate numbers of rows and columns. The elements of a matrix may be quantities, symbols, or other mathematical elements. As a special branch of algebra, matrix algebra has been developed to operate on matrices. In the following example we will introduce the concept of a matrix and the operations for the addition and the multiplication of two matrices. Furthermore, we will introduce an operation to fill a matrix with numbers (Figure 11-4).
component Matrices; type Matrix; Matrix (Rows = integer, Columns = integer) -> Matrix; Matrix + Matrix -> Matrix; Matrix * Matrix -> Matrix; Fill (Matrix, list (list (integer)) ) -> nothing; begin Matrix (Rows, Columns) = [ M = Matrix:[ Rows; Columns; A = array (array(integer), Rows) ]; M.A[ 1..Rows ]:= array (integer, Columns); M ];
Matrix1 + Matrix2 = [ exception (Matrix1.Rows <> Matrix2.Rows or Matrix1.Columns <> Matrix2.Columns, "Addition of incompatible matrices" );<< Matrix3 is result matrix: >> Matrix3 = Matrix (Matrix1.Rows, Matrix1.Columns );[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix1.A[i, j] + Matrix2.A[i, j] ];Matrix3 ];
Matrix1 * Matrix2 = [ exception( Matrix1.Columns <> Matrix2.Rows, "Multiplication of incompatible matrices" );Matrix3 = Matrix (Matrix1.Rows, Matrix2.Columns);[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix2.Columns; Matrix3.A[i, j]:=0; k = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix3.A[i, j] + Matrix1.A[i, k] * Matrix2.A[k, j] ];Matrix3 ];
Fill (Matrix1, List) = [ i:=0; ListRow= items (List); i:=i+1; ready when i > Matrix1.Rows; [ j:=0; ListElement= items (ListRow); j:=j+1; ready when j > Matrix1.Columns; Matrix1.A[i, j]:= ListElement ] ];end component Matrices;
Figure 11-4: An example of a Matrix component.
The first definition is a matrix constructor definition which introduces a new matrix with m rows and n columns. The resulting Matrix-descriptor has three elements: the number of Rows, the number of Columns, and the two-dimensional array A. Because A is an array of arrays, A is an example of a collection of collections. The rectangular array A is set up according to the principles of multi-dimensional arrays discussed in Chapter 7.
The addition of two matrices will result in a new matrix. The matrices involved in matrix addition must have the same number of rows and the same number of columns. The elements of the new resulting matrix are defined as the sum of the corresponding elements of the two input matrices.
The multiplication of two matrices will also result in a new matrix. The number of columns of the first matrix must be equal to the number of rows of the second matrix. The resulting matrix has the same number of rows as the first matrix and the same number of columns as the second matrix. An element [i, j] of the resulting matrix is defined as the sum of the products of the elements [i, k] of the first matrix and the elements [k, j] of the second matrix.
The Fill definition fills a matrix with numbers of a list of lists. The procedure is based on the principles discussed in Section 7.6, "Arrays and Streams". The elements of a list are first converted to a stream and then stored into an array. Note that the Fill operation will only use those elements of the list which fit within the boundaries of the array.
We may now use this component in a session. We start with the creation of a matrix M1 and we will fill it with some numbers:
M1 = Matrix (3, 4);
Values = { { 11, 12, 13, 14 },
{ 21, 22, 23, 24 },
{ 31, 32, 33, 34 },
{ 41, 42, 43, 44 } };
Fill (M1, Values);
M1?
The system will return with the Matrix-descriptor:
Matrix:[ Rows = 3;
Columns = 4;
A = array( array( 11, 12, 13, 14),
array( 21, 22, 23, 24),
array( 31, 32, 33, 34) ) ]
We now have a filled matrix M1. Note that the last row of the list of Values has not been used due to the limitation constraints of the matrix M1.
Let us now try to use matrix addition. Therefore we need two matrices. The easiest way to get a second matrix is to define M2 as being the same as M1, as is done in the following:
M2 = M1; M3 = M1 + M2; M3?
The resulting descriptor is:
Matrix:[ Rows = 3;
Columns = 4;
A = array( array( 22, 24, 26, 28),
array( 42, 44, 46, 48),
array( 62, 64, 66, 68))]
And this is according to our expectations.
The next step is to use matrix multiplication. Therefore we will introduce another matrix M4 which can be multiplied by M1:
M4 = Matrix (4, 4); Fill (M4, Values); M4?
The resulting M4 descriptor is:
Matrix:[ Rows = 4;
Columns = 4;
A = array( array( 11, 12, 13, 14),
array( 21, 22, 23, 24),
array( 31, 32, 33, 34),
array( 41, 42, 43, 44) ) ]
We may now use matrix multiplication:
M5 = M1 * M4; M5?
The result is:
Matrix:[ Rows = 3;
Columns = 4;
A = array( array( 1350, 1400, 1450, 1500),
array( 2390, 2480, 2570, 2660),
array( 3430, 3560, 3690, 3820) ) ]
Exercise:
- 11.3 What is the result if we try
to compute M1 * M2?
11.4 Are matrices as defined here mutable or immutable objects?
- Collections consists of elements.
- In a homogeneous collection all elements are of the same type.
- In a heterogeneous collection the elements may be of different types.
- Stacks and queues are examples of collections based on the basic collection types of arrays and lists.
- A collection may contain other collections. Matrices are examples of nested collections.
 |
Part 1: Language Description | Chapter 11: Collections |