home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / LISTS30.ZIP / LISTS30.DOC < prev   
Encoding:
Text File  |  1988-08-29  |  21.2 KB  |  641 lines

  1.  
  2.   Documentation for LISTS.PAS (ver 3.0)
  3.   Written by Mark Addleman [72777, 740] for Software Applications of Wichita
  4.  
  5.   *** NOTE: This program is distributed under the ShareWare concept.  As
  6.   such, you are granted a limited evaluation period after which continued use
  7.   requires registration in accordance with the Agreement contained in
  8.   License.TXT.  A licensing fee of $15 and a signed Agreement should be sent
  9.   to the address below:
  10.  
  11.   Please send your contributions to
  12.                         Software Applications of Wichita
  13.                               2204 Winstead Circle
  14.                             Wichita, KS  67226-1122
  15.  
  16.   This document was created using Sprint:  The Professional Word Processor
  17.   and whatever printer you are using.
  18.  
  19.   Updates
  20.  
  21.   Any updates which are made available will be placed on the Compuserve
  22.   Borland Forum.
  23.  
  24.  
  25.   Purpose
  26.  
  27.   LISTS is designed to relieve you of the messy details of creating and
  28.   maintaining linked lists.  Features include the ability to add, insert, and
  29.   delete items from lists.  Moving (forward and backward) through lists is
  30.   implemented, along with the capability to rearrange the order of the list.
  31.  
  32.  
  33.  
  34.   Changes from the previous version
  35.  
  36.   LISTS version 3 abounds with changes from the version 2.  Most notable
  37.   changes include a different analogy use in LISTS.  Now, a list is made up
  38.   of ENTRIES.  Each ENTRY contains an ITEM.  It is the ITEM that the
  39.   programmer is primarily interested in.  Another major change is that very
  40.   few of the routines explicitly require the list name as an argument.  For
  41.   example, to refer to the next-to-the-last entry in a list:
  42.        Entry:=PrevEntry(LastEntry(List));
  43.   The change is that PrevEntry doesn't require List as an argument.  The
  44.   advantage is that less code is required, greater memory efficiency, and
  45.   speed since the program no longer must push the name of the list onto the
  46.   stack.
  47.  
  48.   WARNING:  LISTS uses a local variable to make this possible.  Therefore,
  49.   any statement using LISTS routines must somewhere contain the name of the
  50.   list.  For example, the following code is ***** no longer valid:
  51.        Var
  52.           E       :   EntryPtr;
  53.           List    :   ListRec;
  54.  
  55.        Begin
  56.           Entry:=FirstEntry(List);
  57.           MoveToEntry(E);
  58.        End.
  59.  
  60.   The compiler will not generate an error because technically it is correct.
  61.   The problem is that LISTS will be unable to communicate with the variable
  62.   List if it had to.  The Entry function is provided to perform the same
  63.   function as the program above, but in a legal manner:
  64.        Function Entry(List:ListRec; Location:EntryPtr):EntryPtr;
  65.  
  66.   So the above program would look like this:
  67.        Var
  68.           E       :   EntryPtr;
  69.           List    :   ListRec;
  70.  
  71.        Begin
  72.           E:=FirstEntry(List);
  73.           MoveToEntry(Entry(List,E));
  74.        End.
  75.  
  76.  
  77.   Another enhancement to LISTS is the ability to access a list completely at
  78.   random using the EntryNumAbs and EntryNumRel routines.  These routines
  79.   access the absolute entry on the list (1st, 2nd, 3rd, etc) and relative
  80.   entry on the list (back one, back two, forward three, forward four, etc)
  81.   respectively.  Also, GetItem and PutItem are available for accessing the
  82.   item in the entry or changing it.
  83.  
  84.   ListRec (type declaration)
  85.   ---------------------------------------------------------------------------
  86.   ListRec is the backbone of the entire LISTS package.  This is the
  87.   programmer's connection with the linked list.  The following is its type
  88.   definition in the LISTS.TPU:
  89.        ListRec   =    Record
  90.                            OK   :    Boolean;
  91.                            {Set to FALSE if an error occurs}
  92.  
  93.                            F_Entry   :    EntryPtr;
  94.                            {Points to the first entry in the list}
  95.  
  96.                            L_Entry   :    EntryPtr;
  97.                            {Points to the last entry in the list}
  98.  
  99.                            C_Entry   :    EntryPtr;
  100.                            {Points to the entry currently being referenced}
  101.                       End;
  102.  
  103.   EntryPtr is a pointer to the record EntryRec which contains the information
  104.   concerning an entry on the list.
  105.        EntryRec  =    Record
  106.                            P_Entry   :    EntryPtr;
  107.                            {Points to the previous entry}
  108.  
  109.                            N_Entry   :    EntryPtr;
  110.                            {Points to the next entry}
  111.  
  112.                            Size      :    Word;
  113.                            {Size in bytes of the item in this entry}
  114.  
  115.                            Item      :    Byte
  116.                            {The item in this entry}
  117.                       End;
  118.  
  119.   Item is only 1 byte in length.  The reason that Item is only a byte is that
  120.   Item actually becomes part of the Entry data structure.  Whenever an item
  121.   is added to the list, the size is taken as an argument and LISTS allocates
  122.   enough memory for the EntryRec plus the size of the item.  The Item is then
  123.   copied in memory to the end of the entry using Turbo's Move procedure.  If
  124.   this isn't clear, refer to the GetItem and PutItem procedures in the source
  125.   code.
  126.  
  127.  
  128.  
  129.   InitList(Var List:ListRec)
  130.   ---------------------------------------------------------------------------
  131.   InitList must be called for each list before using.  InitList sets all
  132.   pointers to NIL and prepares the list for processing.
  133.  
  134.        Program DemoList;
  135.        Uses Lists;
  136.  
  137.        Var
  138.             MyList              :    ListRec;
  139.  
  140.        Begin
  141.             InitList(MyList);
  142.        End.
  143.  
  144.  
  145.  
  146.   AddEntry(Var List:ListRec; Var Item; Size:Word);
  147.   ---------------------------------------------------------------------------
  148.  
  149.   AddEntry is used for tacking entries onto the end of List.  AddEntry also
  150.   takes an Item and its Size (using the SizeOf procedure usually) as
  151.   arguments and places them in the entry.
  152.  
  153.   AddEntry places the new entry at the end of List.
  154.   AddEntry does not move the current entry pointer.
  155.  
  156.        Program DemoList;
  157.        Uses Lists;
  158.  
  159.        Var
  160.             MyList              :    ListRec;
  161.             I                   :    Byte;
  162.  
  163.        Begin
  164.             InitList(MyList);
  165.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  166.        End.
  167.  
  168.   This program creates the following list:
  169.        1    2    3    4    5    6    7    8    9    10
  170.        ^
  171.        Current entry
  172.  
  173.  
  174.  
  175.   InsertEntry(Location:EntryPtr; Var Item; Size:Word)
  176.   ---------------------------------------------------------------------------
  177.   InsertEntry is another procedure for placing an entry in a list.  Unlike
  178.   AddEntry, however, InsertEntry places the entry immediately before the
  179.   entry specified in Location.
  180.  
  181.   InsertEntry does not move the current entry pointer.
  182.  
  183.   For example:
  184.        Program DemoList;
  185.        Uses Lists;
  186.  
  187.        Var
  188.             MyList              :    ListRec;
  189.             I                   :    Byte;
  190.  
  191.        Begin
  192.             InitList(MyList);
  193.             For I:=1e To 10 Do AddEntry(MyList, I, SizeOf(I));
  194.  
  195.             I:=76;
  196.             InsertEntry(LastEntry(MyList), I, SizeOf(I));
  197.        End.
  198.  
  199.   This program would create the following list:
  200.        1    2    3    4    5    6    7    8    9    76   10
  201.        ^
  202.        Current entry
  203.  
  204.   NOTE: InsertEntry does not take the name of the list as an argument (MyList
  205.   in the above example).  It is the programmer's responsibility to ensure
  206.   that somewhere in the InsertEntry expression the name of the list is
  207.   referenced.
  208.  
  209.  
  210.  
  211.   DeleteEntry(Location:EntryPtr)
  212.   ---------------------------------------------------------------------------
  213.   DeleteEntry deletes the entry in a list at Location.
  214.   DeleteEntry moves the current entry pointer in only one circumstance:  when
  215.   the entry to be deleted is the entry currently being referenced.  In this
  216.   case, the current entry is moved to the next entry.  However, if the
  217.   current entry is the last entry and it is to be deleted, the current entry
  218.   will point to the new last entry.
  219.  
  220.   NOTE: DeleteEntry does not take the name of the list as an argument (MyList
  221.   in the above example).  It is the programmer's responsibility to ensure
  222.   that somewhere in the InsertEntry expression the name of the list is
  223.   referenced.
  224.  
  225.        Program DemoList;
  226.        Uses Lists;
  227.  
  228.        Var
  229.             MyList              :    ListRec;
  230.             I                   :    Byte;
  231.  
  232.        Begin
  233.             InitList(MyList);
  234.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  235.  
  236.             DeleteEntry(LastEntry(MyList));
  237.        End.
  238.  
  239.   This program produces the following list:
  240.        1    2    3    4    5    6    7    8    9
  241.        ^
  242.        Current entry
  243.  
  244.   NOTE: DeleteEntry does not take the name of the list as an argument (MyList
  245.   in the above example).  It is the programmer's responsibility to ensure
  246.   that somewhere in the DeleteEntry expression the name of the list is
  247.   referenced.
  248.  
  249.  
  250.  
  251.  
  252.   DeleteList(Var List:ListRec)
  253.   ---------------------------------------------------------------------------
  254.   DeleteList removes the entire List from memory and initializes List for
  255.   use.
  256.  
  257.  
  258.  
  259.   CurrentEntry(List:ListRec):Pointer
  260.   ---------------------------------------------------------------------------
  261.   CurrentEntry returns the a pointer to the entry currently being referenced
  262.   in List.
  263.  
  264.        Program DemoList;
  265.        Uses Lists;
  266.  
  267.        Var
  268.             MyList              :    ListRec;
  269.             I                   :    Byte;
  270.  
  271.        Begin
  272.             InitList(MyList);
  273.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  274.  
  275.             I:=76;
  276.             InsertEntry(CurrentEntry(MyList), I, SizeOf(I));
  277.        End.
  278.  
  279.   This program would produce the following list:
  280.        76   1    2    3    4    5    6    7    8    9    10
  281.             ^
  282.             Current entry
  283.  
  284.  
  285.  
  286.   FirstEntry(Var List:ListRec):Pointer;
  287.   ---------------------------------------------------------------------------
  288.   FirstEntry returns the location of the first entry in List.
  289.  
  290.        Program DemoList;
  291.        Uses Lists;
  292.  
  293.        Var
  294.             MyList              :    ListRec;
  295.             I                   :    Byte;
  296.  
  297.        Begin
  298.             InitList(MyList);
  299.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  300.  
  301.             I:=76;
  302.             InsertEntry(FirstEntry(MyList), I, SizeOf(I));
  303.        End.
  304.  
  305.   This program would produce the following list:
  306.        76   1    2    3    4    5    6    7    8    9    10
  307.             ^
  308.             Current entry
  309.  
  310.  
  311.  
  312.   LastEntry(Var List:ListRec)
  313.   ---------------------------------------------------------------------------
  314.   LastEntry returns the location of the last entry in List.
  315.  
  316.        Program DemoList;
  317.        Uses Lists;
  318.  
  319.        Var
  320.             MyList              :    ListRec;
  321.             I                   :    Byte;
  322.  
  323.        Begin
  324.             InitList(MyList);
  325.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  326.  
  327.             I:=76;
  328.             InsertEntry(LastEntry(MyList), I, SizeOf(I));
  329.        End.
  330.  
  331.   This program would produce the following list:
  332.        1    2    3    4    5    6    7    8    9    76   10
  333.        ^
  334.        Current entry
  335.  
  336.  
  337.  
  338.   NextEntry(Location:EntryPtr):EntryPtr
  339.   ---------------------------------------------------------------------------
  340.   NextEntry returns the location of the entry immediately after Location.
  341.   Normally location is either CurrentEntry or FirstEntry.  If LastEntry is
  342.   used as an argument, a NIL is returned.
  343.  
  344.        Program DemoList;
  345.        Uses Lists;
  346.        Var
  347.             MyList              :    ListRec;
  348.             I                   :    Byte;
  349.  
  350.        Begin
  351.             InitList(MyList);
  352.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  353.  
  354.             I:=76;
  355.             InsertEntry(NextEntry(FirstEntry(MyList)), I, SizeOf(I));
  356.        End.
  357.  
  358.   This program would produce the following list:
  359.        1    2    3    4    5    6    7    8    9    76   10
  360.        ^
  361.        Current entry
  362.  
  363.   NOTE: NextEntry does not take the name of the list as an argument (MyList
  364.   in the above example).  It is the programmer's responsibility to ensure
  365.   that somewhere in the NextEntry expression the name of the list is
  366.   referenced.
  367.  
  368.  
  369.  
  370.   PrevEntry(Location:EntryPtr):EntryPtr
  371.   ---------------------------------------------------------------------------
  372.   PrevEntry returns the entry immediately preceding Location.  Normally,
  373.   PrevEntry takes CurrentEntry or LastEntry as arguments.  If FirstEntry is
  374.   used, a NIL pointer is returned.
  375.        Program DemoList;
  376.        Uses Lists;
  377.  
  378.        Var
  379.             MyList              :    ListRec;
  380.             I                   :    Byte;
  381.  
  382.        Begin
  383.             InitList(MyList);
  384.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  385.  
  386.             I:=76;
  387.             InsertEntry(PrevEntry(LastEntry(MyList)), I, SizeOf(I));
  388.        End.
  389.  
  390.   This program would procedure the following list:
  391.        1    2    3    4    5    6    7    8    76   9    10
  392.        ^
  393.        Current entry
  394.  
  395.   NOTE: NextEntry does not take the name of the list as an argument (MyList
  396.   in the above example).  It is the programmer's responsibility to ensure
  397.   that somewhere in the NextEntry expression the name of the list is
  398.   referenced.
  399.  
  400.  
  401.  
  402.   MoveToEntry(Location:EntryPtr)
  403.   ---------------------------------------------------------------------------
  404.   MoveToEntry moves the current entry in a list to Location.
  405.  
  406.   MoveToEntry sets OK to FALSE if an attempt is made to move before the
  407.   FirstEntry or after the LastEntry.
  408.        Program DemoList;
  409.        Uses Lists;
  410.  
  411.        Var
  412.             MyList              :    ListRec;
  413.             I                   :    Byte;
  414.  
  415.        Begin
  416.             InitList(MyList);
  417.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  418.  
  419.             MoveToEntry(PrevEntry(LastEntry(MyList)));
  420.        End.
  421.  
  422.   This program would produce the following list:
  423.        1    2    3    4    5    6    7    8    9    10
  424.                                                ^
  425.                                                Current entry
  426.  
  427.   NOTE: MoveToEntry does not take the name of the list as an argument (MyList
  428.   in the above example).  It is the programmer's responsibility to ensure
  429.   that somewhere in the MoveToEntry expression the name of the list is
  430.   referenced.
  431.  
  432.  
  433.  
  434.   EntryNumAbs(Var List:ListRec; N:LongInt)
  435.   ---------------------------------------------------------------------------
  436.   EntryNumAbs returns the Nth entry in List.
  437.  
  438.   If N is zero or less, the current entry is returned.
  439.  
  440.        Program DemoList;
  441.        Uses Lists;
  442.  
  443.        Var
  444.             MyList              :    ListRec;
  445.             I                   :    Byte;
  446.  
  447.        Begin
  448.             InitList(MyList);
  449.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  450.  
  451.             MoveToEntry(EntryNumAbs(MyList, 3)));
  452.        End.
  453.  
  454.   This program would produce the following list:
  455.        1    2    3    4    5    6    7    8    9    10
  456.                  ^
  457.                  Current entry
  458.  
  459.  
  460.  
  461.   EntryNumRel(Location:EntryPtr; N:LongInt):EntryPtr;
  462.   ---------------------------------------------------------------------------
  463.   EntryNumRel returns the entry N positions relative to Location.  If N is
  464.   negative, EntryNumRel returns the Nth entry preceding Location.  If N is
  465.   positive, EntryNumRel returns the Nth entry after Location.
  466.  
  467.  
  468.        Program DemoList;
  469.        Uses Lists;
  470.  
  471.        Var
  472.             MyList              :    ListRec;
  473.             I                   :    Byte;
  474.  
  475.        Begin
  476.             InitList(MyList);
  477.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  478.             MoveToEntry(EntryNumRel(NextEntry(FirstEntry(MyList), 2)));
  479.        End.
  480.  
  481.   This program produces the following list:
  482.        1    2    3    4    5    6    7    8    9    10
  483.                       ^
  484.                       Current entry
  485.  
  486.  
  487.  
  488.   Item(Location:EntryPtr):Pointer
  489.   ---------------------------------------------------------------------------
  490.   Item returns a pointer to the Item in the Entry at Location.
  491.  
  492.        Program DemoList;
  493.        Uses Lists;
  494.  
  495.        Var
  496.             MyList              :    ListRec;
  497.             I                   :    Byte;
  498.  
  499.        Begin
  500.             InitList(MyList);
  501.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  502.  
  503.             MoveToEntry(FirstEntry(MyList));
  504.             While MyList.OK Do Begin
  505.                  Write(Word(Item(CurrentEntry(MyList))^),' ');
  506.                  MoveToEntry(NextEntry(CurrentEntry(MyList)));
  507.             End;
  508.        End.
  509.  
  510.   This program would produce the following output:
  511.        1    2    3    4    5    6    7    8    9    10
  512.  
  513.   NOTE: Item does not take the name of the list as an argument (MyList in the
  514.   above example).  It is the programmer's responsibility to ensure that
  515.   somewhere in the Item expression the name of the list is referenced.
  516.  
  517.  
  518.  
  519.   Entry(Var List:ListRec; Location:EntryPtr):EntryPtr
  520.   ---------------------------------------------------------------------------
  521.   The purpose of Entry is to return the a pointer to the location of
  522.   Location.  Entry is needed because in some cases, it is the only way for
  523.   LISTS to know what list is being used.
  524.  
  525.        Program DemoList;
  526.        Uses Lists;
  527.  
  528.        Var
  529.             MyList              :    ListRec;
  530.             I                   :    Byte;
  531.             E                   :    EntryPtr;
  532.  
  533.        Begin
  534.             InitList(MyList);
  535.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  536.  
  537.             E:=PrevEntry(PrevEntry(LastEntry(MyList)));
  538.             MoveToEntry(Entry(MyList, E));
  539.        End.
  540.  
  541.   This program would produce the following list:
  542.        1    2    3    4    5    6    7    8    9    10
  543.                                           ^
  544.                                           Current entry
  545.  
  546.  
  547.  
  548.   GetItem(Location:EntryPtr; Var _Item);
  549.   ---------------------------------------------------------------------------
  550.   GetItem copies the Item at Location to _Item.  The size is automatically
  551.   taken care of.
  552.  
  553.        Program DemoList;
  554.        Uses Lists;
  555.  
  556.        Var
  557.             MyList              :    ListRec;
  558.             I                   :    Byte;
  559.             E                   :    EntryPtr;
  560.  
  561.        Begin
  562.             InitList(MyList);
  563.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  564.  
  565.             MoveToEntry(LastEntry(MyList));
  566.             While MyList.OK Do Begin
  567.                  GetItem(CurrentEntry(MyList),I);
  568.                  Write(I,' ');
  569.                  MoveToEntry(PrevEntry(CurrentEntry(MyList)));
  570.             End;
  571.        End.
  572.  
  573.   This program would produce the following output:
  574.        10   9    8    7    6    5    4    3    2    1
  575.  
  576.   NOTE: Item does not take the name of the list as an argument (MyList in the
  577.   above example).  It is the programmer's responsibility to ensure that
  578.   somewhere in the Item expression the name of the list is referenced.
  579.  
  580.  
  581.  
  582.   PutItem(Location:EntryPtr; Var _Item)
  583.   ---------------------------------------------------------------------------
  584.   PutItem replaces the item at Location with _Item.  PutItem does not take
  585.   Size as an argument, _Item MUST be the same size as the previous Item.  The
  586.   only way to change a size is to first DeleteEntry and then InsertEntry.
  587.  
  588.        Program DemoList;
  589.        Uses Lists;
  590.  
  591.        Var
  592.             MyList              :    ListRec;
  593.             I                   :    Byte;
  594.  
  595.        Begin
  596.             InitList(MyList);
  597.             For I:=1 To 10 Do AddEntry(MyList, I, SizeOf(I));
  598.  
  599.             I:=76;
  600.             PutItem(LastEntry(MyList), I);
  601.        End.
  602.  
  603.   This program would produce the following list:
  604.        1    2    3    4    5    6    7    8    9    76
  605.        ^
  606.        Current entry
  607.   The following procedures are implemented for the purpose of simulating a
  608.   stack or queue.  Push and Pop are intended for Last In First Out routines
  609.   whereas Queue and DeQueue designed for a First In Last Out buffer.  These
  610.   four routines can be intermixed to produce Last In Last Out and First In
  611.   First Out buffers.
  612.  
  613.  
  614.  
  615.   InitStack(Var Stack:ListRec)
  616.   ---------------------------------------------------------------------------
  617.   InitStack does exactly what InitList does.  It is provided for clarity of
  618.   code.
  619.  
  620.  
  621.  
  622.   Push(Var Stack:ListRec; Var Item; Size:Word)
  623.   ---------------------------------------------------------------------------
  624.   Push places Item at the top of Stack.
  625.  
  626.  
  627.  
  628.   Pop(Var Stack:ListRec; Var Item)
  629.   ---------------------------------------------------------------------------
  630.   Pop removes the top item on Stack and places it in Item.
  631.  
  632.  
  633.  
  634.   Queue(Var Stack:ListRec; Var Item; Size:Word)
  635.   ---------------------------------------------------------------------------
  636.   Queue places Item at the bottom of Stack.
  637.  
  638.  
  639.  
  640.   DeQueue(Var Stack:ListRec; Var Item)
  641.   ---------------------------------------------------------------------------
  642.   DeQueue removes the bottom item on Stack and places it in Item.
  643.  
  644.  
  645.  
  646.  
  647.                       ***** I hope you find LISTS useful.
  648.                 Again, if you have anything to ask let me know.
  649.  
  650.                                  Mark Addleman
  651.                                  [72777, 740]
  652.