SuperStrict

Import "tpriorityheap.bmx"

'define some priorities
Const P_LOW:Int = 4
Const P_NORMAL:Int = 3
Const P_HIGH:Int = 2
Const P_IMMEDIATE:Int = 1

'extend standard heap node
Type TAction Extends THeapNode
	
	Field _text:String
	
	Function CreateAction:TAction(pr:Int, txt:String)
		Local tmpAction:TAction = New TAction
		tmpAction._priority = pr
		tmpAction._text		= txt
		Return tmpAction
	End Function
	
	Method execute()
		Print _text
	End Method
	
End Type

'create my heap
Global myHeap:TPriorityHeap = New TPriorityHeap

'add a few actions
myHeap.addNode(TAction.CreateAction(P_LOW, "Low priority"))
myHeap.addNode(TAction.CreateAction(P_NORMAL, "Normal priority"))
myHeap.addNode(TAction.CreateAction(P_LOW, "Low priority #2"))
myHeap.addNode(TAction.CreateAction(P_HIGH, "High priority"))
myHeap.addNode(TAction.CreateAction(P_IMMEDIATE, "*** URGENT ***"))
myHeap.addNode(TAction.CreateAction(P_NORMAL, "Normal priority"))
myHeap.addNode(TAction.CreateAction(P_IMMEDIATE, "*** URGENT ***"))
myHeap.addNode(TAction.CreateAction(P_HIGH, "High priority"))

'execute these actions
While Not myHeap.isEmpty()
	TAction(myHeap.removeHighest()).execute()
Wend

Const BLOCK_SIZE:Int = 16

Type TPriorityHeap
	
	Field _data:THeapNode[]
	Field _heapPtr:Int

	Method New()
		_data = New THeapNode[BLOCK_SIZE]
	End Method
	
	Rem
		Adds a new element to the heap
	End Rem
	Method add(priority:Int, obj:Object)
		_reallocateHeap()
		
		' add the element at the end of the heap
		_data[_heapPtr] = THeapNode.Create(priority, obj)
		_heapPtr:+1
		
		_siftUp(_heapPtr-1)
	End Method

	Rem
		Adds a new element to the heap
	End Rem
	Method addNode(node:THeapNode)
		_reallocateHeap()
		
		' add the element at the end of the heap

		_data[_heapPtr] = node
		_heapPtr:+1
		
		_siftUp(_heapPtr-1)
	End Method
	
	Rem
		Returns true if the heap is empty
	End Rem
	Method isEmpty:Byte()
		Return (_heapPtr = 0)
	End Method
	
	Rem
		Returns the element with highest priority from the heap
	End Rem
	Method removeHighest:THeapNode()

		' no nodes left 
		If _heapPtr = 0 Return Null

		Local tmpNode:THeapNode = _data[0]
		' swap lowest with last heap item 
		_data[0] = _data[_heapPtr-1]
		_heapPtr:-1
		' restore heap condition 
		_heapify(0)
		Return tmpNode
	End Method
	
	Rem
		allocates new space block wise for extra speed
	End Rem
	Method _reallocateHeap()
		If _heapPtr => _data.Length-1
			_data = _data[.._data.length+BLOCK_SIZE]
		EndIf
	End Method
	
	Rem
		Restores the heap condition after inserting a new item
	End Rem
	Method _siftUp(i:Int)
		Local father:Int = Floor(i/2)
		While i > 0 And _data[i].priority() < _data[father].priority()
			Local tmpNode:THeapNode = _data[i]
			_data[i] = _data[father]
			_data[father] = tmpNode
			i = father
			father = Floor(i/2)
		Wend
	End Method
	
	Rem
		Heap items with lower priority go down the heap until the heap condition is met
	End Rem
	Method _heapify(i:Int)
		Local leftId:Int = 2*i
		Local rightId:Int = 2*i+1
		Local smallest:Int = i

		If (leftId < _heapPtr) And (_data[leftId].priority() < _data[i].priority())
			smallest = leftId
		End If
		
		If (rightId < _heapPtr) And (_data[rightId].priority() < _data[smallest].priority())
			smallest = rightId
		End If
		
		If i <> smallest
			Local tmpNode:THeapNode = _data[i]
			_data[i] = _data[smallest]
			_data[smallest] = tmpNode
			_heapify(smallest)
		End If
	End Method
	
	Rem
		DEBUG prints out the heap
	End Rem
	Method prnt()
		For Local i:Int = 0 Until _heapPtr
			Print _data[i].priority()
		Next
	End Method
	
End Type

Rem
	The heap node stores the priority and the associated object
End Rem
Type THeapNode
	
	Field _priority:Int
	Field _data:Object
	
	Rem
		Creates a new heap node and returns it
	End Rem
	Function Create:THeapNode(priority:Int, data:Object)
		Local tmpNode:THeapNode = New THeapNode
		tmpNode._priority = priority
		tmpNode._data = data
		Return tmpNode
	End Function
	
	Method priority:Int()
		Return _priority
	End Method
	
	Method data:Object()
		Return _data
	End Method
	
End Type