heap.c

Go to the documentation of this file.

/* LIBDGL -- a Directed Graph Library implementation
 * Copyright (C) 2002 Roberto Micarelli
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/* best view tabstop=4
 */
#include <stdio.h>
#include <stdlib.h>

#include "type.h"
#include "heap.h"



void dglHeapInit(dglHeap_s * pheap)
{
    pheap->index = 0;
    pheap->count = 0;
    pheap->block = 256;
    pheap->pnode = NULL;
}

void dglHeapFree(dglHeap_s * pheap, dglHeapCancelItem_fn pfnCancelItem)
{
    int iItem;

    if (pheap->pnode) {
        if (pfnCancelItem) {
            for (iItem = 0; iItem <= pheap->index; iItem++) {
                pfnCancelItem(pheap, &pheap->pnode[iItem]);
            }
        }
        free(pheap->pnode);
    }
    pheap->pnode = NULL;
}

int dglHeapInsertMin(dglHeap_s * pheap,
                     long key, unsigned char flags, dglHeapData_u value)
{
    long i;

    if (pheap->index >= pheap->count - 1) {
        pheap->count += pheap->block;
        if ((pheap->pnode =
             realloc(pheap->pnode,
                     sizeof(dglHeapNode_s) * pheap->count)) == NULL)
            return -1;
    }

    i = ++pheap->index;

    while (i != 1 && key < pheap->pnode[i / 2].key) {
        pheap->pnode[i] = pheap->pnode[i / 2];
        i /= 2;
    }

    pheap->pnode[i].key = key;
    pheap->pnode[i].flags = flags;
    pheap->pnode[i].value = value;

    return i;
}

int dglHeapExtractMin(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
{
    dglHeapNode_s temp;
    long iparent, ichild;

    if (pheap->index == 0)
        return 0;               /* empty heap */

    *pnoderet = pheap->pnode[1];

    temp = pheap->pnode[pheap->index--];

    iparent = 1;
    ichild = 2;

    while (ichild <= pheap->index) {
        if (ichild < pheap->index &&
            pheap->pnode[ichild].key > pheap->pnode[ichild + 1].key) {
            ichild++;
        }
        if (temp.key <= pheap->pnode[ichild].key)
            break;

        pheap->pnode[iparent] = pheap->pnode[ichild];
        iparent = ichild;
        ichild *= 2;
    }
    pheap->pnode[iparent] = temp;

    return 1;
}

int dglHeapInsertMax(dglHeap_s * pheap,
                     long key, unsigned char flags, dglHeapData_u value)
{
    long i;

    if (pheap->index >= pheap->count - 1) {
        pheap->count += pheap->block;
        if ((pheap->pnode =
             realloc(pheap->pnode,
                     sizeof(dglHeapNode_s) * pheap->count)) == NULL)
            return -1;
    }

    i = ++pheap->index;

    while (i != 1 && key > pheap->pnode[i / 2].key) {
        pheap->pnode[i] = pheap->pnode[i / 2];
        i /= 2;
    }

    pheap->pnode[i].key = key;
    pheap->pnode[i].flags = flags;
    pheap->pnode[i].value = value;

    return i;
}

int dglHeapExtractMax(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
{
    dglHeapNode_s temp;
    long iparent, ichild;

    if (pheap->index == 0)
        return 0;               /* empty heap */

    *pnoderet = pheap->pnode[1];

    temp = pheap->pnode[pheap->index--];

    iparent = 1;
    ichild = 2;

    while (ichild <= pheap->index) {
        if (ichild < pheap->index &&
            pheap->pnode[ichild].key < pheap->pnode[ichild + 1].key) {
            ichild++;
        }
        if (temp.key >= pheap->pnode[ichild].key)
            break;

        pheap->pnode[iparent] = pheap->pnode[ichild];
        iparent = ichild;
        ichild *= 2;
    }
    pheap->pnode[iparent] = temp;

    return 1;
}