The use of files allows us to read lists from outside the program and to store them at its end. Unfortunately, as our updating programs show, it is not a good idea to create a new file, external to the program, each time we add, delete or modify an item in a list. We soon end up with a multitude of out of date files.
The use of objects defined by classes allows us to hide a number of basic items inside larger, more complex items. It does not solve the problem of how to refer conveniently to a long list of items in succession. The need to declare and use a separate identifier for each possible line of a letter, for instance, makes long letters unwieldy to process and those of indefinite length almost impossible.
This chapter is the first of three dealing with the handling of lists. It provides simple but elegant mechanisms for solving most of the problems mentioned above. Let us start with the problem of holding a long list of items, which are all of the same type.
Example 10.1 shows the use of an array in a much simplified letter program, where no addresses are allowed for, only the text and the name of the sender.
First look at the array declaration in class Leter. (The mispelling is deliberate since there is a system Boolean procedure called Letter, which we might well wish to use in the same program. This is described in chapter 12.)
Example 10.1: Letter program using a text array.
begin class Leter; begin text Sender; text array Line(1:60); integer Len; procedure ReadLetter; begin InImage; inspect SysIn do while Image.Strip ne ".end" do begin Len := Len + 1; Line(Len) :- Copy(Image.Strip); InImage end end++of++ReadLetter; procedure WriteLetter; begin integer Current; for Current := 1 step 1 until Len do begin OutText(Line(Current)); OutImage end; OutText(" Yours faithfully,"); OutImage; OutText(" "); OutText(Sender); OutImage end++of++WriteLetter; OutText("Type your letter, ending with '.end' on a line by itself"); OutImage; ReadLetter; OutText("Now type your name on a single line"); OutImage; InImage; inspect SysIn do Sender :- Copy(Image.Strip) end--of--class--Leter; new Leter.WriteLetter end**of**program
It is legal to omit the type specifier, in which case the array is asumed to be of type real.
The syntax has not included the form of the bounds. In the commonest case we wish to declare a simple numbered list. The bounds then are two arithmetic values, which are converted to integers if necessary, separated by a colon. In example 10.1 the constant integers 1 and 60 are the bounds. This definition is only the simplest variant, but it covers most uses of arrays for the moment.
The semantics of such a declaration produce information telling the system to reserve space for a list of items of the specified type. This list is to be numbered consecutively, starting with the value before the colon and ending with the value after the colon. This also defines the number of elements in the list.
This list as a whole is referred to by its identifier. Thus a whole array can be passed as a parameter to a class or procedure, by giving just the identifier. Individual items in the list can be referred to by the identifier followed by an arithmetic value enclosed in parentheses, giving the number of the element to be accessed, within the list.
Thus the declaration in example 10.1 tells the SIMULA system to reserve space for a list of sixty text variables. These are to be declared to be numbered from one to sixty. The list will be referred to in the program by the identifier Line.
Note that the value of the first bound does not have to be 1. The bounds can have any values, even negative ones, as long as the first bound is less than the second or equal to it. The first bound is usually referred to as the lower bound and the second as the upper.
Note also that the values of the bounds may be given as real values. In this case they are converted to integers in the same way as for assignments. The values can be arithmetic expressions as well as constants. The normal rules for evaluating expressions apply.
Item number Len of the list is accessed in ReadLetter. It is referred to as Line(Len). Since Len is increased by one before each Image is copied to Line(Len) the effect is to copy successive lines of input into successive elements of the text array Line.
The syntax of a simple subscripted variable is an identifier followed by an arithmetic value enclosed in parentheses. The arithmetic value may be a constant, a variable or a more complicated expression, including a call on an arithmetic type procedure. Where necessary the value will be converted to an integer, following the normal rules.
The semantics are also simple. The value of the subscript gives the number used as an index to the elements of the array.
Note that the value of the lower bound is important in determining which element this refers to. A subscript of six will only refer to the sixth element if the lower bound was one. If the lower bound was four, indexing by six gives the third element.
A subscripted variable may be used wherever a simple variable of the same type may be used.
The value of the subscript, converted to an integer if necessary, must lie between the values of the lower and upper bounds, inclusive. If it is outwith this range a runtime error will be reported.
The lowest permitted value for the lower bound, the highest permitted value for the upper bound and the maximum total number of items permitted in an array are all likely to be different on different systems. The maximum number of elements in an array of one type may also be different from that of another type, even on the same system. Check the Programmers' Reference Manual or Users' Guide for the system you are using.
One problem with the use of arrays is that we must tell the system in their declarations how many elements they contain and what their bounds are. Often this may not be known until runtime. This means that example 10.1 can only cope with letters of up to sixty lines. If someone wanted to use the program for a longer letter, they would have to alter the source and recompile it.
Although the array is not always the best solution when there is no way of knowing in advance how long the list will be, it can be made more generally useful by specifying the bounds in other ways.
We have defined the bounds as any expressions giving arithmetic values. This includes constants, as used in 10.1, but also variables and expressions involving operators and type procedures. The only restriction is that any variables used must already have their values fixed before entering the block in which the array is declared. This means that the bounds can changed each time a block is entered.
This idea is not necessarily obvious at first, so take a while to get it straight in your mind. The SIMULA system allocates the space used by each block only when that block is entered. Thus it does not need to know how big an array is until then. If a variable used in the bounds of an array has been declared in an outer block, this variable can have its value set in that outer block before the array's space is allocated in the inner block. The variable must not be declared in the same block as the array, since the system may allocate the block's arrays before its other variables and, anyway, these variables could only have their initial zero values, since no statements may come in front of declarations in a block.
As a consequence, the only block which cannot use variables in array bounds is the program block. This is the outermost block and must use constants in all its array bounds.
All sub-blocks, procedures and classes used in a program are free to use variables in array bounds so long as these are declared in an enclosing block or, for classes and procedures, are parameters. Remotely accessed variables may also be used.
The simple examples in 10.2, 10.3 and 10.4 show how "dynamic bounds", as this mechanism is known, may be used for sub-blocks, procedures and classes respectively. These trival examples demonstrate a very powerful facility.
One important point to note is that when the parameters of a procedure or class are used in bounds for arrays declared in that procedure or class body, they are treated as outside that body. This is the only case where any distinction is made between parameters and other locally declared variables inside the procedure or class body. It is very important that this be allowed.
Example 10.2: Dynamic array bounds in a sub-block.
begin integer I1,I2; ! Declared at the outermost block level; I1 := 2; ! Sets a non-zero value in I1; I2 := 3; ! Sets a non-zero value in I2; begin comment Start a sub-block which can only be entered after I1 and I2 have had their values set; integer array A1(I1:I2); ! Declare with I1 and I2 as bounds; A1(2) := 6; end--of--sub-block; comment Array no longer accessible; endExample 10.3: Dynamic array bounds in a procedure.
begin procedure Bounder(Lowest); integer Lowest; begin comment Parameters may be used as bounds inside a procedure body; character array C1(Lowest:4*Lowest); ! Use an expression containing Lowest as upper bound; C1(Lowest*2+1) := '&'; ! Use an expression in the subscript too; OutChar(C1(5)); ! Null unless Lowest is 2; OutImage end--of--procedure--Bounder; Bounder(2); ! Should print &; end**of**programExample 10.4: Dynamic array bounds in a class.
begin integer Lower; class Cl1(Upper); integer Upper; begin Boolean array BoolArr(Lower:Upper); ! Use a mixture of enclosing block's declarations and parameters to set bounds; BoolArr(Lower+3) := True end--of--class--Cl1; ref(Cl1) Cl1Ref; Lower := 4; ! Sets lower bound before object generation; Cl1Ref :- new Cl1(7); ! Passes upper bound as a parameter; if Cl1Ref.BoolArr(5) then OutText("True") else OutText("False"); OutImage end**of**program
This section shows how the combination of class objects and arrays can help the design of the Book level of our program. What we are going to try to do is to design a class Book, with the necessary data structures and procedures for manipulating them. Consider example 10.5.
The Book is represented as a class. It is assumed to have a title page, a contents, a preface, a sequence of chapters and an index. The different data structures of each of these are represented in turn by classes. Since each may only exist as a part of a book, they are declared inside the body of Book (or "local to" Book).
A single ref variable is declared for each of these classes, except for Chapter. The number of chapters in a book can vary considerably and so an array of ref(Chapter) variables is declared. Its lower bound is 1 and its upper bound is a parameter of Book. The actual number of chapters can be specified when the Book object is generated in the main program block. We use
new Book(InInt)so that the number is read in and passed, in one statement.
Example 10.5: Class Book and the accompanying program block.
begin class Book(Num_of_Chaps); integer Num_Of_Chaps; begin text Title, Author; ref(chapter) array Chaps(1:Num_Of_Chaps); ref(Contents) Cont; ref(Preface) Pref; ref(Index) Ind; integer Count; procedure Title_Page; begin Eject(10); OutText(Title); OutImage; OutText(" by"); OutImage; OutText(Author); OutImage; Eject(0); end++of++Title++Page; Pref :- new Preface; for Count := 1 step 1 until Num_Of_Chaps do Chaps(Count) :- new Chapter(Count); Cont :- new Contents(Pref,Chaps); Ind :- new Index(Chaps); Cont.PrintContents; Pref.PrintPreface; for Count := 1 step 1 until Num_Of_Chaps do Chaps(Count).PrintChap; Ind.PrintIndex end--of--Book; class Chapter(Numbr); integer Numbr; begin procedure PrintChap; begin comment Print out this chapter in appropriate format; ... ... end++of++PrintChap; ... ... end--of-Chapter; class Contents(Pref,Chaps); ref(Preface) Pref; ref(Chapter) array Chaps; begin procedure PrintContents; begin comment Print a contents page for Pref and Chaps; ... ... end++of++PrintContents; ... ... end--of--Contents; class Preface; begin procedure PrintPreface; begin comment Print a preface in appropriate format; ... ... end++of++PrintPreface; ... ... end--of--Preface; class Index(Chaps,Num_Chaps); ref(Chapter) array Chaps; integer Num_Chaps; begin procedure PrintIndex; begin comment Print an index for Chaps; ... ... end++of++PrintIndex; ... ... end--of--Index; comment This is the main program; OutText("How many chapters?"); OutImage; new Book(InInt) end**of**main**program
This leads to the following description of top down, object oriented design.
The visible properties of each component are defined by the operation of the object of which it forms part. Properties which are not externally visible can be left undefined until the component itself is implemented in detail.Even simpler is,
Don't clutter up your program with unnecessary detail until you need it.
10.2 Extend 10.1 to sort the names into alphabetical order as it first reads them and to print the records in this order.
10.3 Further extend your program to calculate each student's average mark and to print separate lists ordered alphabetically, by order of marks in each subject and by overall average mark.
Exercise 10.2 shows that it is often useful to be able to rearrange the order in which the items of a list are held. Exercise 10.3 takes this further and shows that the same items may need to be thought as being on several different lists, held in different orders. The array can only do this by clumsy rearrangement of its elements or by copying the same elements into a number of different arrays.
Even an apparently trivial operation, like adding a new item to a list which is already in order is not easy. Consider example 10.6.
Once the correct position in the list has been found it is necessary to move all the labels after this up by one in the array, unless the new label happens to belong at the end. This is potentially very time consuming. Another problem is that the array may not be large enough. If we want to allow for a list of unknown length, with any number of new labels, arrays are not likely to be useful.
Fortunately, SIMULA allows us to create much more flexible lists, tailored to the needs of a program. These use the ability of class objects to contain pointers or links, in the form of reference variables, to other objects. Lists can be formed in this way, known as "linked lists".
New objects are added to the end of this list. Pointers to the current first and last members of the list are held in the ref(Linked_Lab) variables List_Head and List_End.
The concept of adding to a list by manipulating pointers is very powerful. It is worth spending some time getting 10.7 clear in your mind.
Example 10.6: Adding an item to an ordered list in an array.
begin ref(InFile) MyInput; class Lab; begin procedure ReadLabel; begin integer I; inspect MyInput do begin SeqNo := InInt; InImage; for I := 1 step 1 until 5 do begin Address(I) :- Copy(Image.Strip); InImage end end end--of--ReadLabel; text array Address(1:6); integer SeqNo; end++of++Lab; integer Count1, Count2, I; ref(InFile) Source; ref(Lab) array Labs(1:100); ref(Lab) NewLab; Source :- new InFile("Labels"); inspect Source do begin Open(Blanks(20)); MyInput :- Source; while not EndFile do begin comment Assume labels in Source already in order of SeqNo; Count1 := Count1 + 1; Labs(Count1) :- new Lab; ! Read in successive labels; Labs(Count1).ReadLabel end..of..reading ..source..into..Labs; Close end%%of%%inspecting%%Source; MyInput :- SysIn; NewLab :- new Lab; NewLab.ReadLabel; Count2 := 1; while Count2<=Count1 do begin if Labs(Count2).SeqNo>NewLab.SeqNo then begin comment New label goes before Labs(Count2) so make room; for I := Count1 step -1 until Count2 do Labs(I+1) :- Labs(I); Labs(Count2) :- NewLab; Count2 := Count1 + 2; ! Force end of while loop; end--of--adding--new--label; Count2 := Count2 + 1; end..of..while..loop; if Count2=Count1+1 then Labs(Count2) :- NewLab; ! Goes at the end; comment Check the sequence; for I := 1 step 1 until Count1 + 1 do OutInt(Labs(I).SeqNo,3) end**of**programExample 10.7: Building the linked list in Diagram 10.1.
begin class Linked_Lab; begin ref(Linked_Lab) Next; integer SeqNo; comment Simplified version of Lab; SeqNo := Inint; end--of--Linked--Lab; ref(Linked_Lab) List_Head, List_End, Temp; ! a) List_Head and List_End are both None; ! b); List_Head :- List_End :- new Linked_Lab; ! c); List_End.Next :- new Linked_Lab; List_End :- List_End.Next; comment Now print the SeqNo of each item in the list; Temp :- List_Head; while Temp=/=None do begin OutInt(Temp.SeqNo,3); Temp :- Temp.Next end..of..printing..list end**of**program
There is also a positive equivalent, ==, meaning "does reference", which tests for reference equality. Thus
if P1==P2 then OutInt(3,3)would print 3 if the class object reference variables P1 and P2 pointed to the same object.
Reference variables of any type can be pointed at None. It is the initial value of reference variables, regardless of their type.
10.5 Write a program to add items to the start of a linked list, rather than the end, and which builds a list of four such items.
If we think further, a linked list is a data structure with attributes unique to itself. Each list has a head and a tail (although it is possible to use just a head). Furthermore, our proposed procedures for adding items at the beginning and end of a list operate only on attributes of a list object. It is sensible to define a class embodying these attributes for use in processing linked lists. Example 10.8 shows how this might be implemented.
10.8 also shows how a new item can be added to the middle of a list without needing to update all the items which follow. The mechanism used is illustrated in diagram 10.2. Only two reference assignments are needed to achieve it.
Example 10.8: Class Label_List.
begin class Linked_Label; begin ref(Linked_Label) Next; integer SeqNo; SeqNo := InInt end--of--Linked--Label; class Label_List; begin ref(Linked_Label) Head, Tail; procedure AddtoEnd(Lab);ref(Linked_Label) Lab; begin if Head==None then begin comment Special case when list is empty; Head :- Tail :- Lab end else begin comment Normal case; Tail.Next :- Lab; Tail :- Lab end end++of++AddtoEnd; procedure AddtoFront(Lab);ref(Linked_Label) Lab; begin if Head==None then begin comment Special case when list is empty; Head :- Tail :- Lab end else begin comment Normal case; Lab.Next :- Head; Head :- Lab end end++of++AddtoFront; end--of--Label--List; ref(Label_List) Labs; ref(Linked_Label) New_Lab, Temp; integer Count; comment Create an initial list of 4 items; Labs :- new Label_List; for Count := 1 step 1 until 4 do Labs.AddtoEnd(new Linked_Label); comment Add a new label to the front; Labs.AddtoFront(New Linked_Label); comment Add a new label between existing nos. 2 and 3; New_Lab :- new Linked_Label; Temp :- Labs.Head; Temp :- Temp.Next; comment Temp now points to item 2 on list; New_Lab.Next :- Temp.Next; ! Step b) in diagram 10.2; Temp.Next :- New_Lab; ! Step c) in diagram 10.2; Temp :- Labs.Head; while Temp=/=None do begin OutInt(Temp.SeqNo,3); Temp :- Temp.Next end; OutImage end**of**program
10.7 Add local procedures to class Linked_Lab, one of which inserts a label object after a given member of the list and one of which removes a label from the list.
10.8 Rewrite your answers to 10.2 and 10.3 using linked lists instead of arrays. Remember that an object can have as many ref attributes as you like and so can be on as many linked lists simultaneously as you wish.
Linked lists are much easier to rearrange and to extend. We do not need to fix an upper limit to the number of elements in them. The same object can exist on several such lists at once. On the other hand, if we wish to find item number six, say, on a linked list, we must chain through, counting as we go. In an array accessing item number six is trivial.
There are strengths and weaknesses in both these list structures. It is a question of picking the more appropriate one for your purposes. As we shall see later, linked lists can be even more flexible than those we have used so far and some of their limitations can be reduced. For certain very common purposes, however, arrays remain the best choice.
The use of dynamic bounds to allow variable sized arrays has been shown
We have considered briefly the use of simple linked lists and noted their advantages over arrays.
Finally we have compared the merits of arrays and linked lists and concluded that each structure is better suited to certain applications.