#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "data_struct.h"

/* 封装优先级队列(使用堆结构) */
/******************************/
static inline int LEFT_PQ(int index) //节点下标为index左孩子的下标

{
        return (index << 1) + 1;
}
static inline int RIGHT_PQ(int index) //节点下标为index的右孩子的下标

{
        return (index << 1) + 2;
}
static inline int PARENT_PQ(int index) //节点下标为index的父节点的下标

{
        return (index - 1) / 2;
}
/* 保持堆的性质,此函数实现将某个子树的根节点按照堆的性质下降到某个子孙节点 */
static void HEAPIFY_PQ(PQ *desc, int index)
{
        int left = LEFT_PQ(index);
        int right = RIGHT_PQ(index);
        int largest;
        PQ_element *tmp = NULL;

        for (; left < desc->heap_size || right < desc->heap_size;
                        left = LEFT_PQ(index), right = RIGHT_PQ(index)) {
                if (left < desc->heap_size &&
                                desc->compar(desc->base[left]->data, desc->base[index]->data) > 0)
                        largest = left;
                else largest = index;
                if (right < desc->heap_size &&
                                desc->compar(desc->base[right]->data, desc->base[largest]->data) > 0)
                        largest = right;
                if (largest == index)
                        break;
                tmp = desc->base[index];
                tmp->index = largest;
                desc->base[largest]->index = index;
                desc->base[index] = desc->base[largest];
                desc->base[largest]= tmp;
                index = largest;
        }
}
/* 分配一个节点 */
PQ_element *malloc_PQ(size_t size)
{
        PQ_element *e = NULL;
       
        e = malloc(sizeof(PQ_element));
        if (e == NULL)
                goto end;
        e->data = malloc(size);
        if (e->data == NULL) {
                free(e);
                e = NULL;
        }
        e->index = -1;
end:
        return e;
}

void free_PQ(PQ_element *ptr)
{
        PQ_element *e = (PQ_element *)ptr;
        if (!e)
                return;
        if (!(e->data)) {
                free(e);
                return;
        }
        free(e->data);
        free(e);
}

PQ *create_PQ(int nmemb, compar_t compar, change_key_t change_key)
{
        PQ *ret = NULL;
        PQ_element *t = NULL;

        ret = (PQ *)malloc(sizeof(PQ));
        if (ret == NULL) {
                goto end;
        }
        ret->compar = compar;
        ret->change_key = change_key;
        ret->heap_size = 0;
        ret->len = nmemb;
        t = malloc(sizeof(PQ_element *) * nmemb);
        if (t == NULL) {
                free(ret);
                ret = NULL;
                goto end;
        }
        memset(t, 0, sizeof(PQ_element *) * nmemb);
        ret->base = (PQ_element **)t;
end:
        return ret;
}

void destroy_PQ(PQ *desc)
{
        if (!desc)
                return;
        if (desc->base)
                free(desc->base);
        free(desc);
}

int insert_PQ(PQ *desc, PQ_element *x)
{
        PQ_element *tmp = NULL;
        int ret = -1, i;

        if (desc->heap_size >= desc->len) {
                tmp = realloc(desc->base, sizeof(PQ_element *) * (desc->len + 5));
                if (tmp == NULL) {
                        goto end;
                }
                memset(&tmp[desc->len], 0, sizeof(PQ_element *) * 5);
                desc->base = (PQ_element **)tmp;
                desc->len += 5;
        }
        x->index = desc->heap_size;
        desc->base[desc->heap_size] = x;
        desc->heap_size++;
        i = x->index;
        while (i > 0 && desc->compar(desc->base[PARENT_PQ(i)]->data, desc->base[i]->data) < 0) {
                tmp = desc->base[i];
                tmp->index = PARENT_PQ(i);
                desc->base[PARENT_PQ(i)]->index = i;
                desc->base[i] = desc->base[PARENT_PQ(i)];
                desc->base[PARENT_PQ(i)] = tmp;
                i = PARENT_PQ(i);
        }
        ret = 0;
end:
        return ret;
}

int delete_PQ(PQ *desc, const PQ_element *x)
{
        int i = x->index;

        desc->base[i] = desc->base[desc->heap_size - 1];
        desc->base[desc->heap_size - 1] = NULL;
        desc->base[i]->index = i;
        desc->heap_size--;
        HEAPIFY_PQ(desc, i);
        return 0;
}

PQ_element *root_PQ(PQ *desc)
{
        if (desc && desc->base)
                return desc->base[0];
        return NULL;
}

PQ_element *extract_PQ(PQ *desc)
{
        if (!desc || !(desc->base))
                return NULL;
        if (desc->heap_size <= 0)
                return NULL;
        PQ_element *max = desc->base[0];
        desc->base[0] = desc->base[desc->heap_size - 1];
        desc->base[desc->heap_size - 1] = NULL;
        if (desc->base[0])
                desc->base[0]->index = 0;
        desc->heap_size--;
        HEAPIFY_PQ(desc, 0);
        return max;
}

void change_key_PQ(PQ *desc, PQ_element *x, const void *key)
{
        int i = x->index;
        PQ_element *tmp = NULL;

        desc->change_key(x->data, key);
        while (i > 0 && desc->compar(desc->base[PARENT_PQ(i)]->data, desc->base[i]->data) < 0) {
                tmp = desc->base[i];
                tmp->index = PARENT_PQ(i);
                desc->base[PARENT_PQ(i)]->index = i;
                desc->base[i] = desc->base[PARENT_PQ(i)];
                desc->base[PARENT_PQ(i)] = tmp;
                i = PARENT_PQ(i);
        }
}
/******************************/

#ifndef DATA_STRUCT___H
#define DATA_STRUCT___H

/* 用户自定义比较函数 */
typedef int (*compar_t)(const void *, const void *);
/* 用户自定义修改关键字函数,
* 前者参数为用户自定义数据结构,
* 后者参数为要修改的key值
*/
typedef void (*change_key_t)(void *, const void *);

/* 队列元素结构 */
typedef struct pq_element
{
        void *data;
        int index; //用于记录该节点所位于数组中的下标值

}PQ_element;

typedef struct PQ_desc
{
        compar_t compar;
        change_key_t change_key;
        int heap_size; /* 堆的大小 */
        int len; /* 当前优先级队列数组中可容纳的最大长度 */
        PQ_element **base;
}PQ;

/* 创建优先级队列,nmemb为队列中包含元素的个数,compar为比较函数,change_key为修改关键字函数 */
PQ *create_PQ(int nmemb, compar_t compar, change_key_t change_key);
void destroy_PQ(PQ *desc); //销毁优先级队列

int insert_PQ(PQ *desc, PQ_element *x); //向队列中插入一个元素,元素为前面定义的元素结构

int delete_PQ(PQ *desc, const PQ_element *x); //删除队列中的一个元素,该元素由x引用

PQ_element *root_PQ(PQ *desc); //得到优先级队列的对头元素

PQ_element *extract_PQ(PQ *desc); //得到优先级队列的对头元素并将对头元素从优先级队列中删除

/*
* 将key指向的用户结构赋值给x指向的用户结构,并改变x在队列中的位置
* 这里将调用用户自定义的change_key函数,
* 并将key和x做为change_key函数的参数传递
*/
void change_key_PQ(PQ *desc, PQ_element *x, const void *key); //将优先级队列desc中的元素x中的关键字修改为key

PQ_element *malloc_PQ(size_t size); //申请节点空间

void free_PQ(PQ_element *ptr); //释放由malloc_PQ申请的节点空间.


#define ELEMENT_DATA(pq_element) ((pq_element)->data) //返回节点元素中用户自定义数据结构的指针

#define CLEAN_ELEMENT(pq_element) ((pq_element)->data = NULL) //将节点元素中的用户数据指针清除

#define INDEX_ELEMENT(pq_element) ((pq_element)->index) //返回节点元素在堆中的索引值

#define PQ_SIZE(desc) ((desc)->heap_size) //优先级队列中队列的长度

#define PQ_LEN(desc) ((desc)->len) //目前能容纳的元素的最大个数


#endif