Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/LISTS30.ZIP/LISTS30.DOC

Text File | 1988-08-29 | 21.2 KB | 641 lines

  Documentation for LISTS.PAS (ver 3.0)
  Written by Mark Addleman [72777, 740] for Software Applications of Wichita

  *** NOTE: This program is distributed under the ShareWare concept.  As
  such, you are granted a limited evaluation period after which continued use
  requires registration in accordance with the Agreement contained in
  License.TXT.  A licensing fee of $15 and a signed Agreement should be sent
  to the address below:

  Please send your contributions to
                        Software Applications of Wichita
                              2204 Winstead Circle
                            Wichita, KS  67226-1122

  This document was created using Sprint:  The Professional Word Processor
  and whatever printer you are using.
  Updates

  Any updates which are made available will be placed on the Compuserve
  Borland Forum.


  Purpose

  LISTS is designed to relieve you of the messy details of creating and
  maintaining linked lists.  Features include the ability to add, insert, and
  delete items from lists.  Moving (forward and backward) through lists is
  implemented, along with the capability to rearrange the order of the list.



  Changes from the previous version

  LISTS version 3 abounds with changes from the version 2.  Most notable
  changes include a different analogy use in LISTS.  Now, a list is made up
  of ENTRIES.  Each ENTRY contains an ITEM.  It is the ITEM that the
  programmer is primarily interested in.  Another major change is that very
  few of the routines explicitly require the list name as an argument.  For
  example, to refer to the next-to-the-last entry in a list:
       Entry:=PrevEntry(LastEntry(List));
  The change is that PrevEntry doesn't require List as an argument.  The
  advantage is that less code is required, greater memory efficiency, and
  speed since the program no longer must push the name of the list onto the
  stack.

  WARNING:  LISTS uses a local variable to make this possible.  Therefore,
  any statement using LISTS routines must somewhere contain the name of the
  list.  For example, the following code is ***** no longer valid:
       Var
          E       :   EntryPtr;
          List    :   ListRec;

       Begin
          Entry:=FirstEntry(List);
          MoveToEntry(E);
       End.

  The compiler will not generate an error because technically it is correct.
  The problem is that LISTS will be unable to communicate with the variable
  List if it had to.  The Entry function is provided to perform the same
  function as the program above, but in a legal manner:
       Function Entry(List:ListRec; Location:EntryPtr):EntryPtr;

  So the above program would look like this:
       Var
          E       :   EntryPtr;
          List    :   ListRec;

       Begin
          E:=FirstEntry(List);
          MoveToEntry(Entry(List,E));
       End.


  Another enhancement to LISTS is the ability to access a list completely at
  random using the EntryNumAbs and EntryNumRel routines.  These routines
  access the absolute entry on the list (1st, 2nd, 3rd, etc) and relative
  entry on the list (back one, back two, forward three, forward four, etc)
  respectively.  Also, GetItem and PutItem are available for accessing the
  item in the entry or changing it.
  ListRec (type declaration)
  ---------------------------------------------------------------------------
  ListRec is the backbone of the entire LISTS package.  This is the
  programmer's connection with the linked list.  The following is its type
  definition in the LISTS.TPU:
       ListRec   =    Record
                           OK   :    Boolean;
                           {Set to FALSE if an error occurs}

                           F_Entry   :    EntryPtr;
                           {Points to the first entry in the list}

                           L_Entry   :    EntryPtr;
                           {Points to the last entry in the list}

                           C_Entry   :    EntryPtr;
                           {Points to the entry currently being referenced}
                      End;

  EntryPtr is a pointer to the record EntryRec which contains the information
  concerning an entry on the list.
       EntryRec  =    Record
                           P_Entry   :    EntryPtr;
                           {Points to the previous entry}

                           N_Entry   :    EntryPtr;
                           {Points to the next entry}

                           Size      :    Word;
                           {Size in bytes of the item in this entry}

                           Item      :    Byte
                           {The item in this entry}
                      End;

  Item is only 1 byte in length.  The reason that Item is only a byte is that
  Item actually becomes part of the Entry data structure.  Whenever an item
  is added to the list, the size is taken as an argument and LISTS allocates
  enough memory for the EntryRec plus the size of the item.  The Item is then
  copied in memory to the end of the entry using Turbo's Move procedure.  If
  this isn't clear, refer to the GetItem and PutItem procedures in the source
  code.



  InitList(Var List:ListRec)
  ---------------------------------------------------------------------------
  InitList must be called for each list before using.  InitList sets all
  pointers to NIL and prepares the list for processing.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;

       Begin
            InitList(MyList);
       End.



  AddEntry(Var List:ListRec; Var Item; Size:Word);
  ---------------------------------------------------------------------------
  AddEntry is used for tacking entries onto the end of List.  AddEntry also
  takes an Item and its Size (using the SizeOf procedure usually) as
  arguments and places them in the entry.

  AddEntry places the new entry at the end of List.
  AddEntry does not move the current entry pointer.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
       End.

  This program creates the following list:
       1    2    3    4    5    6    7    8    9    10
       ^
       Current entry



  InsertEntry(Location:EntryPtr; Var Item; Size:Word)
  ---------------------------------------------------------------------------
  InsertEntry is another procedure for placing an entry in a list.  Unlike
  AddEntry, however, InsertEntry places the entry immediately before the
  entry specified in Location.

  InsertEntry does not move the current entry pointer.

  For example:
       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1e To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(LastEntry(MyList), I, SizeOf(I));
       End.

  This program would create the following list:
       1    2    3    4    5    6    7    8    9    76   10
       ^
       Current entry

  NOTE: InsertEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the InsertEntry expression the name of the list is
  referenced.



  DeleteEntry(Location:EntryPtr)
  ---------------------------------------------------------------------------
  DeleteEntry deletes the entry in a list at Location.  DeleteEntry moves the current entry pointer in only one circumstance:  when
  the entry to be deleted is the entry currently being referenced.  In this
  case, the current entry is moved to the next entry.  However, if the
  current entry is the last entry and it is to be deleted, the current entry
  will point to the new last entry.

  NOTE: DeleteEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the InsertEntry expression the name of the list is
  referenced.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            DeleteEntry(LastEntry(MyList));
       End.

  This program produces the following list:
       1    2    3    4    5    6    7    8    9
       ^
       Current entry

  NOTE: DeleteEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the DeleteEntry expression the name of the list is
  referenced.




  DeleteList(Var List:ListRec)
  ---------------------------------------------------------------------------
  DeleteList removes the entire List from memory and initializes List for
  use.



  CurrentEntry(List:ListRec):Pointer
  ---------------------------------------------------------------------------
  CurrentEntry returns the a pointer to the entry currently being referenced
  in List.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(CurrentEntry(MyList), I, SizeOf(I));
       End.

  This program would produce the following list:       76   1    2    3    4    5    6    7    8    9    10
            ^
            Current entry



  FirstEntry(Var List:ListRec):Pointer;
  ---------------------------------------------------------------------------
  FirstEntry returns the location of the first entry in List.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(FirstEntry(MyList), I, SizeOf(I));
       End.

  This program would produce the following list:
       76   1    2    3    4    5    6    7    8    9    10
            ^
            Current entry



  LastEntry(Var List:ListRec)
  ---------------------------------------------------------------------------
  LastEntry returns the location of the last entry in List.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(LastEntry(MyList), I, SizeOf(I));
       End.

  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    76   10
       ^
       Current entry



  NextEntry(Location:EntryPtr):EntryPtr
  ---------------------------------------------------------------------------
  NextEntry returns the location of the entry immediately after Location.
  Normally location is either CurrentEntry or FirstEntry.  If LastEntry is
  used as an argument, a NIL is returned.

       Program DemoList;
       Uses Lists;       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(NextEntry(FirstEntry(MyList)), I, SizeOf(I));
       End.

  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    76   10
       ^
       Current entry

  NOTE: NextEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the NextEntry expression the name of the list is
  referenced.



  PrevEntry(Location:EntryPtr):EntryPtr
  ---------------------------------------------------------------------------
  PrevEntry returns the entry immediately preceding Location.  Normally,
  PrevEntry takes CurrentEntry or LastEntry as arguments.  If FirstEntry is
  used, a NIL pointer is returned.
       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            InsertEntry(PrevEntry(LastEntry(MyList)), I, SizeOf(I));
       End.

  This program would procedure the following list:
       1    2    3    4    5    6    7    8    76   9    10
       ^
       Current entry

  NOTE: NextEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the NextEntry expression the name of the list is
  referenced.



  MoveToEntry(Location:EntryPtr)
  ---------------------------------------------------------------------------
  MoveToEntry moves the current entry in a list to Location.

  MoveToEntry sets OK to FALSE if an attempt is made to move before the
  FirstEntry or after the LastEntry.
       Program DemoList;
       Uses Lists;

       Var            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            MoveToEntry(PrevEntry(LastEntry(MyList)));
       End.

  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    10
                                               ^
                                               Current entry

  NOTE: MoveToEntry does not take the name of the list as an argument (MyList
  in the above example).  It is the programmer's responsibility to ensure
  that somewhere in the MoveToEntry expression the name of the list is
  referenced.



  EntryNumAbs(Var List:ListRec; N:LongInt)
  ---------------------------------------------------------------------------
  EntryNumAbs returns the Nth entry in List.

  If N is zero or less, the current entry is returned.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            MoveToEntry(EntryNumAbs(MyList, 3)));
       End.

  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    10
                 ^
                 Current entry



  EntryNumRel(Location:EntryPtr; N:LongInt):EntryPtr;
  ---------------------------------------------------------------------------
  EntryNumRel returns the entry N positions relative to Location.  If N is
  negative, EntryNumRel returns the Nth entry preceding Location.  If N is
  positive, EntryNumRel returns the Nth entry after Location.


       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));            MoveToEntry(EntryNumRel(NextEntry(FirstEntry(MyList), 2)));
       End.

  This program produces the following list:
       1    2    3    4    5    6    7    8    9    10
                      ^
                      Current entry



  Item(Location:EntryPtr):Pointer
  ---------------------------------------------------------------------------
  Item returns a pointer to the Item in the Entry at Location.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            MoveToEntry(FirstEntry(MyList));
            While MyList.OK Do Begin
                 Write(Word(Item(CurrentEntry(MyList))^),' ');
                 MoveToEntry(NextEntry(CurrentEntry(MyList)));
            End;
       End.

  This program would produce the following output:
       1    2    3    4    5    6    7    8    9    10

  NOTE: Item does not take the name of the list as an argument (MyList in the
  above example).  It is the programmer's responsibility to ensure that
  somewhere in the Item expression the name of the list is referenced.



  Entry(Var List:ListRec; Location:EntryPtr):EntryPtr
  ---------------------------------------------------------------------------
  The purpose of Entry is to return the a pointer to the location of
  Location.  Entry is needed because in some cases, it is the only way for
  LISTS to know what list is being used.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;
            E                   :    EntryPtr;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            E:=PrevEntry(PrevEntry(LastEntry(MyList)));
            MoveToEntry(Entry(MyList, E));
       End.
  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    10
                                          ^
                                          Current entry



  GetItem(Location:EntryPtr; Var _Item);
  ---------------------------------------------------------------------------
  GetItem copies the Item at Location to _Item.  The size is automatically
  taken care of.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;
            E                   :    EntryPtr;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            MoveToEntry(LastEntry(MyList));
            While MyList.OK Do Begin
                 GetItem(CurrentEntry(MyList),I);
                 Write(I,' ');
                 MoveToEntry(PrevEntry(CurrentEntry(MyList)));
            End;
       End.

  This program would produce the following output:
       10   9    8    7    6    5    4    3    2    1

  NOTE: Item does not take the name of the list as an argument (MyList in the
  above example).  It is the programmer's responsibility to ensure that
  somewhere in the Item expression the name of the list is referenced.



  PutItem(Location:EntryPtr; Var _Item)
  ---------------------------------------------------------------------------
  PutItem replaces the item at Location with _Item.  PutItem does not take
  Size as an argument, _Item MUST be the same size as the previous Item.  The
  only way to change a size is to first DeleteEntry and then InsertEntry.

       Program DemoList;
       Uses Lists;

       Var
            MyList              :    ListRec;
            I                   :    Byte;

       Begin
            InitList(MyList);
            For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));

            I:=76;
            PutItem(LastEntry(MyList), I);
       End.

  This program would produce the following list:
       1    2    3    4    5    6    7    8    9    76
       ^
       Current entry  The following procedures are implemented for the purpose of simulating a
  stack or queue.  Push and Pop are intended for Last In First Out routines
  whereas Queue and DeQueue designed for a First In Last Out buffer.  These
  four routines can be intermixed to produce Last In Last Out and First In
  First Out buffers.



  InitStack(Var Stack:ListRec)
  ---------------------------------------------------------------------------
  InitStack does exactly what InitList does.  It is provided for clarity of
  code.



  Push(Var Stack:ListRec; Var Item; Size:Word)
  ---------------------------------------------------------------------------
  Push places Item at the top of Stack.



  Pop(Var Stack:ListRec; Var Item)
  ---------------------------------------------------------------------------
  Pop removes the top item on Stack and places it in Item.



  Queue(Var Stack:ListRec; Var Item; Size:Word)
  ---------------------------------------------------------------------------
  Queue places Item at the bottom of Stack.



  DeQueue(Var Stack:ListRec; Var Item)
  ---------------------------------------------------------------------------
  DeQueue removes the bottom item on Stack and places it in Item.




                      ***** I hope you find LISTS useful.
                Again, if you have anything to ask let me know.

                                 Mark Addleman
                                 [72777, 740]