experimenting with splay trees

Monkey Forums/Monkey Programming/experimenting with splay trees

Nobuyuki

(Posted 2015) [#1]

Heya fellas,

In preparation for a fork of angelfont which has better support for unicode (amongst other things), I decided to port a splay tree implementation over to Monkey. I chose this one by Josh Israel, since it was easy for me to read and didn't require a lot of extra work to make it "match" the canonical style Mark used for Maps.

For those who aren't familiar with splay trees, they're a form of binary search tree which is self-optimizing -- fetches from the tree perform a 'splay' operation which over time puts your most frequently-accessed elements closer to the root so that there is less cycles used to fetch those elements over time. For certain operations (such as, for example, fetching char information from a potentially very large unicode charset where at runtime you'll usually only be accessing a specific subset, but accessing it frequently), this type of tree may provide significant performance benefits.

However, in practice, the implementation I went with seems much less than optimal. The number of splay operations done on a large tree seems to give my computer a big headache on large but reasonably-sized trees. Particularly, at around a tree size of 5900 elements, this code ends up blowing the call stack on both desktop and html5 targets due to too much recursion.

https://gist.github.com/nobuyukinyuu/6555bf12d3da849d68cb

I never took any cs or programming courses in school, so I'm afraid that binary search trees are something I don't have a really good grasp on. What are the best practices here? How many things in this implementation are suboptimal in addition to the recursion? etc. Any comments would be appreciated :)

muddy_shoes

(Posted 2015) [#2]

Hi,

The problem with splay trees is that the situations where they truly provide an advantage aren't as common as the description suggests. In particular if your dataset is static and your comparison function is cheap then it's unlikely that a splay tree will be able to beat a standard balanced tree implementation like Monkey's standard map. The reason is that splaying has a cost that you're paying per access and if comparisons are cheap then that cost is way more than the few comparisons you save from having items nearer the top of the tree. You can offset this effect by only splaying if a fetch goes deep or if you fetch the same thing twice in a row etc. but it all gets very situation specific.

So, if your intended usage involves an integer key and a fixed dataset for font image lookups then I doubt splay trees will help you. If your comparison function is more expensive and/or your dataset is volatile (like a cache) then they might be worth trying out.

Anyway, I hacked in some iterative code to fix your implementations call-stack issue and had a play to verify my thinking. The code is below if it's of any use to you.

Import mojo
'#CPP_GC_MODE=0
 
Function Main:Int()
	New Game()
End Function
 
Class Game Extends App
	Const NUM_VALUES = 1000000  'Number of values each tree will contain in this test.
	Const FETCH_AMT = 10     'Amount of gets done each fetch cycle.
	Const REPEATS = 10000	'number of times to repeat the fetch group
		
	Field a:= New IntMap<String>
	Field b:= New IntSplayTree<String>
 
	Field fetchVals:Int[]
	Field mapFetchTime:Float
	Field splayFetchTime:Float
	Field numTests:Int = 1
	
	Const NUM_SAMPLES:Int = 600 
	Field sampleStartIndex = 0
	Field mapSamples:Float[] = New Float[NUM_SAMPLES]
	Field splaySamples:Float[] = New Float[NUM_SAMPLES]
	Const GRAPH_Y_HEIGHT:Int = 300
	Field yScale:Float
	
	Method OnCreate:Int()
		SetUpdateRate 3
				
		'Load up the trees with some values.
		Local time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			a.Set(i, "KeyValue " + i)
		End
		time = Millisecs() - time
		Print("Map insert time: " + time)
		
		time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			b.Set(i, "KeyValue " + i)
		End
		time = Millisecs() - time
		Print("Splay insert time: " + 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] = Int(Rnd(NUM_VALUES)) '"KeyValue " + Int(Rnd(NUM_VALUES))
		End
		
		'Now, let's fetch these values a few times from our trees.
		time = Millisecs()
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= a.Get(fetchVals[i])
			End
		End
		time = Millisecs() - time
		mapFetchTime += time
		Print("Initial Map fetch time: " + time)
 
		time = Millisecs()
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= b.Get(fetchVals[i])
				'Print val
				'If (val.Compare("KeyValue " + fetchVals[i]) <> 0)
				'	Error val
				'End
			End
		End
		time = Millisecs() - time
		splayFetchTime += time
		Print("Initial Splay fetch time: " + time)
		
		mapSamples[0] = mapFetchTime
		splaySamples[0] = splayFetchTime
		yScale = Float(GRAPH_Y_HEIGHT)/Max(mapFetchTime,splayFetchTime)
	End
	
	Method OnUpdate:Int()
		
		numTests += 1
		
		'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 j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= a.Get(fetchVals[i])
			End
		End
		time = Millisecs() - time
		mapFetchTime += time
		mapSamples[numTests] = time
		
		time = Millisecs()
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= b.Get(fetchVals[i])
				'If (val.Compare("KeyValue " + fetchVals[i]) <> 0)
				'	Error val
				'End
			End
		End
		time = Millisecs() - time
		splaySamples[numTests] = time
		splayFetchTime += time
				
	End
	
	Method OnRender:Int()
		Cls()
		
		DrawText("Mean Map fetch time:   " + FloatToString(mapFetchTime/numTests,2), 8, 8)
		DrawText("Mean Splay fetch time: " + FloatToString(splayFetchTime/numTests,2), 8, 32)
				
		Local xBase:Int = 20
		Local yBase:Int = 400
		
		For Local i:Int = 0 Until NUM_SAMPLES 
			SetColor(48,48,248)
			DrawPoint(xBase + i, yBase - Int(mapSamples[ Wrap(sampleStartIndex+i,0,NUM_SAMPLES) ] * yScale))
			SetColor(16,248,16)
			DrawPoint(xBase + i, yBase - Int(splaySamples[ Wrap(sampleStartIndex+i,0,NUM_SAMPLES) ] * yScale))
		End
		
		SetColor(255,255,255)
		DrawLine(xBase-1,yBase+1,xBase-1,yBase-GRAPH_Y_HEIGHT-1)
		DrawLine(xBase-1,yBase+1,xBase+NUM_SAMPLES+1,yBase+1)
		 
	End
	
	Function FloatToString:String( f:Float, decimals:Int)
		Local retString:String = String(f)
		Local dp:Int = retString.FindLast(".")
    
		If dp = -1
			dp = retString.Length
		End
    
		dp += decimals+1
    
		If dp > retString.Length
			dp = retString.Length
		End
    
		retString = retString[0..dp]
    
		Return retString

	End
	
	Function Wrap:Int( value:Int, low:Int, high:Int )
		Local range:Int = 1+high-low
			
		If value > high
			Return low + (value-low) Mod range
		ElseIf value < low
			Return high - (high-value) Mod range
		End
			
		Return value
	End
End
 
#THRESHOLD = False
 
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
		elementCount = 0
	End
	
	Method IsEmpty:Bool()
		Return root=Null
	End
 
	Method Contains:Bool(key:K)
		Return (Get(key) <> null)
	End
 
	Field findCompares:Int = 0
	Field splayThreshold:Int = 0
	
	Method Find:Node<K, V>(key:K)
		findCompares = 0
		Local found:Bool = False
		Local currNode:Node<K, V> = root
		
		While ( Not found)
			Local cmp:Int = Compare(key, currNode.key)
			findCompares += 1
			If (cmp < 0)
				If (currNode.left = Null)
					Return Null
				Else
					currNode = currNode.left
				End
			ElseIf(cmp > 0)
				If (currNode.right = Null)
					Return Null
				Else
					currNode = currNode.right
				End
			Else
				found = True
			End
		End
		
		Return currNode
	End
	
	' return value associated with the given key
	' If no such value, return null
	Method Get:V(key:K)
		
		Local node:Node<K, V> = Find(key)
		
		If (node <> Null)
#if THRESHOLD
			If (findCompares > splayThreshold)
				Splay(node)
			End
#else
			Splay(node)
#end
			Return node.value		
		End
		
	End
 
	Method Insert:Node<K, V>(key:K, value:V)
	
		Local insertNode:Node<K,V> = New Node<K, V>(key, value)
		
		If (root = Null)
			root = insertNode
			Return root
		End If
		
		Local inserted:Bool = False
		Local currNode:Node<K, V> = root
		
		While ( Not inserted)
			Local cmp:Int = Compare(key, currNode.key)
			
			If (cmp < 0)
				If (currNode.left = Null)
					currNode.left = insertNode
					insertNode.parent = currNode
					inserted = True
					elementCount += 1
				Else
					currNode = currNode.left
				End
			ElseIf(cmp > 0)
				If (currNode.right = Null)
					currNode.right = insertNode
					insertNode.parent = currNode
					inserted = True
					elementCount += 1
				Else
					currNode = currNode.right
				End
			Else
				currNode.value = value
				inserted = True
			End
		End
		
#if THRESHOLD
		splayThreshold = Min(3, Int(Log(elementCount) * 1.442695 * 0.25))
#end		
		Return insertNode
	End
	
	'*************************************************************************
	'*  Splay insertion
	'*************************************************************************
	Method Set:Void(key:K, value:V)
		
		Local insertedNode:Node<K, V> = Insert(key, value)
		
		Splay(insertedNode)
		
	End
	
	'*************************************************************************
	'*  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)
				If (x <> Null)
					x.parent = root
				End
				root.right = x
			End If
			
			root.parent = Null
			elementCount -= 1
		End If
		' else: it wasn't in the tree to remove
#if THRESHOLD
		splayThreshold = Min(3, Int(Log(elementCount) * 1.442695 * 0.25))
#end		
	End
	
	'   /*************************************************************************
	'	*  helper functions
	'	*************************************************************************/
 
	' height of tree (1-node tree has height 0)
	Method Height:Int()
		Return Height(root)
	End
	
	Method Size:Int()
		Return Size(root)
	End
 
	
	Private
 
	Field elementCount:Int
	
	Method Height(x:Node<K, V>)
		If x = Null Then Return - 1
		Return 1 + Max(Height(x.left), Height(x.right))
	End
	
	Method Size:Int(x:Node<K, V>)
		Local count:Int = 0
		Local parentStack:Stack<Node<K, V>> = New Stack<Node<K, V>>()
		Local currNode:Node<K, V> = x
		
		While ( Not parentStack.IsEmpty() Or currNode <> Null)
			If (currNode <> Null)
				parentStack.Push(currNode)
				currNode = currNode.left
			Else
				currNode = parentStack.Pop()
				count += 1
				currNode = currNode.right
			End
		End
		Return count
	End
		
	
	Method Splay:Void(x:Node<K, V>)
		While (x.parent <> Null)
			If (x.parent.parent = Null)
				If (x.parent.left = x)
					rotateRight(x.parent)
				Else
					rotateLeft(x.parent)
				End
			ElseIf(x.parent.left = x And x.parent.parent.left = x.parent)
				rotateRight(x.parent.parent)
				rotateRight(x.parent)
			ElseIf(x.parent.right = x And x.parent.parent.right = x.parent)
				rotateLeft(x.parent.parent)
				rotateLeft(x.parent)
			ElseIf(x.parent.left = x And x.parent.parent.right = x.parent)
				rotateRight(x.parent)
				rotateLeft(x.parent)
			Else
				rotateLeft(x.parent)
				rotateRight(x.parent)
			End
		End
	End
	
	'************************************************************************
	'* 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 rotateRight:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.left
		
		If (x <> Null)
			h.left = x.right
			x.right = h
			x.parent = h.parent
		End
		
		If (h.left <> Null)
			h.left.parent = h
		End
		
		h.parent = x
		
		If (x.parent = Null)
			root = x
		ElseIf(x.parent.left = h)
			x.parent.left = x
		Else
			x.parent.right = x
		End
		Return x
	End
 
	Method rotateLeft:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.right
		
		If (x <> Null)
			h.right = x.left
			x.left = h
			x.parent = h.parent
		End
		
		If (h.right <> Null)
			h.right.parent = h
		End
		
		h.parent = x
		
		If (x.parent = Null)
			root = x
		ElseIf(x.parent.left = h)
			x.parent.left = x
		Else
			x.parent.right = x
		End
		
		Return x
	End
 
	
	Field root:Node<K, V>
	
End
 
 
'Private
 
Class Node<K, V>
	Field key:K				   ' key
	Field value:V				 ' associated data
	Field left:Node, right:Node   ' left and right subtrees
	Field parent:Node
 
	Method New(key:K, value:V)
		Self.key   = key
		Self.value = value
	End
End
 
 
'Helper versions...
 
Class IntSplayTree<V> Extends SplayTree<Int, V>
	Method Compare(lhs:Int, rhs:Int)
		Return lhs-rhs
	End
End
 
Class FloatSplayTree<V> Extends SplayTree<Float,V>
	Method Compare(lhs:Float, rhs:Float)
		If lhs<rhs Return -1
		Return lhs>rhs
	End
End
 
Class StringSplayTree<V> Extends SplayTree<String,V>
	Method Compare(lhs:String, rhs:String)
		Return lhs.Compare( rhs )
	End
End

Nobuyuki

(Posted 2015) [#3]

hey, thanks a lot man :)

It's all very interesting stuff. I was hoping that someone could get it to work iteratively, and I agree that the splay cost probably outweighs the traversal cost if it's done on every operation. The idea originally was if I could wrap my head around it, to modify / extend the class to basically do what you've done and only splay if the traversal height goes above a certain level, since only a few characters are usually used in a character set at one time, and they're fetched frequently by existing AngelFont code (this is okay in the existing version, because it only supports ascii and all chars are in an array).

That being said, the character map for an international font set, even one that supports CJK, might not exceed 12000 characters, so I'm wondering if there'd be any gain at all if the splay operation stops at a certain point? Traversing >5 levels deep consistently over time might be less efficient than monkey's Map (red-black tree). I guess I just wouldn't know without some real world tests.

I had concerns about efficiency when adapting AngelFont to support unicode for this project, which is why I added a few "ifs" in there to handle ascii the same way as the original, but with all extended characters using a Map. At the time I did it, I was under the belief that the lookup cost for a decent-sized international charset would eat a lot into a game's frame budget, and it was something that kept me from incorporating that support into angelfont-tryouts.

Would you mind me taking the work you've done and putting it up on GitHub? I'll probably add/change a few more things to make it more in sync with Map's methods, maybe throw in some ObjectEnumerators or something.

muddy_shoes

(Posted 2015) [#4]

It's easy enough to test your scenario with the code above. Plug in 12000 elements, a reasonable number for the total characters accesses by an app (<100 for English, certainly) and crank the repeats to a few thousand so the timing has something to work with. For me on HTML5 the splay tree performance is 6x slower than the map even with thresholding turned on.

If you really felt the need to optimise lookups then I'd suggest either generating a secondary cache map or just some sort of lookup table. However, and I know this tends to annoy people when I say this in performance threads, it probably will make no noticeable difference, especially when talking about text where the rendering is generally far more expensive than any lookup will be.

As for the code, use it however you like. It's mostly just a conversion of the wikipedia sample code and some trivial bits from my util libs.

Nobuyuki

(Posted 2015) [#5]

Results are what's important, I don't think I have to worry about lookup times when using a Map most likely :)

probably gonna have to figure out how to do a Remove non-recursively, since I apparently never even tested the code (it wouldn't even compile anyway since I missed a declare line when porting, whoops!)

muddy_shoes

(Posted 2015) [#6]

Here's a version with a delete. I've also manufactured a scenario where the splay tree does eventually beat out the map. It's not your scenario unfortunately.

Import mojo
'#CPP_GC_MODE=0
 
Function Main:Int()
	New Game()
End Function

#STRING_KEY = True
 
Class Game Extends App
	Const NUM_VALUES = 20000  'Number of values each tree will contain in this test.
	Const FETCH_AMT = 100     'Amount of gets done each fetch cycle.
	Const REPEATS = 200	'number of times to repeat the fetch group
	
	Const DELETES_AND_INSERTS:Int = 200
		
#if STRING_KEY
	Field testMap:= New StringMap<String>
	Field testSplay:= New StringSplayTree<String>
 
	Field fetchKeys:String[]
	Field deletes:String[]
#else
	Field testMap:= New IntMap<String>
	Field testSplay:= New IntSplayTree<String>
 
	Field fetchKeys:Int[]
	Field deletes:Int[]
#end
	
	Field fetchVals:String[]
		
	Field mapFetchTime:Float
	Field splayFetchTime:Float
	Field numTests:Int = 1
	
	Const NUM_SAMPLES:Int = 500
	Field sampleStartIndex = 0
	Field mapSamples:Float[] = New Float[NUM_SAMPLES]
	Field splaySamples:Float[] = New Float[NUM_SAMPLES]
	Const GRAPH_Y_HEIGHT:Int = 300
	Field maxTime:Float
	Field yScale:Float
	
	Method OnCreate:Int()
		SetUpdateRate 3
		
		'Load up the trees with some values.
		Local time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			testMap.Set(i, "KeyValue " + i)
		End
		time = Millisecs() - time
		Print("Map insert time: " + time)
		
		time = Millisecs()
		For Local i:Int = 0 Until NUM_VALUES
			testSplay.Set(i, "KeyValue " + i)
		End
		time = Millisecs() - time
		Print("Splay insert time: " + time)
		
		'Validate that the inserts succeeded.
		Print("Map size: " + testMap.Count())
		Print("Splay size: " + testSplay.Size())
		'Print testSplay.Height()
		
		deletes = deletes.Resize(DELETES_AND_INSERTS)
		
		'Prepare testMap set of values to fetch.
		fetchKeys = fetchKeys.Resize(FETCH_AMT)
		
		For Local i:Int = 0 Until FETCH_AMT
#if STRING_KEY
			fetchKeys[i] = "KeyValue " + Int(Rnd(NUM_VALUES))
#else
			fetchKeys[i] = Int(Rnd(NUM_VALUES))
#end
		End
		
		'Now, let's fetch these values testMap few times from our trees.
		time = Millisecs()
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= testMap.Get(fetchKeys[i])
			End
		End
		time = Millisecs() - time
		mapFetchTime += time
		Print("Initial Map fetch time: " + time)
 
		time = Millisecs()
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= testSplay.Get(fetchKeys[i])
				'Print val
				'If (val.Compare("KeyValue " + fetchKeys[i]) <> 0)
				'	Error val
				'End
			End
		End
		time = Millisecs() - time
		splayFetchTime += time
		Print("Initial Splay fetch time: " + time)
		
		mapSamples[0] = mapFetchTime
		splaySamples[0] = splayFetchTime
		maxTime = Max(mapFetchTime,splayFetchTime)
		yScale = Float(GRAPH_Y_HEIGHT)/maxTime
	End
	
	Method OnUpdate:Int()
		
		numTests += 1
		
		For Local i:Int = 0 Until DELETES_AND_INSERTS
			Local index:Int = Int(Rnd(NUM_VALUES))
#if STRING_KEY
			deletes[i] = "KeyValue " + index 
#else
			deletes[i] = index
#end
		End
		
		'Fetch testMap 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 DELETES_AND_INSERTS
			Local key := deletes[i]
			testMap.Remove(key)
			testMap.Insert(key, "KeyValue " + key)
		End
		For Local j:Int = 0 Until REPEATS			
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= testMap.Get(fetchKeys[i])
			End
		End
		time = Millisecs() - time
		mapFetchTime += time
		mapSamples[numTests mod NUM_SAMPLES] = time
		
		time = Millisecs()
		For Local i:Int = 0 Until DELETES_AND_INSERTS
			Local key := deletes[i]
			testSplay.Delete(key)
			testSplay.Set(key, "KeyValue " + key, False)
		End
		
		For Local j:Int = 0 Until REPEATS
			For Local i:Int = 0 Until FETCH_AMT
				Local val:= testSplay.Get(fetchKeys[i])
				'If (val.Compare("KeyValue " + fetchKeys[i]) <> 0)
				'	Error val
				'End
			End
		End
		time = Millisecs() - time
		splaySamples[numTests mod NUM_SAMPLES] = time
		splayFetchTime += time
		
		If( numTests / NUM_SAMPLES >= 1 )
			sampleStartIndex = (sampleStartIndex + 1) Mod NUM_SAMPLES
		End
				
		maxTime = Max(maxTime,(Max(mapSamples[numTests mod NUM_SAMPLES],splaySamples[numTests mod NUM_SAMPLES])))
		yScale = Float(GRAPH_Y_HEIGHT)/maxTime
		If( testMap.Count() <> testSplay.Size() )
			Error "Datasets out of sync"
		End
	End
	
	Method OnRender:Int()
		Cls()
		
		DrawText("Mean Map fetch time:   " + FloatToString(mapFetchTime/numTests,2), 8, 8)
		DrawText("Mean Splay fetch time: " + FloatToString(splayFetchTime/numTests,2), 8, 32)
				
		Local xBase:Int = 20
		Local yBase:Int = 400
		
		For Local i:Int = 0 Until NUM_SAMPLES
			SetColor(48,48,248)
			DrawPoint(xBase + i, yBase - Int(mapSamples[ (sampleStartIndex+i) mod NUM_SAMPLES ] * yScale))
			SetColor(16,248,16)
			DrawPoint(xBase + i, yBase - Int(splaySamples[ (sampleStartIndex+i) mod NUM_SAMPLES ] * yScale))
		End
		
		SetColor(255,255,255)
		DrawLine(xBase-1,yBase+1,xBase-1,yBase-GRAPH_Y_HEIGHT-1)
		DrawLine(xBase-1,yBase+1,xBase+NUM_SAMPLES+1,yBase+1)
		 
	End
	
	Function FloatToString:String( f:Float, decimals:Int)
		Local retString:String = String(f)
		Local dp:Int = retString.FindLast(".")
    
		If dp = -1
			dp = retString.Length
		End
    
		dp += decimals+1
    
		If dp > retString.Length
			dp = retString.Length
		End
    
		retString = retString[0..dp]
    
		Return retString

	End
	
	Function Wrap:Int( value:Int, low:Int, high:Int )
		Local range:Int = 1+high-low
			
		If value > high
			Return low + (value-low) Mod range
		ElseIf value < low
			Return high - (high-value) Mod range
		End
			
		Return value
	End
End
 
#THRESHOLD = True
 
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
		elementCount = 0
	End
	
	Method IsEmpty:Bool()
		Return root=Null
	End
 
	Method Contains:Bool(key:K)
		Return (Get(key) <> null)
	End
 
	Field findCompares:Int = 0
	Field splayThreshold:Int = 0
	
	Method Find:Node<K, V>(key:K)
		findCompares = 0
		Local found:Bool = False
		Local currNode:Node<K, V> = root
		
		While ( Not found)
			Local cmp:Int = Compare(key, currNode.key)
			findCompares += 1
			If (cmp < 0)
				If (currNode.left = Null)
					Return Null
				Else
					currNode = currNode.left
				End
			ElseIf(cmp > 0)
				If (currNode.right = Null)
					Return Null
				Else
					currNode = currNode.right
				End
			Else
				found = True
			End
		End
		
		Return currNode
	End
	
	' return value associated with the given key
	' If no such value, return null
	Method Get:V(key:K)
		
		Local node:Node<K, V> = Find(key)
		
		If (node <> Null)
			#if THRESHOLD
			If (findCompares > splayThreshold)
				Splay(node)
			End
			#else
			Splay(node)
			#end
			Return node.value
		End
		
	End
 
	Method Insert:Node<K, V>(key:K, value:V, splay:Bool = True)
	
		Local insertNode:Node<K,V> = New Node<K, V>(key, value)
		
		If (root = Null)
			root = insertNode
			Return root
		End If
		
		Local inserted:Bool = False
		Local currNode:Node<K, V> = root
		
		While ( Not inserted)
			Local cmp:Int = Compare(key, currNode.key)
			
			If (cmp < 0)
				If (currNode.left = Null)
					currNode.left = insertNode
					insertNode.parent = currNode
					inserted = True
					elementCount += 1
				Else
					currNode = currNode.left
				End
			ElseIf(cmp > 0)
				If (currNode.right = Null)
					currNode.right = insertNode
					insertNode.parent = currNode
					inserted = True
					elementCount += 1
				Else
					currNode = currNode.right
				End
			Else
				currNode.value = value
				inserted = True
			End
		End
		
		#if THRESHOLD
		splayThreshold = Min(3, Int(Log(elementCount) * 1.442695 * 0.25))
		#end
		Return insertNode
	End
	
	'*************************************************************************
	'*  Splay insertion
	'*************************************************************************
	Method Set:Void(key:K, value:V, splay:Bool = True)
		
		Local insertedNode:Node<K, V> = Insert(key, value)
		
		If( splay )
			Splay(insertedNode)
		End
		
	End
	
	Method Replace:Void( u:Node<K,V>, v:Node<K,V> )
		If( u.parent = Null ) 
			root = v
		ElseIf( u = u.parent.left ) 
			u.parent.left = v
		Else 
			u.parent.right = v
		End
		
		If( v <> Null ) 
			v.parent = u.parent
		End
	End
	
	Method FindMinimum:Node<K,V>( root:Node<K,V> )
		Local currNode:Node<K,V> = root
		
		While currNode.left <> Null
			currNode = currNode.left
		End
		
		Return currNode
	End

	Method Delete( key:K )
		Local z:Node<K,V> = Find( key )
	
		If( z = Null ) 
			Return
		End
 
		Splay( z )
 
		If( z.left = Null )
			Replace( z, z.right )
		ElseIf( z.right = Null ) 
			Replace( z, z.left )
		Else 
			Local y:Node<K,V> = FindMinimum( z.right )
			If( y.parent <> z ) 
				Replace( y, y.right )
				y.right = z.right
				y.right.parent = y
			End
			
			Replace( z, y )
			y.left = z.left
			y.left.parent = y
		End
 
 		elementCount -= 1
#if THRESHOLD
		splayThreshold = Min(3, Int(Log(elementCount) * 1.442695 * 0.25))
#end
	End
	
	'*************************************************************************
	'*  Splay deletion
	'*************************************************************************/
	' * This Splays the key, then does testMap 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)
				If (x <> Null)
					x.parent = root
				End
				root.right = x
			End If
			
			root.parent = Null
			elementCount -= 1
		End If
		' else: it wasn't in the tree to remove
		#if THRESHOLD
		splayThreshold = Min(3, Int(Log(elementCount) * 1.442695 * 0.25))
		#end
	End
	
	'   /*************************************************************************
	'	*  helper functions
	'	*************************************************************************/
 
	' height of tree (1-node tree has height 0)
	Method Height:Int()
		Return Height(root)
	End
	
	Method Size:Int()
		Return Size(root)
	End
 
	
	Private
 
	Field elementCount:Int
	
	Method Height(x:Node<K, V>)
		If x = Null Then Return - 1
		Return 1 + Max(Height(x.left), Height(x.right))
	End
	
	Method Size:Int(x:Node<K, V>)
		Local count:Int = 0
		Local parentStack:Stack<Node<K, V>> = New Stack<Node<K, V>>()
		Local currNode:Node<K, V> = x
		
		While ( Not parentStack.IsEmpty() Or currNode <> Null)
			If (currNode <> Null)
				parentStack.Push(currNode)
				currNode = currNode.left
			Else
				currNode = parentStack.Pop()
				count += 1
				currNode = currNode.right
			End
		End
		Return count
	End
		
	
	Method Splay:Void(x:Node<K, V>)
		While (x.parent <> Null)
			If (x.parent.parent = Null)
				If (x.parent.left = x)
					rotateRight(x.parent)
				Else
					rotateLeft(x.parent)
				End
			ElseIf(x.parent.left = x And x.parent.parent.left = x.parent)
				rotateRight(x.parent.parent)
				rotateRight(x.parent)
			ElseIf(x.parent.right = x And x.parent.parent.right = x.parent)
				rotateLeft(x.parent.parent)
				rotateLeft(x.parent)
			ElseIf(x.parent.left = x And x.parent.parent.right = x.parent)
				rotateRight(x.parent)
				rotateLeft(x.parent)
			Else
				rotateLeft(x.parent)
				rotateRight(x.parent)
			End
		End
	End
	
	'************************************************************************
	'* Splay function
	'* **********************************************************************/
	' Splay key in the tree rooted at Node h. If testMap 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 rotateRight:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.left
		
		If (x <> Null)
			h.left = x.right
			x.right = h
			x.parent = h.parent
		End
		
		If (h.left <> Null)
			h.left.parent = h
		End
		
		h.parent = x
		
		If (x.parent = Null)
			root = x
		ElseIf(x.parent.left = h)
			x.parent.left = x
		Else
			x.parent.right = x
		End
		Return x
	End
 
	Method rotateLeft:Node<K, V>(h:Node<K, V>)
		Local x:Node<K, V> = h.right
		
		If (x <> Null)
			h.right = x.left
			x.left = h
			x.parent = h.parent
		End
		
		If (h.right <> Null)
			h.right.parent = h
		End
		
		h.parent = x
		
		If (x.parent = Null)
			root = x
		ElseIf(x.parent.left = h)
			x.parent.left = x
		Else
			x.parent.right = x
		End
		
		Return x
	End
 
	
	Field root:Node<K, V>
	
End
 
 
'Private
 
Class Node<K, V>
	Field key:K				   ' key
	Field value:V				 ' associated data
	Field left:Node, right:Node   ' left and right subtrees
	Field parent:Node
 
	Method New(key:K, value:V)
		Self.key   = key
		Self.value = value
	End
End
 
 
'Helper versions...
 
Class IntSplayTree<V> Extends SplayTree<Int, V>
	Method Compare(lhs:Int, rhs:Int)
		Return lhs-rhs
	End
End
 
Class FloatSplayTree<V> Extends SplayTree<Float,V>
	Method Compare(lhs:Float, rhs:Float)
		If lhs<rhs Return -1
		Return lhs>rhs
	End
End
 
Class StringSplayTree<V> Extends SplayTree<String,V>
	Method Compare(lhs:String, rhs:String)
		Return lhs.Compare( rhs )
	End
End

Nobuyuki

(Posted 2015) [#7]

haha, doin' all the work for me, huh?

The second example is kinda weird. I'm starting to trim and rename functions since it's becoming a bit of a mess. The old recursive Splay() isn't used anymore, so that's the first to go. I've also renamed Insert() to Set(), changed its output type, moved several methods to Private, and renamed Delete() to Remove() while deleting the old Remove().

In your second example, you're doing an insert/remove cycle, but it should be noted that in the code provided, it appears that SplayTree.Insert() as it was would never splay because Splay() was never called anywhere in the method(). This has been fixed. Furthermore, Map.Insert() is depreciated and is just a call to Set(), so .... :)

Here's the code so far after an initial cleanup: https://github.com/nobuyukinyuu/monkey-splaytree

muddy_shoes

(Posted 2015) [#8]

Sure, I was just hacking around so I left old code lying about. The not splaying on insert is intentional, although I must have pasted older code as I changed Set to have a splay option. It only makes sense to splay on insert if you expect retrievals of recently inserted elements.

Nobuyuki

(Posted 2015) [#9]

by the way, do you know if there are "canonical" best practices for ObjectEnumerators? I personally don't care if the tree gets traversed in any particular order, but it seems that the existing containers spit out objects in a sorted order, whereas traversing the splay tree in a similar fashion to Find() would seem likely to spit out elements in semi-last-accessed order. I'm not aware that anyone should expect EachIn to return the values from any container in any particular order; was just asking if you know if this is just something most people assume that most containers will do. Obviously expecting that seems incompatible with the way a splay tree is structured.

muddy_shoes

(Posted 2015) [#10]

Nope. People make all sorts of assumptions about how collections should be enumerated. I tend to think that the default should be whatever is cheapest unless the collection makes explicit claims about being sorted. I tend to write in order enumerators for ordered trees though.

Nobuyuki

(Posted 2015) [#11]

Cool. Allright, I've updated the source code with enumerators. Using EachIn on the tree itself produces a Stack<Node<K,V>> for the duration of the traversal. In addition, the usual enumerator overhead applies, including extra objects created to allow eachIn to work on .Keys() and .Values().