00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include <stdio.h>
00014 #include <stdlib.h>
00015 #include <string.h>
00016 #include "pq.h"
00017
00018 int ReplaceCount,ReplaceCountReheap;
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 void InitPQ(PQ *q,int ne,int (*c)(void **,void **))
00035 {
00036 q->cmp = c;
00037 q->nitems = 0;
00038 q->maxitems = ne;
00039 q->heap = (void **)malloc(sizeof(void *) * ne);
00040 q->bottom = &q->heap[-1];
00041 }
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053 int Insert(PQ* q,void *item)
00054 {
00055 int space_avail;
00056
00057 space_avail = q->maxitems - q->nitems;
00058 if((space_avail) > 0)
00059 {
00060 ++q->nitems;
00061 *(++q->bottom) = item;
00062 ReheapUp(q);
00063 }
00064 return space_avail;
00065 }
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077 int Delete(PQ* q,void **target)
00078 {
00079 int SlotsInUse;
00080
00081 if((SlotsInUse = q->nitems) > 0)
00082 {
00083 *target = *q->heap;
00084 *q->heap = *q->bottom--;
00085 --q->nitems;
00086 ReheapDown(q);
00087 }
00088 return SlotsInUse;
00089 }
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102 int Replace(PQ* q,void **target,void *item)
00103 {
00104 int SlotsInUse;
00105
00106 if((SlotsInUse = q->nitems) > 0)
00107 {
00108 ++ReplaceCount;
00109 if ((*q->cmp)(&item,q->heap) > 0)
00110 {
00111 *target = item;
00112 }
00113 else
00114 {
00115 ++ReplaceCountReheap;
00116 *target = *q->heap;
00117 *q->heap = item;
00118 ReheapDown(q);
00119 }
00120 }
00121 else
00122 *target = item;
00123 return SlotsInUse;
00124 }
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136 int Remove(PQ* q,void **target,int (*cmp)(void **,void **),void *item)
00137 {
00138 int SlotsInUse;
00139
00140 if((SlotsInUse = q->nitems)>0)
00141 {
00142 int i;
00143 int loop;
00144
00145 for(i=0,loop=1;i<q->nitems && loop;++i)
00146 {
00147 if( (*cmp)(&item,&q->heap[i]) == 0)
00148 {
00149 *target = q->heap[i];
00150 memcpy(&q->heap[i],&q->heap[i+1],(q->nitems - i - 1) * sizeof(void *));
00151 q->bottom--;
00152 q->nitems--;
00153 ReheapDown(q);
00154 loop = 0;
00155 }
00156 }
00157 }
00158 return SlotsInUse;
00159 }
00160
00161
00162
00163
00164
00165
00166
00167 void swap(void **s1,void **s2)
00168 {
00169 void *temp;
00170
00171 temp = *s1;
00172 *s1 = *s2;
00173 *s2 = temp;
00174 }
00175
00176 void ReheapUp(PQ* q)
00177 {
00178 int parent;
00179 int child;
00180 void **pparent;
00181 void **pchild;
00182
00183 child = q->nitems - 1;
00184 while((parent = (child - 1)/2) >= 0)
00185 {
00186 pchild = &q->heap[child];
00187 pparent = &q->heap[parent];
00188 if( (*q->cmp)(pparent,pchild) >= 0)
00189 break;
00190 swap(pparent,pchild);
00191 child = parent;
00192 }
00193 }
00194
00195 void ReheapDown(PQ* q)
00196 {
00197 int parent;
00198 int child;
00199 void **pparent;
00200 void **pchild;
00201 void **psibling;
00202 void **pheap;
00203
00204 pheap = q->heap;
00205 for(parent=0,child=1;child < q->nitems;)
00206 {
00207 pparent = &pheap[parent];
00208 pchild = &pheap[child];
00209 if(child + 1 < q->nitems)
00210 {
00211 psibling = pchild + 1;
00212 if((*q->cmp)(pchild,psibling) < 0)
00213 {
00214 pchild = psibling;
00215 child++;
00216 }
00217 }
00218 if((*q->cmp)(pparent,pchild) >= 0)
00219 break;
00220 swap(pparent,pchild);
00221 parent = child;
00222 child = parent * 2 + 1;
00223 }
00224 }
00225
00226 void *Get(PQ* q)
00227 {
00228 return q->heap[0];
00229 }
00230
00231 int NumElem(PQ* q)
00232 {
00233 return q->nitems;
00234 }
00235
00236 void *GetI(PQ* q,int i)
00237 {
00238 return q->heap[i];
00239 }