The importance of lists was demonstrated in chapter 10. It is widely accepted today that list processing is a very powerful part of programming. Several languages have been developed which are based on this idea.
Like many languages, SIMULA includes facilities which make handling lists of objects possible. The key ones are reference variables, which allow pointers or links, and subclasses, which allow objects of different types to be linked together, so long as they have a common parent. The ability to distinguish to which subclass each item on a list belongs enhances the second of these. The use of is, in and inspect allows lists of objects to be processed safely.
Consider figure 17.1. It shows three objects, which might correspond to the class declarations under them. What would happen if the same pointer could be used to access the attributes of all three? With no way of checking which was which type, it would clearly result in chaos.
Diagram 17.1: Potential access conflicts in objects.
A B C
class A; class B; class C;
begin begin begin
integer Var1; real Var1; ref(B) Var1;
real Var2; ref(A) Var2; character Var2;
Boolean Var3; text Var3; integer Var3;
end++of++A; end++of++B; end++of++C;
As an example, the program might wish to assign to the integer location in
object A. If it does not know whether the object is an A, B or C object its
task is hopeless. It either assigns to that location whatever the object or
does nothing. If it assigns to a B object by mistake, the location is
actually used to hold a real. If it assigns to a C object, the location
actually holds a reference variable. Clearly the only safe thing is to do
nothing and so such a language is much weaker than SIMULA. To be fair, some
languages allow a limited subtyping capability. This is usually done through
"variant records". This means declaring all the possible subclasses as
alternatives inside the parent class declaration. This can be more secure,
but is also much more restricting. It does not allow a parent class to be
separately compiled and then extended at will in the main program, for
instance. All possible variations are fixed in the original declaration.
This type of language usually has no equivalent of inspect or is. It may allow you to say what subtype you wish to use rather like half an inspect or a limited qua or it may check the actual type and behave accordingly, but not as flexibily as SIMULA.
SIMULA is almost alone in allowing secure and flexible access to subtypes and in allowing the range of such subtypes to be easily extended. It is uniquely suited to certain kinds of list processing.
One way of coping with the problem is to use a class with pointers for each type of goods to be considered. Each record can be read from a DirectFile and a class object generated to correspond to it. Instead of copying the contents of the record into the object, the index number is entered. The object is then entered on the lists corresponding to its previous purchases.
A skeleton for this program is shown in example 17.1. It assumes that the Image read from the DirectFile has fixed length fields, corresponding to the details of that customer. These include the categories of goods available, each a one character field set to 'N' for no purchase and to 'P' for a past purchase. Where such a field is a 'P' that record's indexing object is added to the corresponding list in the program.
This simple example is intended to refresh your memory and get us back to practical problems. It demonstrates simple one way lists and the use of multiple lists or cross referencing as it is more widely known.
Example 17.1: Customer records on multiple, one way lists.
begin
class Customer(Index); integer Index;
begin
ref(Customer) Gears, Bearings, Bolts;
text Ident;
end--of--Customer;
ref(Customer) Gears, Bearings, Bolts, NewRecord;
ref(DirectFIle) PastRecords;
text Record;
PastRecords :- new DirectFile("Purchases");
PastRecords.Open(Blanks(132));
inspect PastRecords do
while not EndFile do
begin
Record :- InText(132);
NewRecord :- new Customer(Location);
if Record.GetChar='P' then
begin ! Previous purchaser of Gears;
NewRecord.Gears :- Gears; ! Add to Gears list;
Gears :- NewRecord
end;
if Record.GetChar='P' then
begin ! Previous purchaser of bearings;
NewRecord.Bearings :- Bearings; ! Add to Bearings list;
Bearings :- NewRecord
end;
if Record.GetChar='P' then
begin ! Previous purchaser of bolts;
NewRecord.Bolts :- Bolts; ! Add to Bolts list;
Bolts :- NewRecord
end;
NewRecord.Ident :- Copy(Record.Sub(4,129))
end..of..while..loop..and..inspect
end**of**program
A practical application where this might be a problem is in searching lists held in alphabetical order. If the name we want begins with the letter Z, we still have to read through all the other letters to find it. A human searching in a telephone book would probably save a lot of time by starting at the last page and searching backwards.
Another application, which returns to our text editing project, is to hold the current document as a list of line objects, with a text attribute to hold the contents. It would clearly be highly desirable to be able to move backwards as well as forwards when editing. To do this we need a two way list.
Example 17.2 shows a simple version of such an editor. It reads in a file's contents as a linked list. Each object represents a line in the file and has two pointers to other line objects. These are called Previous and Next. Previous always points to the line before the current one, Next always points to the line after.
Example 17.2: A line editor using a two way list.
begin
ref(InFile) Input;
ref(OutFile) Output;
text procedure InLine;
begin
InImage;
InLine :- Copy(SysIn.Image.Strip)
end++of++InLine;
procedure OutLine(T); text T;
begin
OutText(T);
OutImage
end++of++OutLine;
class LineRec(Tex); text Tex;
begin
procedure AddTo(List); ref(Link_List) List;
begin
if List.Last=/=None then List.Last.Next :- this LineRec;
this LineRec.Prev :- List.Last;
List.Last :- this LineRec;
if List.First==None then List.First :- this LineRec
end--of--AddTo;
procedure Add_Before(Record); ref(LineRec) Record;
begin
if Record.Prev=/=None then
begin
Record.Prev.Next :- this LineRec;
Prev :- Record.Prev
end..of..if;
Record.Prev :- this LineRec;
Next :- Record
end--of--Add_Before;
ref(LineRec) Next, Prev;
end++of++LineRec;
class Link_List;
begin
ref(LineRec) First, Last;
end++of++Link_List;
ref(LineRec) Current;
ref(Link_List) Lines;
character Command;
integer Reps, Count;
Input :- new InFile("Source");
Output :- new OutFile("Output");
Lines :- new Link_List;
comment First read in the file;
inspect Input do
begin
Open(Blanks(80));
while not EndFile do new LineRec(InText(80)).AddTo(Lines);
Close
end++of++inspect++Input;
comment Now process commands from SysIn;
Current :- Lines.First;
while Command ne 'E' do
begin
if Command ne '!0!' then Reps := InInt;
InImage;
if Command='M' then
begin ! Move forward or backwards;
if Reps>0 then
begin
for Count := 1 step 1 until Reps do
begin
if Current.Next==None then OutLine("***End of file***")
else Current :- Current.Next
end
end else
if Reps<0 then
begin
for Count := 1 step 1 until -Reps do
begin
if Current.Prev==None then OutLine("***Start of file***")
else Current :- Current.Prev
end
end
end else
if Command='I' then
begin ! Insert new lines;
for Count := 1 step 1 until Reps do
new LineRec(InLine).Add_Before(Current)
end else
if Command='D' then
begin ! Delete lines forwards or backwards;
if Reps>0 then
begin
Current :- Current.Prev;
for Count := 1 step 1 until Reps do
if Current.Next==None then OutLine("***End of file***") else
begin
Current.Next :- Current.Next.Next;
Current.Next.Prev :- Current
end
end else
if Reps<0 then
begin
Current :- Current.Next;
for Count := 1 step 1 until -Reps do
if Current.Prev==None then OutLine("***Start of file***") else
begin
Current.Prev :- Current.Prev.Prev;
Current.Prev.Next :- Current
end
end
end==of==D;
OutLine(Current.Tex);
Command := InChar
end++of++command++loop;
Comment Now write out file;
Current :- Lines.First;
inspect Output do
begin
Open(Blanks(80));
while Current=/=None do
begin
OutText(Current.Tex);
OutImage;
Current :- Current.Next
end;
Close
end++of++inspect++Output;
OutLine("Edit finished")
end**of**program
The program will accept four commands, given as single characters followed by
an integer. Several commands may be given on a single line.
The letter 'M' means move forwards or backwards; the integer specifies how many lines to move. Positive integers mean forwards, negative mean backwards.
The letter 'D' means delete the number of lines specified, starting with the current line. A positive number means delete forwards, a negative number means delete backwards.
The letter 'I' means insert the number of lines specified in front of the current line. Only positive numbers are accepted. The lines are read from SysIn until the required number have been given. The next line is again assumed to contain commands.
The letter 'E' means end the editing session, write the lines out to a file and stop the program.
Note the use of pointers. Check that you follow the way the program works.
The idea of a tree structure is to allow very rapid storage and retrieval of data which is held in some order - usually numerical or alphabetical. It may also be used for other special purposes, but we are not concerned with those here. The use of trees is, incidentally, a nice example of recursion.
Diagram 17.2 shows the building up of a tree structured list, used to hold items in numerical order. Study it closely before reading on, as a diagram is probably the easiest way to understand such a structure.
Diagram 17.2: Building a tree sorted list.
27
27
/
/
16
27
/ \
/ \
16 30
27
/ \
/ \
16 30
/
/
29
27
/ \
/ \
16 30
\ /
\ /
22 29
27
/ \
/ \
16 30
\ / \
\ / \
22 29 31
The most obviously striking feature of such a tree is that it is shown growing downwards. This is only a convention, but I have shown it that way to avoid confusion if you see it elsewhere.
More importantly, the tree always branches into two or one new twigs. This type of tree is called a "binary" tree, because it always subdivides into two new paths.
The building of the tree follows a simple pattern. Each new value is attached to an existing value, so that it forms the left branch from that value if it is smaller than it or the right branch if it is greater. Only values with an unfilled left or right branch may be used to attach a new value. These are either at the ends of branches, and have both left and right free, or next to the end, and have only one of left or right free.
The important rules governing this process of construction are the ones which govern which existing value in the tree is chosen tohave the new branch for the new value attached to it. These rules ensure that the final tree is, indeed, held in order and, consequently, allows other, related rules for searching the tree for a value.
The rules for adding a value are as follow:
Follow these rules through using diagram 17.2. Check that they really do describe how the tree was built.
You will have noticed that rule 6 simply tells us to repeat 4 and 5 until we succeed. It might be sensible to use a mechanism which embodies this idea. The while loop is one such mechanism, but recursion provides the most compact solution. The set of rules (or algorithm) given above is a recursive one. The same actions are performed for a succession of sets of data (objects) until some condition is satisfied. A while loop is more suited to performing the same actions on the same object.
Example 17.3 builds the tree shown in diagram 17.2, using a for loop to supply the values. The building rules are encapsulated in the procedure AddOn. This is given two ref(Val) parameters. The first is the branch to be followed, the second the new Val object which is to be found a home. Check this through once more comparing the rules, the procedure and the diagram.
Example 17.3: Building the tree in diagram 17.2.
begin
class Number(Val); integer Val;
begin
procedure AddOn(Link); name Link; ref(Number) Link;
if Link==None then Link :- this Number else
if Val>Link.Val then AddOn(Link.Right) else AddOn(Link.Left);
ref(Number) Left, Right;
end..of..Number;
procedure LookFor(Val,Link); integer Val; ref(Number) Link;
if Link==None then
begin
OutText("Value not in tree ");
OutInt(Val,4);
OutImage
end else
if Val=Link.Val then
begin
OutText("Number found");
OutInt(Val,4);
OutImage
end else
if Val>Link.Val then
begin
OutText("Following right link");
OutImage;
LookFor(Val,Link.Right)
end else
begin
OutText("Following left link");
OutImage;
LookFor(Val,Link.Left)
end..of..Look..For;
ref(Number) Head;
integer Count;
for Count := 27, 16, 30, 29, 22, 31 do new Number(Count).AddOn(Head);
for Count := 27, 22, 33, 31 do LookFor(Count,Head)
end**of**program
The second part of the example searches for three of the values in the tree
and one which is not present. It too uses a recursive procedure and prints out
the route taken at each branch, so that we can follow its working. Run it and
see if it behaves as you expect.
17.4 It is also useful to be able to find a value which follows one already known. Add a recursive procedure to example 17.3, called Next, which returns an integer value when passed an integer parameter. The value returned should be the one in the list which is the nearest one following that given. Note that the value passed need not be in the tree for a result to be found.
A tree is not better when you merely wish to follow a list. Insertion, deletion and location of specified entries are what it is good at.
Example 17.4 shows most of the attributes. We shall look at it first and then consider a full list of the features of SIMSET.
The example is a program for reading and printing examination marks. It reads a name, followed by an integer mark. It then prints a list of names and corresponding marks. Finally it prints a sort of inverted histogram, with ten columns. Each student whose results fall within the appropriate range is printed in that column. A maximum name length is printed, to keep the columns straight.
Example 17.4: The use of SIMSET.
SIMSET
begin
ref(Head) array HistoChart(0:9);
ref(Head) MixedList;
integer Count;
Boolean MoreLeft;
text Student;
ref(Link) NextRec, ThisRec;
ref(Link) array CurrentRec(0:9);
Link class MarkHolder(Student,Mark); integer Mark;text Student;;
MixedList :- new Head;
Student :- InText(32);
while Student.Sub(1,1) ne "*" do
begin
new MarkHolder(Student,InInt).Into(MixedList);
InImage;
Student :- InText(32)
end--of--reading;
for Count := 0 step 1 until 9 do HistoChart(Count) :- new Head;
NextRec :- MixedList.First;
while NextRec=/=None do
begin
ThisRec :- NextRec;
NextRec :- ThisRec.Suc;
inspect ThisRec when MarkHolder do
begin ! Must inspect to allow access to Mark and Student;
OutText(Student);
OutInt(Mark,8);
OutImage;
if Mark=100 then Into(HistoChart(9)) else Into(HistoChart(Mark//10))
end..of..inspect
end--of--sorting;
for Count := 0 step 1 until 9 do
begin
CurrentRec(Count) :- HistoChart(Count).First;
if CurrentRec(Count)=/=None then MoreLeft := True
end;
if MoreLeft then OutText(
" 0-9 10-19 20-29 30-39 40-49 50-59"
" 60-69 70-79 80-89 90-100")
else OutText("Lists empty");
OutImage;
while MoreLeft do
begin
MoreLeft := False;
for Count := 0 step 1 until 9 do
begin
inspect CurrentRec(Count) when MarkHolder do
begin
if Mark=100 then
begin
OutText("*");
OutText(Student.Sub(1,7))
end else OutText(Student.Sub(1,8));
if Suc=/=None then MoreLeft := True
end..of..clause
otherwise OutText(" ");
if CurrentRec(Count)=/=None
then CurrentRec(Count) :- CurrentRec(Count).Suc
end--of--for;
OutImage
end++of++while
end**of**program
The record for each student is kept in an object which is a subclass of Link.
Link is defined in SIMSET with a forward pointer, Suc, and a backward pointer,
Pred, both of which are returned by procedure calls rather than being directly
accessible.
The complete list is held in the Set defined by the Head object, MixedList. Head has a pointer to the start of the list, First, and a pointer to the end, Last. Again, these are only accessible as results from ref (Link) procedures.
Once the list is complete, which is indicated by an asterisk for the next name, the list headed by MixedList is read through and each record is printed out, before being moved to the list headed by the appropriate entry in the ref (Head) array HistoChart. This has ten elements, which correspond to results in the range 0 - 9, 10 - 19 etc. up to 90 - 100.
The "histogram" is then printed. Students with a perfect mark of 100 have an asterisk printed by their names.
The program could, of course, have been more concise. It is intended as a demonstration of SIMSET, not of how to perform a particular task. On the other hand, this program is capable of extension to perform more complex functions, where a no nonsense program might not be.
As with all prefixed blocks, subclasses of the classes declared within SIMSET may only be declared within the actual block which is prefixed, not within blocks local to this. References may be made to all such classes and subclasses within local blocks, however.
There are three classes declared within SIMSET, one of which is a prefix to the other two. Let us look at them in turn.
Linkage contains the basic linking attributes for forming lists. Here is a brief description.
Notice how all the attributes of Linkage available to us are procedures, not simply ref (Linkage) variables. This prevents us assigning new values to them, except by the use of procedures local to Link and Head. This restriction stops us "tinkering" with the objects and makes us think in object oriented terms. This is a way of producing safe packages for use by inexperienced programmers. We shall look at how to write such packages in chapter eighteen.
These include the only procedures that can be used to add items to a Set. Removal can only be achieved using these or one of the attributes of Head.
Figure 17.3: SIMSET lists. H1 :- new Head
--------------------
--->I H1 I<---
I I------------------I I
I I SUC I----
I I------------------I
I I FIRST I-------> None
I I------------------I
----I PRED I
I------------------I
I LAST I-------> None
I------------------I
I EMPTY = TRUE I
I------------------I
I CARDINAL = 0 I
--------------------
L1 :- new Link; L1.Into(H1)
--------------------
--------->I H1 I<------------
I I------------------I I
I I SUC I--------- I
I I------------------I I I
I I FIRST I------- I I
I I------------------I I I I
I ----I PRED I I I I
I I I------------------I I I I
I I --I LAST I I I I
I I I I------------------I I I I
I I I I EMPTY = FALSE I I I I
I I I I------------------I I I I
I I I I CARDINAL = 1 I I I I
I I I -------------------- I I I
I I I I I I
I I I --------------------------- I I
I I I I --------------------------- I
I I I I I I
I V V V V I
----------------------- I
I SUC I L1 I PRED I I
----------------------- I
I I
---------------------------
L2 :- new Link; L2.Into(H1)
--------------------
--------->I H1 I<------------
I I------------------I I
I I SUC I--------- I
I I------------------I I I
I I FIRST I------- I I
I I------------------I I I I
I ----I PRED I I I I
I I I------------------I I I I
I I --I LAST I I I I
I I I I------------------I I I I
I I I I EMPTY = FALSE I I I I
I I I I------------------I I I I
I I I I CARDINAL = 2 I I I I
I I I -------------------- I I I
I I I I I I
I I I ------------------- I I I
I V V V I V V I
----------------------- ----------------------
I SUC I L2 I PRED I I SUC I L1 I PRED I
----------------------- ----------------------
I ^
----------------------
L3 :- new Link; L3.Precede(L2)
--------------------
--------->I H1 I<---------------------------------------
I I------------------I I
I I SUC I------------------------------------ I
I I------------------I I I
I I FIRST I---------------------------------- I I
I I------------------I I I I
I ----I PRED I I I I
I I I------------------I I I I
I I --I LAST I I I I
I I I I------------------I I I I
I I I I EMPTY = FALSE I I I I
I I I I------------------I I I I
I I I I CARDINAL = 3 I I I I
I I I -------------------- I I I
I I I I I I
I I I ------------------- -------------------- I I I
I V V V I V I V V I
----------------------- ---------------------- ----------------------
I SUC I L2 I PRED I I SUC I L3 I PRED I I SUC I L1 I PRED I
----------------------- ---------------------- ----------------------
I ^ I ^
---------------------- ----------------------
L1.Out
--------------------
--------->I H1 I<------------
I I------------------I I
I I SUC I--------- I
I I------------------I I I
I I FIRST I------- I I
I I------------------I I I I
I ----I PRED I I I I
I I I------------------I I I I
I I --I LAST I I I I
I I I I------------------I I I I
I I I I EMPTY = FALSE I I I I
I I I I------------------I I I I
I I I I CARDINAL = 2 I I I I
I I I -------------------- I I I
I I I I I I
I I I ------------------- I I I
I V V V I V V I
----------------------- ----------------------
I SUC I L2 I PRED I I SUC I L3 I PRED I
----------------------- ----------------------
I ^
----------------------
L1.Follow(L3)
--------------------
--------->I H1 I<---------------------------------------
I I------------------I I
I I SUC I------------------------------------ I
I I------------------I I I
I I FIRST I---------------------------------- I I
I I------------------I I I I
I ----I PRED I I I I
I I I------------------I I I I
I I --I LAST I I I I
I I I I------------------I I I I
I I I I EMPTY = FALSE I I I I
I I I I------------------I I I I
I I I I CARDINAL = 3 I I I I
I I I -------------------- I I I
I I I I I I
I I I ------------------- -------------------- I I I
I V V V I V I V V I
----------------------- ---------------------- ----------------------
I SUC I L2 I PRED I I SUC I L1 I PRED I I SUC I L3 I PRED I
----------------------- ---------------------- ----------------------
I ^ I ^
---------------------- ----------------------
All of the features provided in SIMSET could be written in SIMULA. The
reasons for providing them as a predefined package are first to encourage safe
list handling packages and second to allow them to be provided in an efficient
form for even inexperienced programmers to use. The SIMULA Standard gives the
SIMULA code for all of SIMSET, if you are interested.