mirror of
https://github.com/fulpstation/fulpstation.git
synced 2025-12-09 16:09:15 +00:00
81 lines
1.7 KiB
Plaintext
81 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)
|
|
for(var/i in L) // because this is before the list helpers are loaded
|
|
qdel(i)
|
|
L = null
|
|
return ..()
|
|
|
|
/datum/heap/proc/is_empty()
|
|
return !length(L)
|
|
|
|
//insert and place at its 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 dependent 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()
|