March 05, 2021, 07:13:26 AM

Author Topic: [bmx] THeap by Dreamora [ 1+ years ago ]  (Read 410 times)

Offline BlitzBot

[bmx] THeap by Dreamora [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
Title : THeap
Author : Dreamora
Posted : 1+ years ago

Description : Lightweight THeap datastructure for priority queues etc

Code :
Code: BlitzMax
  1. Strict
  2. Rem
  3.     bbdoc: Heap
  4.     about: Heap class. Can be used for sorting as well as "get always the smallest / largest"
  5. End Rem
  6. Rem
  7. Module dreamora.ds_heap
  8.  
  9. ModuleInfo "Version: 1.0"
  10. ModuleInfo "Author: Marc 'Dreamora' Schaerer"
  11. ModuleInfo "License: Public domain"
  12. ModuleInfo "Copyright: 2006  Marc 'Dreamora' Schaerer"
  13. ModuleInfo "Modserver: dreamora"
  14.  
  15. ModuleInfo "History:"
  16. moduleinfo "-   1.0 Release"
  17. End Rem
  18. Import brl.retro
  19.  
  20. Rem
  21.         bbdoc: THeap
  22.         about: Heap class
  23. End Rem
  24. Type THeap
  25.         Field _data:Object[]
  26.         Field _ascending:Int
  27.         Field _length:Int = 1
  28.         Field _sortingFunction:Int(one:Object,two:Object)
  29.        
  30.         Rem
  31.                 bbdoc: Create
  32.                 about: Creates a new THeap and returns the reference to it.<br>
  33.                 <b>elements:</b> Number of elements you want the heap to initialize with.<br>
  34.                 The heap will dynamically resize if more elements are added than needed and that in a very performant way.<br>
  35.                 This is only if you now that you will push x object directly onto it.<br>
  36.                 Defaults to 1.<br>
  37.                 <b>maximum:</b> Defines if the heap has maximum on top (true) or minimum.<br>
  38.                 Defaults to maximum.<br>
  39.                 <b>ComparisionFunction:int( one:Object,two:Object):</b> Lets you define an own comparision function.<br>
  40.                 The example shows how to use it and for what type of stuff it might be usefull after all.<br>
  41.                 Defaults to BMs internal compare Objects functionality.
  42.                 returns: A valid reference to a THeap object
  43.         End Rem
  44.         Function Create:THeap(elements:Int = 16, maximum:Int = True, ComparisionFunction:Int( one:Object,two:Object)=CompareObjects)
  45.                 Local result:THeap      = New THeap
  46.                 result._data            = New Object[elements]
  47.                 result._ascending       = maximum
  48.                 result._sortingFunction = ComparisionFunction
  49.                 Return result
  50.         End Function
  51.        
  52.         Rem
  53.                 bbdoc: Add
  54.                 about: Adds a new object to the heap.<br>
  55.                 <b>obj:</b> Object you want to add to the heap.
  56.         End Rem
  57.         Method Add(obj:Object)
  58.                 If _length = _data.length               _data   = _data[.._data.length*2]
  59.                 _data[_length] = obj
  60.                 Local ret:Int = _bubbleUp(_length)
  61.                 If ret > 0              _siftDown(ret)
  62.                 _length :+ 1
  63.         End Method
  64.        
  65.         Rem
  66.                 bbdoc: Top
  67.                 about: Returns the top element on the heap, without removing it.
  68.                 returns: Top element on the heap
  69.         End Rem
  70.         Method Top:Object()
  71.                 If isEmpty()                    Throw "THeap.Top: Not supported on an empty heap!"
  72.                 Return _data[1]
  73.         End Method
  74.        
  75.         Rem
  76.                 bbdoc: GetTop
  77.                 about: Returns the top element on the heap, but with removing it!
  78.                 returns: Top element on the heap
  79.         End Rem
  80.         Method GetTop:Object()
  81.                 If isEmpty()            Throw "THeap.GetTop: Not supported on an empty heap!"
  82.                 Local tmp:Object        = _data[1]
  83.                 _data[1]        = _data[_length-1]
  84.                 _length :- 1
  85.                 _siftDown(1)
  86.                 If _data.length <= 0.35 * _length               _data   = _data[.._data.length/2]
  87.                 Return tmp
  88.         End Method
  89.        
  90.         Rem
  91.                 bbdoc: Count
  92.                 about: Returns the number of elements on the heap.
  93.                 returns: Number of elements on the heap.
  94.         End Rem
  95.         Method Count:Int()
  96.                 Return _length-1
  97.         End Method
  98.        
  99.         Rem
  100.                 bbdoc: isEmpty
  101.                 about: Returns if the heap is empty.
  102.                 returns: True if it is empty, otherwise false.
  103.         End Rem
  104.         Method isEmpty:Int()
  105.                 Return _length = 1
  106.         End Method
  107.        
  108.         Method _bubbleUp:Int(index:Int)
  109.                 Local tmp:Object                = _data[index]
  110.                 If _ascending
  111.                         While index > 1 And _sortingFunction(tmp,_data[index/2]) > 0
  112.                                 _data[index]    = _data[index/2]
  113.                                 index                   :/ 2
  114.                         Wend
  115.                 Else
  116.                         While index > 1 And _sortingFunction(tmp,_data[index/2]) < 0
  117.                                 _data[index]    = _data[index/2]
  118.                                 index                   :/ 2
  119.                         Wend
  120.                 EndIf
  121.                 _data[index]            = tmp
  122.                 Return index
  123.         End Method
  124.        
  125.         Method _siftDown(index:Int)
  126.                 Local tmp:Object                        = _data[index]
  127.                 Local j:Int
  128.                 Local N:Int                                     = _length - 1
  129.                 If _ascending
  130.                         While index <= N/2
  131.                                 j       = index+index
  132.                                 If _data[j+1] And _sortingFunction(_data[j + 1],_data[j]) > 0   j :+ 1
  133.                                 If _sortingFunction(tmp,_data[j]) >  0                                  Exit
  134.                                 _data[index]            = _data[j]
  135.                                 index                           = j
  136.                         Wend
  137.                 Else
  138.                         While index <= N/2
  139.                                 j       = index+index
  140.                                 If _data[j+1] And _sortingFunction(_data[j + 1],_data[j]) < 0   j :+ 1
  141.                                 If _sortingFunction(tmp,_data[j]) <  0                                  Exit
  142.                                 _data[index]            = _data[j]
  143.                                 index                           = j
  144.                         Wend
  145.                 EndIf
  146.                 _data[index]                    = tmp
  147.         End Method
  148. End Type
  149.  
  150.  
  151.  
  152. Function CompareObjects:Int(o1:Object, o2:Object)
  153.         Return o1.compare(o2)
  154. End Function


Comments :


NoOdle(Posted 1+ years ago)

 thanks, useful code! What would be the fastest way to amend a priority and resort the heap if you really needed to?


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal