heap.c

Go to the documentation of this file.
00001 /* LIBDGL -- a Directed Graph Library implementation
00002  * Copyright (C) 2002 Roberto Micarelli
00003  *
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017  */
00018 
00019 /* best view tabstop=4
00020  */
00021 #include <stdio.h>
00022 #include <stdlib.h>
00023 
00024 #include "type.h"
00025 #include "heap.h"
00026 
00027 
00028 
00029 void dglHeapInit(dglHeap_s * pheap)
00030 {
00031     pheap->index = 0;
00032     pheap->count = 0;
00033     pheap->block = 256;
00034     pheap->pnode = NULL;
00035 }
00036 
00037 void dglHeapFree(dglHeap_s * pheap, dglHeapCancelItem_fn pfnCancelItem)
00038 {
00039     int iItem;
00040 
00041     if (pheap->pnode) {
00042         if (pfnCancelItem) {
00043             for (iItem = 0; iItem <= pheap->index; iItem++) {
00044                 pfnCancelItem(pheap, &pheap->pnode[iItem]);
00045             }
00046         }
00047         free(pheap->pnode);
00048     }
00049     pheap->pnode = NULL;
00050 }
00051 
00052 int dglHeapInsertMin(dglHeap_s * pheap,
00053                      long key, unsigned char flags, dglHeapData_u value)
00054 {
00055     long i;
00056 
00057     if (pheap->index >= pheap->count - 1) {
00058         pheap->count += pheap->block;
00059         if ((pheap->pnode =
00060              realloc(pheap->pnode,
00061                      sizeof(dglHeapNode_s) * pheap->count)) == NULL)
00062             return -1;
00063     }
00064 
00065     i = ++pheap->index;
00066 
00067     while (i != 1 && key < pheap->pnode[i / 2].key) {
00068         pheap->pnode[i] = pheap->pnode[i / 2];
00069         i /= 2;
00070     }
00071 
00072     pheap->pnode[i].key = key;
00073     pheap->pnode[i].flags = flags;
00074     pheap->pnode[i].value = value;
00075 
00076     return i;
00077 }
00078 
00079 int dglHeapExtractMin(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
00080 {
00081     dglHeapNode_s temp;
00082     long iparent, ichild;
00083 
00084     if (pheap->index == 0)
00085         return 0;               /* empty heap */
00086 
00087     *pnoderet = pheap->pnode[1];
00088 
00089     temp = pheap->pnode[pheap->index--];
00090 
00091     iparent = 1;
00092     ichild = 2;
00093 
00094     while (ichild <= pheap->index) {
00095         if (ichild < pheap->index &&
00096             pheap->pnode[ichild].key > pheap->pnode[ichild + 1].key) {
00097             ichild++;
00098         }
00099         if (temp.key <= pheap->pnode[ichild].key)
00100             break;
00101 
00102         pheap->pnode[iparent] = pheap->pnode[ichild];
00103         iparent = ichild;
00104         ichild *= 2;
00105     }
00106     pheap->pnode[iparent] = temp;
00107 
00108     return 1;
00109 }
00110 
00111 int dglHeapInsertMax(dglHeap_s * pheap,
00112                      long key, unsigned char flags, dglHeapData_u value)
00113 {
00114     long i;
00115 
00116     if (pheap->index >= pheap->count - 1) {
00117         pheap->count += pheap->block;
00118         if ((pheap->pnode =
00119              realloc(pheap->pnode,
00120                      sizeof(dglHeapNode_s) * pheap->count)) == NULL)
00121             return -1;
00122     }
00123 
00124     i = ++pheap->index;
00125 
00126     while (i != 1 && key > pheap->pnode[i / 2].key) {
00127         pheap->pnode[i] = pheap->pnode[i / 2];
00128         i /= 2;
00129     }
00130 
00131     pheap->pnode[i].key = key;
00132     pheap->pnode[i].flags = flags;
00133     pheap->pnode[i].value = value;
00134 
00135     return i;
00136 }
00137 
00138 int dglHeapExtractMax(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
00139 {
00140     dglHeapNode_s temp;
00141     long iparent, ichild;
00142 
00143     if (pheap->index == 0)
00144         return 0;               /* empty heap */
00145 
00146     *pnoderet = pheap->pnode[1];
00147 
00148     temp = pheap->pnode[pheap->index--];
00149 
00150     iparent = 1;
00151     ichild = 2;
00152 
00153     while (ichild <= pheap->index) {
00154         if (ichild < pheap->index &&
00155             pheap->pnode[ichild].key < pheap->pnode[ichild + 1].key) {
00156             ichild++;
00157         }
00158         if (temp.key >= pheap->pnode[ichild].key)
00159             break;
00160 
00161         pheap->pnode[iparent] = pheap->pnode[ichild];
00162         iparent = ichild;
00163         ichild *= 2;
00164     }
00165     pheap->pnode[iparent] = temp;
00166 
00167     return 1;
00168 }

Generated on Thu Jul 16 13:21:17 2009 for GRASS Programmer's Manual by  doxygen 1.5.6