Array list implementation

BlitzMax Forums/BlitzMax Programming/Array list implementation

ziggy

(Posted 2009) [#1]

Sometimes working with arrays is faster than working with linked lists, specially when you're going to get items with an specific index, etc... With this in mind, I've coded this array-based implementation of lists:

SuperStrict
rem
	bbdoc: Array based replacement for linked lists.
end rem
Type TListArray Extends TList

	Field InternalArray:Object[]

	Method New()
		Self._head = Null
	End Method
	
	Rem
		bbdoc:Add an object to the start of the list
	End Rem
	Method AddFirst:TLink( value:Object )
		If InternalArray = Null Then
			InternalArray = New Object[1]
		Else
			InternalArray = (New Object[1]) + InternalArray[0..InternalArray.Length]
		End If
		InternalArray[0] = Value
	End Method
	
	Rem
		bbdoc:Add an object to the end of the list
	End Rem
	Method AddLast:TLink( value:Object )
		If InternalArray = Null Then
			InternalArray = New Object[1]
		Else
			InternalArray = InternalArray[0..InternalArray.Length + 1] ' + New Object[0]
		End If
		InternalArray[InternalArray.Length - 1] = Value
		
	End Method
	
	Rem
		bbdoc:Check if list contains a value
	End Rem
	Method Contains:Int(Value:Object)
		If InternalArray = Null Then Return False
		For Local Obj:Object = EachIn InternalArray
			If Obj = Value Then Return True
		Next
		Return False
	End Method

	Rem
		bbdoc:Creates an identical copy of the list.
	End Rem
	Method Copy:TList()
		
		Local LA:TListArray = New TListArray
		
		If InternalArray = Null Then
			Return LA
		Else
		
			LA.InternalArray = New Object[Self.InternalArray.length]
			For Local i:Int = 0 Until InternalArray.Length
				LA.InternalArray[i] = InternalArray[i]
			Next
			Return LA
		EndIf
	End Method

	Rem
		bbdoc:Returns a link object that contains the value item, if the item exists in the internal array.<br>The returned link instance does not have any real link information as this collection class is not based on a linked list.<br>This method is available here for compatibility reasons.
	End Rem
	Method FindLink:TLink(Value:Object)
		If InternalArray = Null Then Return Null
		For Local Obj:Object = EachIn InternalArray
			If Obj = Value Then
				Local Link:TLink = New TLink
				Link._succ = Null
				Link._pred = Null
				Link._value = Value
				Return Link
			End If
		Next
		Return Null
	End Method
	
	Rem
		bbdoc:Returns the first object in the list
	End Rem
	Method First:Object()
		If InternalArray = Null Then
			Return Null
		Else
			If InternalArray.Length >= 1 Then
				Return InternalArray[0]
			Else
				Return Null
			EndIf
		EndIf
	End Method

	Rem
		bbdoc:Returns a link with the value of the first object in the internal array.<br>This link object does not have any real link information as this is not a real linked list class.
	End Rem
	Method FirstLink:TLink()
		If InternalArray = Null Then
			Return Null
		Else
			If InternalArray.Length >= 1 Then
				Local Link:TLink = New TLink
				Link._pred = Null
				Link._succ = Null
				Link._value = InternalArray[0]
				Return Link
			Else
				Return Null
			EndIf
		EndIf
		
	End Method

	Rem
		bbdoc:Inserts an object after the first occurence of the content in the given link.
	End Rem
	Method InsertAfterLink:TLink( value:Object,pred:TLink )
		'For Local Obj:Object = EachIn InternalArray
		If InternalArray = Null Then Return Null
		Local index:Int = -1
		#For_Bucle
		For Local i:Int = 0 Until InternalArray.length
			If InternalArray[i] = pred._value Then
				index = i
				Exit For_Bucle
			End If
		Next
		If index >= 0 Then
			InternalArray = InternalArray[0..index + 1] + (New Object[0]) + InternalArray[index..InternalArray.length]
			InternalArray[index + 1] = Value
			Local Link:TLink = New TLink
			Link._pred = Null
			Link._succ = Null
			Link._value = Value
			Return Link
		End If
		Return Null

	End Method

	Rem
		bbdoc:Inserts an object before the first occurrence of the link contents.
	End Rem
	Method InsertBeforeLink:TLink(Value:Object, succ:TLink)
		'For Local Obj:Object = EachIn InternalArray
		If InternalArray = Null Then Return Null
		Local index:Int = -1
		#For_Bucle
		For Local i:Int = 0 Until InternalArray.length
			If InternalArray[i] = succ._value Then
				index = i
				Exit For_Bucle
			End If
		Next
		If index >= 0 Then
			InternalArray = InternalArray[0..index] + (New Object[0]) + InternalArray[index - 1..InternalArray.length]
			InternalArray[index] = Value
			Local Link:TLink = New TLink
			Link._pred = Null
			Link._succ = Null
			Link._value = Value
			Return Link
		End If
		Return Null
		
	End Method

	Rem
		bbdoc:Clear a linked list
	End Rem
	Method Clear()
		InternalArray = Null
	End Method

	
	Rem
		bbdoc:Count list length
	End Rem
	Method Count:Int()
		If InternalArray = Null Then Return 0 Else Return InternalArray.length
	End Method

	Rem
		bbdoc:Returns the last object in the list
	End Rem
	Method Last:Object()
		If InternalArray = Null Then
			Return Null
		Else
			If InternalArray.Length >= 1 Then
				Return InternalArray[InternalArray.length - 1]
			Else
				Return Null
			EndIf
		EndIf
	End Method

	Rem
		bbdoc:Check if list is empty
	End Rem
	Method IsEmpty:Int()
		If InternalArray = Null Then
			Return True
		Else
			Return (InternalArray.Length = 0)
		EndIf
	End Method

	Rem
		bbdoc:Returns the last link the list or null if the list is empty.
	End Rem
	Method LastLink:TLink()
		If InternalArray = Null Then
			Return Null
		Else
			If InternalArray.Length >= 1 Then
				Local Link:TLink = New TLink
				Link._pred = Null
				Link._succ = Null
				Link._value = InternalArray[InternalArray.length - 1]
				Return Link

			Else
				Return Null
			EndIf
		EndIf
		
	End Method

	Method ObjectEnumerator:TListEnum()
		Local TLAE:TListArrayEnumerator = New TListArrayEnumerator
		TLAE.ListArray = Self
		Return TLAE
	End Method
	
	Rem
		bbdoc:Remove an object from this array list.
	End Rem
	Method Remove( value:Object )
		If InternalArray = Null Then Return 'Null
		'For Local Obj:Object = EachIn InternalArray
		Local index:Int = -1
		#For_loop
		For Local i:Int = 0 Until InternalArray.length
			Local obj:Object = InternalArray[i]
			If obj = Value Then
				index = i
				Exit For_loop
			End If
		Next
		If index = -1 Then Return
		InternalArray = InternalArray[..index] + InternalArray[index + 1..]

	End Method

	Rem
		bbdoc:Removes and returns the first object in the list.
	End Rem
	Method RemoveFirst:Object()
		If InternalArray = Null Then Return Null
		Local obj:Object = Self.First()
		InternalArray = InternalArray[1..]
		Return obj
	End Method

	Rem
		bbdoc:Removes and returns the last object in the list.
	End Rem
	Method RemoveLast:Object()
		If InternalArray = Null Then Return Null
		Local obj:Object = Self.Last()
		InternalArray = InternalArray[0..InternalArray.length - 1]
		Return obj
	End Method

	Rem
		bbdoc:Reverse the order of the list.
	End Rem
	Method Reverse()
		For Local i:Int = 0 To InternalArray.length / 2
			Local AuxObj:Object = InternalArray[i]
			InternalArray[i] = InternalArray[InternalArray.Length - 1 - i]
			InternalArray[InternalArray.Length - 1 - i] = AuxObj
		Next
	End Method

	Rem
		bbdoc:Creates a new list that is the reversed version of this list.
	End Rem
	Method Reversed:TList()
		Local LA:TListArray = TListArray(Self.Copy())
		LA.Reverse()
		Return LA
	End Method

	Rem
		bbdoc:Sort a list in either ascending (default) or decending order.
	End Rem
	Method Sort:Int(ascending:Int = True, compareFunc(o1:Object, o2:Object) = CompareObjects)
		?Debug
		If compareFunc <> CompareObjects Then
			Throw "ListArrays only support CompareObjects sorting function."
		End If
		?
		InternalArray.Sort(ascending)', compareFunc)
	End Method

	Rem
		bbdoc:Swap contents with the list specified.
	End Rem
	Method Swap(List:TList)
		If TListArray(list) <> Null Then
			Local Target:TListArray = TListArray(List)
			Local Obj:Object[] = Target.InternalArray
			Target.InternalArray = Self.InternalArray
			Self.InternalArray = Obj
		Else
			Local TL:TList = List.Copy()
			List.Clear()
			For Local Obj:Object = EachIn Self.InternalArray
				List.AddLast(Obj)
			Next
			Self.InternalArray = TL.ToArray()
		End If
		
	End Method

	Rem
		bbdoc:Returns the value of the link at the given index.
	End Rem
	Method ValueAtIndex:Object(index:Int)
		If InternalArray = Null Then
			Return Null
		ElseIf index < 0 Or index > InternalArray.Length - 1 Then
			Return Null
		Else
			Return InternalArray[index]
		End If
	End Method

	Rem
		bbdoc:convert a list to an array
	End Rem
	Method ToArray:Object[]()
		Return InternalArray
	End Method

	Method _pad()
	End Method

	Rem
		bbdoc:Create a list from an array
	End Rem
	Function FromArray:TList( arr:Object[] )
		Local TL:TListArray = New TListArray
		TL.InternalArray = arr
		Return TL
	End Function

End Type

Type TListArrayEnumerator Extends TListEnum
	Field ListArray:TListArray, Index:Int
	Method HasNext:Int()
		If Index < ListArray.InternalArray.Length Then Return True
	End Method
	Method NextObject:Object()
	 	Local Value:Object = ListArray.INTERNALARRAY[Index]
		Index:+1
		Return Value
	End Method

	Method Delete()
		ListArray = Null
	End Method
End Type

It takes the default Tlist as an 'interface' and implements all its functionality using an array in the background. You can get the array at any time using the ToArray() method, etc. Everything works like a charm except in one scenario. Whenever a real linked list swaps its contents with the arraybased list, the lined list loses it's contents, beouse it is using the _header inside the array list (wich is not really used in this scenario).
Any ideas how to avoid/fix this?
I know, the best idea would be to have a real generic collection class, and make Tlist and TListArray extend both the same base collection, so the swap is done calling generic methods, but this would mean a change in the current brl modules, wich I supose will not happen, so I'm looking for a workaround. Additionally, link based functions return unlinked links, that is link instances with the appropiate "value" but with a void pred and succ, becose in this scenario it has no sense.

Any ideas?

Czar Flavius

(Posted 2009) [#2]

What would be good would be to have both an array and a list inside, and two flags to denote whether the array and/or list is up to date. You can then access elements using array-style (from a specific position), but first it checks the array is up to date. If it is not, it converts the list to the array first. When adding/removing elements it does so in the list (and in doing so flags the array as not up to date). But rather than updating the array after every change, it only needs to update after all list changes have completed and an access is made.

Hm does this make any sense? The intended advantage is you can add and remove from the middle of the data structure quickly like a list, and you can access a specific position relatively quickly like an array, giving the best of both worlds. Of course at the cost of some overhead when either the array or list needs to update from the other. This only happens when required - if adding elements, and then iterating through one-by-one the array storage is not required to update just yet.

ziggy

(Posted 2009) [#3]

@Czar Flavius: The idea to have several 'list' implementations is that you can choose the faster one in every scenario. Lots of modern programing languages have linked list, key-vale pairs, lifo and fifo piles and array-lists. All of them sharing a base 'generic collection' class, so you can pass one or the other or the generic one on a function or whatever, but you can still decide if you need fast indexed acces (array list) a push-pull functionality (then use piles), a fast 'search' item then you use a key-value pair (like a tmap) collection, fast add/remove/resize list (linked lists) etc...
My attempt in the first post was to generate an array-list using the pre-existing tlist as the generic list, but now I'm not sure if it is the best idea. I should better make my own lists system and publish it on the module tweaks?

Tommo

(Posted 2009) [#4]

Array resizing/slicing can be very very slow. I don't think to use it so often in insertion is a good idea.
In my opinion, linkedlist is born to be used for fast insertion/removal/iteration. Fast random access is not a must.
If I want a list which also has fast random accessed , I may combine a map/hashtable and a simple list to make a hybrid structure, and let each one do the job it's good at.

ziggy

(Posted 2009) [#5]

@tommo: Of course. If you need fast insertion a linked list is your best friend. If you need fast random access a listarray is your best friend (even faster than a hashtable-based collection). Having choice of one or the other is then the best of the scenarios, isn't it? The point on this is that a list-array gives you access too to the underlayng array, so you can pre-scale the array and fill it with valus in a single operation if you want to, while you maintain the list-like access for interfacing.
All in all, this is not linkedlist vs arrays, it 'could be' opening the way BlitzMax handles collections or lists to a more generic way. In the same way we have a generic Stream class and all streams inherit the stream structure, I think it would be great to have a basic 'list' or 'collection' class, and leave linked lists as one of the implementations of collections in BlitzMax. Then users could happilly create their own (listarray, piles, key/value pair based lists, etc.)
I just think current design of collections is too restrictive in this respect. It's just a sort of idea/suggestion.

ziggy

(Posted 2009) [#6]

After working on a complete implementation of LinkedLikst and ListArrays, I've done a small benchmark test, and I get this interesting results (on release mode)

Benchmark.
Adding 20000 items
Time to add 20000 items on a linked list: 4
Time to add 20000 items on a listArray list: 1509
Time to add 20000 items on a listArray list with FastAppendItems: 8

Benchmark.
Getting the values for 20000 indexed items
Time to index 20000 items on a linked list: 970
Time to index 20000 items on a ListArray list: 0

Benchmark.
EachIn iterations.
Time to EachIn iterate 100000 items on a linked list: 2
Time to EachIn iterate 100000 items on a ListArray list: 1
Time to EachIn iterate 100000 items on a ListArray internal array: 1

Depending on the usage of your data(random access vs object creation-destruction) you cah choose one implementation or the other.

ImaginaryHuman

(Posted 2009) [#7]

I like using a linked list of arrays. That way you don't have to reslice, you just add on another link containing an extra array. I then use almost entirely array access, except where you need to go across link boundaries.