November 28, 2020, 10:03:14 AM

Author Topic: [bb] Linked Lists 1.2 by Entity [ 1+ years ago ]  (Read 644 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Linked Lists 1.2 by Entity [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
Title : Linked Lists 1.2
Author : Entity
Posted : 1+ years ago

Description : If you need to have multiple lists of items of the same type, you need custom linked lists, as Blitz' list commands only work on the entire collection of objects of a type.

I didn't implement all Amiga functions (like inserting at specific locations, and inserting by priority), but you could write those yourself if you need them :)
 


Code :
Code: BlitzBasic
  1. ;
  2. ; Lists.bb -- Version 1.2 -- Amiga style linked lists
  3. ; by Jamie "Entity" van den Berge
  4. ;
  5.  
  6. Type List
  7.         Field lh_Head.Node
  8.         Field lh_Tail.Node
  9. End Type
  10.  
  11. Type Node
  12.         Field ln_Succ.Node
  13.         Field ln_Pred.Node
  14.         Field ln_List.List
  15.         Field ln_ID
  16. End Type
  17.  
  18.  
  19. ;______________________________________________________________________________
  20. ; Remove
  21. ;
  22. ; FUNCTION
  23. ;       Removes a node from the list it is in
  24. ;
  25. ; INPUTS
  26. ;       node    - node to unlink
  27. ;
  28. Function Remove .Node ( node.Node )
  29.         If nodeln_Pred <> Null
  30.                 nodeln_Predln_Succ = nodeln_Succ
  31.         Else
  32.                 If node = nodeln_Listlh_Head Then nodeln_Listlh_Head = nodeln_Succ
  33.         EndIf
  34.         If nodeln_Succ <> Null
  35.                 nodeln_Succln_Pred = nodeln_Pred
  36.         Else
  37.                 If node = nodeln_Listlh_Tail Then nodeln_Listlh_Tail = nodeln_Pred
  38.         EndIf
  39.         nodeln_Pred = Null
  40.         nodeln_Succ = Null
  41.         nodeln_List = Null
  42.         Return node
  43. End Function
  44.  
  45.  
  46. ;______________________________________________________________________________
  47. ; RemHead
  48. ;
  49. ; FUNCTION
  50. ;       Removes first node from a list
  51. ;
  52. ; INPUTS
  53. ;       list    - list to remove first node of
  54. ;
  55. ; RESULT
  56. ;       the node that was removed
  57. ;
  58. Function RemHead .Node ( list.List )
  59.         Local node.Node = listlh_Head
  60.         If node <> Null Then listlh_Head = nodeln_Succ
  61.         If listlh_Tail = node Then listlh_Tail = Null ; list is empty?
  62.         nodeln_List = Null
  63.         Return node
  64. End Function
  65.  
  66.  
  67. ;______________________________________________________________________________
  68. ; RemTail
  69. ;
  70. ; FUNCTION
  71. ;       Removes last node from a list
  72. ;
  73. ; INPUTS
  74. ;       list    - list to remove the last node of
  75. ;
  76. ; RESULT
  77. ;       the node that was removed
  78. ;
  79. Function RemTail .Node ( list.List )
  80.         Local node.Node = listlh_Tail
  81.         If node <> Null Then listlh_Tail = nodeln_Pred
  82.         If listlh_Head = node Then listlh_Head = Null ; list is empty?
  83.         nodeln_List = Null
  84.         Return node
  85. End Function
  86.  
  87.  
  88. ;______________________________________________________________________________
  89. ; FindNode
  90. ;
  91. ; FUNCTION
  92. ;       Searches for a node with a particular ID in given list
  93. ;
  94. ; INPUTS
  95. ;       list    - the list to search
  96. ;       id              - the id to look for
  97. ;
  98. ; RESUT
  99. ;       the first node that id, or Null.
  100. ;
  101. Function FindNode .Node ( list.List, id )
  102.         Local n.Node = listlh_Head
  103.         While n <> Null
  104.                 If nln_Id = id Then Return n
  105.                 n = nln_Succ
  106.         Wend
  107.         Return Null
  108. End Function
  109.  
  110.  
  111. ;______________________________________________________________________________
  112. ; AddHead
  113. ;
  114. ; FUNCTION
  115. ;       Inserts a node before the first in given list
  116. ;
  117. ; INPUTS
  118. ;       list    - the list to put the node in
  119. ;       node    - the node to insert
  120. ;
  121. Function AddHead( list.List, node.Node )
  122.         nodeln_Succ = listlh_Head ; current head becomes next node of node one
  123.         If listlh_Head <> Null Then listlh_Headln_Pred = node ; current head gets node node as prev
  124.         If listlh_Tail =  Null Then listlh_Tail = node         ; no tail? then head is tail
  125.         nodeln_Pred = Null ; node is the new head so it cant have prev node
  126.         listlh_Head = node ; make node node the new head
  127.         nodeln_List = list
  128. End Function
  129.  
  130.  
  131. ;______________________________________________________________________________
  132. ; AddTail
  133. ;
  134. ; FUNCTION
  135. ;       Inserts a node after the last in given list
  136. ;
  137. ; INPUTS
  138. ;       list    - the list to put the node in
  139. ;       node    - the node to insert
  140. ;
  141. Function AddTail( list.List, node.Node )
  142.         nodeln_Pred = listlh_Tail ; current tail becomes prev node if node one
  143.         If listlh_Tail <> Null Then listlh_Tailln_Succ = node ; current tail gets node node as next
  144.         If listlh_Head =  Null Then listlh_Head = node         ; no head? then tail is head
  145.         nodeln_Succ = Null ; node is the new tail so it can't have next node
  146.         listlh_Tail = node ; make node node the new tail
  147.         nodeln_List = list
  148. End Function
  149.  
  150.  
  151. ; Next 4 are for clarity. It's more efficient to use the type fields directly
  152. Function FirstNode .Node ( list.List ) Return listlh_Head: End Function
  153. Function LastNode  .Node ( list.List ) Return listlh_Tail: End Function
  154. Function NextNode  .Node ( node.Node ) Return nodeln_Succ: End Function
  155. Function PrevNode  .Node ( node.Node ) Return nodeln_Pred: End Function
  156.  
  157.  
  158. ;##############################################################################
  159. ; EXAMPLE CODE
  160. ;
  161. Graphics 640,480,0,2
  162. SetFont LoadFont("FixedSys", 8)
  163.  
  164. Function White( a$ )
  165.         Color 255,255,255: Write a
  166. End Function
  167.  
  168. l.List = New List               ; Create a new list
  169.  
  170. ; Now add a few nodes
  171. White "Adding nodes to top         : ": Color 0,255,0
  172. For x = 1 To 10
  173.         n.Node = New Node       ; create the node
  174.         nln_ID = x+20           ; give it an ID for the example
  175.         Write nln_ID + " "
  176.         AddHead( l, n )         ; add node to top of list
  177. Next
  178. Print ""
  179.  
  180.  
  181. White "How the list looks now      : "
  182. Gosub dumplist
  183.  
  184. White "Removing 3 nodes from top   : ": Color 255,0,0
  185. For t = 1 To 3
  186.         n = RemHead( l )        ; remove from list
  187.         Write nln_ID + " "      ; print its value (node still exists!)
  188.         Delete n                        ; destroy node completely
  189. Next
  190. Print ""
  191.  
  192. White "Removing 2 nodes from bottom: ": Color 255,0,0
  193. For t = 1 To 2
  194.         n = RemTail( l )        ; remove from list
  195.         Write nln_ID + " "      ; print the value (node still exists!)
  196.         Delete n                        ; destroy node completely
  197. Next
  198. Print ""
  199.  
  200. ; Show what it looks like now
  201. White "Remaining list              : "
  202. Gosub dumplist
  203.  
  204. ; Move first node to the end
  205. AddTail( l, RemHead( l ) )
  206. White "Moved top node to bottom    : "
  207. Gosub dumplist
  208.  
  209. ; Remove a node by its ID
  210. n.Node = FindNode( l, 24 )
  211. If n <> Null Then Remove( n ): Delete n
  212.  
  213. White "Removed node with id 24     : "
  214. Gosub dumplist
  215.  
  216. WaitKey
  217. End
  218.  
  219.  
  220. .dumplist:
  221.         Color 255,255,0
  222.         n = FirstNode( l )              ; get first node in list
  223.         While n <> Null                 ; while there's nodes
  224.                 Write nln_ID + " "      ; print its value
  225.                 n = NextNode( n )       ; move to next node
  226.         Wend
  227.         Print ""
  228. Return
  229.  
  230.  


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal