GRASS Programmer's Manual 6.4.1(2011)
|
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 }