Linked List with Iterator

This code has been declared by its author to be Public Domain code.

Linked List with Iterator by Yasha

2011

This is just an extremely simple list container that allows you to store lists of items without resorting to either 1) the builtin Type lists, or 2) ugly workarounds like extendable banks or "next object" fields.

The interface is, for the most part, based on BlitzMax's BRL.LinkedList module, in order to make usage as simple as possible (the code itself is all original, so it's all safely PD), although there are a few changes to the names. The most notable missing feature is a Sort function, since Blitz Classic doesn't support function pointers (without hacks).

Since Blitz Classic also doesn't have any way to provide EachIn functionality to a class (...not having classes), looping is handled by a construct based on this recent forum discussion, which uses Iterator objects (similar to the way it's done in C++ or old-style Java). Example usage:

Local l.LList = CreateList()

...

Local i.Iterator = GetIterator(l)
While EachIn(i)
    Local elem.SomeType = Object.SomeType(i\Value)
    ...
    If ... Then IteratorBreak(i):Exit

    If ... Then IteratorRemove(i)
Wend

GetIterator obtains an iterator for the specified list. With each loop, EachIn gets the next value in the list (which is always an integer, which usually you'll want to use with Object/Handle) and makes it available through iterator\Value. At the end of the loop the iterator is disconnected from the list, so in most programs you don't need to think about cleaning up after it; however, if you want to break out of the loop you need to manually disconnect it with IteratorBreak before exiting (or just Delete it).

During an EachIn loop, you can remove an item from the list being iterated over with IteratorRemove, which will adjust the list so that the next iteration of the loop will work as expected. If the element was storing an object, you'll need to clean it up manually as B3D provides no garbage collection, and the list doesn't know what the values it holds represent (and is thus not able to free them for you).

This entry duplicates functionality that has almost certainly been submitted many times before, and a linked list is so pathetically trivial that even a beginner could make this with their eyes shut. With this in mind, the reason for posting this library is mainly so that I can post later Code Archives entries that just Include "LList.bb" and not have to include the same boilerplate rubbish each time!

; Double-linked list container class
;====================================

; with thanks to MusicianKool, for concept and issue fixes


Type LList
	Field head_.ListNode
	Field tail_.ListNode
End Type

Type ListNode
	Field pv_.ListNode
	Field nx_.ListNode
	Field Value
End Type

Type Iterator
	Field Value
	Field l_.LList
	Field cn_.ListNode, cni_
End Type


;Create a new LList object
Function CreateList.LList()
	Local l.LList = New LList
	
	l\head_ = New ListNode
	l\tail_ = New ListNode
	
	l\head_\nx_ = l\tail_		;End caps
	l\head_\pv_ = l\head_		;These make it more or less safe to iterate freely
	l\head_\Value = 0
	
	l\tail_\nx_ = l\tail_
	l\tail_\pv_ = l\head_
	l\tail_\Value = 0
	
	Return l
End Function

;Free a list and all elements (not any values)
Function FreeList(l.LList)
	ClearList l
	Delete l\head_
	Delete l\tail_
	Delete l
End Function

;Remove all the elements from a list (does not free values)
Function ClearList(l.LList)
	Local n.ListNode = l\head_\nx_
	While n <> l\tail_
		Local nx.ListNode = n\nx_
		Delete n
		n = nx
	Wend
	l\head_\nx_ = l\tail_
	l\tail_\pv_ = l\head_
End Function

;Count the number of elements in a list (slow)
Function ListLength(l.LList)
	Local i.Iterator = GetIterator(l), elems
	While EachIn(i)
		elems = elems + 1
	Wend
	Return elems
End Function

;Return True if a list contains a given value
Function ListContains(l.LList, Value)
	Return (ListFindNode(l, Value) <> Null)
End Function

;Create a linked list from the intvalues in a bank (slow)
Function ListFromBank.LList(bank)
	Local l.LList = CreateList()
	Local size = BankSize(bank), p
	
	For p = 0 To size - 4 Step 4
		ListAddLast l, PeekInt(bank, p)
	Next
	
	Return l
End Function

;Create a bank containing all the values in a list (slow)
Function ListToBank(l.LList)
	Local size = ListLength(l) * 4
	Local bank = CreateBank(size)
	
	Local i.Iterator = GetIterator(l), p = 0
	While EachIn(i)
		PokeInt bank, p, i\Value
		p = p + 4
	Wend
	
	Return bank
End Function

;Swap the contents of two list objects
Function SwapLists(l1.LList, l2.LList)
	Local tempH.ListNode = l1\head_, tempT.ListNode = l1\tail_
	l1\head_ = l2\head_
	l1\tail_ = l2\tail_
	l2\head_ = tempH
	l2\tail_ = tempT
End Function

;Create a new list containing the same values as the first
Function CopyList.LList(lo.LList)
	Local ln.LList = CreateList()
	Local i.Iterator = GetIterator(lo) : While EachIn(i)
		ListAddLast ln, i\Value
	Wend
	Return ln
End Function

;Reverse the order of elements of a list
Function ReverseList(l.LList)
	Local n1.ListNode, n2.ListNode, tmp.ListNode
	
	n1 = l\head_
	n2 = l\head_\nx_
	
	While n1 <> l\tail_
		n1\pv_ = n2
		tmp = n2\nx_
		n2\nx_ = n1
		n1 = n2
		n2 = tmp
	Wend
	
	tmp = l\head_
	l\head_ = l\tail_
	l\tail_ = tmp
	
	l\head_\pv_ = l\head_
	l\tail_\nx_ = l\tail_
End Function

;Search a list to retrieve the first node with the given value
Function ListFindNode.ListNode(l.LList, Value)
	Local n.ListNode = l\head_\nx_
	
	While n <> l\tail_
		If n\Value = Value Then Return n
		n = n\nx_
	Wend
	
	Return Null
End Function

;Append a value to the end of a list (fast) and return the node
Function ListAddLast.ListNode(l.LList, Value)
	Local n.ListNode = New ListNode
	
	n\pv_ = l\tail_\pv_
	n\nx_ = l\tail_
	n\Value = Value
	
	l\tail_\pv_ = n
	n\pv_\nx_ = n
	
	Return n
End Function

;Attach a value to the start of a list (fast) and return the node
Function ListAddFirst.ListNode(l.LList, Value)
	Local n.ListNode = New ListNode
	
	n\pv_ = l\head_
	n\nx_ = l\head_\nx_
	n\Value = Value
	
	l\head_\nx_ = n
	n\nx_\pv_ = n
	
	Return n
End Function

;Remove the first occurence of the given value from a list
Function ListRemove(l.LList, Value)
	Local n.ListNode = ListFindNode(l, Value)
	If n <> Null Then RemoveListNode n
End Function

;Remove a node from a list
Function RemoveListNode(n.ListNode)
	n\pv_\nx_ = n\nx_
	n\nx_\pv_ = n\pv_
	Delete n
End Function

;Return the value of the element at the given position from the start of the list,
;or backwards from the end of the list for a negative index
Function ValueAtIndex(l.LList, index)
	Local n.ListNode = ListNodeAtIndex(l, index)
	If n <> Null Then Return n\Value : Else Return 0
End Function

;Return the ListNode at the given position from the start of the list, or backwards
;from the end of the list for a negative index, or Null if invalid
Function ListNodeAtIndex.ListNode(l.LList, index)
	Local e, n.ListNode
	
	If index >= 0
		n = l\head_
		For e = 0 To index
			n = n\nx_
		Next
		If n = l\tail_ Then n = Null	;Beyond the end of the list - not valid
		
	Else	;Negative index - count backward
		n = l\tail_
		For e = 0 To index Step -1
			n = n\pv_
		Next
		If n = l\head_ Then n = Null	;Before the start of the list - not valid
		
	EndIf
	
	Return n
End Function

;Replace a value at the given position (added by MusicianKool)
Function ReplaceValueAtIndex(l.LList,index,value)
	Local n.ListNode = ListNodeAtIndex(l,index)
	If n <> Null Then n\Value = value:Else Return 0
End Function

;Remove and return a value at the given position (added by MusicianKool)
Function RemoveNodeAtIndex(l.LList,index)
	Local n.ListNode = ListNodeAtIndex(l,index),tval
	If n <> Null Then tval = n\Value:RemoveListNode(n):Return tval:Else Return 0
End Function

;Retrieve the first value from a list
Function ListFirst(l.LList)
	If l\head_\nx_ <> l\tail_ Then Return l\head_\nx_\Value
End Function

;Retrieve the last value from a list
Function ListLast(l.LList)
	If l\tail_\pv_ <> l\head_ Then Return l\tail_\pv_\Value
End Function

;Remove the first element from a list, and return its value
Function ListRemoveFirst(l.LList)
	Local val
	If l\head_\nx_ <> l\tail_
		val = l\head_\nx_\Value
		RemoveListNode l\head_\nx_
	EndIf
	Return val
End Function

;Remove the last element from a list, and return its value
Function ListRemoveLast(l.LList)
	Local val
	If l\tail_\pv_ <> l\head_
		val = l\tail_\pv_\Value
		RemoveListNode l\tail_\pv_
	EndIf
	Return val
End Function

;Insert a value into a list before the specified node, and return the new node
Function InsertBeforeNode.ListNode(Value, n.ListNode)
	Local bef.ListNode = New ListNode
	
	bef\pv_ = n\pv_
	bef\nx_ = n
	bef\Value = Value
	
	n\pv_ = bef
	bef\pv_\nx_ = bef
	
	Return bef
End Function

;Insert a value into a list after the specified node, and return then new node
Function InsertAfterNode.ListNode(Value, n.ListNode)
	Local aft.ListNode = New ListNode
	
	aft\nx_ = n\nx_
	aft\pv_ = n
	aft\Value = Value
	
	n\nx_ = aft
	aft\nx_\pv_ = aft
	
	Return aft
End Function

;Get an iterator object to use with a loop
;This function means that most programs won't have to think about deleting iterators manually
;(in general only a small, constant number will be created)
Function GetIterator.Iterator(l.LList)
	Local i.Iterator
	
	If l = Null Then RuntimeError "Cannot create Iterator for Null"
	
	For i = Each Iterator		;See if there's an available iterator at the moment
		If i\l_ = Null Then Exit
	Next
	
	If i = Null Then i = New Iterator	;If there wasn't, create one
	
	i\l_ = l
	i\cn_ = l\head_
	i\cni_ = -1
	i\Value = 0		;No especial reason why this has to be anything, but meh
	
	Return i
End Function

;Use as the argument to While to iterate over the members of a list
Function EachIn(i.Iterator)
	
	i\cn_ = i\cn_\nx_
	
	If i\cn_ <> i\l_\tail_		;Still items in the list
		i\Value = i\cn_\Value
		i\cni_ = i\cni_ + 1
		Return True
		
	Else
		i\l_ = Null		;Disconnect from the list, having reached the end
		i\cn_ = Null
		i\cni_ = -1
		Return False
		
	EndIf
End Function

;Remove from the containing list the element currently pointed to by an iterator
Function IteratorRemove(i.Iterator)
	If (i\cn_ <> i\l_\head_) And (i\cn_ <> i\l_\tail_)
		Local temp.ListNode = i\cn_
		
		i\cn_ = i\cn_\pv_
		i\cni_ = i\cni_ - 1
		i\Value = 0
		
		RemoveListNode temp
		
		Return True
	Else
		Return False
	EndIf
End Function

;Call this before breaking out of an EachIn loop, to disconnect the iterator from the list
Function IteratorBreak(i.Iterator)
	i\l_ = Null
	i\cn_ = Null
	i\cni_ = -1
	i\Value = 0
End Function


;~IDEal Editor Parameters:
;~F#5#A#10#18#2A#32#3E#47#4C#58#66#6F#78#8F#9B#A9#B7#BD#C5#CC
;~F#E3#E9#EF#F4#F9#103#10D#11B#12B#13F#152#163
;~C#Blitz3D

Comments

MusicianKool

2011

This is perfect. The only thing i see as a problem is

;Search a list to retrieve the first node with the given value
Function ListFindNode.ListNode(l.LList, Value)
	Local n.ListNode = l\head_\nx_
	
	While n <> l\tail_
		If n\Value = Value Then Return n
	Wend
	
	Return Null
End Function

needs:
While n <> l\tail_
If n\Value = Value Then Return n
------>n = n\nx_
Wend

Yasha

2011

Nice catch, thank you!

...yeah you can tell I didn't exactly test this thoroughly (*cough* at all *cough*).

MusicianKool

2011

here is an addition, to treat the linked list like an array.

;Replace a value at index)
Function ReplaceValueAtIndex(l.LList,index,value)
	Local n.ListNode = ListNodeAtIndex(l,index)
	If n <> Null Then n\Value = value:Else Return 0
End Function

Function RemoveNodeAtIndex(l.LList,index)
	Local n.ListNode = ListNodeAtIndex(l,index),tval
	If n <> Null Then tval = n\Value:RemoveListNode(n):Return tval:Else Return 0
End Function

MusicianKool

2011

Found another issue, or safety for the insert before and after.

;Insert a value into a list before the specified node, and return the new node
Function InsertBeforeNode.ListNode(Value, n.ListNode)
	Local l.LList = n\Parent
	If l\head_ = n Then Return ListAddFirst(l,Value$)
		
	Local bef.ListNode = New ListNode
	
	bef\pv_ = n\pv_
	bef\nx_ = n
	bef\Value = Value
	bef\Parent = n\Parent
	
	n\pv_ = bef
	bef\pv_\nx_ = bef
	
	Return bef
End Function

;Insert a value into a list after the specified node, and return then new node
Function InsertAfterNode.ListNode(Value, n.ListNode)
	Local l.LList = n\Parent
	If l\tail_ = n Then Return ListAddLast(l,Value)
	Local aft.ListNode = New ListNode
	
	aft\nx_ = n\nx_
	aft\pv_ = n
	aft\Value = Value
	aft\Parent = n\Parent
	
	n\nx_ = aft
	aft\nx_\pv_ = aft
	
	Return aft
End Function

Yasha

2011

Thanks for the additions.

I should point out that the ListNode type as given doesn't have a "Parent" member any more (it did in the original forum thread) as I felt it was more or less unnecessary, and more importantly, meant SwapLists would cease to be O(1) and become O(n).

I'm not sure there are many uses for SwapLists, but I thought it was more useful than a parent field since I can't think of any sensible uses for that one at all.

MusicianKool

2011

Found one more thing.

;Create a new list containing the same values as the first
Function CopyList.LList(lo.LList)
	Local ln.LList = New LList
	Local i.Iterator = GetIterator(lo) : While EachIn(i)
		ListAddLast ln, i\Value
	Wend
	Return ln
End Function

should be.

;Create a new list containing the same values as the first
Function CopyList.LList(lo.LList)
	Local ln.LList = CreateList()
	Local i.Iterator = GetIterator(lo) : While EachIn(i)
		ListAddLast ln, i\Value
	Wend
	Return ln
End Function

Yasha

2011

Updated. Thanks for noticing that last one - that's pretty important!

Yasha

2012

Couple of extension packages -

Higher-order list functions using function pointers ("List-Fptr.bb"):

; Linked list higher-order extension
;====================================

; Higher order list-handling functions, using native function pointers
; For use with FastPointer: <a href="http://www.fastlibs.com/index.php" target="_blank">http://www.fastlibs.com/index.php</a>

; Every function pointer used by this library is expected to take one integer argument,
; and return nothing. Any return values should be returned into the "LList_HOF_Return"
; global variable, since FastPointer doesn't allow for return values from function pointers.

; For the copy/free methods, Map, Foreach, Filter and Partition the function parameter
; should be the list element to be processed. For Sort  and the Fold functions, it should
; be expected to be an eight-byte bank containing the two "real" parameters. For Unfold,
; it should be the seed integer.


Include "LList.bb"	;Basic list library - get it here: <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2873" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2873</a>


; Return register: callbacks should put their "return value" here
Global LList_HOF_ReturnValue


; Basic list functions
;======================

; Create a new LList with the given copy and free methods
; These methods should operate on the individual values contained in the list
Function CreateListCFF.LList(copyF = 0, freeF = 0)
	Local l.LList = CreateList()
	SetListMethodsF l, copyF, freeF
	Return l
End Function

; Free a list, invoking its destructor method on the elements if present
Function FreeListF(l.LList)
	ClearListF l : FreeList l
End Function

; Clear all elements of a list, invoking the destructor method on each
Function ClearListF(l.LList)
	Local freeF = GetListFreeMethodF(l)
	If freeF Then ListForEachF l, freeF
	ClearList l
End Function

; Create a copy of a list, using the copy method to copy each element
Function CopyListF.LList(lo.LList)
	Return ListMapF(lo, GetListCopyMethodF(lo))
End Function

; Set the copy and free methods for an existing list
Function SetListMethodsF(l.LList, copyF, freeF)
	l\head_\Value = copyF : l\tail_\Value = freeF	;Not otherwise in use
End Function

; Examine the current Copy method of a list
Function GetListCopyMethodF(l.LList)
	Return l\head_\Value
End Function

; Examine the current Free method of a list
Function GetListFreeMethodF(l.LList)
	Return l\tail_\Value
End Function


; Higher-order list functions (accept function pointers directly)
;=================================================================

;Sort a list in-place, using F:(ELEM -> ELEM -> Int) as a compare function (insertion sort)
Function SortListF(l.LList, F)
	If l\head_\nx_ = l\tail_ Or l\head_\nx_ = l\tail_\pv_ Then Return
	
	Local bk = CreateBank(8), n.ListNode, p.ListNode = l\tail_\pv_, pv.ListNode
	l\head_\nx_\pv_ = l\head_ : l\head_\nx_\nx_ = l\tail_
	
	While p <> l\head_
		pv = l\head_
		n = pv\nx_ : While n <> l\tail_
			PokeInt bk, 0, p\Value : PokeInt bk, 4, n\Value : CallFunctionVarInt F, bk
			If LList_HOF_ReturnValue < 0
				pv\nx_ = p : p\nx_ = n
				Exit
			EndIf
			pv = n : n = n\nx_
		Wend
		If n = l\tail_ Then pv\nx_ = p : p\nx_ = n
		
		p = p\pv_
	Wend
	
	pv = l\head_ : n = pv\nx_ : While n <> l\tail_
		n\pv_ = pv : pv = n : n = n\nx_
	Wend
	l\tail_\pv_ = pv
	
	FreeBank bk
End Function

; Apply F:(ELEM -> ELEM) to each element of the input list, returning a list of the results
Function ListMapF.LList(lo.LList, F)
	Local ln.LList = CreateListCFF(GetListCopyMethodF(lo), GetListFreeMethodF(lo))
	Local i.Iterator = GetIterator(lo) : While EachIn(i)
		ListAddLast ln, ListF_CallAndReturn_(F, i\Value)
	Wend
	Return ln
End Function

; Apply F:(ELEM -> ()) to each element of the input list, without storing the results
Function ListForEachF(l.LList, F)
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		CallFunctionVarInt F, i\Value
	Wend
End Function

; Left fold operation on l, using F:(ELEM -> ELEM -> Int) with initial value n
Function ListFoldF(l.LList, F, n)
	Local acc = n, i.Iterator = GetIterator(l), bk = CreateBank(8)
	While EachIn(i)
		PokeInt bk, 0, acc : PokeInt bk, 4, i\Value
		acc = ListF_CallAndReturn_(F, bk)
	Wend
	FreeBank bk : Return acc
End Function

; Right fold operation on l, using F:(ELEM -> ELEM -> Int) with initial value n
Function ListFoldRightF(l.LList, F, n)
	Local acc = n, bk = CreateBank(8), node.ListNode = l\tail_\nx_
	While node <> l\head_
		PokeInt bk, 0, acc : PokeInt bk, 4, node\Value
		acc = ListF_CallAndReturn_(F, bk)
		node = node\pv_
	Wend
	FreeBank bk : Return acc
End Function

; Left unfold operation, building a list of values starting with seed (see SRFI-1)
Function ListUnFoldF.LList(seed, stopF, elemF, nextF, tailF = 0)
	Local l.LList = CreateListCFF(0, 0)
	While Not ListF_CallAndReturn_(stopF, seed)
		ListAddLast l, ListF_CallAndReturn_(elemF, seed)
		seed = ListF_CallAndReturn_(nextF, seed)
	Wend
	If tailF Then ListAddLast l, ListF_CallAndReturn_(tailF, seed)
	Return l
End Function

; Right unfold operation, building a list of values starting with seed (see SRFI-1)
Function ListUnFoldRightF.LList(seed, stopF, elemF, nextF)
	Local l.LList = CreateListCFF(0, 0)
	While Not ListF_CallAndReturn_(stopF, seed)
		ListAddFirst l, ListF_CallAndReturn_(elemF, seed)
		seed = ListF_CallAndReturn_(nextF, seed)
	Wend
	Return l
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning a list of those elements returning true
; Elements are NOT copied with the copy method
Function ListFilterF.LList(l.LList, testF)
	Local ret.LList = CreateListCFF(GetListCopyMethodF(l), GetListFreeMethodF(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If ListF_CallAndReturn_(testF, i\Value) Then ListAddLast ret, i\Value
	Wend
	Return ret
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning a list of those elements returning false
; Elements are NOT copied with the copy method
Function ListFilterOutF.LList(l.LList, testF)
	Local ret.LList = CreateListCFF(GetListCopyMethodF(l), GetListFreeMethodF(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If Not ListF_CallAndReturn_(testF, i\Value) Then ListAddLast ret, i\Value
	Wend
	Return ret
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning two lists in the out-parameter array
; out[0] contains the elements for which testF returned true
; out[1] contains the elements for which testF returned false
; Elements are NOT copied with the copy method
Function ListPartitionF(l.LList, testF, out.LList[1])
	out[0] = CreateListCFF(GetListCopyMethodF(l), GetListFreeMethodF(l))
	out[1] = CreateListCFF(GetListCopyMethodF(l), GetListFreeMethodF(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If ListF_CallAndReturn_(testF, i\Value)
			ListAddLast out[0], i\Value
		Else
			ListAddLast out[1], i\Value
		EndIf
	Wend
End Function


; Helper function (allow direct use of "returned" values)
Function ListF_CallAndReturn_(F, v)
	CallFunctionVarInt F, v : Return LList_HOF_ReturnValue
End Function


;~IDEal Editor Parameters:
;~F#1D#24#29#30#35#3A#3F#48#66#6F#76#80#8B#96#A1#AB#B7#C5
;~C#Blitz3D

Higher-order list functions using closures ("List-Lambda.bb"):

; Linked list higher-order extension (closure)
;==============================================

; Higher order list-handling functions, using Lambda functions (closures)


Include "LList.bb"		;Basic list library - get it here: <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2873" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2873</a>
Include "Lambda.bb"		;Lambda library - get it here:     <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=2992" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=2992</a>


; Basic list functions
;======================

; Create a new LList with the given copy and free methods
; These methods should operate on the individual values contained in the list
Function CreateListCFL.LList(copyF = 0, freeF = 0)
	Local l.LList = CreateList()
	SetListMethodsL l, copyF, freeF
	Return l
End Function

; Free a list, invoking its destructor method on the elements if present
Function FreeListL(l.LList)
	ClearListL l : FreeList l
End Function

; Clear all elements of a list, invoking the destructor method on each
Function ClearListL(l.LList)
	Local freeF = GetListFreeMethodL(l)
	If freeF Then ListForEachL l, freeF
	ClearList l
End Function

; Create a copy of a list, using the copy method to copy each element
Function CopyListL.LList(lo.LList)
	Return ListMapL(lo, GetListCopyMethodL(lo))
End Function

; Set the copy and free methods for an existing list
Function SetListMethodsL(l.LList, copyF, freeF)
	l\head_\Value = copyF : l\tail_\Value = freeF	;Not otherwise in use
End Function

; Examine the current Copy method of a list
Function GetListCopyMethodL(l.LList)
	Return l\head_\Value
End Function

; Examine the current Free method of a list
Function GetListFreeMethodL(l.LList)
	Return l\tail_\Value
End Function


; Higher-order list functions (accept function pointers directly)
;=================================================================

;Sort a list in-place, using F:(ELEM -> ELEM -> Int) as a compare function (insertion sort)
Function SortListL(l.LList, F)
	If l\head_\nx_ = l\tail_ Or l\head_\nx_ = l\tail_\pv_ Then Return
	
	Local n.ListNode, p.ListNode = l\tail_\pv_, pv.ListNode
	l\head_\nx_\pv_ = l\head_ : l\head_\nx_\nx_ = l\tail_
	
	While p <> l\head_
		pv = l\head_
		n = pv\nx_ : While n <> l\tail_
			If CallFunc(F, p\Value, n\Value) < 0
				pv\nx_ = p : p\nx_ = n
				Exit
			EndIf
			pv = n : n = n\nx_
		Wend
		If n = l\tail_ Then pv\nx_ = p : p\nx_ = n
		
		p = p\pv_
	Wend
	
	pv = l\head_ : n = pv\nx_ : While n <> l\tail_
		n\pv_ = pv : pv = n : n = n\nx_
	Wend
	l\tail_\pv_ = pv
End Function

; Apply F:(ELEM -> ELEM) to each element of the input list, returning a list of the results
Function ListMapL.LList(lo.LList, F)
	Local ln.LList = CreateListCFL(GetListCopyMethodL(lo), GetListFreeMethodL(lo))
	Local i.Iterator = GetIterator(lo) : While EachIn(i)
		ListAddLast ln, CallFunc(F, i\Value)
	Wend
	Return ln
End Function

; Apply F:(ELEM -> ()) to each element of the input list, without storing the results
Function ListForEachL(l.LList, F)
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		CallFunc F, i\Value
	Wend
End Function

; Left fold operation on l, using F:(ELEM -> ELEM -> Int) with initial value n
Function ListFoldL(l.LList, F, n)
	Local acc = n, i.Iterator = GetIterator(l)
	While EachIn(i)
		acc = CallFunc(F, acc, i\Value)
	Wend
	Return acc
End Function

; Right fold operation on l, using F:(ELEM -> ELEM -> Int) with initial value n
Function ListFoldRightL(l.LList, F, n)
	Local acc = n, node.ListNode = l\tail_\nx_
	While node <> l\head_
		acc = CallFunc(F, acc, node\Value)
		node = node\pv_
	Wend
	Return acc
End Function

; Left unfold operation, building a list of values starting with seed (see SRFI-1)
Function ListUnFoldL.LList(seed, stopF, elemF, nextF, tailF = 0)
	Local l.LList = CreateListCFL(0, 0)
	While Not CallFunc(stopF, seed)
		ListAddLast l, CallFunc(elemF, seed)
		seed = CallFunc(nextF, seed)
	Wend
	If tailF Then ListAddLast l, CallFunc(tailF, seed)
	Return l
End Function

; Right unfold operation, building a list of values starting with seed (see SRFI-1)
Function ListUnFoldRightL.LList(seed, stopF, elemF, nextF)
	Local l.LList = CreateListCFL(0, 0)
	While Not CallFunc(stopF, seed)
		ListAddFirst l, CallFunc(elemF, seed)
		seed = CallFunc(nextF, seed)
	Wend
	Return l
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning a list of those elements returning true
; Elements are NOT copied with the copy method
Function ListFilterL.LList(l.LList, testF)
	Local ret.LList = CreateListCFL(GetListCopyMethodL(l), GetListFreeMethodL(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If CallFunc(testF, i\Value) Then ListAddLast ret, i\Value
	Wend
	Return ret
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning a list of those elements returning false
; Elements are NOT copied with the copy method
Function ListFilterOutL.LList(l.LList, testF)
	Local ret.LList = CreateListCFL(GetListCopyMethodL(l), GetListFreeMethodL(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If Not CallFunc(testF, i\Value) Then ListAddLast ret, i\Value
	Wend
	Return ret
End Function

; Apply testF:(ELEM -> Bool) to each element of the input list, returning two lists in the out-parameter array
; out[0] contains the elements for which testF returned true
; out[1] contains the elements for which testF returned false
; Elements are NOT copied with the copy method
Function ListPartitionL(l.LList, testF, out.LList[1])
	out[0] = CreateListCFL(GetListCopyMethodL(l), GetListFreeMethodL(l))
	out[1] = CreateListCFL(GetListCopyMethodL(l), GetListFreeMethodL(l))
	Local i.Iterator = GetIterator(l) : While EachIn(i)
		If CallFunc(testF, i\Value)
			ListAddLast out[0], i\Value
		Else
			ListAddLast out[1], i\Value
		EndIf
	Wend
End Function


;~IDEal Editor Parameters:
;~F#10#17#1C#23#28#2D#32#3B#56#5F#66#6F#79#84#8F#99#A5
;~C#Blitz3D

They add exactly the same features, just designed to work with different callback systems (native function pointers for the first, functor objects for the second):

-- Copy/Free methods (so that copying or freeing a list can cleanup its owned objects, or create new ones for the new list)

-- Sort
-- Map
-- ForEach
-- Left and right folds
-- Left and right unfolds (see SRFI-1 for the direct source & usage)
-- Positive, negative and partition filters

Both of these require MikhailV's FastPointer DLL (the latter only indirectly), which is why they aren't in the main include file: they can't be implemented in "pure" Blitz Basic.

You can use both in the same project, if you wish: the names are suffixed with an F or an L respectively so that there are no namespace clashes.

Code Archives Forum