home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / LISTS30.ZIP / LISTS.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1988-08-23  |  11.2 KB  |  403 lines
  1. (*****************************************************************************
  2.    Program:  Lists.Pas
  3.    Author:   Mark Addleman
  4.    Version:  3.0
  5.    Date:     August 5, 1988
  6.    Note:     Public domain software
  7.              Please distribute in complete form
  8.  
  9.  
  10. VERSION RECORD
  11. 1.0 - Gosh, I thought everything was right!
  12.  
  13. 1.1 - Minor bug found in DisposeOfList routine
  14.       If no items were added, DisposeOfList would try to dispose of
  15.       a NIL variable (List.FirstItem).  This is a no-no
  16.  
  17. 1.2 - Bug in DeleteItemFromList routine
  18.       If list contained only 1 item, the routine would not properly
  19.       reclaim the used memory
  20.  
  21. 2.0 - Revision to make life easier
  22.       - Renames of procedures/variables
  23.         - AddToList              becomes   AddItem
  24.         - InsertInList           becomes   InsertItem
  25.         - DeleteItemFromList     becomes   DeleteItem
  26.         - ListOK                 becomes   OK
  27.       - Replaced routines
  28.         - MoveTo______ routines replaced with MoveToItem
  29.         - _____ItemPtr routines replaced with Item
  30.       - New routines to process Stacks and Queues
  31.         - PUSH and POP provided to act as a Last In First Out stack
  32.         - Queue and Dequeue provided to act as a First In Last Out queue
  33.       - No external routines are needed to process lists
  34.         - Size of the Item is now taken as an argument
  35.         - DeleteItem now truly deletes the item and its reference in the list
  36.         - Pointers no longer necessary as arguments to AddItem and InsertItem
  37.       - The name of the list ALWAYS comes first in the arguments
  38.       - ItemInList is no longer implemented
  39.  
  40. 3.0 - Complete revision of source code, less Procedures/Functions, more power
  41.       - Renaming of routines/variables for easier understanding
  42.         - Each Entry in the list contains an Item
  43.         - Items are put into the list by the programmer
  44.       - Renaming of routines/variables:
  45.         - ItemRec and ItemPtr are now referred to as EntryRec and EntryPtr
  46.         - AddItem       becomes   AddEntry
  47.         - InsertItem    becomes   InsertEntry
  48.         - DeleteItem    becomes   DeleteEntry
  49.         - MoveToItem    becomes   MoveToEntry
  50.       - PutItem(Location:EntryPtr; Var Item) added
  51.         - Allows any item in list to be changed
  52.         - SizeOf(Item) must be the same as the old item
  53.       - Entry(Var List:ListRec; Location:EntryPtr) added
  54.         - Allows programmer hooks into list to be used as arguments
  55.       - EntryNumAbs(N:LongInt) added
  56.         - Used as argument to Entry, allows access to the Nth entry in list
  57.       - EntryNumRel(N:LongInt; Location:EntryPtr) added
  58.         - Used as argument to Entry, allows relative access to entries in list
  59.       - MoveItem(Source, Dest:EntryPtr) added
  60.         - Allows shuffling of entries in list
  61.       - New memory allocation for easier memory manipulation
  62.       - Compiled code is about 20% smaller than version 2.0 !
  63.     - Now ShareWare, $10 requested
  64. ******************************************************************************)
  65.  
  66. {$R-,S-,I-,D-,T-,F-,V+,B-,N-,L+ }
  67. {$M 16384,0,655360 }
  68.  
  69. Unit Lists;
  70.  
  71. INTERFACE
  72. Type
  73.    EntryPtr                  =   ^EntryRec;
  74.    EntryRec                  =   Record
  75.                                     P_Entry      :   EntryPtr;
  76.                                     N_Entry      :   EntryPtr;
  77.                                     Size         :   Word;
  78.                                     Item         :   Byte;
  79.                                  End;
  80.  
  81.    ListRec                   =   Record
  82.                                     OK           :   Boolean;
  83.                                     F_Entry      :   EntryPtr; {First entry}
  84.                                     L_Entry      :   EntryPtr; {Last entry}
  85.                                     C_Entry      :   EntryPtr; {Current entry}
  86.                                  End;
  87.  
  88. Procedure InitList           (Var List:ListRec);
  89. Procedure AddEntry           (Var List:ListRec; Var _Item; _Size:Word);
  90. Procedure InsertEntry        (Location:EntryPtr; Var _Item; _Size:Word);
  91.  
  92. Procedure DeleteEntry        (Location:EntryPtr);
  93. Procedure DeleteList         (Var List:ListRec);
  94.  
  95. Function Item                (Location:EntryPtr):Pointer;
  96. Function Entry               (Var List:ListRec; Location:EntryPtr):EntryPtr;
  97.  
  98. Procedure GetItem            (Location:EntryPtr; Var _Item);
  99. Procedure PutItem            (Location:EntryPtr; Var _Item);
  100.  
  101. Procedure MoveToEntry        (Location:EntryPtr);
  102. Procedure MoveEntry          (Source, Dest:EntryPtr);
  103.  
  104. Function CurrentEntry        (Var List:ListRec):EntryPtr;
  105. Function FirstEntry          (Var List:ListRec):EntryPtr;
  106. Function LastEntry           (Var List:ListRec):EntryPtr;
  107. Function NextEntry           (Location:EntryPtr):EntryPtr;
  108. Function PrevEntry           (Location:EntryPtr):EntryPtr;
  109. Function EntryNumAbs         (Var List:ListRec; Num:LongInt):EntryPtr;
  110. Function EntryNumRel         (Location:EntryPtr; Num:LongInt):EntryPtr;
  111.  
  112. Procedure InitStack          (Var Stack:ListRec);
  113. Procedure Push               (Var Stack:ListRec; Var Item; Size:Word);
  114. Procedure Pop                (Var Stack:ListRec; Var Item);
  115. Procedure Queue              (Var Stack:ListRec; Var Item; Size:Word);
  116. Procedure DeQueue            (Var Stack:ListRec; Var Item);
  117.  
  118.  
  119. IMPLEMENTATION
  120. Var
  121.    GlobalList                :   ^ListRec;
  122.  
  123. Procedure InitList(Var List:ListRec);
  124. Begin
  125.    List.F_Entry:=nil;  List.F_Entry^.P_Entry:=nil;
  126.    List.L_Entry:=nil;  List.L_Entry^.N_Entry:=nil;
  127.  
  128.    List.C_Entry:=nil;
  129.    List.C_Entry^.N_Entry:=nil;
  130.    List.C_Entry^.P_Entry:=nil;
  131.  
  132.    List.OK:=True;
  133. End;
  134.  
  135.  
  136. Procedure AddEntry(Var List:ListRec; Var _Item; _Size:Word);
  137. Begin
  138.    GetMem(List.L_Entry^.N_Entry, _Size+SizeOf(List.L_Entry^.N_Entry^));
  139.  
  140.    List.L_Entry^.N_Entry^.Size:=_Size;
  141.    List.L_Entry^.N_Entry^.N_Entry:=nil;
  142.    List.L_Entry^.N_Entry^.P_Entry:=List.L_Entry;
  143.  
  144.    PutItem(List.L_Entry^.N_Entry, _Item);
  145.  
  146.    If List.F_Entry=nil Then Begin
  147.       List.F_Entry:=List.L_Entry^.N_Entry;
  148.       List.F_Entry^.P_Entry:=nil;
  149.       List.C_Entry:=List.L_Entry;
  150.    End;
  151.  
  152.    List.L_Entry:=List.L_Entry^.N_Entry;
  153.    List.L_Entry^.N_Entry:=nil;
  154. End;
  155.  
  156.  
  157. Procedure InsertEntry(Location:EntryPtr; Var _Item; _Size:Word);
  158. Var
  159.    NewEntry                  :   EntryPtr;
  160.  
  161. Begin
  162.    If Location=nil Then Begin
  163.       AddEntry(GlobalList^, _Item, _Size);
  164.       Exit;
  165.    End;
  166.  
  167.  
  168.    GetMem(NewEntry, _Size+SizeOf(NewEntry^));
  169.  
  170.    NewEntry^.Size:=_Size;
  171.    NewEntry^.N_Entry:=Location;
  172.    NewEntry^.P_Entry:=Location^.P_Entry;
  173.    PutItem(NewEntry, _Item);
  174.  
  175.    Location^.P_Entry^.N_Entry:=NewEntry;
  176.    Location^.P_Entry:=NewEntry;
  177.  
  178.    If Location=GlobalList^.F_Entry Then
  179.       GlobalList^.F_Entry:=Location^.P_Entry;
  180. End;
  181.  
  182.  
  183. Procedure GetItem(Location:EntryPtr; Var _Item);
  184. Begin
  185.    Move(Location^.Item, _Item, Location^.Size);
  186. End;
  187.  
  188.  
  189. Procedure PutItem(Location:EntryPtr; Var _Item);
  190. Begin
  191.    Move(_Item, Location^.Item, Location^.Size);
  192. End;
  193.  
  194.  
  195. Function Item(Location:EntryPtr):Pointer;
  196. Begin
  197.    Item:=@Location^.Item;
  198. End;
  199.  
  200.  
  201. Function PrevEntry(Location:EntryPtr):EntryPtr;
  202. Begin
  203.    If Location^.P_Entry=nil Then PrevEntry:=nil
  204.    Else PrevEntry:=Location^.P_Entry;
  205. End;
  206.  
  207.  
  208. Function NextEntry(Location:EntryPtr):EntryPtr;
  209. Begin
  210.    If Location^.N_Entry=nil Then NextEntry:=nil
  211.    Else NextEntry:=Location^.N_Entry;
  212. End;
  213.  
  214.  
  215. Function EntryNumAbs(Var List:ListRec; Num:LongInt):EntryPtr;
  216. Var
  217.    TempEntry                 :   EntryPtr;
  218.    I                         :   LongInt;
  219.  
  220. Label
  221.    Finish;
  222.  
  223. Begin
  224.    GlobalList:=@List;
  225.    TempEntry:=GlobalList^.F_Entry;
  226.  
  227.    With TempEntry^ Do
  228.    For I:=1 To Pred(Num) Do Begin
  229.       If TempEntry=nil Then Goto Finish;
  230.       TempEntry:=N_Entry;
  231.    End;
  232.  
  233.    Begin Finish:
  234.       EntryNumAbs:=TempEntry;
  235.    End;
  236. End;
  237.  
  238.  
  239. Function EntryNumRel(Location:EntryPtr; Num:LongInt):EntryPtr;
  240. Var
  241.    TempEntry                 :   EntryPtr;
  242.    I                         :   LongInt;
  243.  
  244. Label
  245.    Finish;
  246.  
  247. Begin
  248.    TempEntry:=Location;
  249.  
  250.    With TempEntry^ Do
  251.    If Num < 0 Then
  252.       For I:=0 DownTo Succ(Num) Do Begin
  253.          If TempEntry=nil Then Goto Finish;
  254.          TempEntry:=P_Entry;
  255.       End
  256.    Else
  257.       For I:=1 To Pred(Num) Do Begin
  258.          If TempEntry=nil Then Goto Finish;
  259.          TempEntry:=N_Entry;
  260.       End;
  261.  
  262.    Begin Finish:
  263.       EntryNumRel:=TempEntry;
  264.    End;
  265. End;
  266.  
  267.  
  268. Function CurrentEntry(Var List:ListRec):EntryPtr;
  269. Begin
  270.    CurrentEntry:=List.C_Entry;
  271.    GlobalList:=@List;
  272. End;
  273.  
  274.  
  275. Function FirstEntry(Var List:ListRec):EntryPtr;
  276. Begin
  277.    FirstEntry:=List.F_Entry;
  278.    GlobalList:=@List;
  279. End;
  280.  
  281.  
  282. Function LastEntry(Var List:ListRec):EntryPtr;
  283. Begin
  284.    LastEntry:=List.L_Entry;
  285.    GlobalList:=@List;
  286. End;
  287.  
  288.  
  289. Function Entry(Var List:ListRec; Location:EntryPtr):EntryPtr;
  290. Begin
  291.    Entry:=Location;
  292.    GlobalList:=@List;
  293. End;
  294.  
  295.  
  296. Procedure MoveToEntry(Location:EntryPtr);
  297. Begin
  298.    GlobalList^.OK:=Not (Location=nil);
  299.    If GlobalList^.OK Then GlobalList^.C_Entry:=Location;
  300. End;
  301.  
  302.  
  303. Procedure MoveEntry(Source, Dest:EntryPtr);
  304. Begin
  305.    If Source=GlobalList^.F_Entry Then
  306.       GlobalList^.F_Entry:=GlobalList^.F_Entry^.N_Entry
  307.    Else
  308.    If Source=GlobalList^.L_Entry Then
  309.       GlobalList^.L_Entry:=GlobalList^.L_Entry^.P_Entry;
  310.  
  311.    If Dest=GlobalList^.F_Entry Then
  312.       GlobalList^.F_Entry:=Source;
  313.  
  314.    Source^.P_Entry^.N_Entry:=Source^.N_Entry;
  315.    Source^.N_Entry^.P_Entry:=Source^.P_Entry;
  316.  
  317.    Source^.P_Entry:=Dest^.P_Entry;
  318.    Source^.N_Entry:=Dest;
  319.  
  320.    If Dest=nil Then Begin
  321.       GlobalList^.L_Entry^.N_Entry:=Source;
  322.       GlobalList^.L_Entry:=GlobalList^.L_Entry^.N_Entry;
  323.    End
  324.    Else Begin
  325.       Dest^.P_Entry^.N_Entry:=Source;
  326.       Dest^.P_Entry:=Source;
  327.    End;
  328. End;
  329.  
  330.  
  331. Procedure DeleteEntry(Location:EntryPtr);
  332. Begin
  333.    If Location=nil Then Begin
  334.       GlobalList^.OK:=False;
  335.       Exit;
  336.    End;
  337.  
  338.    Location^.P_Entry^.N_Entry:=Location^.N_Entry;
  339.    Location^.N_Entry^.P_Entry:=Location^.P_Entry;
  340.  
  341.    If Location=GlobalList^.F_Entry Then
  342.       GlobalList^.F_Entry:=Location^.N_Entry;
  343.    If Location=GlobalList^.L_Entry Then
  344.       GlobalList^.L_Entry:=Location^.P_Entry;
  345.  
  346.    If Location^.N_Entry=nil Then
  347.       GlobalList^.C_Entry:=Location^.P_Entry
  348.    Else
  349.       GlobalList^.C_Entry:=Location^.N_Entry;
  350.  
  351.    If GlobalList^.C_Entry=nil Then GlobalList^.OK:=False;
  352.  
  353.    FreeMem(Location, Location^.Size+SizeOf(Location^));
  354. End;
  355.  
  356.  
  357. Procedure DeleteList(Var List:ListRec);
  358. Begin
  359.    MoveToEntry(FirstEntry(List));
  360.  
  361.    With List Do
  362.    While OK Do Begin
  363.       FreeMem(C_Entry, C_Entry^.Size+SizeOf(C_Entry^));
  364.       MoveToEntry(NextEntry(CurrentEntry(List)));
  365.    End;
  366.  
  367.    InitList(List);
  368. End;
  369.  
  370.  
  371.  
  372.  
  373.  
  374. Procedure InitStack(Var Stack:ListRec);
  375. Begin
  376.    InitList(Stack);
  377. End;
  378.  
  379. Procedure Push(Var Stack:ListRec; Var Item; Size:Word);
  380. Begin
  381.    AddEntry(Stack, Item, Size);
  382. End;
  383.  
  384. Procedure Pop(Var Stack:ListRec; Var Item);
  385. Begin
  386.    GetItem(LastEntry(Stack), Item);
  387.    DeleteEntry(LastEntry(Stack));
  388. End;
  389.  
  390. Procedure Queue(Var Stack:ListRec; Var Item; Size:Word);
  391. Begin
  392.    InsertEntry(FirstEntry(Stack), Item, Size);
  393. End;
  394.  
  395. Procedure DeQueue(Var Stack:ListRec; Var Item);
  396. Begin
  397.    GetItem(FirstEntry(Stack), Item);
  398.    DeleteEntry(FirstEntry(Stack));
  399. End;
  400.  
  401.  
  402. End.
  403.