October 24, 2021, 04:50:48

Author Topic: [bb] Binary Heaps by pexe [ 1+ years ago ]  (Read 764 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Binary Heaps by pexe [ 1+ years ago ]
« on: June 29, 2017, 00:28:42 »
Title : Binary Heaps
Author : pexe
Posted : 1+ years ago

Description : binaryheaps.bb V1.0
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
                      Matheus Cansian

This LIB provide tools to create Binary Heaps ordered lists. It
can handle more than one simultaneous list and ascending and
descending order.

HOW-TO: Create a list with New(), use one of the sorting
constants to select with each sorting order your list will
operate. Then use the functions Add(), Remove() and Modify(), to
manipulate the data within the list.
If you need a debug tool, you can use Draw() to show all your
list elements.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Example:

BinID% = BinaryHeap_New%(BinaryHeap_SORT_BIGGEST) ;Create a new list
BinaryHeap_Add%(BinID,32,"First") ;Add a value
BinaryHeap_Add%(BinID,68,"Second") ;Add a value
BinaryHeap_Add%(BinID,15,"Third") ;Add a value

;Get the biggest value
print BinaryHeap_Remove%(BinID) ;Output: Second


Code :
Code: BlitzBasic
  1. ;;;;                    binaryheaps.bb V1.0
  2. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  3. ;;;;                      Matheus Cansian
  4. ;;;;
  5. ;;;; This LIB provide tools to create Binary Heaps ordered lists. It
  6. ;;;; can handle more than one simultaneous list and ascending and
  7. ;;;; descending order.
  8. ;;;;
  9. ;;;; HOW-TO: Create a list with New(), use one of the sorting
  10. ;;;; constants to select with each sorting order your list will
  11. ;;;; operate. Then use the functions Add(), Remove() and Modify(), to
  12. ;;;; manipulate the data within the list.
  13. ;;;; If you need a debug tool, you can use Draw() to show all your
  14. ;;;; list elements.
  15.  
  16.  
  17. ;; LIB CONFIGURATIONS ;;
  18. Const BinaryHeap_MaxElements% = 1000   ;Max of elements each list can store
  19. Const BinaryHeap_MaxSimultaneous% = 5  ;Max simultaneous list you can have
  20.  
  21. ;Note: Memory storage is calculated by multiplying MaxElements with MaxSimoultaneous.
  22. ;      eg: MaxElements = 1000 and MaxSimultaneous = 5
  23. ;          1000 * 5 = 5000 bytes or approx. 5 KB
  24.  
  25.  
  26. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; LIB ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  27. ;;;;;;;;;;; Probably there's nothing you need to change down there! ;;;;;;;;;;;;
  28.  
  29. ;; LIB CONSTANTS ;;
  30. Const BinaryHeap_Version$ = "1.0"
  31. Const BinaryHeap_SORT_SMALLEST = 1
  32. Const BinaryHeap_SORT_BIGGEST  = 2
  33.  
  34. ;; LIB ARRAYS ;;
  35. Dim BinaryHeap_Sort%(BinaryHeap_MaxSimultaneous%) ;What kind of sorting method?
  36. Dim BinaryHeap_Elements%(BinaryHeap_MaxSimultaneous%) ;Count the number of elements
  37. Dim BinaryHeap_Value%(BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%)
  38. Dim BinaryHeap_Data% (BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%)
  39.  
  40. ;;; <summary>Create a list ordered list</summary>
  41. ;;; <param name="SortMethod">How the list will be sorted? Use the constants above</param>
  42. ;;; <remarks></remarks>
  43. ;;; <returns></returns>
  44. ;;; <subsystem></subsystem>
  45. ;;; <example></example>
  46. Function BinaryHeap_New%(SortMethod%)
  47.         For Cont% = 1 To BinaryHeap_MaxSimultaneous%
  48.                 If BinaryHeap_Sort%(Cont%) = 0 Then
  49.                         BinaryHeap_Sort%(Cont%) = SortMethod%
  50.                         Return Cont%
  51.                 Else
  52.                         DebugLog Cont
  53.                 EndIf
  54.         Next
  55.         Return 0
  56. End Function
  57.  
  58. ;;; <summary>Delete a binary heap thread</summary>
  59. ;;; <param name="BinaryHeapThread">BinaryHeap Thread ID</param>
  60. ;;; <remarks></remarks>
  61. ;;; <returns>1 if the thread was deleted, 0 if the thread dont exists</returns>
  62. ;;; <subsystem></subsystem>
  63. ;;; <example></example>
  64. Function BinaryHeap_Delete%(BinaryHeapThread%)
  65.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  66.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0
  67.        
  68.         ;Clear Sort and Elements variables
  69.         BinaryHeap_Sort%(BinaryHeapThread%) = 0
  70.         BinaryHeap_Elements%(BinaryHeapThread%) = 0
  71.        
  72.         ;Clear Value and Data variables
  73.         For Cont% = 1 To BinaryHeap_MaxElements%
  74.                 BinaryHeap_Value%(BinaryHeapThread%, Cont%) = 0
  75.                 BinaryHeap_Data% (BinaryHeapThread%, Cont%) = 0
  76.         Next
  77.        
  78.         Return 1
  79. End Function
  80.  
  81. Function BinaryHeap_Add%(BinaryHeapThread%, Value%, HeapData%)
  82.         ;Check HeapThread
  83.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  84.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
  85.        
  86.         ;Check if max elements reached
  87.         If BinaryHeap_Elements%(BinaryHeapThread%) >= BinaryHeap_MaxElements% Then Return 0 ;Max elements reached
  88.        
  89.         ;Add Elements counter
  90.         BinaryHeap_Elements%(BinaryHeapThread%) = BinaryHeap_Elements%(BinaryHeapThread%) + 1
  91.        
  92.         ;Get the last element position
  93.         Local MyElement% = BinaryHeap_Elements%(BinaryHeapThread%)
  94.        
  95.         ;Add element to the end of the list
  96.         BinaryHeap_Value%(BinaryHeapThread%, MyElement)  = Value%
  97.         BinaryHeap_Data%(BinaryHeapThread%, MyElement)   = HeapData%
  98.        
  99.         ;Get sorting method
  100.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
  101.        
  102.         Local MyValue%, ParentValue%, ParentElement%
  103.         Repeat
  104.                 ;Get parent position
  105.                 ParentElement% = Floor(MyElement%/2)
  106.                 If ParentElement% <= 0 Then Exit
  107.                
  108.                 ;Get elements values
  109.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement)
  110.                 ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement)
  111.                
  112.                 ;Compare data
  113.                 If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then
  114.                         ;Leave it alone
  115.                         Exit
  116.                 Else
  117.                         ;Swap elements
  118.                         BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement)
  119.                          
  120.                          ;Get new element position
  121.                          MyElement = ParentElement
  122.                 EndIf
  123.         Forever
  124.         Return 1
  125. End Function
  126.  
  127. ;;; <summary>Get the first heap element</summary>
  128. ;;; <param name="BinaryHeapThread"></param>
  129. ;;; <remarks></remarks>
  130. ;;; <returns></returns>
  131. ;;; <subsystem></subsystem>
  132. ;;; <example></example>
  133. Function BinaryHeap_Remove%(BinaryHeapThread%)
  134.         ;Check HeapThread
  135.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  136.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
  137.        
  138.         ;Check if the are elements
  139.         If BinaryHeap_Elements%(BinaryHeapThread%) <= 0 Then Return 0 ;No elements
  140.        
  141.         ;Decrease Elements counter
  142.         BinaryHeap_Elements%(BinaryHeapThread%) = BinaryHeap_Elements%(BinaryHeapThread%) - 1
  143.        
  144.         ;Save first element data
  145.         Local FirstData% = BinaryHeap_Data% (BinaryHeapThread%, 1)
  146.        
  147.         ;Delete first element
  148.         BinaryHeap_Value% (BinaryHeapThread%, 1) = 0
  149.         BinaryHeap_Data%  (BinaryHeapThread%, 1) = 0
  150.        
  151.         ;Swap last element with first
  152.         BinaryHeap_Private_Swap(BinaryHeapThread%, 1, BinaryHeap_Elements%(BinaryHeapThread%)+1)
  153.        
  154.         ;Get sorting method
  155.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
  156.        
  157.         Local MyValue%, Child1Value%, Child2Value%, Child1Active%, Child2Active%, Child1Element%, Child2Element%, MyElement% = 1
  158.         Repeat
  159.                 ;Get element child
  160.                 Child1Element% = Floor(MyElement%*2)
  161.                 Child2Element% = Floor(MyElement%*2)+1
  162.                
  163.                 ;Get elements value
  164.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement%)
  165.                 If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Value% = BinaryHeap_Value%(BinaryHeapThread%, Child1Element%):Else:Child1Value% = 0
  166.                 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Value% = BinaryHeap_Value%(BinaryHeapThread%, Child2Element%):Else:Child2Value% = 0
  167.                
  168.                 ;Get elements status
  169.                 If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child1Element%)<>0):Else:Child1Active% = 0
  170.                 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child2Element%)<>0):Else:Child2Active% = 0
  171.                
  172.                 ;Compare data
  173.                 If (Child1Active% And ((MyValue% >= Child1Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= Child1Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))) Or (Child2Active% And ((MyValue% >= Child2Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= Child2Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))) Then
  174.                         If Child1Active% And ((Child1Value% <= Child2Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (Child1Value% >= Child2Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))
  175.                                 ;Swap with child 1
  176.                                 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child1Element)
  177.                                 ;Get new element position
  178.                                 MyElement = Child1Element
  179.                         Else   
  180.                                 ;Swap with child 2
  181.                                 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child2Element)
  182.                                 ;Get new element position
  183.                                 MyElement = Child2Element
  184.                         EndIf
  185.                 Else
  186.                         ;Leave it alone
  187.                         Exit
  188.                 EndIf
  189.         Forever
  190.        
  191.         Return FirstData%
  192. End Function
  193.  
  194. ;;; <summary>Change an element value</summary>
  195. ;;; <param name="BinaryHeapThread"></param>
  196. ;;; <param name="Value"></param>
  197. ;;; <param name="HeapData"></param>
  198. ;;; <param name="NewValue"></param>
  199. ;;; <remarks></remarks>
  200. ;;; <returns>1 if succeed, 0 if fail</returns>
  201. ;;; <subsystem></subsystem>
  202. ;;; <example></example>
  203. Function BinaryHeap_Modify%(BinaryHeapThread%, Value%, HeapData%, NewValue%)
  204.         ;Check HeapThread
  205.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  206.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
  207.        
  208.         ;Store number of elements
  209.         TotalElements% = BinaryHeap_Elements%(BinaryHeapThread%)
  210.        
  211.         ;Search for the element
  212.         For Cont% = 1 To TotalElements%
  213.                 If BinaryHeap_Value%(BinaryHeapThread%, Cont) = Value% And BinaryHeap_Data%(BinaryHeapThread%, Cont) = HeapData% Then
  214.                         MyElement% = Cont%
  215.                         Exit
  216.                 EndIf
  217.         Next
  218.        
  219.         ;Change element data
  220.         BinaryHeap_Value%(BinaryHeapThread%, MyElement%) = NewValue%
  221.        
  222.         ;Get sorting method
  223.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
  224.        
  225.         Local MyValue%, ParentValue%, ParentElement%
  226.         Repeat
  227.                 ;Get parent position
  228.                 ParentElement% = Floor(MyElement%/2)
  229.                 If ParentElement% <= 0 Then Exit
  230.                
  231.                 ;Get elements values
  232.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement)
  233.                 ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement)
  234.                
  235.                 ;Compare data
  236.                 If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then
  237.                         ;Leave it alone
  238.                         Exit
  239.                 Else
  240.                         ;Swap elements
  241.                         BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement)
  242.                          
  243.                          ;Get new element position
  244.                          MyElement = ParentElement
  245.                 EndIf
  246.         Forever
  247.         Return 1
  248. End Function
  249.  
  250. ;;; <summary>Draw the BinaryHeaps structure in the screen</summary>
  251. ;;; <param name="BinaryHeapThread"></param>
  252. ;;; <param name="SkipKey">Keycode to exit, or 0 to exit automatically</param>
  253. ;;; <param name="Levels">Number of levels to draw, or 0 to draw all</param>
  254. ;;; <remarks></remarks>
  255. ;;; <returns>Level drawn or 0 for failure</returns>
  256. ;;; <subsystem></subsystem>
  257. ;;; <example></example>
  258. Function BinaryHeap_Draw%(BinaryHeapThread%, SkipKey%=0, Levels%=0)
  259.         ;Check HeapThread
  260.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  261.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
  262.  
  263.         ;Get graphics size
  264.         Local Width% = GraphicsWidth()
  265.         Local Height% = GraphicsHeight()
  266.        
  267.         ;Clear screen
  268.         SetBuffer BackBuffer():ClsColor 200,200,200
  269.        
  270.         ;Get total os elements
  271.         Local MaxElements% = BinaryHeap_Elements%(BinaryHeapThread%)
  272.        
  273.         ;Get number of levels
  274.         Local Elements% = 0, MaxLevels%
  275.         Repeat
  276.                 Elements% = Elements% * 2
  277.                 Elements% = Elements% + 1
  278.                 MaxLevels% = MaxLevels% + 1
  279.                 If Elements% >= MaxElements% Then Exit
  280.         Forever
  281.         If Levels% =  0 Then Levels% = MaxLevels%
  282.         If MaxElements% <=  1 Then Levels% = 2
  283.        
  284.         Local FirstPosition%, LevelSpacing%, LevelElements%, LevelSpacingSteps%, LastLevelSize%
  285.         Local OffsetX%, OffsetY%, Value%, HeapActive%
  286.         Repeat
  287.                 ;Get input keys
  288.                 If KeyDown(200) Then OffsetY = OffsetY + 10
  289.                 If KeyDown(208) Then OffsetY = OffsetY - 10
  290.                 If KeyDown(205) Then OffsetX = OffsetX - 10
  291.                 If KeyDown(203) Then OffsetX = OffsetX + 10
  292.                 If KeyHit(201) And Levels% < MaxLevels% Then Levels% = Levels% + 1
  293.                 If KeyHit(209) And Levels% > 1 Then Levels% = Levels% - 1
  294.                
  295.                 Cls
  296.                
  297.                 ;Draw header
  298.                 Color 0,0,0
  299.                 Text OffsetX+Width%/2, OffsetY+5,"Exploring BinaryHeap: "+BinaryHeapThread%+" | TotalElements: "+MaxElements%,1,0
  300.                 Text OffsetX+Width%/2, OffsetY+25,"Use PAGEUP/DOWN to change the number of levels and keyboard arrows to move",1,0
  301.                
  302.                
  303.                 ;Draw Elements
  304.                 LastLevelSize% = ((2^Levels%)/2)*StringWidth(" 100 ")*2
  305.                 For Level% = 1 To Levels%
  306.                         FirstPosition% = 2^(Level%-1)
  307.                         LevelSpacing% = LastLevelSize% / 2^Level%
  308.                         LevelElements% = (2^Level%)/2
  309.                         LevelSpacingSteps% = -(LevelElements%-1)
  310.                        
  311.                         For Pos% = 0 To LevelElements%-1                       
  312.                                 ;Check if maximum reached
  313.                                 If FirstPosition%+Pos% > BinaryHeap_MaxElements% Then Exit
  314.                                
  315.                                 ;Get element value and data%
  316.                                 Value% = BinaryHeap_Value%(BinaryHeapThread%, FirstPosition%+Pos%)
  317.                                 HeapActive% = (BinaryHeap_Data%(BinaryHeapThread%, FirstPosition%+Pos%)<>0)
  318.                                
  319.                                 ;Draw child lines
  320.                                 If Level% < Levels%
  321.                                         Color 180,180,180
  322.                                         ;These lines are a total mess!!
  323.                                         Line OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40, OffsetX+(Width%/2)+(LastLevelSize% / 2^(Level%+1))*((-((2^(Level%+1))/2-1))+2*Pos%*2), OffsetY+(Level%+1)*20+40
  324.                                         Line OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40, OffsetX+(Width%/2)+(LastLevelSize% / 2^(Level%+1))*((-((2^(Level%+1))/2-1))+2*((Pos%*2)+1)), OffsetY+(Level%+1)*20+40
  325.                                 EndIf
  326.                                
  327.                                 ;Draw element value
  328.                                 If HeapActive% <> 0 Then Color 0,0,0:Else:Color 230,100,100
  329.                                 Text OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40,Value%,1,1
  330.                         Next
  331.                 Next
  332.                 Flip
  333.         Until (KeyHit(SkipKey)) Or SkipKey%=0
  334.        
  335.         Return Levels%
  336. End Function
  337.  
  338. ;;; <summary>Swap two elements</summary>
  339. ;;; <param name="BinaryHeapThread">BinaryHeap thread ID</param>
  340. ;;; <param name="Position1">Position of the first element</param>
  341. ;;; <param name="Position2">Position of the second element</param>
  342. ;;; <remarks></remarks>
  343. ;;; <returns>1 for successful 0 for failure</returns>
  344. ;;; <subsystem></subsystem>
  345. ;;; <example></example>
  346. Function BinaryHeap_Private_Swap(BinaryHeapThread%, Position1%, Position2%)
  347.         ;Check HeapThread
  348.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
  349.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
  350.  
  351.         ;Store temp variables
  352.         Local TempValue%  = BinaryHeap_Value% (BinaryHeapThread%, Position1%)
  353.         Local TempData%   = BinaryHeap_Data%  (BinaryHeapThread%, Position1%)
  354.        
  355.         ;Change first
  356.         BinaryHeap_Value% (BinaryHeapThread%, Position1%) = BinaryHeap_Value% (BinaryHeapThread%, Position2%)
  357.         BinaryHeap_Data%  (BinaryHeapThread%, Position1%) = BinaryHeap_Data%  (BinaryHeapThread%, Position2%)
  358.        
  359.         BinaryHeap_Value%(BinaryHeapThread%, Position2%) = TempValue%
  360.         BinaryHeap_Data% (BinaryHeapThread%, Position2%) = TempData%
  361.        
  362.         Return 1
  363. End Function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal