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         if ( pheap->pnode ) {
00041                 if ( pfnCancelItem ) {
00042                         for (iItem = 0 ; iItem <= pheap->index ; iItem ++) {
00043                                 pfnCancelItem(pheap, & pheap->pnode[iItem] );
00044                         }
00045                 }
00046                 free( pheap->pnode );
00047         }
00048         pheap->pnode = NULL;
00049 }
00050 
00051 int dglHeapInsertMin(
00052                 dglHeap_s * pheap ,
00053                 long key ,
00054                 unsigned char flags ,
00055                 dglHeapData_u value
00056                 )
00057 {
00058         long i;
00059 
00060         if ( pheap->index >= pheap->count - 1 )
00061         {
00062                 pheap->count += pheap->block;
00063                 if ( (pheap->pnode = realloc( pheap->pnode , sizeof( dglHeapNode_s ) * pheap->count )) == NULL ) return -1;
00064         }
00065 
00066         i = ++pheap->index;
00067 
00068         while( i != 1 && key < pheap->pnode[ i / 2 ].key )
00069         {
00070                 pheap->pnode[ i ] = pheap->pnode[ i / 2 ];
00071                 i /= 2;
00072         }
00073 
00074         pheap->pnode[ i ].key = key;
00075         pheap->pnode[ i ].flags = flags;
00076         pheap->pnode[ i ].value = value;
00077 
00078         return i;
00079 }
00080 
00081 int dglHeapExtractMin(
00082                 dglHeap_s * pheap,
00083                 dglHeapNode_s * pnoderet
00084                 )
00085 {
00086         dglHeapNode_s temp;
00087         long iparent , ichild;
00088 
00089         if ( pheap->index == 0 ) return 0; /* empty heap */
00090 
00091         *pnoderet = pheap->pnode[ 1 ];
00092 
00093         temp = pheap->pnode[ pheap->index-- ];
00094         
00095         iparent = 1;
00096         ichild = 2;
00097 
00098         while( ichild <= pheap->index )
00099         {
00100                 if ( ichild < pheap->index && pheap->pnode[ ichild ].key > pheap->pnode[ ichild + 1 ].key )
00101                 {
00102                         ichild ++;
00103                 }
00104                 if ( temp.key <= pheap->pnode[ ichild ].key ) break;
00105 
00106                 pheap->pnode[ iparent ] = pheap->pnode[ ichild ];
00107                 iparent = ichild;
00108                 ichild *= 2;
00109         }
00110         pheap->pnode[ iparent ] = temp;
00111 
00112         return 1;       
00113 }
00114 
00115 int dglHeapInsertMax(
00116                 dglHeap_s * pheap ,
00117                 long key ,
00118                 unsigned char flags ,
00119                 dglHeapData_u value
00120                 )
00121 {
00122         long i;
00123 
00124         if ( pheap->index >= pheap->count - 1 )
00125         {
00126                 pheap->count += pheap->block;
00127                 if ( (pheap->pnode = realloc( pheap->pnode , sizeof( dglHeapNode_s ) * pheap->count )) == NULL ) return -1;
00128         }
00129 
00130         i = ++pheap->index;
00131 
00132         while( i != 1 && key > pheap->pnode[ i / 2 ].key )
00133         {
00134                 pheap->pnode[ i ] = pheap->pnode[ i / 2 ];
00135                 i /= 2;
00136         }
00137 
00138         pheap->pnode[ i ].key = key;
00139         pheap->pnode[ i ].flags = flags;
00140         pheap->pnode[ i ].value = value;
00141 
00142         return i;
00143 }
00144 
00145 int dglHeapExtractMax(
00146                 dglHeap_s * pheap,
00147                 dglHeapNode_s * pnoderet
00148                 )
00149 {
00150         dglHeapNode_s temp;
00151         long iparent , ichild;
00152 
00153         if ( pheap->index == 0 ) return 0; /* empty heap */
00154 
00155         *pnoderet = pheap->pnode[ 1 ];
00156 
00157         temp = pheap->pnode[ pheap->index-- ];
00158         
00159         iparent = 1;
00160         ichild = 2;
00161 
00162         while( ichild <= pheap->index )
00163         {
00164                 if ( ichild < pheap->index && pheap->pnode[ ichild ].key < pheap->pnode[ ichild + 1 ].key )
00165                 {
00166                         ichild ++;
00167                 }
00168                 if ( temp.key >= pheap->pnode[ ichild ].key ) break;
00169 
00170                 pheap->pnode[ iparent ] = pheap->pnode[ ichild ];
00171                 iparent = ichild;
00172                 ichild *= 2;
00173         }
00174         pheap->pnode[ iparent ] = temp;
00175 
00176         return 1;
00177 }
00178 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5