Splay test.monkey

Import mojo
'#CPP_GC_MODE=0

Function Main:Int()
	New Game()
End Function

Class Game Extends App
	Const NUM_VALUES = 5850  'Number of values each tree will contain in this test.
	Const FETCH_AMT = 300     'Amount of gets done each fetch cycle.
	
	Field a:= New IntMap<String>
	Field b:= New IntSplayTree<String>

	Field fetchVals:Int[]
	Field fetchTime1, fetchTime2
	
	Method OnCreate:Int()
		SetUpdateRate 10
		
		'Load up the trees with some values.
		Local time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			a.Set(i, "KeyValue " + i)
		Next
		Print("Map insert time: " + (Millisecs() -time))
		
		time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			b.Set(i, "KeyValue " + i)
		Next
		Print("Splay insert time: " + (Millisecs() -time))
		
		'Validate that the inserts succeeded.
		Print("Map size: " + a.Count())
		Print("Splay size: " + b.Size())
		'Print b.Height()
		
		'Prepare a set of values to fetch.
		fetchVals = fetchVals.Resize(FETCH_AMT)
		For Local i:Int = 0 Until FETCH_AMT
			fetchVals[i] = Rnd(NUM_VALUES)
		Next
		
		'Now, let's fetch these values a few times from our trees.
		time = Millisecs()
			For Local j:Int = 0 Until fetchVals.Length()
				a.Get(fetchVals[j])
			Next
		Print("Map fetch time: " + (Millisecs() -time))

		time = Millisecs()
			For Local j:Int = 0 Until fetchVals.Length()
				b.Get(fetchVals[j])
			Next
		Print("Splay fetch time: " + (Millisecs() -time))
		
				
	End Method
	
	Method OnUpdate:Int()
		'Fetch a couple of values from the trees and display how long it took to do this.  As time progresses, the splay tree should become more efficient.
		Local time = Millisecs()
		For Local i:Int = 0 Until FETCH_AMT
			a.Get(fetchVals[i])
		Next
		fetchTime1 = Millisecs() -time

		time = Millisecs()
		For Local i:Int = 0 Until FETCH_AMT
			b.Get(fetchVals[i])
		Next
		fetchTime2 = Millisecs() -time
		
	End Method
	
	Method OnRender:Int()
		Cls()
		
		DrawText("Map fetch time:  " + fetchTime1, 8, 8)
		DrawText("Splay fetch time:" + fetchTime2, 8, 32)
				
	End Method
End Class


Class SplayTree<K, V>

	'This method MUST be implemented by subclasses of SplayTree...
	Method Compare( lhs:K,rhs:K ) Abstract

	Method Clear:Void()
		root=Null
	End Method
	
	Method IsEmpty:Bool()
		Return root=Null
	End Method

	Method Contains:Bool(key:K)
		Return (Get(key) <> null)
	End Method

	' return value associated with the given key
	' If no such value, return null
	Method Get:V(key:K)
		root = Splay(root, key)
		Local cmp:Int = Compare(key, root.key)
		If (cmp = 0) Then Return root.value
	End Method

	'*************************************************************************
	'*  Splay insertion
	'*************************************************************************
	Method Set:Void(key:K, value:V)
		' Splay key to root
		If (root = null)
			root = New Node<K, V>(key, value)
			Return
		End If
		
		root = Splay(root, key)

		Local cmp:Int = Compare(key, root.key)
		
		' Insert new node at root
		If (cmp < 0)
			Local n:= New Node<K, V>(key, value)
			n.left = root.left
			n.right = root
			root.left = null
			root = n

			' Insert new node at root
		ElseIf (cmp > 0)
			Local n:= New Node<K, V>(key, value)
			n.right = root.right
			n.left = root
			root.right = null
			root = n

			' It was a duplicate key. Simply replace the value
		ElseIf (cmp = 0)
			root.value = value
		End If
	End Method
	
	'*************************************************************************
	'*  Splay deletion
	'*************************************************************************/
	' * This Splays the key, then does a slightly modified Hibbard deletion on
	' * the root (If it is the node to be deleted; If it is not, the key was
	' * not in the tree). The modification is that rather than swapping the
	' * root (call it node A) with its successor, it's successor (call it Node B)
	' * is moved to the root position by Splaying for the deletion key in A's
	' * right subtree. Finally, A's right child is made the new root's right
	' * child.
	' *
	Method Remove:Void(key:K)
		If (root = null) then Return ' empty tree
		
		root = Splay(root, key)

		Local cmp:Int = Compare(key, root.key)
		
		If (cmp = 0)
			If root.left = Null
				root = root.right
			Else
				Node x = root.right
				root = root.left
				Splay(root, key)
				root.right = x
			End If
		End If
		' else: it wasn't in the tree to remove
	End Method
	
	'   /*************************************************************************
	'	*  helper functions
	'	*************************************************************************/

	' height of tree (1-node tree has height 0)
	Method Height:Int()
		Return Height(root)
	End Method
	
	Method Size:Int()
		Return Size(root)
	End Method

	
  Private

	Method Height(x:Node<K, V>)
		If x = Null Then Return - 1
		Return 1 + Max(Height(x.left), Height(x.right))
	End Method
	
	Method Size:Int(x:Node<K, V>)
		If x = Null Then Return 0 Else Return (1 + Size(x.left) + Size(x.right))
	End Method
		
	
	'************************************************************************
	'* Splay function
	'* **********************************************************************/
	' Splay key in the tree rooted at Node h. If a node with that key exists,
	'   it is Splayed to the root of the tree. If it does not, the last node
	'   along the search path for the key is Splayed to the root.
	Method Splay:Node<K, V>(h:Node<K,V>, key:K)
		If (h = Null) Then Return Null

		Local cmp1:Int = Compare(key, h.key)

		If (cmp1 < 0)
			' key not in tree, so we're done
			If h.left = Null Then Return h
			
			Local cmp2:Int = Compare(key, h.left.key)
			If (cmp2 < 0)
				h.left.left = Splay(h.left.left, key)
				h = rotateRight(h)
			ElseIf (cmp2 > 0)
				h.left.right = Splay(h.left.right, key)
				If (h.left.right <> Null) Then h.left = rotateLeft(h.left)
			End If
			
			If h.left = Null Then Return h Else Return rotateRight(h)

		ElseIf(cmp1 > 0)
			' key not in tree, so we're done
			If h.right = Null Then Return h

			Local cmp2:Int = Compare(key, h.right.key)
			If (cmp2 < 0)
				h.right.left  = Splay(h.right.left, key)
				If (h.right.left <> null)
					h.right = rotateRight(h.right)
				End
			ElseIf(cmp2 > 0)
				h.right.right = Splay(h.right.right, key)
				h = rotateLeft(h)
			End If
			
			If h.right = Null Then Return h Else Return rotateLeft(h)

		Else
			Return h
		End If
	End Method

	
	Method rotateRight:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.left
		h.left = x.right
		x.right = h
		Return x
	End Method

	Method rotateLeft:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.right
		h.right = x.left
		x.left = h
		Return x
	End Method

	
	Field root:Node<K, V>
	
End Class


'Private

Class Node<K, V>
	Field key:K				   ' key
	Field value:V				 ' associated data
	Field left:Node, right:Node   ' left and right subtrees

	Method New(key:K, value:V)
		Self.key   = key
		Self.value = value
	End Method
End Class


'Helper versions...

Class IntSplayTree<V> Extends SplayTree<Int, V>
	Method Compare(lhs:Int, rhs:Int)
		Return lhs-rhs
	End Method
End Class

Class FloatSplayTree<V> Extends SplayTree<Float,V>
	Method Compare(lhs:Float, rhs:Float)
		If lhs<rhs Return -1
		Return lhs>rhs
	End Method
End Class

Class StringSplayTree<V> Extends SplayTree<String,V>
	Method Compare(lhs:String, rhs:String)
		Return lhs.Compare( rhs )
	End Method
End Class