Chapter 17 - Add To The List

More Complex List Structures - SimSet

Back to real problems

We have spent several chapters learning new features of SIMULA. Let us spend rather more time on their application in the next few pages.

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.

Safe access

The concept of security in accessing objects is more important than may sometimes be realised. Some languages do not allow lists of objects of different types at all. This is safe, since a location in an object cannot be accessed in the mistaken belief that it is an attribute of an object of another type. On the other hand, some languages allow pointers to reference any object, regardless of type. This allows lists to be used more widely, but is totally unsafe.

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.

A first practical example

Consider a firm wishing to keep records of all its customers. From time to time it sends out mail shots on various types of goods that it sells. It only wishes to send such information to customers who have bought goods of that type before. It will want to build up lists of customers on this basis. Since some customers will have bought several types, some records may be on several lists.

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

Exercise

17.1 Complete the program in example 17.1 to print out lists of customers in each category as labels for mailing. Create a file of records and test it out. Refine it to prompt for the category wanted for this mailing and to produce only that list.

Backwards and forwards

One limitation of our lists so far has been the difficulty of moving backwards along them. How, for instance, could we find the preceding record once we had printed an object on our list of Gear customers in example 17.1? We would have to go back to the start and read through until we found the object pointing to the one currently being accessed.

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.

Exercise

17.2 Add a command to move a line to a new location forwards or backwards. The integer should specify how far.

Lists held as "trees"

There is one more type of list that is very useful and deserves to be covered in some detail, before we look at SIMULA's built in list handling package. This last type is very different from the one and two way lists that we have used so far. It usually known as a "tree structured" list.

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.

  1. Tree empty. Insert 27.
                               27
    
  2. Insert 16.
                              27
                             /
                            /
                          16
    
  3. Insert 30.
                               27
                             /    \
                           /        \
                         16           30
    
  4. Insert 29.
                               27
                             /    \
                           /        \
                         16           30
                                     /
                                   /
                                 29
    
  5. Insert 22.
                               27
                             /    \
                           /        \
                         16           30
                           \         /
                             \     /
                              22 29
    
  6. Insert 31.
                               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:

  1. Start at the head of the list, i.e. with the first value put into the tree.
  2. If the head is empty, use that to hold the new value. This is now the first value to be put into the tree.
  3. If the head contains a value, compare it to the new value. If the new value is less than the head's, follow the left branch; if it is greater follow the right. (the question of how to behave if the two values are equal can only be answered in the light of the use to which the list is to be put.)
  4. If the branch followed is empty, use it to hold the value.
  5. If the branch is not empty, compare its value to the new value. If the new value is less, follow the left branch; if it is greater, follow the right.
  6. Repeat d and e until a home is found for the value.

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.

Exercises

17.3 Write down the algorithm used by the search procedure in Example 17.3, as a set of rules.

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.

The advantages of trees

In most cases the use of tree structured lists for the purposes shown is quicker than the use of simple linked lists. The number of values checked in a search is fewer, since whole branches are eliminated at once. You may wish to try reworking diagram 17.2 and example 17.3 with a simple list structure and see, by hand or by using the measure of time taken for the program to run, whether this holds true. The bigger the list, the greater the benefit.

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.

System class SIMSET

The remainder of this chapter is concerned with one of SIMULA's two ready made packages. It is held in a class called SIMSET and contains building blocks for two way linked list handling. It is different from our earlier two way lists in that it holds its lists as circles of objects rather than straight lines. In SIMULA, such a list is known as a Set.

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.

A formal description of SIMSET

SIMSET is a special separately compiled class available as part of every SIMULA system. It does not need to be declared before use. It can be used to prefix a block anywhere in a program, including, as example 17.4 showed, the program block itself.

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.

Class Linkage

Linkage is the prefix of the other two classes in SIMSET. There are Link, representing Set members, and Head, representing the start and end of the Set. Prefixing by Linkage allows a reference to be made to either, where appropriate.

Linkage contains the basic linking attributes for forming lists. Here is a brief description.

ref(Link) procedure Prev
returns a pointer to the item before this one in the list, if it is a Link object. If the previous item is the Head object it returns None.

ref(Link) procedure Suc
returns a pointer to the item behind this one, if it is an object of class Link or a subclass of Link. If the next item is the Head it returns None.

ref(Linkage) procedure Pred
returns a pointer to the item before this one, whether it is a Link or Link subclass object or a Head or Head subclass object.

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.

Linkage class Link

The items in the list of a Set are represented by objects of class Link, or more usefully, of subclasses of Link. It adds four procedures to those inherited from Linkage.

procedure Out
removes this item from the list. Its predecessor and successor will be linked, to heal the breach. If it is not currently in a Set this procedure has no effect.

procedure Into
has one ref (Head) parameter. It removes this object from any Set it is in at present and makes it the last item in the Set whose head is given as parameter.

procedure Follow
has one ref (Linkage) parameter. It places this object after the one referred to by the parameter in the appropriate Set, after removing this object from any Set that it is currently in. If the parameter refers to a Head object the effect is to put this object into first place in the set. The effect is the same as Out if the parameter is None or does not belong to a Set and is not a reference to a Head object.

procedure Precede
is exactly like Follow, except that it will attempt to place this object before the one referred to by the parameter. If the parameter refers to a Head object, the effect is the same as Into. (Think about the last statement, bearing in mind that this is a circular list structure.)

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.

Linkage class Head

Head represents the whole Set. It will give pointers to both ends of the list and other information concerning it.

ref (Link) procedure First
returns a pointer to the first item in this list. If the list is empty it returns None. It will always give the same result as a call of Suc for this Head object.

ref (Link) procedure Last
returns a pointer to the last item in this list. If the list is empty it returns None. It will always give the same result as a call of Pred for this Head object.

procedure Clear
removes all the Link items from this list, by calling Out for them.

Boolean procedure Empty
returns True if this list is empty, otherwise it returns False.

integer procedure Cardinal
returns the number of Link items currently in this list.

What a SIMSET list looks like

Figure 17.3 shows two SIMSET lists, starting with them empty and applying the various procedures mentioned in turn.

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.

Summary

We have seen further uses of list structures, including new forms of list. We have used multiple lists, tree structures and two way lists in various examples. We have seen the ready defined list handling facilities available in the system class SIMSET and learned of the features which it contains.