#include "general.h"
#include "cutil.h"
Go to the source code of this file.
#define EMPTY -1 |
Definition at line 32 of file oldheap.h.
Referenced by CreateClusterTree(), FreeHeapData(), GetTopOfHeap(), HeapPop(), HeapPopWorst(), and PrintBadWords().
#define FreeHeap | ( | H | ) | memfree(H) |
Definition at line 58 of file oldheap.h.
Referenced by CreateClusterTree(), FreeHeapData(), and pick_good_seam().
#define HeapFull | ( | H | ) | ((H)->FirstFree > (H)->Size) |
#define HEAPFULL 3000 |
#define HeapKeyFor | ( | H, | |||
E | ) | ((H)->Entry[(E)+1].Key) |
macros for accessing elements in heap by index.
The indicies vary from 0 to SizeOfHeap-1. No bounds checking is done. Elements accessed in this manner are in random order relative to the Key values.
These macros should never be used as the LHS (Left Hand Side) of an assignment statement as this will corrupt the heap.
#define InitHeap | ( | H | ) | (H->FirstFree = 1) |
#define MaxSizeOfHeap | ( | H | ) | (H->Size) |
#define OK 0 |
Definition at line 31 of file oldheap.h.
Referenced by GetTopOfHeap(), HeapPop(), pick_good_seam(), and pop_queue().
#define SizeOfHeap | ( | H | ) | (H->FirstFree - 1) |
Similarily to FreeHeap, deallocates the memory consumed by the heap but also calls Deallocator for each item in the heap so that this data is also deallocated.
Heap | Heap whose data is to be freed | |
destructor | Function to be used to destroy data |
Definition at line 298 of file oldheap.cpp.
References HEAPENTRY::Data, EMPTY, FreeHeap, GetTopOfHeap(), and Heap.
Referenced by delete_search().
00298 { 00299 HEAPENTRY Entry; 00300 00301 while (GetTopOfHeap (Heap, &Entry) != EMPTY) 00302 destructor (Entry.Data); 00303 00304 FreeHeap(Heap); 00305 } /* FreeHeapData */
Removes the top item on the heap and copies its contents into Entry.
Heap | Ptr to heap whose top is to be removed and returned | |
Entry | Ptr to heap entry to be filled with top entry on Heap |
Definition at line 248 of file oldheap.cpp.
References HEAPENTRY::Data, EMPTY, HEAP::Entry, HEAP::FirstFree, Heap, HEAPENTRY::Key, LEFTSON, and OK.
Referenced by CreateClusterTree(), FreeHeapData(), pop_queue(), and PrintBadWords().
00248 { 00249 INT32 Hole; 00250 FLOAT32 HoleKey; 00251 INT32 Son; 00252 00253 if (Heap->FirstFree <= 1) 00254 return (EMPTY); 00255 00256 Entry->Key = Heap->Entry[1].Key; 00257 Entry->Data = Heap->Entry[1].Data; 00258 00259 Heap->FirstFree--; 00260 00261 /* imagine the hole at the root is filled with the last entry in the heap */ 00262 HoleKey = Heap->Entry[Heap->FirstFree].Key; 00263 Hole = 1; 00264 00265 /* while hole has 2 sons */ 00266 while ((Son = LEFTSON (Hole)) < Heap->FirstFree) { 00267 /* find the son with the smallest key */ 00268 if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key) 00269 Son++; 00270 00271 /* if key for hole is greater than key for son, sift hole down */ 00272 if (HoleKey > Heap->Entry[Son].Key) { 00273 Heap->Entry[Hole].Key = Heap->Entry[Son].Key; 00274 Heap->Entry[Hole].Data = Heap->Entry[Son].Data; 00275 Hole = Son; 00276 } 00277 else 00278 break; 00279 } 00280 Heap->Entry[Hole].Key = HoleKey; 00281 Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data; 00282 return (OK); 00283 } /* GetTopOfHeap */
Removes the top item on the heap and places its contents into Key and Data.
Heap | Ptr to heap whose top is to be removed and returned | |
Key | Place to put key of top heap item | |
out_ptr | Place to put data of top heap item |
Definition at line 71 of file oldheap.cpp.
References HEAPENTRY::Data, EMPTY, HEAP::Entry, HEAP::FirstFree, Heap, HEAPENTRY::Key, LEFTSON, and OK.
Referenced by pick_good_seam().
00071 { 00072 INT32 Hole; 00073 FLOAT32 HoleKey; 00074 INT32 Son; 00075 void **Data = (void **) out_ptr; 00076 00077 if (Heap->FirstFree <= 1) 00078 return (EMPTY); 00079 00080 *Key = Heap->Entry[1].Key; 00081 *Data = Heap->Entry[1].Data; 00082 00083 Heap->FirstFree--; 00084 00085 /* imagine the hole at the root is filled with the last entry in the heap */ 00086 HoleKey = Heap->Entry[Heap->FirstFree].Key; 00087 Hole = 1; 00088 00089 /* while hole has 2 sons */ 00090 while ((Son = LEFTSON (Hole)) < Heap->FirstFree) { 00091 /* find the son with the smallest key */ 00092 if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key) 00093 Son++; 00094 00095 /* if key for hole is greater than key for son, sift hole down */ 00096 if (HoleKey > Heap->Entry[Son].Key) { 00097 Heap->Entry[Hole].Key = Heap->Entry[Son].Key; 00098 Heap->Entry[Hole].Data = Heap->Entry[Son].Data; 00099 Hole = Son; 00100 } 00101 else 00102 break; 00103 } 00104 Heap->Entry[Hole].Key = HoleKey; 00105 Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data; 00106 return (OK); 00107 } /* HeapPop */
Remove the largest item from the heap.
Heap | Pointer to heap whose top is to be removed and returned | |
Key | Place to put key of top heap item | |
out_ptr | Place to put data of top heap item |
Definition at line 119 of file oldheap.cpp.
References EMPTY, HEAP::Entry, FATHER, HEAP::FirstFree, Heap, and HEAPENTRY::Key.
Referenced by junk_worst_seam().
00119 { 00120 INT32 Index; /*current index */ 00121 INT32 Hole; 00122 FLOAT32 HoleKey; 00123 INT32 Father; 00124 void *HoleData; 00125 void **Data = (void **) out_ptr; 00126 00127 if (Heap->FirstFree <= 1) 00128 return (EMPTY); 00129 00130 HoleKey = Heap->Entry[1].Key; 00131 Hole = 1; 00132 Heap->FirstFree--; 00133 for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father; 00134 Index--) 00135 if (Heap->Entry[Index].Key > HoleKey) { 00136 /*find biggest */ 00137 HoleKey = Heap->Entry[Index].Key; 00138 Hole = Index; 00139 } 00140 *Key = HoleKey; 00141 *Data = Heap->Entry[Hole].Data; 00142 00143 HoleKey = Heap->Entry[Heap->FirstFree].Key; 00144 Heap->Entry[Hole].Key = HoleKey; 00145 HoleData = Heap->Entry[Heap->FirstFree].Data; 00146 Heap->Entry[Hole].Data = HoleData; 00147 00148 /* now sift last entry to its rightful place */ 00149 Father = FATHER (Hole); /*father of hole */ 00150 while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) { 00151 /*swap entries */ 00152 Heap->Entry[Hole].Key = Heap->Entry[Father].Key; 00153 Heap->Entry[Hole].Data = Heap->Entry[Father].Data; 00154 Heap->Entry[Father].Data = HoleData; 00155 Heap->Entry[Father].Key = HoleKey; 00156 Hole = Father; 00157 Father = FATHER (Hole); 00158 } 00159 return (OK); 00160 } /* HeapPop */
Stores Data into Heap and associates it with Key.
Heap | Ptr to heap to store new item in | |
Key | Numeric key associated with new item | |
Data | Ptr to data contents of new item |
Definition at line 177 of file oldheap.cpp.
References HEAPENTRY::Data, DoError(), HEAP::Entry, FATHER, HEAP::FirstFree, Heap, HEAPFULL, HEAPENTRY::Key, and HEAP::Size.
Referenced by junk_worst_seam().
00177 { 00178 INT32 Item; 00179 INT32 Father; 00180 00181 if (Heap->FirstFree > Heap->Size) 00182 DoError (HEAPFULL, "Heap size exceeded"); 00183 00184 Item = Heap->FirstFree; 00185 Heap->FirstFree++; 00186 while (Item != 1) { 00187 Father = FATHER (Item); 00188 if (Heap->Entry[Father].Key > Key) { 00189 Heap->Entry[Item].Key = Heap->Entry[Father].Key; 00190 Heap->Entry[Item].Data = Heap->Entry[Father].Data; 00191 Item = Father; 00192 } 00193 else 00194 break; 00195 } 00196 Heap->Entry[Item].Key = Key; 00197 Heap->Entry[Item].Data = Data; 00198 } /* HeapPush */
Stores Entry into Heap.
Heap | Ptr to heap to store new item in | |
Entry | Ptr to item to be stored in Heap |
Definition at line 214 of file oldheap.cpp.
References HEAPENTRY::Data, DoError(), HEAP::Entry, FATHER, HEAP::FirstFree, Heap, HEAPFULL, HEAPENTRY::Key, and HEAP::Size.
Referenced by add_point_to_list(), CreateClusterTree(), MakePotentialClusters(), push_queue(), and SaveBadWord().
00214 { 00215 INT32 Item; 00216 INT32 Father; 00217 00218 if (Heap->FirstFree > Heap->Size) 00219 DoError (HEAPFULL, "Heap size exceeded"); 00220 00221 Item = Heap->FirstFree; 00222 Heap->FirstFree++; 00223 while (Item != 1) { 00224 Father = FATHER (Item); 00225 if (Heap->Entry[Father].Key > Entry->Key) { 00226 Heap->Entry[Item].Key = Heap->Entry[Father].Key; 00227 Heap->Entry[Item].Data = Heap->Entry[Father].Data; 00228 Item = Father; 00229 } 00230 else 00231 break; 00232 } 00233 Heap->Entry[Item].Key = Entry->Key; 00234 Heap->Entry[Item].Data = Entry->Data; 00235 } /* HeapStore */
HEAP* MakeHeap | ( | int | Size | ) |
Creates and initializes a new heap data structure containing Size elements.
Size | Maximum number of entries in the heap |
Definition at line 48 of file oldheap.cpp.
References Emalloc(), HEAP::FirstFree, and HEAP::Size.
Referenced by CreateClusterTree(), new_search(), pick_good_seam(), and SaveBadWord().
00048 { 00049 HEAP *NewHeap; 00050 00051 NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY)); 00052 00053 NewHeap->Size = Size; 00054 NewHeap->FirstFree = 1; 00055 return (NewHeap); 00056 } /* MakeHeap */