eg_eheap.ex.c

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 /** @file 
00021  * @ingroup EGeHeap */
00022 /** @addtogroup EGeHeap */
00023 /** @{ */
00024 /* ========================================================================= */
00025 /** @brief This program reads a list of double values from a text file and 
00026  * uses a heap to sort them. It also allows the user to change the value of 
00027  * one of the read numbers after they have been placed in the heap. The 
00028  * purpose of this program is to illustrate the use of the @ref EGeHeap 
00029  * structure and its associated functions. 
00030  * 
00031  * The input file format is: 
00032  * n
00033  * Value_0
00034  * Value_1
00035  * Value_2
00036  * Value_3
00037  *   ...  
00038  * Value_n 
00039  * */
00040 /* ========================================================================= */
00041 #include "EGlib.h"
00042 
00043 /* ========================================================================= */
00044 /** @brief display the usage message for this program */
00045 void eheap_usage (char *program)
00046 {
00047   fprintf (stdout, "Usage: %s [options]\n", program);
00048   fprintf (stdout, "Options:\n");
00049   fprintf (stdout, "     -d n   'd' value.\n");
00050   fprintf (stdout, "     -f n   file name.\n");
00051   fprintf (stdout, "     -c n   item whose value to change.\n");
00052   fprintf (stdout, "     -v n   new item value (0 by default).\n");
00053 
00054 }
00055 
00056 /* ========================================================================= */
00057 /** @brief parse the input argumenbts for the program */
00058 int eheap_parseargs (int argc,
00059                      char **argv,
00060                      unsigned int *d,
00061                      unsigned int *ch,
00062                      EGlpNum_t * v,
00063                      char **file_name)
00064 {
00065   int c;
00066   while ((c = getopt (argc, argv, "f:d:c:v:")) != EOF)
00067   {
00068     switch (c)
00069     {
00070     case 'f':
00071       *file_name = optarg;
00072       break;
00073     case 'd':
00074       *d = atoi (optarg);
00075       break;
00076     case 'c':
00077       *ch = atoi (optarg);
00078       break;
00079     case 'v':
00080       EGlpNumReadStr (*v, optarg);
00081       break;
00082     default:
00083       eheap_usage (argv[0]);
00084       return 1;
00085     }
00086   }
00087   /* reporting the options */
00088   if (!*file_name)
00089   {
00090     eheap_usage (argv[0]);
00091     return 1;
00092   }
00093   fprintf (stdout, "Parsed Options:\n");
00094   fprintf (stdout, "input         : %s\n", *file_name);
00095   fprintf (stdout, "d             : %u\n", *d);
00096   if (*ch != UINT_MAX)
00097   {
00098     fprintf (stdout, "c             : %u\n", *ch);
00099     fprintf (stdout, "v             : %lf\n", EGlpNumToLf (*v));
00100   }
00101   return 0;
00102 }
00103 
00104 /* ========================================================================= */
00105 /** @brief main function */
00106 int main (int argc,
00107           char **argv)
00108 {
00109 
00110   int rval = 0;
00111   unsigned int i,
00112     c = UINT_MAX,
00113     d = 2;
00114   char *file_name = 0,
00115     str1[1024];
00116   FILE *file;
00117   unsigned int nval;
00118   EGlpNum_t v;
00119   EGeHeap_t my_heap;
00120   EGeHeapCn_t *all_cn = 0,
00121    *ccn;
00122   EGlib_info();
00123   EGlib_version();
00124   EGlpNumStart();
00125   /* set signal and limits */
00126   EGsigSet(rval,CLEANUP);
00127   EGsetLimits(3600.0,4294967295UL);
00128   EGlpNumInitVar (v);
00129   EGlpNumZero (v);
00130   EGeHeapInit (&my_heap);
00131   rval = EGeHeapCheck (&my_heap);
00132   CHECKRVALG (rval, CLEANUP);
00133 
00134   /* Parse command line input to get 'file name' and 'd'. */
00135   rval = eheap_parseargs (argc, argv, &d, &c, &v, &file_name);
00136   CHECKRVALG (rval, CLEANUP);
00137   EGeHeapChangeD (&my_heap, d);
00138   rval = EGeHeapCheck (&my_heap);
00139   CHECKRVALG (rval, CLEANUP);
00140 
00141   /* Read the objects to sort from the file */
00142   file = fopen (file_name, "r");
00143   TEST (!file, "unable to open file %s", file_name);
00144   fscanf (file, "%u", &nval);
00145   all_cn = EGsMalloc (EGeHeapCn_t, nval);
00146   EGeHeapResize (&my_heap, nval);
00147   rval = EGeHeapCheck (&my_heap);
00148   CHECKRVALG (rval, CLEANUP);
00149   IFMESSAGE (1, "Inserting %u elements into the heap", nval);
00150   for (i = 0; i < nval; i++)
00151   {
00152     EGeHeapCnInit (all_cn + i);
00153     fscanf (file, "%s", str1);
00154     EGlpNumReadStr (all_cn[i].val, str1);
00155     IFMESSAGE (1, "Adding value (%s,%lg) to the heap", str1,
00156              EGlpNumToLf (all_cn[i].val));
00157     rval = EGeHeapAdd (&my_heap, all_cn + i);
00158     CHECKRVALG (rval, CLEANUP);
00159     rval = EGeHeapCheck (&my_heap);
00160     CHECKRVALG (rval, CLEANUP);
00161   }
00162   fclose (file);
00163 
00164   /* Check if change value is in range */
00165   TESTG (c != UINT_MAX && c >= nval, CLEANUP,
00166          "Change item (%u) is out of range (only %u objects)", c, nval);
00167 
00168   /* Popping the values from the heap */
00169   fprintf (stderr, "\nRemoving:\n\n");
00170   for (i = 0; i < nval; i++)
00171   {
00172     ccn = EGeHeapGetMin (&my_heap);
00173     IFMESSAGE (1, "%u: item %zd : %lg", i, ccn - all_cn,
00174              EGlpNumToLf (ccn->val));
00175     EGeHeapDel (&my_heap, ccn);
00176     rval = EGeHeapCheck (&my_heap);
00177     CHECKRVALG (rval, CLEANUP);
00178   }
00179 
00180   if (c == UINT_MAX)
00181     goto CLEANUP;
00182 
00183   /* Re-inserting the values into the heap */
00184   fprintf (stderr, "\nRe-Inserting.\n\n");
00185   for (i = 0; i < nval; i++)
00186   {
00187     rval = EGeHeapAdd (&my_heap, all_cn + i);
00188     CHECKRVALG (rval, CLEANUP);
00189     rval = EGeHeapCheck (&my_heap);
00190     CHECKRVALG (rval, CLEANUP);
00191   }
00192 
00193   /* Changing value of an item */
00194   fprintf (stderr, "Changing value of item %u from %lf to %lf.\n", c,
00195            EGlpNumToLf (all_cn[c].val), EGlpNumToLf (v));
00196   rval = EGeHeapChangeVal (&my_heap, all_cn + c, v);
00197   CHECKRVALG (rval, CLEANUP);
00198   rval = EGeHeapCheck (&my_heap);
00199   CHECKRVALG (rval, CLEANUP);
00200 
00201   /* Popping the values from the heap */
00202   fprintf (stderr, "\nRemoving:\n\n");
00203   for (i = 0; i < nval; i++)
00204   {
00205     //ccn = EGeHeapGetMin (&my_heap);
00206     ccn = my_heap.cn[my_heap.sz-1];
00207     IFMESSAGE (1, "%u: item %zd : %lf", i, ccn - all_cn,
00208              EGlpNumToLf (ccn->val));
00209     EGeHeapDel (&my_heap, ccn);
00210     rval = EGeHeapCheck (&my_heap);
00211     CHECKRVALG (rval, CLEANUP);
00212   }
00213 
00214   /* Liberating allocated memory */
00215 CLEANUP:
00216   if (all_cn) EGfree (all_cn);
00217   EGeHeapClear (&my_heap);
00218   EGlpNumClearVar (v);
00219   EGlpNumClear();
00220   return rval;
00221 }
00222 
00223 /* ========================================================================= */
00224 /** @} */