'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 TLink2
    'Ptr 
	Field _value:Object
	Field _succ:TLink2,_pred:TLink2
	
	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:TLink2()
		If _succ._value<>_succ Return _succ
	End Method

	Rem
	BBDoc: Returns the previous link in the List.
	End Rem
	Method PrevLink:TLink2()
		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


Type TListEnum2

	Field _link:TLink2

	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 TList2 Extends TData

	Field _head:TLink2
	'Field _array[10000]:TLink2,_i:Int
	
	Method DataType:TListDataType()
		Return ListDataType
	End Method

	Method New()
		_head=New TLink2
		_head._succ=_head
		_head._pred=_head
		_head._value=_head
		'_array[_i]=_head
	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
	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:TLink2=_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:TLink2( value:Object )
		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:TLink2( value:Object )
		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"
		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"
		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:TLink2()
		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:TLink2()
		If _head._pred<>_head Return _head._pred
	End Method

	Rem
	BBDoc: Inserts an object before the specified list link.
	End Rem
	Method InsertBeforeLink:TLink2( value:Object,succ:TLink2 )
		Local link:TLink2=New TLink2
		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:TLink2( value:Object,pred:TLink2 )
		Local link:TLink2=New TLink2
		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
	Method FindLink:TLink2( value:Object )
		Local link:TLink2=_head._succ
		While link<>_head
			If link._value.Compare( value )=0 Return link
			link=link._succ
		Wend
	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
	Method ValueAtIndex:Object( index )
		Assert index>=0 Else "Object index must be positive"
		Local link:TLink2=_head._succ
		While link<>_head
			If Not index Return link._value
			link=link._succ
			index:-1
		Wend
		RuntimeError "List index out of range"
	End Method

	Rem
	BBDoc: Count list length
	Returns: The numbers of objects in @list.
	End Rem
	Method Count()
		Local link:TLink2=_head._succ,count
		While link<>_head
			count:+1
			link=link._succ
		Wend
		Return count
	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:TLink2=FindLink( value )
		If Not link Return False
		link.Remove
		Return True
	End Method
	
	Rem
	BBDoc: Swap contents with the list specified.
	End Rem
	Method Swap( list:TList2 )
		Local head:TLink2=_head
		_head=list._head
		list._head=head
	End Method
	
	Rem
	BBDoc: Creates an identical copy of the list.
	End Rem
	Method Copy:TList2()
		Local list:TList2=New TList2
		Local link:TLink2=_head._succ
		While link<>_head
			list.AddLast link._value
			link=link._succ
		Wend
		Return list
	End Method

	Rem
	BBDoc: Reverse the order of the list.
	End Rem
	Method Reverse()
		Local pred:TLink2=_head,succ:TLink2=pred._succ
		Repeat
			Local link:TLink2=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:TList2()
		Local list:TList2=New TList2
		Local link:TLink2=_head._succ
		While link<>_head
			list.AddFirst link._value
			link=link._succ
		Wend
		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:TLink2=_head
		Repeat
			Local link:TLink2=_head._succ
			Local sorted=True
			Repeat
				Local succ:TLink2=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:TLink2=link._pred
					Local succ_succ:TLink2=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:TListEnum2()
		Local enum:TListEnum2=New TListEnum2
		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 arr:Object[Count()],i
		Local link:TLink2=_head._succ
		While link<>_head
			arr[i]=link._value
			link=link._succ
			i:+1
		Wend
		Return arr
	End Method

	Rem
	BBDoc: Create a list from an array
	Returns: A new linked list
	End Rem
	Function FromArray:TList2( arr:Object[] )
		Local list:TList2=New TList2
		For Local i=0 Until arr.length
			list.AddLast arr[i]
		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:TList2=New TList2
		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:TList2=TList2(o)
		stream.WriteInt t.Count()
		Local link:TLink2=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 CreateList2:TList2()
	Return New TList2
End Function

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

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

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

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

Rem
BBDoc: Sort a list
End Rem
Function SortList2( list:TList2,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 ListFromArray2:TList2( arr:Object[] )
	Return TList2.FromArray( arr )
End Function

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

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

Rem
BBDoc: Reverse the order of elements of a list
End Rem
Function ReverseList2( list:TList2 )
	list.Reverse
End Function

Rem
BBDoc: Find a link in a list
Returns: The link containting @value
End Rem
Function ListFindLink2:TLink2( list:TList2,value:Object )
	Return list.FindLink( value )
End Function

Rem
BBDoc: Add an object to a linked list
Returns: A link object
End Rem
Function ListAddLast2:TLink2( list:TList2,value:Object )
	Return list.AddLast( value )
End Function

Rem
BBDoc: Add an object to a linked list
Returns: A link object
End Rem
Function ListAddFirst2:TLink2( list:TList2,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 ListRemove2( list:TList2,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 RemoveLink2( link:TLink2)
	link.Remove
End Function

