eg_ekheap.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
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 EGeKHeap */
00022 /** @addtogroup EGeKHeap */
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 EGeKHeap 
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 ekheap_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 /** @brief parse the input argumenbts for the program */
00057 int ekheap_parseargs (int argc,
00058                      char **argv,
00059                      unsigned int *d,
00060                      unsigned int *ch,
00061                      EGlpNum_t * v,
00062                      char **file_name)
00063 {
00064   int c;
00065   while ((c = getopt (argc, argv, "f:d:c:v:")) != EOF)
00066   {
00067     switch (c)
00068     {
00069     case 'f':
00070       *file_name = optarg;
00071       break;
00072     case 'd':
00073       *d = atoi (optarg);
00074       break;
00075     case 'c':
00076       *ch = atoi (optarg);
00077       break;
00078     case 'v':
00079       EGlpNumReadStr (*v, optarg);
00080       break;
00081     default:
00082       ekheap_usage (argv[0]);
00083       return 1;
00084     }
00085   }
00086   /* reporting the options */
00087   if (!*file_name)
00088   {
00089     ekheap_usage (argv[0]);
00090     return 1;
00091   }
00092   fprintf (stdout, "Parsed Options:\n");
00093   fprintf (stdout, "input         : %s\n", *file_name);
00094   fprintf (stdout, "d             : %u\n", *d);
00095   if (*ch != UINT_MAX)
00096   {
00097     fprintf (stdout, "c             : %u\n", *ch);
00098     fprintf (stdout, "v             : %lf\n", EGlpNumToLf (*v));
00099   }
00100   return 0;
00101 }
00102 
00103 /* ========================================================================= */
00104 /** @brief main function */
00105 int main (int argc,
00106           char **argv)
00107 {
00108 
00109   int rval = 0;
00110   unsigned int i,
00111     c = UINT_MAX,
00112     d = 2;
00113   char *file_name = 0,
00114     str1[1024], *argv1[128];
00115   int argc1;
00116   EGioFile_t *file = 0;
00117   unsigned int nval = 0;
00118   EGlpNum_t v[EG_EKHEAP_ENTRY];
00119   EGeKHeap_t my_heap;
00120   EGeKHeapCn_t *all_cn = 0,
00121    *ccn;
00122   EGlib_info();
00123   EGlib_version();
00124   EGlpNumStart();
00125   for( i = EG_EKHEAP_ENTRY ; i-- ; )
00126   {
00127     EGlpNumInitVar (v[i]);
00128     EGlpNumZero (v[i]);
00129   }
00130   EGeKHeapInit (&my_heap);
00131   /* set signal and limits */
00132   EGsigSet(rval,CLEANUP);
00133   EGsetLimits(3600.0,4294967295UL);
00134   rval = EGeKHeapCheck (&my_heap);
00135   CHECKRVALG (rval, CLEANUP);
00136 
00137   /* Parse command line input to get 'file name' and 'd'. */
00138   rval = ekheap_parseargs (argc, argv, &d, &c, v, &file_name);
00139   CHECKRVALG (rval, CLEANUP);
00140   EGeKHeapChangeD (&my_heap, d);
00141   rval = EGeKHeapCheck (&my_heap);
00142   CHECKRVALG (rval, CLEANUP);
00143 
00144   /* Read the objects to sort from the file */
00145   file = EGioOpen (file_name, "r");
00146   TEST (!file, "unable to open file %s", file_name);
00147   EGioGets(str1,1024,file);
00148   EGioNParse(str1,128," ","%#",&argc1,argv1);
00149   TESTG((rval=(argc1!=1)),CLEANUP,"Expected one token, found %d",argc1);
00150   nval = atoi(argv1[0]);
00151   all_cn = EGsMalloc (EGeKHeapCn_t, nval);
00152   EGeKHeapResize (&my_heap, nval);
00153   rval = EGeKHeapCheck (&my_heap);
00154   CHECKRVALG (rval, CLEANUP);
00155   MESSAGE (EG_EKHEAP_DEBUG, "Inserting %u elements into the heap", nval);
00156   for (i = 0; i < nval; i++)
00157   {
00158     EGeKHeapCnInit (all_cn + i);
00159     EGioGets(str1,1024,file);
00160     EGioNParse(str1,128," ","%#",&argc1,argv1);
00161     TESTG((rval=(argc1!=1)),CLEANUP,"Expected one token, found %d",argc1);
00162     EGlpNumReadStr (all_cn[i].val[0], argv1[0]);
00163     MESSAGE (EG_EKHEAP_DEBUG, "Adding value (%s,%lf) to the heap", str1,
00164              EGlpNumToLf (all_cn[i].val[0]));
00165     rval = EGeKHeapAdd (&my_heap, all_cn + i);
00166     CHECKRVALG (rval, CLEANUP);
00167     rval = EGeKHeapCheck (&my_heap);
00168     CHECKRVALG (rval, CLEANUP);
00169   }
00170   EGioClose (file);
00171   file = 0;
00172   /* Check if change value is in range */
00173   TESTG (c != UINT_MAX && c >= nval, CLEANUP,
00174          "Change item (%u) is out of range (only %u objects)", c, nval);
00175 
00176   /* Popping the values from the heap */
00177   fprintf (stderr, "\nRemoving:\n\n");
00178   for (i = 0; i < nval; i++)
00179   {
00180     ccn = EGeKHeapGetMin (&my_heap);
00181     MESSAGE (EG_EKHEAP_DEBUG, "%u: item %zd : %lf", i, ccn - all_cn,
00182              EGlpNumToLf (ccn->val[0]));
00183     EGeKHeapDel (&my_heap, ccn);
00184     rval = EGeKHeapCheck (&my_heap);
00185     CHECKRVALG (rval, CLEANUP);
00186   }
00187 
00188   if (c == UINT_MAX)
00189     goto CLEANUP;
00190 
00191   /* Re-inserting the values into the heap */
00192   fprintf (stderr, "\nRe-Inserting.\n\n");
00193   for (i = 0; i < nval; i++)
00194   {
00195     rval = EGeKHeapAdd (&my_heap, all_cn + i);
00196     CHECKRVALG (rval, CLEANUP);
00197     rval = EGeKHeapCheck (&my_heap);
00198     CHECKRVALG (rval, CLEANUP);
00199   }
00200 
00201   /* Changing value of an item */
00202   fprintf (stderr, "Changing value of item %u from %lf to %lf.\n", c,
00203            EGlpNumToLf (all_cn[c].val[0]), EGlpNumToLf (v[0]));
00204   rval = EGeKHeapChangeVal (&my_heap, all_cn + c, v);
00205   CHECKRVALG (rval, CLEANUP);
00206   rval = EGeKHeapCheck (&my_heap);
00207   CHECKRVALG (rval, CLEANUP);
00208 
00209   /* Popping the values from the heap */
00210   fprintf (stderr, "\nRemoving:\n\n");
00211   for (i = 0; i < nval; i++)
00212   {
00213     ccn = EGeKHeapGetMin (&my_heap);
00214     MESSAGE (EG_EKHEAP_DEBUG, "%u: item %zd : %lf", i, ccn - all_cn,
00215              EGlpNumToLf (ccn->val[0]));
00216     EGeKHeapDel (&my_heap, ccn);
00217     rval = EGeKHeapCheck (&my_heap);
00218     CHECKRVALG (rval, CLEANUP);
00219   }
00220 
00221   /* Liberating allocated memory */
00222 CLEANUP:
00223   if(file) EGioClose(file);
00224   if (all_cn)
00225   {
00226     for( i = nval ; i-- ; ) EGeKHeapCnClear(all_cn+i);
00227     EGfree (all_cn);
00228   }
00229   EGeKHeapClear (&my_heap);
00230   for( i = EG_EKHEAP_ENTRY ; i-- ; ) EGlpNumClearVar (v[i]);
00231   EGlpNumClear();
00232   return rval;
00233 }
00234 
00235 /* ========================================================================= */
00236 /** @} */