Can I add lists together?

BlitzMax Forums/BlitzMax Programming/Can I add lists together?

Arowx

(Posted 2008) [#1]

Hi there, just playing with some code and realised that I'm looping through one list copying all of the elemets to a new list.

In effect I'm creating a large list built up from lots of little ones.

So is there a relativly easy way to do this?

E.g. ListA:+ ListB.Copy()

I understand that under the hood I need to add the first link from ListB's copy to the end of list A, just can't see A simple way to do it.

plash

(Posted 2008) [#2]

SuperStrict

Framework brl.standardio
Import brl.linkedlist


Local dest:TList = New(TList), from:TList = New(TList)
dest.AddLast("Hello")
from.AddLast("World!")

Print "Success: " + AddListToList(dest, from)

For Local val:String = EachIn dest
	
	Print "Value: " + val
	
Next

Function AddListToList:Int(dest:TList, from:TList)
	
	If dest = Null Or from = Null Or from.Count() = 0 Then Return False
	
	For Local obj:Object = EachIn from
		
		dest.AddLast(obj)
		
	Next
	
	Return True
	
End Function

plash

(Posted 2008) [#3]

I can think of a way to do it with the TLink's.. but I don't know if using the same reference for a link in two lists is a good idea.

Arowx

(Posted 2008) [#4]

Hi plash that's what I'm doing at the moment, only not as functional!

Well you can create a copy of the 'from' list with fromList.Copy() which should prevent a spaghetti list mess (as long as TList.Copy() does a deep copy)!

But how would you add them together using TLinks?

Grey Alien

(Posted 2008) [#5]

Nice thanks Plash, simple but effective. Code snaffled.

plash

(Posted 2008) [#6]

EDIT: See below...

Arowx

(Posted 2008) [#7]

Very nice, just the business!

plash

(Posted 2008) [#8]

Eeek! I forgot about the rest of the objects in the list.. here is the correct version:

SuperStrict

Framework brl.standardio
Import brl.linkedlist

Local dest:TList = New(TList), from:TList = New(TList)
dest.AddLast("Hello")
dest.AddLast("And goodbye!")

from.AddLast("World!")
from.AddLast("....!")
from.AddLast("Longer?")
from.AddLast("Sweet.")

Print "Success: " + ListAppendList(dest, from)

For Local val:String = EachIn dest
	
	Print "Value: " + val
	
Next

Function ListAppendList:Int(dest:TList, from:TList)
  Local copy:TList
	
	If dest = Null Or from = Null Or from.Count() = 0 Then Return False
	
	copy = from.Copy()
	InsertListBeforeLink(copy, dest._head)
	
	Return True
	
End Function

Function InsertListBeforeLink(thislist:TList, beforethis:TLink)
  Local this:TLink = thislist.FirstLink(), last:TLink = thislist.LastLink()
	
	'this._succ = beforethis
	this._pred = beforethis._pred
	this._pred._succ = this
	
	last._succ = beforethis
	beforethis._pred = last
	
End Function

Grey Alien

(Posted 2008) [#9]

I don't get it. What was wrong with the first version? Could this second version have any memory leaks?

plash

(Posted 2008) [#10]

Could this second version have any memory leaks?

Not sure..

What was wrong with the first version?

Speed, maybe. I'm not certain which way is faster, but he wanted one that could use a copy of a list.. which you could also use the first one for, but since you already have the list there is no point.

tonyg

(Posted 2008) [#11]

Not sure if this is any better :

Local list1:TList=CreateList()
Local list2:TList=CreateList()
ListAddLast list1,"one"
ListAddLast list2,"two"
Local array1:Object[]=ListToArray(list1)
Local array2:Object[]=ListToArray(list2)
Local array3:Object[]=array1+array2

Local list3:TList=ListFromArray(array3)
For Local all:Object = EachIn list3
   Print String(all)
Next

Arowx

(Posted 2008) [#12]

Hi gents,

I thought appending a copy of the list would be faster than incramentally adding each element to the list...

So I wrote this as a test...

SuperStrict

Framework brl.Graphics
Import brl.max2d
Import brl.standardio
Import brl.linkedlist
Import brl.d3d7max2d

Graphics 800,600

Global console:TList = New TList
Global state:String = "Starting"

Local dest:TList = New(TList), from:TList = New(TList)

Const LISTSIZE:Int = 999999

Output "Creating lists "+LISTSIZE+" elements in length"

For Local value:Int = 0 To LISTSIZE
	dest.AddLast("A"+value)
	from.AddLast("B"+value)
Next

Status "Copying the lists for test purposes..."
Local testDest1:TList = dest.Copy()
Local testDest2:TList = dest.Copy()
Status "Running tests..."

Local timestamp1:Int = MilliSecs()
	AddListToList(testDest1, from)
Local timeStamp2:Int = MilliSecs()
	ListAppendList(testDest2, from)
Local timeStamp3:Int = MilliSecs()

Local timeToAddLists:Int = timeStamp2-timeStamp1
Local timeToAppendLists:Int = timeStamp3-timeStamp2

Output "Time to Add: "+timeToAddLists
Output "Time to AppendLists: "+timeToAppendLists

Output "Verifying that lists match in content forwards..."

Local listLinkA:TLink = testDest1.FirstLink()
Local listLinkB:TLink = testDest2.FirstLink()

Global Verified:Int = False

Local stringA:String = String(listLinkA.Value())
Local stringB:String = String(listLinkB.Value())

Local counter:Int = 0

While stringA.contains(stringB)
	listLinkA = listLinkA.NextLink()
	listLinkB = listLinkB.NextLink()
	
	If (counter Mod (LISTSIZE/100)) = 0 Then
		Status counter+":"+stringA +" = "+stringB
	EndIf
	counter:+1
	
	If listLinkA = Null Or listLinkB = Null Then
		If listLinkA = listLinkB Then verified = True
		Status stringA+" ? "+stringB
		Exit
	EndIf
	stringA = String(listLinkA.Value())
	stringB = String(listLinkB.Value())
Wend

Output "Verification Forward Ended"

If verified = True Then 
	Output "Lists Match"
Else
	Output "Lists failed Verification"
EndIf


Output "Verifying that lists match in content backwards..."

listLinkA = testDest1.LastLink()
listLinkB = testDest2.LastLink()

While stringA.contains(stringB)
	listLinkA = listLinkA.PrevLink()
	listLinkB = listLinkB.PrevLink()
	
	If (counter Mod (LISTSIZE/100)) = 0 Then
		Status counter+":"+stringA +" = "+stringB
	EndIf
	counter:+1
	
	If listLinkA = Null Or listLinkB = Null Then
		If listLinkA = listLinkB Then verified = True
		Status stringA+" ? "+stringB
		Exit
	EndIf
	stringA = String(listLinkA.Value())
	stringB = String(listLinkB.Value())
Wend

Output "Verification Backwards Ended"

If verified = True Then 
	Output "Lists Match"
Else
	Output "Lists failed Verification"
EndIf




While Not AppTerminate()
	display()
Wend


'simple console 
Function display()
	Cls
	Local x:Int = 0
	Local y:Int = 0
	DrawText(state,x,y)
	y:+20
	For Local str:String = EachIn console
		DrawText(str,x,y)
		y:+12
	Next
	Flip
End Function

Function output(text:String)
	console.AddLast(text)
	display()
End Function

Function status(text:String)
	state = text
	display()
End Function

Function AddListToList:Int(dest:TList, from:TList)
	
	If dest = Null Or from = Null Or from.Count() = 0 Then Return False
	
	For Local obj:Object = EachIn from
		dest.AddLast(obj)
	Next
	
	Return True
	
End Function

Function ListAppendList:Int(dest:TList, from:TList)
  Local copy:TList
	
	If dest = Null Or from = Null Or from.Count() = 0 Then Return False
	
	copy = from.Copy()
	AppendLink(copy.FirstLink(), dest.LastLink())
	
	Return True
	
End Function

Function AppendLink(appendee:TLink, appended:TLink)
	
	appended._succ = appendee
	appendee._pred = appended
	
End Function

I get the following result for 999,999 items in list:
Time to Add: 754ms
Time to Append: 583ms

So with the copy there is very little between the two.

Plash not sure why you were using 4 operations to link two lists:

Linked list A <-> B

A -> B A._succ = B
A <- B B._pred = A

Unless I'm missing something?

plash

(Posted 2008) [#13]

The linkedlist that Max has (as I understand it) is a chained loop, where list._head is the link of the chain that sits between the last and first link.

To *add* one list to another you actually have to insert it after the last link and before the head.

Thus:

Set predecessor of the first link from the copied list to the last link in the appendto list, and set the successor of the last link, from the appendto list, to the first link from the copied list.

Now set the predecessor for the head of the appendto list to the last link in the copied list, and set the successor of the last link, from the copied list, to the head of the appendto list.

EDIT: Basically:
copied.first.pred = appendto.last
appendto.last.succ = copied.first

appendto.head.pred = copied.last
copied.last.succ = appendto.head

Make sense?

Arowx

(Posted 2008) [#14]

OK I think I get it...

First <-Linked List-> Last
^.............................^
|...............................|
'--------- head ---------'

;o)

Grey Alien

(Posted 2008) [#15]

Interesting approach TonyG. Would be good to speed test that too, I guess it might be slower due to the conversion to array.

tonyg

(Posted 2008) [#16]

True but the original post asked for 'relatively easy'.

big10p

(Posted 2008) [#17]

Well, it's certainly an easier way. :)