ArraySortProvider (non-recursive quicksort)

ArraySortProvider.lss

%REM
	Class ArraySortProvider
	Non-recursive quicksort algorithm
	Using custom stack object instead-of recursion
	Must be non-recursive, for lotusscript recursion stack is limited by 200!
	
	@author Jiri Krakora
	@date 15.6.2012
	@uses Stack
	@revision
	
	EXAMPLE:
	----------------------------------------------------------------------------
	Dim array() As Integer
	Dim i As Long
	ReDim array(0)
	
	For i = 0 To 32000
		Let array(i) = Rnd() * 1000
		ReDim Preserve array(UBound(array) + 1)
	Next

	Dim sorter As New ArraySortProvider(array)
	
	For i = 0 To 1000
		Print sorter.SortedArray(i)
	Next
%END REM
Public Class ArraySortProvider
	Private oArray As Variant
	Private oStack As Stack
	
	%REM
		There is dependency on array to be sorted
		@param fixed or dynamic array of any primitive type - strings or numbers
	%END REM
	Public Sub New(arr As Variant)
		Dim l As Long
		Dim r As Long
		Dim dt As Integer
		
		Set Me.oStack = New Stack(0)
		Let dt = DataType(arr)
		
		If dt > 8000 Then
			Let Me.oArray = arr
			
			Let l = LBound(oArray)
			Let r = UBound(oArray)
			
			Call Me.Quicksort(l, r)
		Else
			Let Me.oArray = Evaluate(|""|)
		End If
	End Sub
	
	Public Property Get SortedArray As Variant
		Let SortedArray = Me.oArray
	End Property
	
	Public Property Get UpperBound As Integer
		Let UpperBound = UBound(Me.oArray)
	End Property
	
	%REM
		Non-Recursive function for sorting
		@param array to be sorted
		@param left bound to start from
		@param right bound to end with
	%END REM
	Private Sub Quicksort(ByVal l As Long, ByVal r As Long)
		Dim pivot As Long
		
		Call Me.oStack.Push(l)
		Call Me.oStack.Push(r)
		
		While Not Me.oStack.IsEmpty
			Let r = Me.oStack.Pop()
			Let l = Me.oStack.Pop()
			
			If r > l Then
				Let pivot = Me.SetPivot(l, r)
				
				' sort left side from pivot
				Call Me.oStack.Push(l)
				Call Me.oStack.Push(pivot)
				
				' sort right side from pivot
				Call Me.oStack.Push(pivot + 1)
				Call Me.oStack.Push(r)
			End If
		Wend
	End Sub
	
	%REM
		Set pivot position between smaller items on the left and larger on the right
		@param left bound of the items array
		@return right bound of the items array
	%END REM
	Private Function SetPivot(l As Long, r As Long) As Long
		Dim i As Long
		Dim boundary As Long
		
		Let boundary = l
		
		' get boundary position for pivot
		For i = l + 1 To r
			If Me.oArray(i) < Me.oArray(l) Then
				Let boundary = boundary  + 1
				Call Swap(i, boundary)
			End If
		Next
		
		' set pivot as a boundary
		Call Me.Swap(l, boundary)
		
		Let SetPivot = boundary
	End Function
	
	%REM
		Swap two values in the array
		@param array to be sorted
		@param left position
		@param right position
	%END REM
	Private Sub Swap(l As Long, r As Long)
		Dim tmp As Variant
		
		Let tmp = Me.oArray(r)
		Let Me.oArray(r) = Me.oArray(l)
		Let Me.oArray(l) = tmp
	End Sub
End Class