brl.linkedlist docs

BlitzMax Forums/BlitzMax Module Tweaks/brl.linkedlist docs

markcw

(Posted 2010) [#1]

This is an update to the brl.linkedlist docs. Most of the examples are based on code by Psyced (Plash).

There are code examples for Tlink and Tlist methods too but ~~I've left them out as~~ that appears to break makedocs... Perhaps code examples for methods is overkill anyway??

Edit: I fixed this, see makedocs tweak.

The files are zipped in a doc folder (but not the module source due to the BSSC license). I've also added the TLink and TList folders.
linkedlist-doc.zip (expired)

I'm posting the module source (from v 1.41) and the patch.

Last edit: 16 Aug 2010

linkedlist.diff

--- linkedlist-old.bmx	2010-07-15 03:07:18.145005443 +0100
+++ linkedlist.bmx	2010-08-16 20:10:44.301518425 +0100
@@ -24,7 +24,7 @@
 End Function
 
 Rem
-bbdoc: Link Object used by TList
+bbdoc: Link object used by TList
 End Rem
 Type TLink
 
@@ -32,28 +32,28 @@
 	Field _succ:TLink,_pred:TLink
 	
 	Rem
-	bbdoc: Returns the Object associated with this Link.
+	bbdoc: Return the object associated with this link
 	End Rem
 	Method Value:Object()
 		Return _value
 	End Method
 
 	Rem
-	bbdoc: Returns the next link in the List.
+	bbdoc: Return the next link in the list
 	End Rem
 	Method NextLink:TLink()
 		If _succ._value<>_succ Return _succ
 	End Method
 
 	Rem
-	bbdoc: Returns the previous link in the List.
+	bbdoc: Return the previous link in the list
 	End Rem
 	Method PrevLink:TLink()
 		If _pred._value<>_pred Return _pred
 	End Method
 
 	Rem
-	bbdoc: Removes the link from the List.
+	bbdoc: Remove the link from the list
 	End Rem
 	Method Remove()
 		_value=Null
@@ -64,7 +64,7 @@
 End Type
 
 Rem
-bbdoc: Enumerator Object use by TList in order to implement Eachin support. 
+Enumerator object used by TList in order to implement EachIn support
 End Rem
 Type TListEnum
 
@@ -84,7 +84,7 @@
 End Type
 
 Rem
-bbdoc: Linked List 
+bbdoc: Linked list
 End Rem
 Type TList
 
@@ -110,7 +110,8 @@
 ?
 	Rem
 	bbdoc: Clear a linked list
-	about: Removes all objects from @list.
+	about:
+	Removes all objects from list.
 	End Rem
 	Method Clear()
 		While _head._succ<>_head
@@ -121,7 +122,7 @@
 	Rem
 	bbdoc: Check if list is empty
 	returns: True if list is empty, else false
-	end rem
+	End Rem
 	Method IsEmpty()
 		Return _head._succ=_head
 	End Method
@@ -129,7 +130,7 @@
 	Rem
 	bbdoc: Check if list contains a value
 	returns: True if list contains @value, else false
-	end rem
+	End Rem
 	Method Contains( value:Object )
 		Local link:TLink=_head._succ
 		While link<>_head
@@ -158,8 +159,8 @@
 	End Method
 
 	Rem
-	bbdoc: Returns the first object in the list
-	about: Returns Null if the list is empty.
+	bbdoc: Return the first object in the list
+	returns: Null if the list is empty
 	End Rem
 	Method First:Object()
 		If IsEmpty() Return
@@ -167,8 +168,8 @@
 	End Method
 
 	Rem
-	bbdoc: Returns the last object in the list
-	about: Returns Null if the list is empty.
+	bbdoc: Return the last object in the list
+	returns: Null if the list is empty
 	End Rem
 	Method Last:Object()
 		If IsEmpty() Return
@@ -176,8 +177,8 @@
 	End Method
 
 	Rem
-	bbdoc: Removes and returns the first object in the list.
-	about: Returns Null if the list is empty.
+	bbdoc: Remove and return the first object in the list
+	returns: Null if the list is empty
 	End Rem
 	Method RemoveFirst:Object()
 		If IsEmpty() Return
@@ -187,8 +188,8 @@
 	End Method
 
 	Rem
-	bbdoc: Removes and returns the last object in the list.
-	about: Returns Null if the list is empty.
+	bbdoc: Remove and return the last object in the list
+	returns: Null if the list is empty
 	End Rem
 	Method RemoveLast:Object()
 		If IsEmpty() Return
@@ -198,21 +199,23 @@
 	End Method
 
 	Rem
-	bbdoc: Returns the first link the list or null if the list is empty.
+	bbdoc: Return the first link in the list
+	returns: Null if the list is empty
 	End Rem
 	Method FirstLink:TLink()
 		If _head._succ<>_head Return _head._succ
 	End Method
 
 	Rem
-	bbdoc: Returns the last link the list or null if the list is empty.
+	bbdoc: Return the last link in the list
+	returns: Null if the list is empty
 	End Rem
 	Method LastLink:TLink()
 		If _head._pred<>_head Return _head._pred
 	End Method
 
 	Rem
-	bbdoc: Inserts an object before the specified list link.
+	bbdoc: Insert an object before the specified list link
 	End Rem
 	Method InsertBeforeLink:TLink( value:Object,succ:TLink )
 		Assert value Else "Can't insert Null object into list"
@@ -226,7 +229,7 @@
 	End Method
 
 	Rem
-	bbdoc: Inserts an object after the specified list link.
+	bbdoc: Insert an object after the specified list link
 	End Rem
 	Method InsertAfterLink:TLink( value:Object,pred:TLink )
 		Assert value Else "Can't insert Null object into list"
@@ -240,7 +243,8 @@
 	End Method
 
 	Rem
-	bbdoc: Returns the first link in the list with the given value, or null if none found.
+	bbdoc: Return the first link in the list with the given value
+	returns: Null if @value not found
 	End Rem
 	Method FindLink:TLink( value:Object )
 		Local link:TLink=_head._succ
@@ -251,8 +255,9 @@
 	End Method
 
 	Rem
-	bbdoc: Returns the value of the link at the given index.
-	about: Throws an exception if the index is out of range (must be 0..list.Count()-1 inclusive).
+	bbdoc: Return the value of the link at the given index
+	about:
+	Throws an exception if @index is out of range (must be 0..list.Count()-1 inclusive).
 	End Rem
 	Method ValueAtIndex:Object( index )
 		Assert index>=0 Else "Object index must be positive"
@@ -267,8 +272,8 @@
 
 	Rem
 	bbdoc: Count list length
-	returns: The numbers of objects in @list.
-	end rem
+	returns: The number of objects in the list
+	End Rem
 	Method Count()
 		Local link:TLink=_head._succ,count
 		While link<>_head
@@ -280,7 +285,8 @@
 
 	Rem
 	bbdoc: Remove an object from a linked list
-	about: Remove scans a list for the specified value and removes its link.
+	about:
+	Scans a list for the specified value and removes its link.
 	End Rem
 	Method Remove( value:Object )
 		Local link:TLink=FindLink( value )
@@ -290,7 +296,7 @@
 	End Method
 	
 	Rem
-	bbdoc: Swap contents with the list specified.
+	bbdoc: Swap contents with the list specified
 	End Rem
 	Method Swap( list:TList )
 		Local head:TLink=_head
@@ -299,7 +305,7 @@
 	End Method
 	
 	Rem
-	bbdoc: Creates an identical copy of the list.
+	bbdoc: Create an identical copy of the list
 	End Rem
 	Method Copy:TList()
 		Local list:TList=New TList
@@ -312,7 +318,7 @@
 	End Method
 
 	Rem
-	bbdoc: Reverse the order of the list.
+	bbdoc: Reverse the order of the list
 	End Rem
 	Method Reverse()
 		Local pred:TLink=_head,succ:TLink=pred._succ
@@ -326,7 +332,7 @@
 	End Method
 	
 	Rem
-	bbdoc: Creates a new list that is the reversed version of this list.
+	bbdoc: Create a new list that is the reversed version of this list
 	End Rem
 	Method Reversed:TList()
 		Local list:TList=New TList
@@ -339,8 +345,9 @@
 	End Method
 
 	Rem
-	bbdoc: Sort a list in either ascending (default) or decending order.
-	about: User types should implement a Compare method in order to be sorted.
+	bbdoc: Sort a list in either ascending (default) or decending order
+	about:
+	User types should implement a Compare method in order to be sorted.
 	End Rem
 	Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
 		Local ccsgn=-1
@@ -407,9 +414,9 @@
 	End Method
 
 	Rem
-	bbdoc: convert a list to an array
+	bbdoc: Convert a list to an array
 	returns: An array of objects
-	end rem
+	End Rem
 	Method ToArray:Object[]()
 		Local arr:Object[Count()],i
 		Local link:TLink=_head._succ
@@ -424,7 +431,7 @@
 	Rem
 	bbdoc: Create a list from an array
 	returns: A new linked list
-	end rem
+	End Rem
 	Function FromArray:TList( arr:Object[] )
 		Local list:TList=New TList
 		For Local i=0 Until arr.length
@@ -438,46 +445,49 @@
 Rem
 bbdoc: Create a linked list
 returns: A new linked list object
-end rem
+End Rem
 Function CreateList:TList()
 	Return New TList
 End Function
 
 Rem
 bbdoc: Clear a linked list
-about: Removes all objects from @list.
-end rem
+about:
+Removes all objects from @list.
+End Rem
 Function ClearList( list:TList )
 	list.Clear
 End Function
 
 Rem
 bbdoc: Count list length
-returns: The numbers of objects in @list.
-end rem
+returns: The number of objects in @list
+End Rem
 Function CountList( list:TList )
 	Return list.Count()
 End Function
 
 Rem
 bbdoc: Check if list is empty
-returns: True if list is empty, else false
-end rem
+returns: True if @list is empty, else false
+End Rem
 Function ListIsEmpty( list:TList )
 	Return list.IsEmpty()
 End Function
 
 Rem
 bbdoc: Check if list contains a value
-returns: True if list contains @value, else false
-end rem
+returns: True if @list contains @value, else false
+End Rem
 Function ListContains( list:TList,value:Object )
 	Return list.Contains( value )
 End Function
 
 Rem
-bbdoc: Sort a list
-end rem
+bbdoc: Sort a list in either ascending (default) or decending order
+about:
+User types should implement a Compare method in order to be sorted.
+End Rem
 Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
 	list.Sort ascending,compareFunc
 End Function
@@ -485,69 +495,71 @@
 Rem
 bbdoc: Create a list from an array
 returns: A new linked list
-end rem
+End Rem
 Function ListFromArray:TList( arr:Object[] )
 	Return TList.FromArray( arr )
 End Function
 
 Rem
-bbdoc: convert a list to an array
+bbdoc: Convert a list to an array
 returns: An array of objects
-end rem
+End Rem
 Function ListToArray:Object[]( list:TList )
 	Return list.ToArray()
 End Function
 
 Rem
 bbdoc: Swap the contents of 2 lists
-end rem
+End Rem
 Function SwapLists( list_x:TList,list_y:TList )
 	list_x.Swap list_y
 End Function
 
 Rem
-bbdoc: Reverse the order of elements of a list
-end rem
+bbdoc: Reverse the order of elements in a list
+End Rem
 Function ReverseList( list:TList )
 	list.Reverse
 End Function
 
 Rem
 bbdoc: Find a link in a list
-returns: The link containting @value
-end rem
+returns: The first link in the list containing @value, or Null if not found
+End Rem
 Function ListFindLink:TLink( list:TList,value:Object )
 	Return list.FindLink( value )
 End Function
 
 Rem
-bbdoc: Add an object to a linked list
+bbdoc: Add an object to the end of a linked list
 returns: A link object
-end rem
+End Rem
 Function ListAddLast:TLink( list:TList,value:Object )
 	Return list.AddLast( value )
 End Function
 
 Rem
-bbdoc: Add an object to a linked list
+bbdoc: Add an object to the start of a linked list
 returns: A link object
-end rem
+End Rem
 Function ListAddFirst:TLink( list:TList,value:Object )
 	Return list.AddFirst( value )
 End Function
 
 Rem
-bbdoc: Remove an object from a linked list
-about: #ListRemove scans a list for the specified value and removes its link.
-end rem
+bbdoc: Find and remove an object from a linked list
+about:
+Scans a list for the specified value and removes its link.
+End Rem
 Function ListRemove( list:TList,value:Object )
 	list.Remove value
 End Function
 
 Rem
 bbdoc: Remove an object from a linked list
-about: #RemoveLink is more efficient than #ListRemove.
-end rem
+about:
+More efficient than #ListRemove.
+End Rem
 Function RemoveLink( link:TLink )
 	link.Remove
 End Function

linkedlist.bmx

Strict

Rem
bbdoc: Data structures/Linked lists
End Rem
Module BRL.LinkedList

ModuleInfo "Version: 1.07"
ModuleInfo "Author: Mark Sibly"
ModuleInfo "License: Blitz Shared Source Code"
ModuleInfo "Copyright: Blitz Research Ltd"
ModuleInfo "Modserver: BRL"

ModuleInfo "History: 1.07 Release"
ModuleInfo "History: Changed Reverse to maintain TLink stability"
ModuleInfo "History: 1.06 Release"
ModuleInfo "History: Added optional CompareFunc parameter to Sort"
ModuleInfo "History: 1.05 Release"
ModuleInfo "History: Sort now swaps links instead of values"

Function CompareObjects( o1:Object,o2:Object )
	Return o1.Compare( o2 )
End Function

Rem
bbdoc: Link object used by TList
End Rem
Type TLink

	Field _value:Object
	Field _succ:TLink,_pred:TLink
	
	Rem
	bbdoc: Return the object associated with this link
	End Rem
	Method Value:Object()
		Return _value
	End Method

	Rem
	bbdoc: Return the next link in the list
	End Rem
	Method NextLink:TLink()
		If _succ._value<>_succ Return _succ
	End Method

	Rem
	bbdoc: Return the previous link in the list
	End Rem
	Method PrevLink:TLink()
		If _pred._value<>_pred Return _pred
	End Method

	Rem
	bbdoc: Remove the link from the list
	End Rem
	Method Remove()
		_value=Null
		_succ._pred=_pred
		_pred._succ=_succ
	End Method

End Type

Rem
Enumerator object used by TList in order to implement EachIn support
End Rem
Type TListEnum

	Field _link:TLink

	Method HasNext()
		Return _link._value<>_link
	End Method

	Method NextObject:Object()
		Local value:Object=_link._value
		Assert value<>_link
		_link=_link._succ
		Return value
	End Method

End Type

Rem
bbdoc: Linked list
End Rem
Type TList

	Field _head:TLink
	
	Method _pad()
	End Method

	Method New()
		_head=New TLink
		_head._succ=_head
		_head._pred=_head
		_head._value=_head
	End Method
	
?Not Threaded
	Method Delete()
		Clear
		_head._value=Null
		_head._succ=Null
		_head._pred=Null
	End Method
?
	Rem
	bbdoc: Clear a linked list
	about:
	Removes all objects from list.
	End Rem
	Method Clear()
		While _head._succ<>_head
			_head._succ.Remove
		Wend
	End Method

	Rem
	bbdoc: Check if list is empty
	returns: True if list is empty, else false
	End Rem
	Method IsEmpty()
		Return _head._succ=_head
	End Method
	
	Rem
	bbdoc: Check if list contains a value
	returns: True if list contains @value, else false
	End Rem
	Method Contains( value:Object )
		Local link:TLink=_head._succ
		While link<>_head
			If link._value.Compare( value )=0 Return True
			link=link._succ
		Wend
		Return False
	End Method

	Rem
	bbdoc: Add an object to the start of the list
	returns: A link object
	End Rem
	Method AddFirst:TLink( value:Object )
		Assert value Else "Can't insert Null object into list"
		Return InsertAfterLink( value,_head )
	End Method

	Rem
	bbdoc: Add an object to the end of the list
	returns: A link object
	End Rem
	Method AddLast:TLink( value:Object )
		Assert value Else "Can't insert Null object into list"
		Return InsertBeforeLink( value,_head )
	End Method

	Rem
	bbdoc: Return the first object in the list
	returns: Null if the list is empty
	End Rem
	Method First:Object()
		If IsEmpty() Return
		Return _head._succ._value
	End Method

	Rem
	bbdoc: Return the last object in the list
	returns: Null if the list is empty
	End Rem
	Method Last:Object()
		If IsEmpty() Return
		Return _head._pred._value
	End Method

	Rem
	bbdoc: Remove and return the first object in the list
	returns: Null if the list is empty
	End Rem
	Method RemoveFirst:Object()
		If IsEmpty() Return
		Local value:Object=_head._succ._value
		_head._succ.remove
		Return value
	End Method

	Rem
	bbdoc: Remove and return the last object in the list
	returns: Null if the list is empty
	End Rem
	Method RemoveLast:Object()
		If IsEmpty() Return
		Local value:Object=_head._pred._value
		_head._pred.remove
		Return value
	End Method

	Rem
	bbdoc: Return the first link in the list
	returns: Null if the list is empty
	End Rem
	Method FirstLink:TLink()
		If _head._succ<>_head Return _head._succ
	End Method

	Rem
	bbdoc: Return the last link in the list
	returns: Null if the list is empty
	End Rem
	Method LastLink:TLink()
		If _head._pred<>_head Return _head._pred
	End Method

	Rem
	bbdoc: Insert an object before the specified list link
	End Rem
	Method InsertBeforeLink:TLink( value:Object,succ:TLink )
		Assert value Else "Can't insert Null object into list"
		Local link:TLink=New TLink
		link._value=value
		link._succ=succ
		link._pred=succ._pred
		link._pred._succ=link
		succ._pred=link
		Return link
	End Method

	Rem
	bbdoc: Insert an object after the specified list link
	End Rem
	Method InsertAfterLink:TLink( value:Object,pred:TLink )
		Assert value Else "Can't insert Null object into list"
		Local link:TLink=New TLink
		link._value=value
		link._pred=pred
		link._succ=pred._succ
		link._succ._pred=link
		pred._succ=link
		Return link
	End Method

	Rem
	bbdoc: Return the first link in the list with the given value
	returns: Null if @value not found
	End Rem
	Method FindLink:TLink( value:Object )
		Local link:TLink=_head._succ
		While link<>_head
			If link._value.Compare( value )=0 Return link
			link=link._succ
		Wend
	End Method

	Rem
	bbdoc: Return the value of the link at the given index
	about:
	Throws an exception if @index is out of range (must be 0..list.Count()-1 inclusive).
	End Rem
	Method ValueAtIndex:Object( index )
		Assert index>=0 Else "Object index must be positive"
		Local link:TLink=_head._succ
		While link<>_head
			If Not index Return link._value
			link=link._succ
			index:-1
		Wend
		RuntimeError "List index out of range"
	End Method

	Rem
	bbdoc: Count list length
	returns: The number of objects in the list
	End Rem
	Method Count()
		Local link:TLink=_head._succ,count
		While link<>_head
			count:+1
			link=link._succ
		Wend
		Return count
	End Method

	Rem
	bbdoc: Remove an object from a linked list
	about:
	Scans a list for the specified value and removes its link.
	End Rem
	Method Remove( value:Object )
		Local link:TLink=FindLink( value )
		If Not link Return False
		link.Remove
		Return True
	End Method
	
	Rem
	bbdoc: Swap contents with the list specified
	End Rem
	Method Swap( list:TList )
		Local head:TLink=_head
		_head=list._head
		list._head=head
	End Method
	
	Rem
	bbdoc: Create an identical copy of the list
	End Rem
	Method Copy:TList()
		Local list:TList=New TList
		Local link:TLink=_head._succ
		While link<>_head
			list.AddLast link._value
			link=link._succ
		Wend
		Return list
	End Method

	Rem
	bbdoc: Reverse the order of the list
	End Rem
	Method Reverse()
		Local pred:TLink=_head,succ:TLink=pred._succ
		Repeat
			Local link:TLink=succ._succ
			pred._pred=succ
			succ._succ=pred
			pred=succ
			succ=link
		Until pred=_head
	End Method
	
	Rem
	bbdoc: Create a new list that is the reversed version of this list
	End Rem
	Method Reversed:TList()
		Local list:TList=New TList
		Local link:TLink=_head._succ
		While link<>_head
			list.AddFirst link._value
			link=link._succ
		Wend
		Return list
	End Method

	Rem
	bbdoc: Sort a list in either ascending (default) or decending order
	about:
	User types should implement a Compare method in order to be sorted.
	End Rem
	Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
		Local ccsgn=-1
		If ascending ccsgn=1
		
		Local insize=1
		Repeat
			Local merges
			Local tail:TLink=_head
			Local p:TLink=_head._succ

			While p<>_head
				merges:+1
				Local q:TLink=p._succ,qsize=insize,psize=1
				
				While psize<insize And q<>_head
					psize:+1
					q=q._succ
				Wend

				Repeat
					Local t:TLink
					If psize And qsize And q<>_head
						Local cc=CompareFunc( p._value,q._value ) * ccsgn
						If cc<=0
							t=p
							p=p._succ
							psize:-1
						Else
							t=q
							q=q._succ
							qsize:-1
						EndIf
					Else If psize
						t=p
						p=p._succ
						psize:-1
					Else If qsize And q<>_head
						t=q
						q=q._succ
						qsize:-1
					Else
						Exit
					EndIf
					t._pred=tail
					tail._succ=t
					tail=t
				Forever
				p=q
			Wend
			tail._succ=_head
			_head._pred=tail

			If merges<=1 Return

			insize:*2
		Forever
	End Method
		
	Method ObjectEnumerator:TListEnum()
		Local enum:TListEnum=New TListEnum
		enum._link=_head._succ
		Return enum
	End Method

	Rem
	bbdoc: Convert a list to an array
	returns: An array of objects
	End Rem
	Method ToArray:Object[]()
		Local arr:Object[Count()],i
		Local link:TLink=_head._succ
		While link<>_head
			arr[i]=link._value
			link=link._succ
			i:+1
		Wend
		Return arr
	End Method

	Rem
	bbdoc: Create a list from an array
	returns: A new linked list
	End Rem
	Function FromArray:TList( arr:Object[] )
		Local list:TList=New TList
		For Local i=0 Until arr.length
			list.AddLast arr[i]
		Next
		Return list
	End Function

End Type

Rem
bbdoc: Create a linked list
returns: A new linked list object
End Rem
Function CreateList:TList()
	Return New TList
End Function

Rem
bbdoc: Clear a linked list
about:
Removes all objects from @list.
End Rem
Function ClearList( list:TList )
	list.Clear
End Function

Rem
bbdoc: Count list length
returns: The number of objects in @list
End Rem
Function CountList( list:TList )
	Return list.Count()
End Function

Rem
bbdoc: Check if list is empty
returns: True if @list is empty, else false
End Rem
Function ListIsEmpty( list:TList )
	Return list.IsEmpty()
End Function

Rem
bbdoc: Check if list contains a value
returns: True if @list contains @value, else false
End Rem
Function ListContains( list:TList,value:Object )
	Return list.Contains( value )
End Function

Rem
bbdoc: Sort a list in either ascending (default) or decending order
about:
User types should implement a Compare method in order to be sorted.
End Rem
Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
	list.Sort ascending,compareFunc
End Function

Rem
bbdoc: Create a list from an array
returns: A new linked list
End Rem
Function ListFromArray:TList( arr:Object[] )
	Return TList.FromArray( arr )
End Function

Rem
bbdoc: Convert a list to an array
returns: An array of objects
End Rem
Function ListToArray:Object[]( list:TList )
	Return list.ToArray()
End Function

Rem
bbdoc: Swap the contents of 2 lists
End Rem
Function SwapLists( list_x:TList,list_y:TList )
	list_x.Swap list_y
End Function

Rem
bbdoc: Reverse the order of elements in a list
End Rem
Function ReverseList( list:TList )
	list.Reverse
End Function

Rem
bbdoc: Find a link in a list
returns: The first link in the list containing @value, or Null if not found
End Rem
Function ListFindLink:TLink( list:TList,value:Object )
	Return list.FindLink( value )
End Function

Rem
bbdoc: Add an object to the end of a linked list
returns: A link object
End Rem
Function ListAddLast:TLink( list:TList,value:Object )
	Return list.AddLast( value )
End Function

Rem
bbdoc: Add an object to the start of a linked list
returns: A link object
End Rem
Function ListAddFirst:TLink( list:TList,value:Object )
	Return list.AddFirst( value )
End Function

Rem
bbdoc: Find and remove an object from a linked list
about:
Scans a list for the specified value and removes its link.
End Rem
Function ListRemove( list:TList,value:Object )
	list.Remove value
End Function

Rem
bbdoc: Remove an object from a linked list
about:
More efficient than #ListRemove.
End Rem
Function RemoveLink( link:TLink )
	link.Remove
End Function

And the zip contents below.

intro.bbdoc (added "Lists vs. arrays")

A linked list allows you to efficiently add and remove objects to and from a collection of objects.

To create a linked list, use the #CreateList command.

Add objects to a linked list using #ListAddFirst or #ListAddLast. Both commands return a link object which can be used to later remove the object with the #RemoveLink command. You can also remove objects with the #ListRemove command. However this is not as efficient as using #RemoveLink because the list must first be searched for the object to be removed.

To visit all the objects in a linked list, you can use an #EachIn loop.

+Lists vs. arrays

Index based access in a linked list is much slower than in an array, since a list must iterate through internal links to find the specific index whereas an array can directly access any index.

"So why use linked lists at all?" you might ask. Inserting a value into the middle of an array is an 'expensive' operation, we must move all items after the insert position down in the array by one, then insert the new value in the space created. In a list however, all we have to do is redirect the pointers between links.

So when you need to make many changes to data use a list and when you need to access data randomly, or if speed is critical, use an array. To make many insertions and deletions to an array you can convert it to a list with #ListFromArray and then back to an array with #ListToArray.

clearlist.bmx

' clearlist.bmx

list:TList=CreateList()

ListAddFirst( list,"item 1" )
ListAddFirst( list,"item 2" )

ClearList( list )

For item$=EachIn list
	Print item
Next

countlist.bmx

' countlist.bmx

list:TList=CreateList()

ListAddFirst( list,"item 1" )
ListAddFirst( list,"item 2" )

Print CountList( list )

createlist.bmx

' createlist.bmx

' create a list to hold some objects

list:TList=CreateList()

' add some string objects to the list

ListAddLast( list,"one" )
ListAddLast( list,"two" )
ListAddLast( list,"three" )

' enumerate all the strings in the list

For item$=EachIn list
	Print item
Next

listaddfirst.bmx

' listaddfirst.bmx

list:TList=CreateList()

ListAddFirst( list,"item 1" )
ListAddFirst( list,"item 2" )

For item$=EachIn list
	Print item
Next

listaddlast.bmx

' listaddlast.bmx

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )

For item$=EachIn list
	Print item
Next

listcontains.bmx

' listcontains.bmx

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )

Print ListContains( list,"item 2" )
Print ListContains( list,"item 3" )

listfromarray.bmx

' listfromarray.bmx

Local array:String[]=["item 1","item 2","item 3"]

list:TList=ListFromArray( array )

For item$=EachIn list
	Print item
Next

listisempty.bmx

' listisempty.bmx

list:TList=CreateList()

Print ListIsEmpty( list )

ListAddFirst( list,"item 1" )

Print ListIsEmpty( list )

listremove.bmx

' listremove.bmx

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )
ListAddLast( list,"item 3" )

ListRemove( list,"item 2" )

For item$=EachIn list
	Print item
Next

listtoarray.bmx

' listtoarray.bmx

Local array:Object[]

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )
ListAddLast( list,"item 3" )

array=ListToArray( list )

For index=0 To array.length-1
	Print String( array[index] )
Next

removelink.bmx

' removelink.bmx

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )
ListAddLast( list,"item 3" )

link:TLink=ListFindLink( list,"item 2" )

If link<>Null Then RemoveLink( link )

For item$=EachIn list
	Print item
Next

reverselist.bmx

' reverselist.bmx

list:TList=CreateList()

ListAddLast( list,"item 1" )
ListAddLast( list,"item 2" )
ListAddLast( list,"item 3" )

ReverseList( list )

For item$=EachIn list
	Print item
Next

sortlist.bmx

' sortlist.bmx

list:TList=CreateList()

ListAddLast( list,"item 3" )
ListAddLast( list,"item 1" )
ListAddLast( list,"item 4" )
ListAddLast( list,"item 2" )

SortList( list )

For item$=EachIn list
	Print item
Next

swaplists.bmx

' swaplists.bmx

list:TList=ListFromArray( ["item 1","item 2","item 3"] )

swap:TList=ListFromArray( ["one","two","three"] )

SwapLists( list,swap )

For item$=EachIn list
	Print item
Next

For item=EachIn swap
	Print item
Next

TLink folder

nextlink.bmx

' nextlink.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

link:TLink=list.FindLink( "item 2" )

Print String( link.NextLink().Value() )

prevlink.bmx

' prevlink.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

link:TLink=list.FindLink( "item 2" )

Print String( link.PrevLink().Value() )

value.bmx

' value.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

link:TLink=list.FindLink( "item 2" )

Print String( link.Value() )

TList folder

copy.bmx

' copy.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

clone:TList=list.Copy()

For item$=EachIn clone
	Print item
Next

first.bmx

' first.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

Print String( list.First() )

firstlink.bmx

' firstlink.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

link:TLink=list.FirstLink()

Print String( link.Value() )

insertafterlink.bmx

' insertafterlink.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )
list.AddLast( "item 4" )

list.Remove( "item 3" )

link:TLink=list.FindLink( "item 2" )

If link<>Null Then list.InsertAfterLink( "new item 3!",link )

For item$=EachIn list
	Print item
Next

last.bmx

' last.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

Print String( list.Last() )

lastlink.bmx

' lastlink.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

link:TLink=list.LastLink()

Print String( link.Value() )

removefirst.bmx

' removefirst.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

list.RemoveFirst()

For item$=EachIn list
	Print item
Next

removelast.bmx

' removelast.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

list.RemoveLast()

For item$=EachIn list
	Print item
Next

reversed.bmx

' reversed.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

reversed:TList=list.Reversed()

For item$=EachIn reversed
	Print item
Next

valueatindex.bmx

' valueatindex.bmx

list:TList=New TList

list.AddLast( "item 1" )
list.AddLast( "item 2" )
list.AddLast( "item 3" )

Print String( list.ValueAtIndex( 1 ) )

plash

(Posted 2010) [#2]

There are code examples for the Tlink and Tlist methods too but I've left them out as that appears to break makedocs... Perhaps code examples for methods is overkill anyway??

Personally, I don't think one can be too exhaustive when it comes to documentation - hence why I added examples to each method on the wiki.

markcw

(Posted 2010) [#3]

So Psyced is Plash then? These are great code examples by the way.

I'm not sure but perhaps you're right. I'll let Mark Sibly decide then. :)

Edit: moved TList and Tlink examples to first post.

plash

(Posted 2010) [#4]

So Psyced is Plash then?

Yes.

I should also note that the last time we tried to properly format and document the BRL modules, it was ignored.

I seriously want this to work out, but it's just not going to happen with Mark not adding the changes. We clearly need an organized solution - as suggested previously, an official repository where users could make changes would be ideal.
Though, again, lack of response from Mark/BRL isn't exactly helping.

markcw

(Posted 2010) [#5]

I should also note that the last time we tried to properly format and document the BRL modules, it was ignored.

Well actually that made it into v 1.32, see here. So you can get changes added if you go about it the right way. Sadly there is no advice given on how to contribute so we have to figure it out ourselves.

degac

(Posted 2010) [#6]

Why dont' use the 'manual' section of the site to add examples and comments?
It's the only 'stable' solution at the moment and it doesnt' require hacks/changes to the modules source.
I added some examples to the CreateMap command more than 1 year ago (related to another markcw's thread) - not the best implementation probably...

plash

(Posted 2010) [#7]

@degac: That's not a real solution, as the main text is not changeable by users and the content on the online manual is only online.

degac

(Posted 2010) [#8]

Ok, but the 'bad' thing is you need to *manually* change some source code... not everyone can do this without problems - unless these changes become officials.

plash

(Posted 2010) [#9]

Ok, but the 'bad' thing is you need to *manually* change some source code... not everyone can do this without problems - unless these changes become officials.

I would gladly do this if there was a better (guaranteed) avenue to have them added to a release.

Writing docs in code is far easier than using WikiBooks or the online manual.

markcw

(Posted 2010) [#10]

Just did a major revision of everything today. I'm finished this module now (well... maybe).

Who was John Galt?

(Posted 2010) [#11]

I seriously hope these mods make it into a release. Many thanks for your efforts, guys.