Azinix

heap.c

Go to the documentation of this file.
00001 /** \file heap.c
00002 
00003 \brief Heap code
00004 
00005 Array starts at 
00006 zero, so left and right children are at (2*index + 1) 
00007 and ( 2 * index + 2 ).
00008 
00009 ******************************************************************************/
00010 
00011 #include "heap.h"
00012 
00013 /**AutomaticStart*************************************************************/
00014 
00015 /**AutomaticEnd***************************************************************/
00016 
00017 
00018 /**
00019   * \brief  Return index of left child
00020   * 
00021   */
00022 
00023 static inline int
00024 leftChild (int index)
00025 {
00026   return ((2 * index) + 1);
00027 }
00028 
00029 
00030 /**
00031   * \brief  Return index of right child
00032   * 
00033   */
00034 
00035 static inline int
00036 rightChild (int index)
00037 {
00038   return ((2 * index) + 2);
00039 }
00040 
00041 
00042 /**
00043   * \brief  Return index of parent
00044   * 
00045   */
00046 
00047 static inline int
00048 getParent (int index)
00049 {
00050   if (index == 0)
00051     {
00052       printf ("root has no parent!\n");
00053       assert (0);
00054     }
00055   return ((index % 2) == 1) ? (index / 2) : ((index - 1) / 2);
00056 }
00057 
00058 
00059 /**
00060   * \brief  Create a heap with N entries
00061   * 
00062   */
00063 
00064 Heap_t *
00065 Heap_InitN (int (*less) (char *, char *), int N)
00066 {
00067   assert (N >= 0);
00068   Heap_t *result = (Heap_t *) malloc (sizeof (Heap_t));
00069   result->less = less;
00070 
00071   result->entryArray = array_alloc (char *, N);
00072   return result;
00073 }
00074 
00075 
00076 /**
00077   * \brief  Create a heap with 0 entries
00078   */
00079 
00080 Heap_t *
00081 Heap_Init (int (*less) (char *, char *))
00082 {
00083   return Heap_InitN (less, 0);
00084 }
00085 
00086 
00087 /**
00088   * \brief  Insert an entry into a heap
00089   */
00090 
00091 void
00092 Heap_Insert (Heap_t * aHeap, char *entry)
00093 {
00094   array_insert_last (char *, aHeap->entryArray, entry);
00095 
00096   unsigned int index = array_n (aHeap->entryArray) - 1; // this is the index of what we just inserted
00097   char *current = entry;
00098   char *parent = NIL (char);
00099   while (1)
00100     {
00101       if (index == 0)
00102     {
00103       return;       // it's at the top of the heap
00104     }
00105       parent = array_fetch (char *, aHeap->entryArray, getParent (index));
00106       int currIsLessThanParent = aHeap->less (current, parent);
00107       if (currIsLessThanParent)
00108     {
00109       return;       // heap invariant is satisfied
00110     }
00111       else
00112     {
00113       // perform swap - current goes to getParent( index ),
00114       // parent goes to index
00115       // index becomes its parent
00116       array_insert (char *, aHeap->entryArray, getParent (index),
00117             current);
00118       array_insert (char *, aHeap->entryArray, index, parent);
00119       index = getParent (index);
00120     }
00121     }
00122   assert (0);
00123 }
00124 
00125 
00126 /**
00127   * \brief  Returns the number of elements in the heap
00128   */
00129 
00130 int
00131 Heap_Size (Heap_t * aHeap)
00132 {
00133   return array_n (aHeap->entryArray);
00134 }
00135 
00136 
00137 /**
00138   * \brief  Return the max element of the heap; does not change heap
00139   */
00140 
00141 char *
00142 Heap_ReadMax (Heap_t * aHeap)
00143 {
00144   array_t *entryArray = aHeap->entryArray;
00145   assert (array_n (entryArray) > 0);
00146   char *result = array_fetch (char *, entryArray, 0);
00147 
00148   return result;
00149 }
00150 
00151 
00152 /**
00153   * \brief  Take a heap which satisfies the heap property everywhere but
00154   * possibly the root, and make it into a heap
00155   * 
00156   */
00157 
00158 void
00159 Heap_Heapify (Heap_t * aHeap)
00160 {
00161   array_t *entryArray = aHeap->entryArray;
00162   int (*less) (char *, char *) = aHeap->less;
00163 
00164   int numEntries = array_n (entryArray);
00165   if (numEntries == 0)
00166     {
00167       return;
00168     }
00169   unsigned int rootIndex = 0;
00170   char *root = array_fetch (char *, entryArray, rootIndex);
00171   char *child0, *child1;
00172   while (1)
00173     {
00174       if (leftChild (rootIndex) < numEntries)
00175     {
00176       child0 = array_fetch (char *, entryArray, leftChild (rootIndex));
00177     }
00178       else
00179     {
00180       child0 = NIL (char);
00181     }
00182       if (rightChild (rootIndex) < numEntries)
00183     {
00184       child1 = array_fetch (char *, entryArray, rightChild (rootIndex));
00185     }
00186       else
00187     {
00188       child1 = NIL (char);
00189     }
00190       if (child0 == NIL (char))
00191     {
00192       return;       // nothing to swap with
00193     }
00194       if (child1 == NIL (char))
00195     {
00196       // have only a left child
00197       if (less (root, child0))
00198         {
00199           array_insert (char *, entryArray, rootIndex, child0);
00200           array_insert (char *, entryArray, leftChild (rootIndex), root);
00201         }
00202       return;       // only one child means we're done
00203     }
00204       if (!less (root, child0) && !less (root, child1))
00205     {
00206       // root is bigger than both children, so we're done
00207       return;
00208     }
00209       if (less (child0, child1))
00210     {
00211       // child0 is less than child1 so swap with child1
00212       array_insert (char *, entryArray, rootIndex, child1);
00213       array_insert (char *, entryArray, rightChild (rootIndex), root);
00214       rootIndex = rightChild (rootIndex);
00215     }
00216       else
00217     {
00218       // child1 is less than child0, so swap with child0
00219       array_insert (char *, entryArray, rootIndex, child0);
00220       array_insert (char *, entryArray, leftChild (rootIndex), root);
00221       rootIndex = leftChild (rootIndex);
00222     }
00223     }
00224   assert (0);
00225 }
00226 
00227 /**
00228   * \brief  Code to test the heap package
00229   */
00230 
00231 int
00232 Heap_Test ()
00233 {
00234   Heap_t *aHeap = Heap_Init ( ( int (*)(char*, char*) ) strcmp);
00235 
00236   Heap_Insert (aHeap, "foo");
00237   Heap_Insert (aHeap, "bar");
00238   Heap_Insert (aHeap, "a");
00239   Heap_Insert (aHeap, "123");
00240 
00241   printf ("%s\n", Heap_ReadMax (aHeap));
00242   Heap_Insert (aHeap, "goo");
00243   Heap_Insert (aHeap, "zzz");
00244   Heap_Insert (aHeap, "bar");
00245   printf ("%s\n", Heap_ReadMax (aHeap));
00246 
00247   return 0;
00248 }