diff options
| author | gingerBill <bill@gingerbill.org> | 2021-12-28 14:05:09 +0000 |
|---|---|---|
| committer | gingerBill <bill@gingerbill.org> | 2021-12-28 14:05:09 +0000 |
| commit | 7f61a90ea1be96c22cae87fdbfdc08b30f2421d6 (patch) | |
| tree | ff009a150eec737aa4ba6a8abe46e81eda91028c /core/container/priority_queue.odin | |
| parent | 0548db423067bce16d45af651819bf56feb5d411 (diff) | |
Remove `core:container` contents
Diffstat (limited to 'core/container/priority_queue.odin')
| -rw-r--r-- | core/container/priority_queue.odin | 121 |
1 files changed, 0 insertions, 121 deletions
diff --git a/core/container/priority_queue.odin b/core/container/priority_queue.odin deleted file mode 100644 index c54e964a6..000000000 --- a/core/container/priority_queue.odin +++ /dev/null @@ -1,121 +0,0 @@ -package container - -Priority_Queue :: struct($T: typeid) { - data: Array(T), - len: int, - priority: proc(item: T) -> int, -} - -priority_queue_init_none :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, allocator := context.allocator) { - queue_init_len(q, f, 0, allocator) -} -priority_queue_init_len :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, len: int, allocator := context.allocator) { - queue_init_len_cap(q, f, 0, 16, allocator) -} -priority_queue_init_len_cap :: proc(q: ^$Q/Priority_Queue($T), f: proc(item: T) -> int, len: int, cap: int, allocator := context.allocator) { - array_init(&q.data, len, cap, allocator) - q.len = len - q.priority = f -} - -priority_queue_init :: proc{priority_queue_init_none, priority_queue_init_len, priority_queue_init_len_cap} - - -priority_queue_delete :: proc(q: $Q/Priority_Queue($T)) { - array_delete(q.data) -} - -priority_queue_clear :: proc(q: ^$Q/Priority_Queue($T)) { - q.len = 0 -} - -priority_queue_len :: proc(q: $Q/Priority_Queue($T)) -> int { - return q.len -} - -priority_queue_cap :: proc(q: $Q/Priority_Queue($T)) -> int { - return array_cap(q.data) -} - -priority_queue_space :: proc(q: $Q/Priority_Queue($T)) -> int { - return array_len(q.data) - q.len -} - -priority_queue_reserve :: proc(q: ^$Q/Priority_Queue($T), capacity: int) { - if capacity > q.len { - array_resize(&q.data, new_capacity) - } -} - -priority_queue_resize :: proc(q: ^$Q/Priority_Queue($T), length: int) { - if length > q.len { - array_resize(&q.data, new_capacity) - } - q.len = length -} - -_priority_queue_grow :: proc(q: ^$Q/Priority_Queue($T), min_capacity: int = 0) { - new_capacity := max(array_len(q.data)*2 + 8, min_capacity) - array_resize(&q.data, new_capacity) -} - - -priority_queue_push :: proc(q: ^$Q/Priority_Queue($T), item: T) { - if array_len(q.data) - q.len == 0 { - _priority_queue_grow(q) - } - - s := array_slice(q.data) - s[q.len] = item - - i := q.len - for i > 0 { - p := (i - 1) / 2 - if q.priority(s[p]) <= q.priority(item) { - break - } - s[i] = s[p] - i = p - } - - q.len += 1 - if q.len > 0 { - s[i] = item - } -} - - - -priority_queue_pop :: proc(q: ^$Q/Priority_Queue($T)) -> T { - assert(q.len > 0) - - s := array_slice(q.data) - min := s[0] - root := s[q.len-1] - q.len -= 1 - - i := 0 - for i * 2 + 1 < q.len { - a := i * 2 + 1 - b := i * 2 + 2 - c := b < q.len && q.priority(s[b]) < q.priority(s[a]) ? b : a - - if q.priority(s[c]) >= q.priority(root) { - break - } - s[i] = s[c] - i = c - } - - if q.len > 0 { - s[i] = root - } - return min -} - -priority_queue_peek :: proc(q: ^$Q/Priority_Queue($T)) -> T { - assert(q.len > 0) - - s := array_slice(q.data) - return s[0] -} |