Merge two lists

BlitzMax Forums/BlitzMax Programming/Merge two lists

Czar Flavius

(Posted 2011) [#1]

Is there a FAST way of merging two TLists into one? Or appending one after the other?

Otherwise I am having to return a TList/array of TLists and iterate through two levels.

Jesse

(Posted 2011) [#2]

No, I had to extend functionality into Tlist to add that as I wanted to do a quick chop and connect list for the solitaire game I was making.

AdamRedwoods

(Posted 2011) [#3]

couldn't you just take the link from the last of one and point it to the first link of another?

ziggy

(Posted 2011) [#4]

I think this is a good example:

SuperStrict

'We get two separated TList objects:
Global List1:TList = New TList
Global List2:TList = New TList
Print List2.Count()

'Add items to the first list:
List1.AddLast("one")
List1.AddLast("two")
List1.AddLast("three")

'Add items to the second list:
List2.AddLast("four")
List2.AddLast("five")
List2.AddLast("six")

'We merge the two lists in one:
Local ResultList:TList = MergeTwoList(List1, List2)

'Show results:
Print "ResultList contains " + ResultList.Count() + " items."

For Local Str:String = EachIn ResultList
	Print Str
Next


Print
Print "---- reverse display -----"
Print

Global lnk:TLink = ResultList.lastLink()
While lnk
	Print String(lnk.value())
	lnk = lnk.PrevLink()
Wend

End

'This function appends one list to another.
Function AppendList(Source:TList, Additional:TList)
	Local lastlink:TLink = source.LastLink()
	If lastlink = Null Then
		Source._head = Additional._head
	Else
		lastlink._succ = Additional._head._succ
		Additional._head._succ._pred = lastlink
		Local LastLink2:TLink = Additional.lastlink()
		LastLink2._succ = Source._head
		Source._head._pred = LastLink2
	End If
	Additional._head = New TLink
	Additional._head._succ = Additional._head
	Additional._head._pred = Additional._head
	Additional._head._value = Additional._head
End Function

'This function joins 2 lists and creates a new one
Function MergeTwoList:TList(List1:TList, List2:TList)
	Local TempList:TList = New TList
	AppendList(TempList, List1)
	AppendList(TempList, List2)
	Return TempList
End Function

EDIT: Notice that after the merge operation, List2 is no longer valid. Anyway, fix should be easy to implement.

EDIT2: Fixed. It no longer leaves List2 in a corrupted state. Notice that the merge operation clears List2. Thats intended to keep data consitency.

Last edited 2011

Last edited 2011

Czar Flavius

(Posted 2011) [#5]

Thank you.

ziggy

(Posted 2011) [#6]

I've just fixed a small issue (see above) that was causing a crash if one of the lists was empty. It's fast but clears the merged lists once the merge operation is done. This is by design.

Jesse

(Posted 2011) [#7]

@ziggy
the list is not quite consolidated when it's merged:


SuperStrict

'We get two separated TList objects:
Global List1:TList = New TList
Global List2:TList = New TList
Print List2.Count()

'Add items to the first list:
List1.AddLast("one")
List1.AddLast("two")
List1.AddLast("three")

'Add items to the second list:
List2.AddLast("four")
List2.AddLast("five")
List2.AddLast("six")

'We merge the two lists in one:
Local ResultList:TList = MergeTwoList(List1, List2)

'Show results:
Print "ResultList contains " + ResultList.Count() + " items."

For Local Str:String = EachIn ResultList
	Print Str
Next


Print
Print "---- reverse display -----"
Print

Global lnk:TLink = ResultList.lastLink()
While lnk
	Print String(lnk.value())
	lnk = lnk.PrevLink()
Wend



End

'This function appends one list to another.
Function AppendList(Source:TList, Additional:TList)
	Local lastlink:TLink = source.LastLink()
	If lastlink = Null Then
		Source._head = Additional._head
	Else
		lastlink._succ = Additional._head._succ
		Local LastLink2:TLink = Additional.lastlink()
		LastLink2._succ = Source._head
	End If
	Additional._head = New TLink
	Additional._head._succ = Additional._head
	Additional._head._pred = Additional._head
	Additional._head._value = Additional._head
End Function

'This function joins 2 lists and creates a new one
Function MergeTwoList:TList(List1:TList, List2:TList)
	Local TempList:TList = New TList
	AppendList(TempList, List1)
	AppendList(TempList, List2)
	Return TempList
End Function

ziggy

(Posted 2011) [#8]

I was missing an assignation for the reverse _succ _pred. This should fix this:

SuperStrict

'We get two separated TList objects:
Global List1:TList = New TList
Global List2:TList = New TList
Print List2.Count()

'Add items to the first list:
List1.AddLast("one")
List1.AddLast("two")
List1.AddLast("three")

'Add items to the second list:
List2.AddLast("four")
List2.AddLast("five")
List2.AddLast("six")

'We merge the two lists in one:
Local ResultList:TList = MergeTwoList(List1, List2)

'Show results:
Print "ResultList contains " + ResultList.Count() + " items."

For Local Str:String = EachIn ResultList
	Print Str
Next


Print
Print "---- reverse display -----"
Print

Global lnk:TLink = ResultList.lastLink()
While lnk
	Print String(lnk.value())
	lnk = lnk.PrevLink()
Wend

End

'This function appends one list to another.
Function AppendList(Source:TList, Additional:TList)
	Local lastlink:TLink = source.LastLink()
	If lastlink = Null Then
		Source._head = Additional._head
	Else
		lastlink._succ = Additional._head._succ
		Additional._head._succ._pred = lastlink
		Local LastLink2:TLink = Additional.lastlink()
		LastLink2._succ = Source._head
		Source._head._pred = LastLink2
	End If
	Additional._head = New TLink
	Additional._head._succ = Additional._head
	Additional._head._pred = Additional._head
	Additional._head._value = Additional._head
End Function

'This function joins 2 lists and creates a new one
Function MergeTwoList:TList(List1:TList, List2:TList)
	Local TempList:TList = New TList
	AppendList(TempList, List1)
	AppendList(TempList, List2)
	Return TempList
End Function

Ah right, I was forgetting to modify the appended list _head._predd pointer too. It should be ok now.

Last edited 2011

Jesse

(Posted 2011) [#9]