mirror of
https://github.com/Aurorastation/Aurora.3.git
synced 2026-07-18 03:21:13 +01:00
Batrachophreno
c2f054fd81
Progress on DMDocs. PRing progress so far so there's not one mega PR later with 1500 affected files. I want my goddamn highlight text on what all these goddamn procs goddamn do goddamnit. >:( No actual code change anywhere in this PR, only comments. --------- Signed-off-by: Batrachophreno <Batrochophreno@gmail.com>
92 lines
1.7 KiB
Plaintext
92 lines
1.7 KiB
Plaintext
//////////////////////
|
|
//datum/heap object
|
|
//////////////////////
|
|
|
|
/datum/heap
|
|
var/list/L
|
|
var/cmp
|
|
|
|
/datum/heap/New(compare)
|
|
L = new()
|
|
cmp = compare
|
|
|
|
/datum/heap/Destroy(force)
|
|
// Because this is before the list helpers are loaded
|
|
for(var/i in L)
|
|
qdel(i)
|
|
L = null
|
|
return ..()
|
|
|
|
/datum/heap/proc/is_empty()
|
|
return !length(L)
|
|
|
|
/**
|
|
* insert and place at A's position a new node in the heap
|
|
*/
|
|
/datum/heap/proc/insert(A)
|
|
L.Add(A)
|
|
swim(length(L))
|
|
|
|
/**
|
|
* Removes and returns the first element of the heap
|
|
* (i.e the max or the min dependant on the comparison function)
|
|
*/
|
|
/datum/heap/proc/pop()
|
|
if(!length(L))
|
|
return 0
|
|
. = L[1]
|
|
|
|
L[1] = L[length(L)]
|
|
L.Cut(length(L))
|
|
if(length(L))
|
|
sink(1)
|
|
|
|
/**
|
|
* Get a node up to its right position in the heap
|
|
*/
|
|
/datum/heap/proc/swim(index)
|
|
var/parent = round(index * 0.5)
|
|
|
|
while(parent > 0 && (call(cmp)(L[index],L[parent]) > 0))
|
|
L.Swap(index,parent)
|
|
index = parent
|
|
parent = round(index * 0.5)
|
|
|
|
/**
|
|
* Get a node down to its right position in the heap.
|
|
*/
|
|
/datum/heap/proc/sink(index)
|
|
var/g_child = get_greater_child(index)
|
|
|
|
while(g_child > 0 && (call(cmp)(L[index],L[g_child]) < 0))
|
|
L.Swap(index,g_child)
|
|
index = g_child
|
|
g_child = get_greater_child(index)
|
|
|
|
/**
|
|
* Returns the greater (relative to the comparison proc) of a node children or 0 if there's no child.
|
|
*/
|
|
/datum/heap/proc/get_greater_child(index)
|
|
if(index * 2 > length(L))
|
|
return 0
|
|
|
|
if(index * 2 + 1 > length(L))
|
|
return index * 2
|
|
|
|
if(call(cmp)(L[index * 2],L[index * 2 + 1]) < 0)
|
|
return index * 2 + 1
|
|
else
|
|
return index * 2
|
|
|
|
/**
|
|
* Replaces a given node so it verify the heap condition
|
|
*/
|
|
/datum/heap/proc/resort(A)
|
|
var/index = L.Find(A)
|
|
|
|
swim(index)
|
|
sink(index)
|
|
|
|
/datum/heap/proc/List()
|
|
. = L.Copy()
|