December 03, 2020, 08:31:54 PM

Author Topic: [bmx] Heap by Pineapple [ 1+ years ago ]  (Read 403 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Heap by Pineapple [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
Title : Heap
Author : Pineapple
Posted : 1+ years ago

Description : Just a regular old heap type module

Code :
Code: BlitzMax
  1. '       --+-----------------------------------------------------------------------------------------+--
  2. '         |   This code was originally written by Sophie Kirschner (sophiek@pineapplemachine.com)   |  
  3. '         | It is released as public domain. Please don't interpret that as liberty to claim credit |  
  4. '         |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |  
  5. '         |                because that would be a really shitty thing of you to do.                |
  6. '       --+-----------------------------------------------------------------------------------------+--
  7.  
  8.  
  9. SuperStrict
  10.  
  11.  
  12. Rem
  13. bbdoc: Data structures/Heaps
  14. End Rem
  15. Module pine.heap
  16.  
  17. ModuleInfo "Version: 1.00"
  18. ModuleInfo "Author: Sophie Kirschner : meapineapple@gmail.com"
  19. ModuleInfo "License: Public domain"
  20. ModuleInfo "Modserver: pine"
  21.  
  22.  
  23.         Rem
  24.         bbdoc: Create a new heap
  25.         returns: A new heap
  26.         End Rem
  27. Function CreateHeap:THeap(descending:Int=True,dynamic:Int=True,depth:Int=4,comparisonfunc:Int(o1:Object,o2:Object)=CompareObjects)
  28.         Return THeap.Create(depth,descending,dynamic,comparisonfunc)
  29. End Function
  30.         Rem
  31.         bbdoc: Clear a heap
  32.         End Rem
  33. Function ClearHeap(heap:THeap)
  34.         heap.clear
  35. End Function
  36.         Rem
  37.         bbdoc: Create a copy of a heap
  38.         returns: A new heap with contents and properties identical to the original
  39.         End Rem
  40. Function CopyHeap:THeap(heap:THeap)
  41.         Return heap.copy()
  42. End Function
  43.         Rem
  44.         bbdoc: Insert a new value into the heap
  45.         returns: The index of the new value in the heap's array
  46.         End Rem
  47. Function HeapInsert:Int(heap:THeap,value:Object)
  48.         Return heap.insert(value)
  49. End Function
  50.         Rem
  51.         bbdoc: Insert an array of new values into the heap
  52.         End Rem
  53. Function HeapInsertArray(heap:THeap,array:Object[])
  54.         heap.insertarray array
  55. End Function
  56.         Rem
  57.         bbdoc: Get the value in a heap's array at the given index
  58.         returns: The object in the heap at the given @index
  59.         about: Note that the heap starts storing objects at 1, not 0
  60.         End Rem
  61. Function HeapValue:Object(heap:THeap,index:Int)
  62.         Return heap.data[index]
  63. End Function
  64.         Rem
  65.         bbdoc: Get the object at the top of a heap
  66.         returns: The object at the top of the heap
  67.         End Rem
  68. Function HeapTop:Object(heap:THeap)
  69.         Return heap.top()
  70. End Function
  71.         Rem
  72.         bbdoc: Get and remove the object at the top of a heap
  73.         returns: The object at the top of the heap
  74.         End Rem
  75. Function HeapRemove:Object(heap:THeap)
  76.         Return heap.removetop()
  77. End Function
  78.         Rem
  79.         bbdoc: Sort the contents of some array using heapsort
  80.         End Rem
  81. Function HeapSortArray(array:Object[],descending:Int=True,comparisonfunc:Int(o1:Object,o2:Object)=CompareObjects)
  82.         THeap.sortarray(array,descending,comparisonfunc)
  83. End Function
  84.         Rem
  85.         bbdoc: Get a sorted array from a heap
  86.         returns: An array containing the sorted contents of the heap
  87.         End Rem
  88. Function HeapToArray:Object[](heap:THeap,reverseorder:Int=False)
  89.         Return heap.tosortedarray(reverseorder)
  90. End Function
  91.         Rem
  92.         bbdoc: Get a heapified array from a heap
  93.         returns: An array containing the heapified contents of the heap
  94.         End Rem
  95. Function HeapToUnsortedArray:Object[](heap:THeap)
  96.         Return heap.toarray()
  97. End Function
  98.         Rem
  99.         bbdoc: Get the number of values in a heap
  100.         returns: The number of values in the heap
  101.         End Rem
  102. Function CountHeap:Int(heap:THeap)
  103.         Return heap.count()
  104. End Function
  105.         Rem
  106.         bbdoc: Determine whether the heap contains any values
  107.         returns: 1 if the heap is empty, 0 if it contains any values
  108.         End Rem
  109. Function HeapIsEmpty:Int(heap:THeap)
  110.         Return heap.isempty()
  111. End Function
  112.         Rem
  113.         bbdoc: Merge two heaps into one
  114.         about: All the contents of @other are copied into @heap
  115.         End Rem
  116. Function HeapMerge(heap:THeap,other:THeap)
  117.         heap.merge other
  118. End Function
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.         Rem
  126.         bbdoc: A heap object
  127.         End Rem
  128. Type THeap
  129.         Field data:Object[]
  130.         Field sortfunc%(o1:Object,o2:Object)=CompareObjects
  131.         Field dir%=True,dynamic%=True
  132.         Field length%=1
  133.         Field minsize%=%11111 'don't dynamically shrink if it's already this small or smaller
  134.         Field maxsize%=$7fffffff 'don't dynamically grow if it's already this small or smaller
  135.         Rem
  136.         bbdoc: Sort the contents of some array using heapsort
  137.         End Rem
  138.         Function sortarray(array:Object[],descending:Int=False,comparisonfunc:Int(o1:Object,o2:Object)=CompareObjects)
  139.                 Local h:THeap=New THeap
  140.                 h.dynamic=False
  141.                 h.dir=descending
  142.                 h.sortfunc=comparisonfunc
  143.                 h.data=New Object[array.length+1]
  144.                 For Local x%=0 To array.length-1
  145.                         h.insert array[x]
  146.                 Next
  147.                 For Local x%=0 To array.length-1
  148.                         array[x]=h.removetop()
  149.                 Next
  150.         End Function
  151.         Rem
  152.         bbdoc: Create a new heap
  153.         returns: A new heap
  154.         End Rem
  155.         Function Create:THeap(depth:Int=4,maximum:Int=True,dynamic:Int=True,comparisonfunc:Int(o1:Object,o2:Object)=CompareObjects)
  156.                 Local h:THeap=New THeap
  157.                 h.dir=maximum
  158.                 h.dynamic=dynamic
  159.                 h.sortfunc=comparisonfunc
  160.                 If depth>31 Then depth=31
  161.                 If depth>=0 h.data=New Object[($ffffffff Shr (32-depth))+1] Else h.data=New Object[2]
  162.                 Return h
  163.         End Function
  164.         Rem
  165.         bbdoc: Clear a heap
  166.         End Rem
  167.         Method clear()
  168.                 length=1
  169.                 If dynamic Then data=New Object[minsize]
  170.         End Method
  171.         Rem
  172.         bbdoc: Insert a new value into the heap
  173.         returns: The index of the new value in the heap's array
  174.         End Rem
  175.         Method insert%(value:Object)
  176.                 If dynamic And data.length<=maxsize Then
  177.                         While length>=data.length
  178.                                 data=data[..data.length*2]
  179.                         Wend
  180.                 ElseIf length>=data.length
  181.                         Return -1
  182.                 EndIf
  183.                 data[length]=value
  184.                 Local r%=up(length)
  185.                 If r>0 r=down(r)
  186.                 length:+1
  187.                 Return r
  188.         End Method
  189.         Rem
  190.         bbdoc: Get a heapified array from a heap
  191.         returns: An array containing the heapified contents of the heap
  192.         End Rem
  193.         Method toarray:Object[]()
  194.                 Return data[1..length]
  195.         End Method
  196.         Rem
  197.         bbdoc: Get a sorted array from a heap
  198.         returns: An array containing the sorted contents of the heap
  199.         End Rem
  200.         Method tosortedarray:Object[](reverse%=False)
  201.                 Local tl%=length,t:Object[]=data[0..]
  202.                 Local r:Object[]=New Object[length-1]
  203.                 For Local x%=0 To length-2
  204.                         If reverse
  205.                                 r[r.length-1-x]=removetop()
  206.                         Else
  207.                                 r[x]=removetop()
  208.                         EndIf
  209.                 Next
  210.                 length=tl;data=t
  211.                 Return r
  212.         End Method
  213.         Rem
  214.         bbdoc: Insert an array of new values into the heap
  215.         End Rem
  216.         Method insertarray%(array:Object[])
  217.                 If dynamic
  218.                         If length+array.length>maxsize Return 0
  219.                         If length+array.length>data.length Then data=data[..length+array.length]
  220.                 ElseIf length+array.length>=data.length
  221.                         Return 0
  222.                 EndIf
  223.                 Local r%
  224.                 For Local x%=0 To array.length-1
  225.                         data[length]=array[x]
  226.                         r=up(length)
  227.                         If r>0 down r
  228.                         length:+1
  229.                 Next
  230.                 Return 1
  231.         End Method
  232.         Rem
  233.         bbdoc: Merge two heaps into one
  234.         about: All the contents of @other are copied into @heap
  235.         End Rem
  236.         Method merge%(other:THeap)
  237.                 If dynamic
  238.                         If length+other.length>maxsize Return 0
  239.                         If length+other.length>data.length Then data=data[..length+other.length]
  240.                 ElseIf length+other.length>=data.length
  241.                         Return 0
  242.                 EndIf
  243.                 Local r%
  244.                 For Local x%=1 To other.length-1
  245.                         data[length]=other.data[x]
  246.                         r=up(length)
  247.                         If r>0 down r
  248.                         length:+1
  249.                 Next
  250.                 Return 1
  251.         End Method
  252.         Rem
  253.         bbdoc: Create a copy of a heap
  254.         returns: A new heap with contents and properties identical to the original
  255.         End Rem
  256.         Method copy:THeap()
  257.                 Local n:THeap=New THeap
  258.                 n.dir=dir
  259.                 n.length=length
  260.                 n.dynamic=dynamic
  261.                 n.minsize=minsize
  262.                 n.maxsize=maxsize
  263.                 n.sortfunc=sortfunc
  264.                 n.data=data[0..]
  265.                 Return n
  266.         End Method
  267.         Rem
  268.         bbdoc: Get the object at the top of a heap
  269.         returns: The object at the top of the heap
  270.         End Rem
  271.         Method top:Object()
  272.                 If length=<1 Return Null
  273.                 Return data[1]
  274.         End Method
  275.         Rem
  276.         bbdoc: Get and remove the object at the top of a heap
  277.         returns: The object at the top of the heap
  278.         End Rem
  279.         Method removetop:Object()
  280.                 If length<=1 Return Null
  281.                 Local t:Object=data[1]
  282.                 data[1]=data[length-1]
  283.                 length:-1
  284.                 down(1)
  285.                 If dynamic And data.length>minsize Then
  286.                         While data.length<=length/3
  287.                                 data=data[..data.length/2]
  288.                         Wend
  289.                 EndIf
  290.                 Return t
  291.         End Method
  292.         Rem
  293.         bbdoc: Get the number of values in a heap
  294.         returns: The number of values in the heap
  295.         End Rem
  296.         Method count%()
  297.                 Return length-1
  298.         End Method
  299.         Rem
  300.         bbdoc: Determine whether the heap contains any values
  301.         returns: 1 if the heap is empty, 0 if it contains any values
  302.         End Rem
  303.         Method isempty%()
  304.                 Return length<=1
  305.         End Method
  306.         Rem
  307.         bbdoc: Move an object up in the heap toward its proper place via its index
  308.         returns: The new index of the same object
  309.         End Rem
  310.         Method up%(i%)
  311.                 Local t:Object=data[i],v%=(dir Shl 1)-1
  312.                 While i>1 And Sgn(sortfunc(t,data[i/2]))=v
  313.                         data[i]=data[i/2]
  314.                         i:/2
  315.                 Wend
  316.                 data[i]=t
  317.                 Return i
  318.         End Method
  319.         Rem
  320.         bbdoc: Move an object down in the heap toward its proper place via its index
  321.         returns: The new index of the same object
  322.         End Rem
  323.         Method down%(i%)
  324.                 Local t:Object=data[i],j%,n%=(length-1)/2,v%=(dir Shl 1)-1
  325.                 While i<=n
  326.                         j=i+i
  327.                         If data[j+1] And Sgn(sortfunc(data[j+1],data[j]))=v Then j:+1
  328.                         If Sgn(sortfunc(t,data[j]))=v Exit
  329.                         data[i]=data[j]
  330.                         i=j
  331.                 Wend
  332.                 data[i]=t
  333.                 Return i
  334.         End Method
  335.         Rem
  336.         bbdoc: Method implements #EachIn support
  337.         returns: An iterator object
  338.         about: Iterates through the objects in the heap
  339.         End Rem
  340.         Method ObjectEnumerator:THeapEnum()
  341.                 Local e:THeapEnum=New THeapEnum
  342.                 e.data=data
  343.                 e.length=length
  344.                 Return e
  345.         End Method
  346. End Type
  347.  
  348. Type THeapEnum
  349.         Field i%=0,data:Object[],length%=0
  350.         Method HasNext%()
  351.                 Return (i+1)<length
  352.         End Method
  353.         Method NextObject:Object()
  354.                 i:+1
  355.                 Return data[i]
  356.         End Method
  357. End Type
  358.  
  359.  
  360.  
  361. Function CompareObjects:Int(o1:Object, o2:Object)
  362.         Return o1.compare(o2)
  363. End Function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal