; 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