src/util/heap.c

/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
 * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * This work was supported in part by funding from the Defense Advanced 
 * Research Projects Agency and the National Science Foundation of the 
 * United States of America, and the CMU Sphinx Speech Consortium.
 *
 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ====================================================================
 *
 */
/*
 * heap.c -- Generic heap structure for inserting in any and popping in sorted
 * 		order.
 *
 * **********************************************
 * CMU ARPA Speech Project
 *
 * Copyright (c) 1999 Carnegie Mellon University.
 * ALL RIGHTS RESERVED.
 * **********************************************
 * 
 * HISTORY
 * $Log: heap.c,v $
 * Revision 1.4  2005/06/22 03:05:49  arthchan2003
 * 1, Fixed doxygen documentation, 2, Add  keyword.
 *
 * Revision 1.3  2005/03/30 01:22:48  archan
 * Fixed mistakes in last updates. Add
 *
 * 
 * 05-Mar-99	M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
 * 		Fixed bug in heap_destroy() (in while loop exit condition).
 * 
 * 23-Dec-96	M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
 * 		Started.
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <pocketsphinx/err.h>

#include "util/heap.h"
#include "util/ckd_alloc.h"

/**
 * One node on the heap
 */
typedef struct heapnode_s {
    void *data;                 /**< Application data at this node */
    int32 val;                  /**< Associated with above application data; according to which
                                   heap is sorted (in ascending order) */
    int32 nl, nr;               /**< left/right descendants of this node (for balancing heap) */
    struct heapnode_s *l;       /**< Root of left descendant heap */
    struct heapnode_s *r;       /**< Root of right descendant heap */
} heapnode_t;

/**
 * Internal heap data structure.
 */
struct heap_s {
    heapnode_t *top;
};


#if 0
static void
heap_dump(heapnode_t * top, int32 level)
{
    int32 i;

    if (!top)
        return;

    for (i = 0; i < level; i++)
        printf("  ");
    /* print top info */
    heap_dump(top->l, level + 1);
    heap_dump(top->r, level + 1);
}
#endif


heap_t *
heap_new(void)
{
    heap_t *h = ckd_calloc(1, sizeof(*h));
    return h;
}


static heapnode_t *
subheap_insert(heapnode_t * root, void *data, int32 val)
{
    heapnode_t *h;
    void *tmpdata;
    int32 tmpval;

    if (!root) {
        h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
        h->data = data;
        h->val = val;
        h->l = h->r = NULL;
        h->nl = h->nr = 0;
        return h;
    }

    /* Root already exists; if new value is less, replace root node */
    if (root->val > val) {
        tmpdata = root->data;
        tmpval = root->val;
        root->data = data;
        root->val = val;
        data = tmpdata;
        val = tmpval;
    }

    /* Insert new or old (replaced) node in right or left subtree; keep them balanced */
    if (root->nl > root->nr) {
        root->r = subheap_insert(root->r, data, val);
        root->nr++;
    }
    else {
        root->l = subheap_insert(root->l, data, val);
        root->nl++;
    }

    return root;
}


int
heap_insert(heap_t *heap, void *data, int32 val)
{
    heap->top = subheap_insert(heap->top, data, val);
    return 0;
}


static heapnode_t *
subheap_pop(heapnode_t * root)
{
    heapnode_t *l, *r;

    /* Propagate best value from below into root, if any */
    l = root->l;
    r = root->r;

    if (!l) {
        if (!r) {
            ckd_free((char *) root);
            return NULL;
        }
        else {
            root->data = r->data;
            root->val = r->val;
            root->r = subheap_pop(r);
            root->nr--;
        }
    }
    else {
        if ((!r) || (l->val < r->val)) {
            root->data = l->data;
            root->val = l->val;
            root->l = subheap_pop(l);
            root->nl--;
        }
        else {
            root->data = r->data;
            root->val = r->val;
            root->r = subheap_pop(r);
            root->nr--;
        }
    }

    return root;
}


int
heap_pop(heap_t *heap, void **data, int32 * val)
{
    if (heap->top == NULL)
        return 0;
    *data = heap->top->data;
    *val = heap->top->val;
    heap->top = subheap_pop(heap->top);
    return 1;
}


int
heap_top(heap_t *heap, void **data, int32 * val)
{
    if (heap->top == NULL)
        return 0;
    *data = heap->top->data;
    *val = heap->top->val;
    return 1;
}

static int
heap_remove_one(heap_t *heap, heapnode_t *top, void *data)
{
    if (top == NULL)
        return -1;
    else if (top->data == data) {
        assert(top == heap->top);
        heap->top = subheap_pop(heap->top);
        return 0;
    }
    if (top->l) {
        if (top->l->data == data) {
            top->l = subheap_pop(top->l);
            --top->nl;
            return 0;
        }
        else if (heap_remove_one(heap, top->l, data) == 0) {
            --top->nl;
            return 0;
        }
    }
    if (top->r) {
        if (top->r->data == data) {
            top->r = subheap_pop(top->r);
            --top->nr;
            return 0;
        }
        else if (heap_remove_one(heap, top->r, data) == 0) {
            --top->nr;
            return 0;
        }
    }
    return -1;
}

int
heap_remove(heap_t *heap, void *data)
{
    return heap_remove_one(heap, heap->top, data);
}


size_t
heap_size(heap_t *heap)
{
    if (heap->top == NULL)
        return 0;
    return heap->top->nl + heap->top->nr + 1;
}

int
heap_destroy(heap_t *heap)
{
    void *data;
    int32 val;

    /* Empty the heap and free it */
    while (heap_pop(heap, &data, &val) > 0)
        ;
    ckd_free(heap);

    return 0;
}