Cashed TList

Strict

Rem
BBDoc: Lists
End Rem
Module BRL.LinkedList

ModuleInfo "Version: 1.09"
ModuleInfo "Author: Mark Sibly and jimon"
ModuleInfo "License: Blitz Shared Source Code"
ModuleInfo "Copyright: Blitz Research Ltd and jimon game studio"
ModuleInfo "Modserver: BRL"

ModuleInfo "History: 1.09 Release"
ModuleInfo "History: Remove memalloced error"
ModuleInfo "History: 1.08 Release"
ModuleInfo "History: Add some cache methods to Count() and ValueAtIndex()"
ModuleInfo "History: 1.07 Release"
ModuleInfo "History: Changed Reverse to maintain TLink stability"
ModuleInfo "History: 1.06 Release"
ModuleInfo "History: Added optional CompareFunc parameter to Sort"
ModuleInfo "History: 1.05 Release"
ModuleInfo "History: Sort now swaps links instead of values"

Import BRL.Data

Private

Global ListDataType:TListDataType=New TListDataType

Public

Function CompareObjects( o1:Object,o2:Object )
	Return o1.Compare( o2 )
End Function

Rem
BBDoc: Link Object used by TList
End Rem
Type TLink

	Field _value:Object
	Field _succ:TLink,_pred:TLink
	
	Rem
	BBDoc: Returns the Object associated with this Link.
	End Rem
	Method Value:Object()
		Return _value
	End Method

	Rem
	BBDoc: Returns the next link in the List.
	End Rem
	Method NextLink:TLink()
		If _succ._value<>_succ Return _succ
	End Method

	Rem
	BBDoc: Returns the previous link in the List.
	End Rem
	Method PrevLink:TLink()
		If _pred._value<>_pred Return _pred
	End Method

	Rem
	BBDoc: Removes the link from the List.
	End Rem
	Method Remove()
		_value=Null
		_succ._pred=_pred
		_pred._succ=_succ
	End Method

End Type

Rem
BBDoc: Enumerator Object use by TList in order to implement Eachin support. 
End Rem
Type TListEnum

	Field _link:TLink

	Method HasNext()
		Return _link._value<>_link
	End Method

	Method NextObject:Object()
		Local value:Object=_link._value
		Assert value<>_link
		_link=_link._succ
		Return value
	End Method

End Type

Rem
BBDoc: Linked List 
End Rem
Type TList Extends TData

	Field _head:TLink
	
	Field EnableCache% = 1
	
	Field ValueAtIndexCacheChange%
	Field CountCacheChange%
	Method CacheChangeList()
		If Not EnableCache Then Return
		
		ValueAtIndexCacheChange = 1
		CountCacheChange = 1
	End Method
	
	Method DataType:TListDataType()
		Return ListDataType
	End Method

	Method New()
		_head=New TLink
		_head._succ=_head
		_head._pred=_head
		_head._value=_head
		CacheChangeList()
		ValueAtIndexCache = Null
		FreeFindLinkCache()
	End Method

	Method Delete()
		Clear
		_head._value=Null
		_head._succ=Null
		_head._pred=Null
	End Method

	Rem
	BBDoc: Clear a linked list
	About: Removes all objects from @list.
	End Rem
	Method Clear()
		While _head._succ<>_head
			_head._succ.Remove
		Wend
		CacheChangeList()
		ValueAtIndexCache = Null
		FreeFindLinkCache()
	End Method

	Rem
	BBDoc: Check if list is empty
	Returns: True if list is empty, else false
	End Rem
	Method IsEmpty()
		Return _head._succ=_head
	End Method
	
	Rem
	BBDoc: Check if list contains a value
	Returns: True if list contains @value, else false
	End Rem
	Method Contains( value:Object )
		Local link:TLink=_head._succ
		While link<>_head
			If link._value.Compare( value )=0 Return True
			link=link._succ
		Wend
		Return False
	End Method

	Rem
	BBDoc: Add an object to the start of the list
	Returns: A link object
	End Rem
	Method AddFirst:TLink( value:Object )
		CacheChangeList()
		Return InsertAfterLink( value,_head )
	End Method

	Rem
	BBDoc: Add an object to the end of the list
	Returns: A link object
	End Rem
	Method AddLast:TLink( value:Object )
		CacheChangeList()
		Return InsertBeforeLink( value,_head )
	End Method

	Rem
	BBDoc: Returns the first object in the list
	About: Throws an exception if the list is empty.
	End Rem
	Method First:Object()
		Assert Not IsEmpty() Else "Illegal operation on empty list"
		Return _head._succ._value
	End Method

	Rem
	BBDoc: Returns the last object in the list
	About: Throws an exception if the list is empty.
	End Rem
	Method Last:Object()
		Assert Not IsEmpty() Else "Illegal operation on empty list"
		Return _head._pred._value
	End Method

	Rem
	BBDoc: Removes and returns the first object in the list.
	About: Throws an exception if the list is empty.
	End Rem
	Method RemoveFirst:Object()
		Assert Not IsEmpty() Else "Illegal operation on empty list"
		CacheChangeList()
		Local value:Object=_head._succ._value
		_head._succ.remove
		Return value
	End Method

	Rem
	BBDoc: Removes and returns the last object in the list.
	About: Throws an exception if the list is empty.
	End Rem
	Method RemoveLast:Object()
		Assert Not IsEmpty() Else "Illegal operation on empty list"
		CacheChangeList()
		Local value:Object=_head._pred._value
		_head._pred.remove
		Return value
	End Method

	Rem
	BBDoc: Returns the first link the list or null if the list is empty.
	End Rem
	Method FirstLink:TLink()
		If _head._succ<>_head Return _head._succ
	End Method

	Rem
	BBDoc: Returns the last link the list or null if the list is empty.
	End Rem
	Method LastLink:TLink()
		If _head._pred<>_head Return _head._pred
	End Method

	Rem
	BBDoc: Inserts an object before the specified list link.
	End Rem
	Method InsertBeforeLink:TLink( value:Object,succ:TLink )
		CacheChangeList()
		Local link:TLink=New TLink
		link._value=value
		link._succ=succ
		link._pred=succ._pred
		link._pred._succ=link
		succ._pred=link
		Return link
	End Method

	Rem
	BBDoc: Inserts an object after the specified list link.
	End Rem
	Method InsertAfterLink:TLink( value:Object,pred:TLink )
		CacheChangeList()
		Local link:TLink=New TLink
		link._value=value
		link._pred=pred
		link._succ=pred._succ
		link._succ._pred=link
		pred._succ=link
		Return link
	End Method

	Rem
	BBDoc: Returns the first link in the list with the given value, or null if none found.
	End Rem
	Field FindLinkCache:TLink = Null
	Field FindLinkObjectCache:Object = Null
	Method FindLink:TLink( value:Object )
		If EnableCache = 1 And FindLinkObjectCache = value Then Return FindLinkCache
		
		Local link:TLink=_head._succ
		While link<>_head
			If link._value.Compare( value )=0 Then
				FindLinkCache = link
				FindLinkObjectCache = value
				Return link
			End If
			link=link._succ
		Wend
	End Method

	Rem
	BBDoc: Clear FindLink method cache.
	End Rem
	Method FreeFindLinkCache()
		FindLinkCache = Null
		FindLinkObjectCache = Null
	End Method

	Rem
	BBDoc: Returns the value of the link at the given index.
	About: Throws an exception if the index is out of range (must be 0..list.Count()-1 inclusive).
	End Rem
	Field ValueAtIndexCache:Object[]
	Method ValueAtIndex:Object( index )
		If EnableCache = 1 Then
			'Assert index>=0 Else "Object index must be positive"
			'If index > Count()-1 Then RuntimeError "Object index must be in 0 .. Count - 1"
			If index = 0 Then Return First()
			
			If ValueAtIndexCacheChange = 1 Then
				ValueAtIndexCache = ToArray()
				ValueAtIndexCacheChange = 0
			End If
			Return ValueAtIndexCache[index]
		Else
			Assert index>=0 Else "Object index must be positive"
			For Local value:Object=EachIn Self
				If Not index Return value
				index:-1
			Next               
			RuntimeError "List index out of range"
		End If
	End Method

	Rem
	BBDoc: Count list length
	Returns: The numbers of objects in @list.
	End Rem
	Field CountCache%
	Method Count()
		If EnableCache = 1 Then
			If CountCacheChange = 1 Then
				Local link:TLink=_head._succ,count
				While link<>_head
					count:+1
					link=link._succ
				Wend
				CountCache = count
				CountCacheChange = 0
			End If
			Return CountCache
		Else
			Local link:TLink=_head._succ,count
			While link<>_head
				count:+1
				link=link._succ
			Wend
			Return count
		End If
	End Method

	Rem
	BBDoc: Remove an object from a linked list
	About: Remove scans a list for the specified value and removes its link.
	End Rem
	Method Remove( value:Object )
		Local link:TLink=FindLink( value )
		If Not link Return False
		link.Remove
		CacheChangeList()
		Return True
	End Method
	
	Rem
	BBDoc: Swap contents with the list specified.
	End Rem
	Method Swap( list:TList )
		Local head:TLink=_head
		_head=list._head
		list._head=head
	End Method
	
	Rem
	BBDoc: Creates an identical copy of the list.
	End Rem
	Method Copy:TList()
		Local list:TList=New TList
		For Local value:Object=EachIn Self
			list.AddLast value
		Next
		Return list
	End Method

	Rem
	BBDoc: Reverse the order of the list.
	End Rem
	Method Reverse()
		Local pred:TLink=_head,succ:TLink=pred._succ
		Repeat
			Local link:TLink=succ._succ
			pred._pred=succ
			succ._succ=pred
			pred=succ
			succ=link
		Until pred=_head
	End Method
	
	Rem
	BBDoc: Creates a new list that is the reversed version of this list.
	End Rem
	Method Reversed:TList()
		Local list:TList=New TList
		For Local value:Object=EachIn Self
			list.AddFirst value
		Next
		Return list
	End Method

	Rem
	BBDoc: Sort a list in either ascending (default) or decending order.
	About: User types should implement a Compare method in order to be sorted.
	End Rem
	Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
		Local term:TLink=_head
		Repeat
			Local link:TLink=_head._succ
			Local sorted=True
			Repeat
				Local succ:TLink=link._succ
				If succ=term Exit
				Local cc=CompareFunc( link._value,succ._value )	'link._value.Compare( succ._value )
				If (cc>0 And ascending) Or (cc<0 And Not ascending)
					Local link_pred:TLink=link._pred
					Local succ_succ:TLink=succ._succ
					link_pred._succ=succ
					succ._succ=link
					succ._pred=link_pred
					link._succ=succ_succ
					link._pred=succ
					succ_succ._pred=link
					sorted=False
				Else
					link=succ
				EndIf
			Forever
			If sorted Return
			term=link
		Forever
	End Method
		
	Method ObjectEnumerator:TListEnum()
		Local enum:TListEnum=New TListEnum
		enum._link=_head._succ
		Return enum
	End Method

	Rem
	BBDoc: convert a list to an array
	Returns: An array of objects
	End Rem
	Method ToArray:Object[]()
		Local n=count(),arr:Object[n],i
		For Local o:Object=EachIn Self
			arr[i]=o
			i:+1
		Next
		Return arr
	End Method

	Rem
	BBDoc: Create a list from an array
	Returns: A new linked list
	End Rem
	Function FromArray:TList( arr:Object[] )
		Local list:TList=New TList
		For Local o:Object=EachIn arr
			list.AddLast o
		Next
		Return list
	End Function

End Type

Type TListDataType Extends TDataType

	Method Tag$()
		Return "BRL.LinkedList.TList"
	End Method
	
	Method ReadObject:Object( stream:TStream )
		Local t:TList=New TList
		Local count=stream.ReadInt()
		For Local i=0 Until count
			t.AddLast stream.ReadObject()
		Next
	End Method
	
	Method WriteObject( o:Object,stream:TStream )
		Local t:TList=TList(o)
		stream.WriteInt t.Count()
		Local link:TLink=t._head._succ,count
		While link<>t._head
			stream.WriteObject link._value
			link=link._succ
		Wend
	End Method

End Type

Rem
BBDoc: Create a linked list
Returns: A new linked list object
End Rem
Function CreateList:TList()
	Return New TList
End Function

Rem
BBDoc: Clear a linked list
About: Removes all objects from @list.
End Rem
Function ClearList( list:TList )
	list.Clear
End Function

Rem
BBDoc: Count list length
Returns: The numbers of objects in @list.
End Rem
Function CountList( list:TList )
	Return list.Count()
End Function

Rem
BBDoc: Check if list is empty
Returns: True if list is empty, else false
End Rem
Function ListIsEmpty( list:TList )
	Return list.IsEmpty()
End Function

Rem
BBDoc: Check if list contains a value
Returns: True if list contains @value, else false
End Rem
Function ListContains( list:TList,value:Object )
	Return list.Contains( value )
End Function

Rem
BBDoc: Sort a list
End Rem
Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
	list.Sort ascending,compareFunc
End Function

Rem
BBDoc: Create a list from an array
Returns: A new linked list
End Rem
Function ListFromArray:TList( arr:Object[] )
	Return TList.FromArray( arr )
End Function

Rem
BBDoc: convert a list to an array
Returns: An array of objects
End Rem
Function ListToArray:Object[]( list:TList )
	Return list.ToArray()
End Function

Rem
BBDoc: Swap the contents of 2 lists
End Rem
Function SwapLists( list_x:TList,list_y:TList )
	list_x.Swap list_y
End Function

Rem
BBDoc: Reverse the order of elements of a list
End Rem
Function ReverseList( list:TList )
	list.Reverse
End Function

Rem
BBDoc: Find a link in a list
Returns: The link containting @value
End Rem
Function ListFindLink:TLink( list:TList,value:Object )
	Return list.FindLink( value )
End Function

Rem
BBDoc: Add an object to a linked list
Returns: A link object
End Rem
Function ListAddLast:TLink( list:TList,value:Object )
	Return list.AddLast( value )
End Function

Rem
BBDoc: Add an object to a linked list
Returns: A link object
End Rem
Function ListAddFirst:TLink( list:TList,value:Object )
	Return list.AddFirst( value )
End Function

Rem
BBDoc: Remove an object from a linked list
About: #ListRemove scans a list for the specified value and removes its link.
End Rem
Function ListRemove( list:TList,value:Object )
	list.Remove value
End Function

Rem
BBDoc: Remove an object from a linked list
About: #RemoveLink is more efficient than #ListRemove.
End Rem
Function RemoveLink( link:TLink )
	link.Remove
End Function