//
// heap_insert - 堆插入数据
// h        : 堆对象
// node     : 操作对象
// return   : void
//
inline void 
heap_insert(heap_t h, void * node) {
    heap_expand(h);
    up(h->fcmp, node, h->data, h->len++);
}

//
// heap_top - 查看堆顶结点数据
// h        : 堆对象
// return   : 堆顶节点
//
inline void * 
heap_top(heap_t h) {
    return h->len <= 0 ? NULL : *h->data;
}

//
// heap_top - 摘掉堆顶结点数据
// h        : 堆对象
// return   : 返回堆顶节点
//
inline void * 
heap_pop(heap_t h) {
    void * node = heap_top(h);
    if (node && --h->len > 0) {
        // 尾巴节点一定比小堆顶节点大, 那么要下沉
        h->data[0] = h->data[h->len];
        down(h->fcmp, h->data, h->len, 0);
    }
    return node;
}

//
// heap_remove - 堆删除数据
// h        : 堆对象
// arg      : 操作参数
// fcmp     : 比较行为, 规则 fcmp() == 0
// return   : 找到的堆节点
//
void * 
heap_remove(heap_t h, void * arg, cmp_f fcmp) {
    if (h == NULL || h->len <= 0)
        return NULL;

    // 开始查找这个节点
    unsigned i = 0;
    fcmp = fcmp ? fcmp : h->fcmp;
    do {
        void * node = h->data[i];
        if (fcmp(arg, node) == 0) {
            if (--h->len > 0 && h->len != i) {
                // 尾巴节点和待删除节点比较
                int ret = h->fcmp(h->data[h->len], node);

                // 小顶堆, 新的值比老的值小, 那么上浮
                if (ret < 0)
                    up(h->fcmp, h->data[h->len], h->data, i);
                else if (ret > 0) {
                    // 小顶堆, 新的值比老的值大, 那么下沉
                    h->data[i] = h->data[h->len];
                    down(h->fcmp, h->data, h->len, i);
                }
            }

            return node;
        }
    } while (++i < h->len);

    return NULL;
}

#include "heap.h"
#include <stdio.h>

struct node {
    int value;
};

static inline int node_cmp(const struct node * l, const struct node * r) {
    return l->value - r->value;
}

static void heap_print(heap_t h) {
    struct heap {
        cmp_f   fcmp;       // 比较行为
        unsigned len;       // heap 长度
        unsigned cap;       // heap 容量
        void ** data;       // 数据节点数组
    } * x = (struct heap *)h;

    // 数据打印for (unsigned i = 0; i < x->len; ++i) {
        struct node * node = x->data[i];
        printf("%d ", node->value);
    }
    putchar('\n');
}

int main() {
    heap_t h = heap_create(node_cmp);
    struct node a[] = { { 53 }, { 17 }, { 78 }, { 9 }, { 45 }, { 65 }, { 87 }, { 23} };
    for (int i = 0; i < sizeof a / sizeof *a; ++i)
        heap_insert(h, a + i);

    heap_print(h);

    // 数据打印
    struct node * node;
    while ((node = heap_pop(h))) {
        printf("%d ", node->value);
    }
    putchar('\n');

    // 重新插入数据
    for (int i = 0; i < sizeof a / sizeof *a; ++i)
        heap_insert(h, a + i);

    // 删除操作 - 下沉
    heap_remove(h, &(struct node){ 17 }, NULL);
    heap_print(h);

    // 插入操作
    heap_insert(h, &(struct node){ 17 });
    heap_print(h);

    // 删除操作 - 上浮
    heap_remove(h, &(struct node){ 78 }, NULL);
    heap_print(h);

    heap_delete(h, NULL);
    return 0;
}