home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / library / dos / bix / linked.lib < prev    next >
Encoding:
Text File  |  1986-07-07  |  4.1 KB  |  160 lines
  1. {
  2.         procedures and function for linked lists
  3.  
  4. NOTE:  the following routines assume that you have declared the following
  5. data types (they won't compile, otherwise):
  6.  
  7.         type
  8.           NodePtr            = ^Node;
  9.           Node =
  10.             record
  11.               Next,Last      : NodePtr;
  12.               ...            : (* data fields *)
  13.             end;
  14.  
  15. Using such a structure, these routines will implement a circular, doubly-
  16. linked list.  They assume that you have use a header node for each list,
  17. that is, a variable of type NodePtr which is used only to point to the
  18. list and which (usually) doesn't hold any other information.  To create
  19. the list, just call GetNode, passing it that header variable.
  20.  
  21. InsertNode           inserts one node after another in a linked list
  22. RemoveNode           removes a node from a linked list
  23. GetNode              creates new node if space in available
  24. CreateList           creates a new linked list
  25. RemoveList           completely removes linked list (incl. header)
  26. Push                 pushes node onto stack
  27. Pop                  pops node off of stack
  28. Add                  adds node to one end of list (queue or deque)
  29. Take                 pulls node off of one end of list (queue or deque)
  30.  
  31. }
  32.  
  33. const
  34.   Front              = True;    { for use with Put and Get }
  35.   Rear               = False;   { ditto }
  36.  
  37.  
  38. procedure InsertNode(var NPtr,TPtr : NodePtr);
  39. {
  40.        purpose       inserts NPtr after TPtr
  41.        last update   03 Jul 85
  42. }
  43. begin
  44.   NPtr^.Last := TPtr;
  45.   NPtr^.Next := TPtr^.Next;
  46.   TPtr^.Next := NPtr;
  47.   NPtr^.Next^.Last := NPtr
  48. end; { of proc InsertNode }
  49.  
  50. procedure RemoveNode(var NPtr,TPtr : NodePtr);
  51. {
  52.        purpose       assigns NPtr = TPtr and removes NPtr from linked list
  53.        last update   08 Jul 85
  54. }
  55. begin
  56.   NPtr := TPtr;
  57.   with NPtr^ do begin
  58.     Last^.Next := Next;
  59.     Next^.Last := Last;
  60.     Last := nil; Next := nil
  61.   end
  62. end; { of proc RemoveNode }
  63.  
  64. function GetNode(var NPtr : NodePtr) : Boolean;
  65. {
  66.        purpose       allocate node if space is available
  67.        last update   08 Jul 85
  68. }
  69. begin
  70.   if MemAvail > 4*SizeOf(Node) then begin { leave a little cushion }
  71.     New(NPtr);
  72.     with NPtr^ do begin
  73.       FillChar(NPtr^,SizeOf(NPtr^),0);
  74.       Next := nil;
  75.       Last := nil
  76.     end;
  77.     GetNode := True
  78.   end
  79.   else begin
  80.     GetNode := False;
  81.     NPtr := nil
  82.   end
  83. end; { of func GetNode }
  84.  
  85. procedure CreateList(var Header : NodePtr);
  86. {
  87.        purpose       creates a new linked list
  88.        last update   10 Jul 85
  89. }
  90. begin
  91.   if GetNode(Header) then with Header^ do begin
  92.     Next := Header;
  93.     Last := Header
  94.   end
  95. end; { of proc CreateList }
  96.  
  97. procedure RemoveList(var Header : NodePtr);
  98. {
  99.        purpose       completely removes linked list
  100.        last update   03 Jul 85
  101. }
  102. var
  103.   TPtr               : NodePtr;
  104. begin
  105.   while Header^.Next <> Header do begin
  106.     RemoveNode(TPtr,Header^.Next);
  107.     Dispose(TPtr)
  108.   end;
  109.   Dispose(Header)
  110. end; { of proc RemoveList }
  111.  
  112. {   routines for stack handling }
  113.  
  114. procedure Push(var NPtr,Header : NodePtr);
  115. {
  116.        purpose       pushes NPtr onto stack
  117.        last update   09 Jul 85
  118. }
  119. begin
  120.   InsertNode(NPtr,Header)
  121. end; { of proc Push }
  122.  
  123. procedure Pop(var NPtr,Header : NodePtr);
  124. {
  125.        purpose       pops NPtr off of stack
  126.        last update   09 Jul 85
  127. }
  128. begin
  129.   if Header^.Next <> Header
  130.     then RemoveNode(NPtr,Header^.Next)
  131.     else NPtr := nil
  132. end; { of proc Pop }
  133.  
  134. {        routines for queues and deques              }
  135.  
  136. procedure Add(var NPtr,Header : NodePtr; onFront : Boolean);
  137. {
  138.        purpose       adds NPtr on front or rear of list
  139.        last update   09 Jul 85
  140. }
  141. begin
  142.   if onFront
  143.     then InsertNode(NPtr,Header)
  144.     else InsertNode(NPtr,Header^.Last)
  145. end; { of proc Add }
  146.  
  147. procedure Take(var NPtr,Header : NodePtr; offFront : Boolean);
  148. {
  149.        purpose       takes NPtr off of front or rear of list
  150.        last update   09 Jul 85
  151. }
  152. begin
  153.   if Header^.Next = Header
  154.     then NPtr := nil
  155.   else if offFront
  156.     then RemoveNode(NPtr,Header^.Next)
  157.     else RemoveNode(NPtr,Header^.Last)
  158. end; { of proc Take }
  159.  
  160.