GMWolf
aka fel666
Heaps are an essential data structure that is unfortunately missing from GML. (Though yes, priority queues can be used in many cases).
What I suggest is the inclusion of a new data structure called ds_heap, with the following functions:
(The heap would use an array representation internally)
Ds_heap_create(comp_script)
Creates a new Ds_heap. Comp_script is the script used to compare elements.
Ds_heap_sift_up(heap, index)
Sifts an element up the heap.
Ds_heap_sift_down(heap, index)
Sifts an element down the heap.
Ds_heap_find_max(heap)
Returns max (A[0]) element.
Ds_heap_find_min(heap)
Returns min (A[n]) element.
Ds_heap_delete_max(heap)
Deletes and return max
Ds_heap_delete_min(heap)
Deletes and returns min
Ds_heap_insert(heap, value)
Inserts value into heap.
Ds_list_heapify(list, comp_script)
Heapifies the list and returns a new heap index, with comp_script as the comparative script.
The functions would allow the user to define the comparative script. This would allow objects, arrays etc to be passed, and be compared as the user wants.
(Currently working on some path finding. This would be super useful).
P.s. currently, ds_list_find_value, ds_map_find_value, etc can only return reals and strings. So if you stored an array, you musr use accessors.
This is a problem with priority queues; they don't have accessors.
What I suggest is the inclusion of a new data structure called ds_heap, with the following functions:
(The heap would use an array representation internally)
Ds_heap_create(comp_script)
Creates a new Ds_heap. Comp_script is the script used to compare elements.
Ds_heap_sift_up(heap, index)
Sifts an element up the heap.
Ds_heap_sift_down(heap, index)
Sifts an element down the heap.
Ds_heap_find_max(heap)
Returns max (A[0]) element.
Ds_heap_find_min(heap)
Returns min (A[n]) element.
Ds_heap_delete_max(heap)
Deletes and return max
Ds_heap_delete_min(heap)
Deletes and returns min
Ds_heap_insert(heap, value)
Inserts value into heap.
Ds_list_heapify(list, comp_script)
Heapifies the list and returns a new heap index, with comp_script as the comparative script.
The functions would allow the user to define the comparative script. This would allow objects, arrays etc to be passed, and be compared as the user wants.
(Currently working on some path finding. This would be super useful).
P.s. currently, ds_list_find_value, ds_map_find_value, etc can only return reals and strings. So if you stored an array, you musr use accessors.
This is a problem with priority queues; they don't have accessors.