SphinxBase  0.6
src/libsphinxbase/util/heap.c
00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
00002 /* ====================================================================
00003  * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
00004  * reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  *
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer. 
00012  *
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  * This work was supported in part by funding from the Defense Advanced 
00019  * Research Projects Agency and the National Science Foundation of the 
00020  * United States of America, and the CMU Sphinx Speech Consortium.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
00023  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
00024  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00025  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
00026  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00027  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
00028  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
00029  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
00030  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
00031  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
00032  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00033  *
00034  * ====================================================================
00035  *
00036  */
00037 /*
00038  * heap.c -- Generic heap structure for inserting in any and popping in sorted
00039  *              order.
00040  *
00041  * **********************************************
00042  * CMU ARPA Speech Project
00043  *
00044  * Copyright (c) 1999 Carnegie Mellon University.
00045  * ALL RIGHTS RESERVED.
00046  * **********************************************
00047  * 
00048  * HISTORY
00049  * $Log: heap.c,v $
00050  * Revision 1.4  2005/06/22 03:05:49  arthchan2003
00051  * 1, Fixed doxygen documentation, 2, Add  keyword.
00052  *
00053  * Revision 1.3  2005/03/30 01:22:48  archan
00054  * Fixed mistakes in last updates. Add
00055  *
00056  * 
00057  * 05-Mar-99    M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
00058  *              Fixed bug in heap_destroy() (in while loop exit condition).
00059  * 
00060  * 23-Dec-96    M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
00061  *              Started.
00062  */
00063 
00064 
00065 #include <stdio.h>
00066 #include <stdlib.h>
00067 #include <string.h>
00068 #include <assert.h>
00069 
00070 #include "sphinxbase/heap.h"
00071 #include "sphinxbase/err.h"
00072 #include "sphinxbase/ckd_alloc.h"
00073 
00077 typedef struct heapnode_s {
00078     void *data;                 
00079     int32 val;                  
00081     int32 nl, nr;               
00082     struct heapnode_s *l;       
00083     struct heapnode_s *r;       
00084 } heapnode_t;
00085 
00089 struct heap_s {
00090     heapnode_t *top;
00091 };
00092 
00093 
00094 #if 0
00095 static void
00096 heap_dump(heapnode_t * top, int32 level)
00097 {
00098     int32 i;
00099 
00100     if (!top)
00101         return;
00102 
00103     for (i = 0; i < level; i++)
00104         printf("  ");
00105     /* print top info */
00106     heap_dump(top->l, level + 1);
00107     heap_dump(top->r, level + 1);
00108 }
00109 #endif
00110 
00111 
00112 heap_t *
00113 heap_new(void)
00114 {
00115     heap_t *h = ckd_calloc(1, sizeof(*h));
00116     return h;
00117 }
00118 
00119 
00120 static heapnode_t *
00121 subheap_insert(heapnode_t * root, void *data, int32 val)
00122 {
00123     heapnode_t *h;
00124     void *tmpdata;
00125     int32 tmpval;
00126 
00127     if (!root) {
00128         h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
00129         h->data = data;
00130         h->val = val;
00131         h->l = h->r = NULL;
00132         h->nl = h->nr = 0;
00133         return h;
00134     }
00135 
00136     /* Root already exists; if new value is less, replace root node */
00137     if (root->val > val) {
00138         tmpdata = root->data;
00139         tmpval = root->val;
00140         root->data = data;
00141         root->val = val;
00142         data = tmpdata;
00143         val = tmpval;
00144     }
00145 
00146     /* Insert new or old (replaced) node in right or left subtree; keep them balanced */
00147     if (root->nl > root->nr) {
00148         root->r = subheap_insert(root->r, data, val);
00149         root->nr++;
00150     }
00151     else {
00152         root->l = subheap_insert(root->l, data, val);
00153         root->nl++;
00154     }
00155 
00156     return root;
00157 }
00158 
00159 
00160 int
00161 heap_insert(heap_t *heap, void *data, int32 val)
00162 {
00163     heap->top = subheap_insert(heap->top, data, val);
00164     return 0;
00165 }
00166 
00167 
00168 static heapnode_t *
00169 subheap_pop(heapnode_t * root)
00170 {
00171     heapnode_t *l, *r;
00172 
00173     /* Propagate best value from below into root, if any */
00174     l = root->l;
00175     r = root->r;
00176 
00177     if (!l) {
00178         if (!r) {
00179             ckd_free((char *) root);
00180             return NULL;
00181         }
00182         else {
00183             root->data = r->data;
00184             root->val = r->val;
00185             root->r = subheap_pop(r);
00186             root->nr--;
00187         }
00188     }
00189     else {
00190         if ((!r) || (l->val < r->val)) {
00191             root->data = l->data;
00192             root->val = l->val;
00193             root->l = subheap_pop(l);
00194             root->nl--;
00195         }
00196         else {
00197             root->data = r->data;
00198             root->val = r->val;
00199             root->r = subheap_pop(r);
00200             root->nr--;
00201         }
00202     }
00203 
00204     return root;
00205 }
00206 
00207 
00208 int
00209 heap_pop(heap_t *heap, void **data, int32 * val)
00210 {
00211     if (heap->top == NULL)
00212         return 0;
00213     *data = heap->top->data;
00214     *val = heap->top->val;
00215     heap->top = subheap_pop(heap->top);
00216     return 1;
00217 }
00218 
00219 
00220 int
00221 heap_top(heap_t *heap, void **data, int32 * val)
00222 {
00223     if (heap->top == NULL)
00224         return 0;
00225     *data = heap->top->data;
00226     *val = heap->top->val;
00227     return 1;
00228 }
00229 
00230 static int
00231 heap_remove_one(heap_t *heap, heapnode_t *top, void *data)
00232 {
00233     if (top == NULL)
00234         return -1;
00235     else if (top->data == data) {
00236         assert(top == heap->top);
00237         heap->top = subheap_pop(heap->top);
00238         return 0;
00239     }
00240     if (top->l) {
00241         if (top->l->data == data) {
00242             top->l = subheap_pop(top->l);
00243             --top->nl;
00244             return 0;
00245         }
00246         else if (heap_remove_one(heap, top->l, data) == 0) {
00247             --top->nl;
00248             return 0;
00249         }
00250     }
00251     if (top->r) {
00252         if (top->r->data == data) {
00253             top->r = subheap_pop(top->r);
00254             --top->nr;
00255             return 0;
00256         }
00257         else if (heap_remove_one(heap, top->r, data) == 0) {
00258             --top->nr;
00259             return 0;
00260         }
00261     }
00262     return -1;
00263 }
00264 
00265 int
00266 heap_remove(heap_t *heap, void *data)
00267 {
00268     return heap_remove_one(heap, heap->top, data);
00269 }
00270 
00271 
00272 size_t
00273 heap_size(heap_t *heap)
00274 {
00275     if (heap->top == NULL)
00276         return 0;
00277     return heap->top->nl + heap->top->nr + 1;
00278 }
00279 
00280 int
00281 heap_destroy(heap_t *heap)
00282 {
00283     void *data;
00284     int32 val;
00285 
00286     /* Empty the heap and free it */
00287     while (heap_pop(heap, &data, &val) > 0)
00288         ;
00289     ckd_free(heap);
00290 
00291     return 0;
00292 }