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**programThe 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**programThe 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**programThe 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.