dheaps_i.c

Go to the documentation of this file.
00001 /****************************************************************************/
00002 /*                                                                          */
00003 /*  This file is part of QSopt_ex.                                          */
00004 /*                                                                          */
00005 /*  (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash,      */
00006 /*  and Daniel Espinoza                                                     */
00007 /*                                                                          */
00008 /*  Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his     */
00009 /*  copyright in QSopt.                                                     */
00010 /*                                                                          */
00011 /*  This code may be used under the terms of the GNU General Public License */
00012 /*  (Version 2.1 or later) as published by the Free Software Foundation.    */
00013 /*                                                                          */
00014 /*  Alternatively, use is granted for research purposes only.               */
00015 /*                                                                          */
00016 /*  It is your choice of which of these two licenses you are operating      */
00017 /*  under.                                                                  */
00018 /*                                                                          */
00019 /*  We make no guarantees about the correctness or usefulness of this code. */
00020 /*                                                                          */
00021 /****************************************************************************/
00022 
00023 /* RCSINFO $Id: dheaps_i.c,v 1.2 2003/11/05 16:47:22 meven Exp $ */
00024 /****************************************************************************/
00025 /*                                                                          */
00026 /*  This file is part of CONCORDE                                           */
00027 /*                                                                          */
00028 /*  (c) Copyright 1995--1999 by David Applegate, Robert Bixby,              */
00029 /*  Vasek Chvatal, and William Cook                                         */
00030 /*                                                                          */
00031 /*  Permission is granted for academic research use.  For other uses,       */
00032 /*  contact the authors for licensing options.                              */
00033 /*                                                                          */
00034 /*  Use at your own risk.  We make no guarantees about the                  */
00035 /*  correctness or usefulness of this code.                                 */
00036 /*                                                                          */
00037 /****************************************************************************/
00038 
00039 /****************************************************************************/
00040 /*                                                                          */
00041 /*                           DHEAP ROUTINES                                 */
00042 /*                                                                          */
00043 /*                                                                          */
00044 /*                              TSP CODE                                    */
00045 /*  Written by:  Applegate, Bixby, Chvatal, and Cook                        */
00046 /*  Date: February 9, 1995                                                  */
00047 /*        March 11, 2002 - Cook (Modifed for QS)                            */
00048 /*  Reference: R.E. Tarjan, Data Structures and Network Algorithms          */
00049 /*                                                                          */
00050 /*    EXPORTED FUNCTIONS:                                                   */
00051 /*                                                                          */
00052 /*  int ILLutil_dheap_init (ILLdheap *h, int k)                             */
00053 /*        -h should point to a ILLdheap struct.                             */
00054 /*        -k the max number of elements in the dheap.                       */
00055 /*                                                                          */
00056 /*  void ILLutil_dheap_free (ILLdheap *h)                                   */
00057 /*    -frees the spaces allocated by ILLutil_dheap_init                     */
00058 /*                                                                          */
00059 /*  int ILLutil_dheap_resize (ILLdheap *h, int newsize)                     */
00060 /*    -REALLOCs h so it can contain newsize elements.                       */
00061 /*    -returns -1 if it can't resize the heap.                              */
00062 /*                                                                          */
00063 /*  void ILLutil_dheap_findmin (ILLdheap *h, int *i)                        */
00064 /*    -sets i to the index of the element with min value h->key[i]          */
00065 /*    -sets i to -1 if no elements in heap.                                 */
00066 /*                                                                          */
00067 /*  int ILLutil_dheap_insert (ILLdheap *h, int i)                           */
00068 /*    -inserts the element with index i (so its key should be loaded        */
00069 /*     beforehand in h->key[i]).                                            */
00070 /*                                                                          */
00071 /*  void ILLutil_dheap_delete (ILLdheap *h, int i)                          */
00072 /*    -deletes the element with index i.                                    */
00073 /*                                                                          */
00074 /*  void ILLutil_dheap_deletemin (ILLdheap *h, int *i)                      */
00075 /*    -sets i to the min element in the heap, and deletes the min element   */
00076 /*    -sets i to -1 if no elements in heap.                                 */
00077 /*                                                                          */
00078 /*  void ILLutil_dheap_changekey (ILLdheap *h, int i, EGlpNum_t* newkey)        */
00079 /*    -changes the key of the element with index i to newkey.               */
00080 /*                                                                          */
00081 /****************************************************************************/
00082 
00083 /****************************************************************************/
00084 /*                                                                          */
00085 /*  NOTES:                                                                  */
00086 /*      A k-element heap will malloc 16k bytes of memory. If memory is      */
00087 /*  tight, using integer keys (instead of doubles), brings it down to       */
00088 /*  12k bytes, and if arbitrary deletions are not required, with a little   */
00089 /*  rewriting, the h->loc field can be eliminated, bring the space down     */
00090 /*  to 8k bytes.                                                            */
00091 /*      These routines work with indices into the h->key array, so in       */
00092 /*  some cases, you will need to maintain a separate names array to know    */
00093 /*  what element belongs to index i. For an example, see the k_nearest      */
00094 /*  code in kdnear.c.                                                       */
00095 /*                                                                          */
00096 /****************************************************************************/
00097 
00098 #include "qs_config.h"
00099 #include "dheaps_i.h"
00100 #include "allocrus.h"
00101 #include "machdefs.h"
00102 #include "except.h"
00103 #include "trace.h"
00104 #ifdef USEDMALLOC
00105 #include "dmalloc.h"
00106 #endif
00107 
00108 static int TRACE = 0;
00109 
00110 #define HEAP_D 3
00111 #define HEAP_UP(x) (((x)-1)/HEAP_D)
00112 #define HEAP_DOWN(x) (((x)*HEAP_D)+1)
00113 
00114 
00115 static void dheap_siftup (
00116   ILLdheap * h,
00117   int i,
00118   int x),
00119   dheap_siftdown (
00120   ILLdheap * h,
00121   int i,
00122   int x);
00123 
00124 static int dheap_minchild (
00125   int x,
00126   ILLdheap * h);
00127 
00128 
00129 int ILLutil_dheap_init (
00130   ILLdheap * h,
00131   int k)
00132 {
00133   int rval = 0;
00134 
00135   h->entry = (int *) NULL;
00136   h->loc = (int *) NULL;
00137   h->key = 0;
00138 
00139 
00140   ILL_SAFE_MALLOC (h->entry, k, int);
00141   ILL_SAFE_MALLOC (h->loc, k, int);
00142 
00143   h->key = EGlpNumAllocArray (k);
00144   h->size = 0;
00145   h->total_space = k;
00146 
00147 CLEANUP:
00148 
00149   if (rval)
00150   {
00151     ILLutil_dheap_free (h);
00152   }
00153 
00154   ILL_RETURN (rval, "ILLutil_dheap_init");
00155 }
00156 
00157 void ILLutil_dheap_free (
00158   ILLdheap * h)
00159 {
00160   ILL_IFFREE (h->entry, int);
00161   ILL_IFFREE (h->loc, int);
00162 
00163   EGlpNumFreeArray (h->key);
00164 }
00165 
00166 int ILLutil_dheap_resize (
00167   ILLdheap * h,
00168   int newsize)
00169 {
00170   int rval = 0;
00171 
00172   if (newsize < h->size || newsize < h->total_space)
00173   {
00174     ILL_CLEANUP;
00175   }
00176 
00177   h->key = EGrealloc (h->key, sizeof (double) * newsize);
00178   //rval = ILLutil_reallocrus_count ((void **) &(h->key), newsize,
00179   //                                 sizeof (double));
00180   //ILL_CLEANUP_IF (rval);
00181   h->entry = EGrealloc (h->entry, sizeof (int) * newsize);
00182   //rval = ILLutil_reallocrus_count ((void **) &(h->entry), newsize,
00183   //                                 sizeof (int));
00184   //ILL_CLEANUP_IF (rval);
00185   h->loc = EGrealloc (h->loc, sizeof (int) * newsize);
00186   //rval = ILLutil_reallocrus_count ((void **) &(h->loc), newsize, sizeof (int));
00187   //ILL_CLEANUP_IF (rval);
00188   h->total_space = newsize;
00189 
00190 CLEANUP:
00191 
00192   ILL_RETURN (rval, "ILLutil_dheap_resize");
00193 }
00194 
00195 void ILLutil_dheap_findmin (
00196   ILLdheap * h,
00197   int *i)
00198 {
00199   if (h->size == 0)
00200     *i = -1;
00201   else
00202     *i = h->entry[0];
00203 }
00204 
00205 int ILLutil_dheap_insert (
00206   ILLdheap * h,
00207   int i)
00208 {
00209   if (h->size >= h->total_space)
00210   {
00211     fprintf (stderr, "Error - heap already full\n");
00212     return 1;
00213   }
00214   h->size++;
00215   dheap_siftup (h, i, h->size - 1);
00216 
00217   return 0;
00218 }
00219 
00220 void ILLutil_dheap_delete (
00221   ILLdheap * h,
00222   int i)
00223 {
00224   int j;
00225 
00226   h->size--;
00227   j = h->entry[h->size];
00228   h->entry[h->size] = -1;
00229 
00230   if (j != i)
00231   {
00232     if (EGlpNumIsLeq (h->key[j], h->key[i]))
00233     {
00234       dheap_siftup (h, j, h->loc[i]);
00235     }
00236     else
00237     {
00238       dheap_siftdown (h, j, h->loc[i]);
00239     }
00240   }
00241 }
00242 
00243 void ILLutil_dheap_deletemin (
00244   ILLdheap * h,
00245   int *i)
00246 {
00247   int j;
00248 
00249   if (h->size == 0)
00250     *i = -1;
00251   else
00252   {
00253     j = h->entry[0];
00254     ILLutil_dheap_delete (h, j);
00255     *i = j;
00256   }
00257 }
00258 
00259 void ILLutil_dheap_changekey (
00260   ILLdheap * h,
00261   int i,
00262   EGlpNum_t * newkey)
00263 {
00264   if (EGlpNumIsLess (*newkey, h->key[i]))
00265   {
00266     EGlpNumCopy (h->key[i], *newkey);
00267     dheap_siftup (h, i, h->loc[i]);
00268   }
00269   else if (EGlpNumIsLess (h->key[i], *newkey))
00270   {
00271     EGlpNumCopy (h->key[i], *newkey);
00272     dheap_siftdown (h, i, h->loc[i]);
00273   }
00274 }
00275 
00276 static void dheap_siftup (
00277   ILLdheap * h,
00278   int i,
00279   int x)
00280 {
00281   int p;
00282 
00283   p = HEAP_UP (x);
00284   while (x && EGlpNumIsLess (h->key[i], h->key[h->entry[p]]))
00285   {
00286     h->entry[x] = h->entry[p];
00287     h->loc[h->entry[p]] = x;
00288     x = p;
00289     p = HEAP_UP (p);
00290   }
00291   h->entry[x] = i;
00292   h->loc[i] = x;
00293 }
00294 
00295 static void dheap_siftdown (
00296   ILLdheap * h,
00297   int i,
00298   int x)
00299 {
00300   int c;
00301 
00302   c = dheap_minchild (x, h);
00303 
00304   while (c >= 0 && EGlpNumIsLess (h->key[h->entry[c]], h->key[i]))
00305   {
00306     h->entry[x] = h->entry[c];
00307     h->loc[h->entry[c]] = x;
00308     x = c;
00309     c = dheap_minchild (c, h);
00310   }
00311   h->entry[x] = i;
00312   h->loc[i] = x;
00313 }
00314 
00315 static int dheap_minchild (
00316   int x,
00317   ILLdheap * h)
00318 {
00319   int c = HEAP_DOWN (x);
00320   int cend;
00321   EGlpNum_t minval;
00322   int minloc;
00323 
00324   if (c >= h->size)
00325     return -1;
00326 
00327   EGlpNumInitVar (minval);
00328   EGlpNumCopy (minval, h->key[h->entry[c]]);
00329   minloc = c;
00330   cend = c + HEAP_D;
00331   if (h->size < cend)
00332     cend = h->size;
00333   for (c++; c < cend; c++)
00334   {
00335     if (EGlpNumIsLess (h->key[h->entry[c]], minval))
00336     {
00337       EGlpNumCopy (minval, h->key[h->entry[c]]);
00338       minloc = c;
00339     }
00340   }
00341   EGlpNumClearVar (minval);
00342   return minloc;
00343 }

Generated on Thu Mar 29 09:32:29 2012 for QSopt_ex by  doxygen 1.4.7