heap.h

Go to the documentation of this file.

 
#pragma once
 
#include <datatypes/array.h>
 
#define heap_declare(type) dyn_array(type)
 
#define heap_items(self) array_items(self)
 
#define heap_count(self) array_count(self)
 
#define heap_init(self) array_init(self)
 
#define heap_fini(self) array_fini(self)
 
#define heap_is_empty(self) array_is_empty(self)
 
#define heap_min(self) (*(__typeof(*array_items(self)) *const)array_items(self))
 
#define heap_insert(self, cmp_f, elem)                                                                                 \
    __extension__({                                                                                                \
        array_reserve(self, 1);                                                                                \
        __typeof(array_count(self)) i = array_count(self)++;                                                   \
        __typeof__(array_items(self)) items = array_items(self);                                               \
        while(i && cmp_f(elem, items[(i - 1U) / 2U])) {                                                        \
            items[i] = items[(i - 1U) / 2U];                                                               \
            i = (i - 1U) / 2U;                                                                             \
        }                                                                                                      \
        items[i] = elem;                                                                                       \
        i;                                                                                                     \
    })
 
#define heap_insert_n(self, cmp_f, ins, n)                                                                             \
    __extension__({                                                                                                \
        array_reserve(self, n);                                                                                \
        __typeof(array_count(self)) j = n;                                                                     \
        __typeof__(array_items(self)) items = array_items(self);                                               \
        while(j--) {                                                                                           \
            __typeof(array_count(self)) i = array_count(self)++;                                           \
            while(i && cmp_f((ins)[j], items[(i - 1U) / 2U])) {                                            \
                items[i] = items[(i - 1U) / 2U];                                                       \
                i = (i - 1U) / 2U;                                                                     \
            }                                                                                              \
            items[i] = (ins)[j];                                                                           \
        }                                                                                                      \
    })
 
#define heap_extract(self, cmp_f)                                                                                      \
    __extension__({                                                                                                \
        __typeof__(array_items(self)) items = array_items(self);                                               \
        __typeof(*array_items(self)) ret = array_items(self)[0];                                               \
        __typeof(*array_items(self)) last = array_pop(self);                                                   \
        __typeof(array_count(self)) cnt = array_count(self);                                                   \
        __typeof(array_count(self)) i = 1U;                                                                    \
        __typeof(array_count(self)) j = 0U;                                                                    \
        while(i < cnt) {                                                                                       \
            i += i + 1 < cnt && cmp_f(items[i + 1U], items[i]);                                            \
            if(!cmp_f(items[i], last))                                                                     \
                break;                                                                                 \
            items[j] = items[i];                                                                           \
            j = i;                                                                                         \
            i = i * 2U + 1U;                                                                               \
        }                                                                                                      \
        items[j] = last;                                                                                       \
        ret;                                                                                                   \
    })