Code archives/Miscellaneous/Simple Linked Lists
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
This code is public domain, use how you wish. Use these functions when you want to separate Blitz objects into different lists for processing. You can declare as many lists as you like using any of your own user defined types without the need to modify the BList file. Since we are dealing with pointers to objects, we need to use the Blitz commands Object() and Handle(). Use Handle() when passing a function one of your user defined types. Use Object() when the function returns a user defined type. So… Type Ball Field id End Type list.BList = New BList b.Ball = New Ball AddFront(list,Handle(b)) ptr% = FirstItem(list) b = Object.Ball(ptr) Lets make that code a little smaller… Type Ball Field id End Type list.BList = New BList AddFront(list,Handle(New Ball)) b.Ball = Object.Ball(FirstItem(list)) I hope you find this useful, -dmaz Function List: userTypePtr% = AddFront%( list.Blist, userTypePtr% ) userTypePtr% = AddBack%( list.Blist, userTypePtr% ) trueFalse% = ResetList%( list.BList ) userTypePtr% = NextItem%( list.BList ) userTypePtr% = PrevItem%( list.BList ) userTypePtr% = FirstItem%( list.BList ) userTypePtr% = LastItem%( list.BList ) userTypePtr% = CurrentItem%( list.BList ) userTypePtr% = MoveItem%( fromList.BList, toList.BList ) userTypePtr% = KillItem%( list.BList, node.BNode ) node.BNode = CurrentNode.BNode( list.Blist ) totalItems% = TotalItems%( list.BList ) Example Code: Include "BList.bb" Type Ball Field id Field x# Field y# End Type ; declare the 2 lists list1.BList = New BList list2.BList = New BList ;create 6 objects in the list For i = 0 To 5 b.Ball = Object.Ball(AddFront(list1,Handle(New Ball))) b\id = i Next Print "list1:" : printlist(list1) ;process list1 ResetList(list1) While NextItem(list1) b.Ball = Object.Ball(CurrentItem(list1)) ; move id 4 to list2 If b\id = 4 Then MoveItem(list1,list2) ; delete id 3 later If b\id = 3 Then tmp.BNode = CurrentNode(list1) ; delete id 2. this needs to be the last test, because if ; you delete an object you can no longer perform other tests. If b\id = 2 Then Delete Object.Ball(KillItem(list1,Null)) Wend Delete Object.Ball(KillItem(list1,tmp)) Print "list1: (deleted 2,3; moved 4)" : printlist(list1) Print "list2:" : printlist(list2) ;clear entire list1 While FirstItem(list1) Delete Object.Ball(KillItem(list1,Null)) Wend Print "list1:" : printlist(list1) WaitKey End Function printlist(list.BList) ResetList(list) While NextItem(list) b.Ball = Object.Ball(CurrentItem(list)) Print b\id Wend End Function The full code to include: | |||||
; -BList.bb--------------------------------------------------------------------------------------------------- ; created: July 2004 ; version: 1.1 ; author: dmaz ; Public Domain, use as you wish. ; ; userTypePtr% = AddFront%( list.Blist, userTypePtr% ) ; userTypePtr% = AddBack%( list.Blist, userTypePtr% ) ; trueFalse% = ResetList%( list.BList ) ; userTypePtr% = NextItem%( list.BList ) ; userTypePtr% = PrevItem%( list.BList ) ; userTypePtr% = FirstItem%( list.BList ) ; userTypePtr% = LastItem%( list.BList ) ; userTypePtr% = CurrentItem%( list.BList ) ; userTypePtr% = MoveItem%( fromList.BList, toList.BList ) ; userTypePtr% = KillItem%( list.BList, node.BNode ) ; node.BNode = CurrentNode.BNode( list.Blist ) ; totalItems% = TotalItems%( list.BList ) Type BNode Field prevNode.BNode Field nextNode.BNode Field userTypePtr% End Type Type BList Field firstNode.BNode Field lastNode.BNode Field currentNode.BNode Field totalNodes% End Type ; ------------------------------------------------------------------------------------------------------------ ; AddFront%( list.Blist, userTypePtr% ) ; Discription: ; Inserts object at the beginning of the list. AddFront() DOES NOT change ; the 'current item' pointer to the newly added object. The Parameter ; userTypePtr should be passed using the Blitz Basic command 'Handle()'. ; Returns: ; Pointer to the newly added user defined object. ; Example: ; AddFront(myList,Handle(New MyUserType)) Function AddFront%( list.BList, userTypePtr% ) If list = Null Or userTypePtr = 0 Then Return False n.BNode = New BNode If list\firstNode = Null ; list is empty n\prevNode = Null n\nextNode = Null list\firstNode = n list\lastNode = n Else ; list is not empty n\prevNode = Null n\nextNode = list\firstNode list\firstNode\prevNode = n list\firstNode = n EndIf n\userTypePtr = userTypePtr list\totalNodes = list\totalNodes+1 Return n\userTypePtr End Function ; AddBack%( list.Blist, userTypePtr% ) ; Discription: ; Attaches object at the end of the list. AddBack DOES NOT change ; the 'current item' pointer to the newly added object. The Parameter ; userTypePtr should be passed using the Blitz Basic command 'Handle()'. ; Returns: ; Pointer to the newly added user defined object. ; Example: ; AddBack(myList,Handle(New MyUserType)) Function AddBack%( list.BList, userTypePtr% ) If list = Null Or userTypePtr = 0 Then Return False n.BNode = New BNode If list\firstNode = Null ; list is empty n\prevNode = Null n\nextNode = Null list\firstNode = n list\lastNode = n Else ; list is not empty n\prevNode = list\lastNode n\nextNode = Null list\lastNode\nextNode = n list\lastNode = n EndIf n\userTypePtr = userTypePtr list\totalNodes = list\totalNodes+1 Return n\userTypePtr End Function ; ResetList%( list.BList ) ; Discription: ; Use ResetList() to prepare the list for processing with NextItem() ; ResetList() DOES change the list's 'current item' pointer previous to ; the first item. ; Returns: ; True if successfull, false if it's been passed a null BList ; Example: ; ResetList(myList) Function ResetList( list.BList ) If list = Null Then Return False list\currentNode = Null Return True End Function ; NextItem%( list.BList ) ; Discription: ; NextItem() DOES change the list's 'current item' pointer to the item after the ; current 'current item'. ; Returns: ; If there is a next item, NextItem() will return a pointer to a user defined ; object. Otherwise it will return false. When a function returns a pointer to ; an object you generally want to convert it using the Blitz Basic command ; 'Object()' ; Example: ; ResetList(myList) ; While NextItem(myList) ; u.MyUserType = Object.Bull(CurrentItem(myList)) ; Print u\myField ; Wend Function NextItem%( list.BList ) If list = Null Then Return False If list\currentNode = Null If list\firstNode = Null Return False Else list\currentNode = list\firstNode Return list\currentNode\userTypePtr EndIf Else If list\currentNode\nextNode = Null Return False Else list\currentNode = list\currentNode\nextNode Return list\currentNode\userTypePtr EndIf EndIf End Function ; PrevItem%( list.BList ) ; Discription: ; PrevItem() DOES change the list's 'current item' pointer to the item before the ; current 'current item'. ; Returns: ; If there is a previous item, PrevItem() will return a pointer to a user defined ; object. Otherwise it will return false. When a function returns a pointer to ; an object you generally want to convert it using the Blitz Basic command ; 'Object()' ; Example: Function PrevItem%( list.BList ) If list = Null Then Return False If list\currentNode = Null If list\lastNode = Null Return False Else list\currentNode = list\lastNode Return list\currentNode\userTypePtr EndIf Else If list\currentNode\prevNode = Null Return False Else list\currentNode = list\currentNode\prevNode Return list\currentNode\userTypePtr EndIf EndIf End Function ; FirstItem%( list.BList ) ; Discription: ; FirstItem() DOES change the list's 'current item' pointer to the first item ; the list ; Returns: ; If there are any items in the list, FirstItem() will return a pointer to a ; user defined object. Otherwise it will return false if the list is empty. ; Example: ; u.MyUserType = Object.MyUserType(FirstItem(myList)) Function FirstItem%( list.BList ) If list = Null Then Return False If list\firstNode = Null Return False Else list\currentNode = list\firstNode Return list\currentNode\userTypePtr EndIf End Function ; LastItem%( list.BList ) ; Discription: ; LastItem() DOES change the list's 'current item' pointer to the last item ; the list ; Returns: ; If there are any items in the list, LastItem() will return a pointer to a ; user defined object. Otherwise it will return false if the list is empty. ; Example: ; u.MyUserType = Object.MyUserType(LastItem(myList)) Function LastItem%( list.BList ) If list = Null Then Return False If list\lastNode = Null Return False Else list\currentNode = list\lastNode Return list\currentNode\userTypePtr EndIf End Function ; CurrentItem%( list.BList ) ; Discription: ; CurrentItem() returns a pointer to the current item in the list. ; Returns: ; If there are any items in the list, CurrentItem() will return a pointer to a ; user defined object. Otherwise it will return false if the list is empty or ; ResetList() was just called. ; Example: ; u.MyUserType = Object.MyUserType(CurrentItem(myList)) Function CurrentItem%( list.BList ) If list = Null Then Return False If list\currentNode = Null Return False Else Return list\currentNode\userTypePtr EndIf End Function ; MoveItem%( fromList.BList, toList.BList ) ; Discription: ; Moves the current item from one list to the BACK of another list. ; Returns: ; It will return a pointer to a user defined object. Otherwise it will ; return false if the from list is empty or either list is Null. ; Example: ; MoveItem(myList,myOtherList) Function MoveItem%( fromList.BList, toList.BList ) If fromList = Null Or toList = Null Then Return False If fromList\currentNode = Null Return False Else If fromList\currentNode\nextNode <> Null Then fromList\currentNode\nextNode\prevNode = fromList\currentNode\prevNode If fromList\currentNode\prevNode <> Null Then fromList\currentNode\prevNode\nextNode = fromList\currentNode\nextNode If fromList\firstNode = fromList\currentNode Then fromList\firstNode = fromList\currentNode\nextNode If fromList\lastNode = fromList\currentNode Then fromList\lastNode = fromList\currentNode\prevNode n.BNode = fromList\currentNode fromList\currentNode = fromList\currentNode\prevNode fromList\totalNodes = fromList\totalNodes-1 If toList\firstNode = Null ; list is empty n\prevNode = Null n\nextNode = Null toList\firstNode = n toList\lastNode = n Else ; list is not empty n\prevNode = toList\lastNode n\nextNode = Null toList\lastNode\nextNode = n toList\lastNode = n EndIf toList\totalNodes = toList\totalNodes+1 Return n\userTypePtr EndIf End Function ; KillItem%( list.BList, node.BNode ) ; Discription: ; Removes the node from the list. If itme is Null it then removes the ; 'current item' from the list. ; Returns: ; It will return a pointer to a user defined object so you can delete that. ; Otherwise it will return false if the list is empty or current item and ; the passed node are null. ; Example: ; Delete Object.MyUserType(KillItem(myList,Null)) Function KillItem%( list.BList, node.BNode ) If list = Null Then Return False If node = Null And list\currentNode = Null Return False Else If node = Null Then node = list\currentNode If node\nextNode <> Null Then node\nextNode\prevNode = node\prevNode If node\prevNode <> Null Then node\prevNode\nextNode = node\nextNode If list\firstNode = node Then list\firstNode = node\nextNode If list\lastNode = node Then list\lastNode = node\prevNode If list\currentNode = node Then list\currentNode = node\prevNode userTypePtr% = node\userTypePtr list\totalNodes = list\totalNodes-1 Delete node Return userTypePtr EndIf End Function ; CurrentNode.BNode( list.Blist ) ; Discription: ; Use with KillItem to remove an item that's not pointed to by 'current item'. ; Returns: ; It will return the BNode of the 'current item' ; Example: ; Print CountItems(myList) Function CurrentNode.BNode( list.Blist ) If list = Null Then Return Null Return list\currentNode End Function ; TotalItems%( list.BList ) ; Discription: ; Returns how many items are currently in the list ; Example: ; Print CountItems(myList) Function TotalItems%( list.BList ) If list = Null Then Return False Return list\totalNodes End Function |
Comments
| ||
Updated: userTypePtr% = KillItem%( list.BList, node.BNode ) from userTypePtr% = KillItem%( list.BList ) Added: node.BNode = CurrentNode.BNode( list.Blist ) I also changed the example to match the new updated command. Since you can't use Null as a default value, you have to pass it yourself. changed lines from old example: If b\id = 4 Then MoveItem(list1,list2) ; delete id 2 If b\id = 2 Then Delete Object.Ball(KillItem(list1)) Wend Print "list1: (deleted 2, moved 4)" : printlist(list1) to: If b\id = 4 Then MoveItem(list1,list2) ; delete id 3 later If b\id = 3 Then tmp.BNode = CurrentNode(list1) ; delete id 2. this needs to be the last test, because if ; you delete an object you can no longer perform other tests. If b\id = 2 Then Delete Object.Ball(KillItem(list1,Null)) Wend Delete Object.Ball(KillItem(list1,tmp)) Print "list1: (deleted 2,3; moved 4)" : printlist(list1) |
| ||
I say 2 words : Simply perfect. Thanks dmaz, many thanks. |
| ||
Well, I don't know a about perfect, but thanks Extron. |
| ||
Yes i know, but this is very useful. :) |
| ||
Added: userTypePtr% = PrevItem%( list.BList ) I almost never needed to go backwards in a list before. but a couple of days ago I needed to... |
Code Archives Forum