~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina5/tina-libs/tina/sys/sysLst_sort.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  * 
  3  * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
  4  * University of Manchester, UK.  All rights reserved.
  5  * 
  6  * Redistribution and use in source and binary forms, with or without modification, 
  7  * are permitted provided that the following conditions are met:
  8  * 
  9  *   . Redistributions of source code must retain the above copyright notice, 
 10  *     this list of conditions and the following disclaimer.
 11  *    
 12  *   . Redistributions in binary form must reproduce the above copyright notice,
 13  *     this list of conditions and the following disclaimer in the documentation 
 14  *     and/or other materials provided with the distribution.
 15  * 
 16  *   . Neither the name of the University of Manchester nor the names of its
 17  *     contributors may be used to endorse or promote products derived from this 
 18  *     software without specific prior written permission.
 19  * 
 20  * 
 21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 31  * POSSIBILITY OF SUCH DAMAGE.
 32  *
 33  **********
 34  * 
 35  * Program :    TINA
 36  * File    :  $Source: /home/tina/cvs/tina-libs/tina/sys/sysLst_sort.c,v $
 37  * Date    :  $Date: 2003/09/22 16:09:02 $
 38  * Version :  $Revision: 1.5 $
 39  * CVS Id  :  $Id: sysLst_sort.c,v 1.5 2003/09/22 16:09:02 tony Exp $
 40  */
 41 /**
 42  * @file List sorting (generic)
 43  * @brief List based sorting algorithms outperform all forms of array based sorting.
 44  * The functions here support simple sorting and sorting with user defined functions
 45  * and data.
 46  *
 47  *********
 48 */
 49 
 50 #include "sysLst_sort.h"
 51 
 52 #if HAVE_CONFIG_H
 53   #include <config.h>
 54 #endif
 55 
 56 #include <stdio.h>
 57 #include <tina/sys/sys_LstDef.h>
 58 #include <tina/sys/sysMem_ralloc.h>
 59 #include <tina/sys/sysLst_list.h>
 60 
 61 
 62 /* key sorting algorithm */
 63 
 64 void sort_keys_simple(int *key, float *val, int n)
 65 {
 66         int i, j;
 67         int nm1 = n - 1;
 68 
 69         for (i = 0; i < n; ++i)                         /* initialise keys */
 70                 key[i] = i;
 71 
 72         for (i = 0; i < nm1; ++i)
 73         {
 74                 float minval = val[key[i]];
 75                 int minkey = i;
 76 
 77                 for (j = i + 1; j < n; ++j)
 78                         if (val[key[j]] < minval)
 79                         {
 80                                 minkey = j;
 81                                 minval = val[key[j]];
 82                         }
 83                 if (minkey != i)
 84                 {
 85                         int temp = key[i];
 86 
 87                         key[i] = key[minkey];
 88                         key[minkey] = temp;
 89                 }
 90         }
 91 }
 92 
 93 List *sort_list(List * list, double (*valfunc) ( /* ??? */ ), void *data)
 94 {
 95         int i, n;
 96         float *val;
 97         int *key;
 98         List **listel;
 99         List *lptr;
100         List *sorted;
101 
102         if (list == NULL)
103                 return (NULL);
104 
105         for (lptr = list, n = 0; lptr != NULL; lptr = lptr->next)
106                 ++n;
107 
108         val = (float *) ralloc((unsigned) n * sizeof(float));
109         key = (int *) ralloc((unsigned) n * sizeof(int));
110         listel = (List **) ralloc((unsigned) n * sizeof(List *));
111 
112         for (i = 0, lptr = list; i < n; ++i, lptr = lptr->next)
113         {
114                 val[i] = (float) valfunc(lptr->to, lptr->type, data);
115                 listel[i] = lptr;
116         }
117 
118         sort_keys_simple(key, val, n);
119 
120         sorted = NULL;
121         for (i = n - 1; i >= 0; --i)
122                 sorted = link_addtostart(sorted, listel[key[i]]);
123 
124         rfree((void *) val);
125         rfree((void *) key);
126         rfree((void *) listel);
127         return (sorted);
128 }
129 
130 List *sort_ddlist(List * list, double (*valfunc) ( /* ??? */ ), void *data)
131 {
132         int i, n;
133         float *val;
134         int *key;
135         List **listel;
136         List *lptr;
137         List *sorted;
138         List *dd_link_addtostart();
139 
140         if (list == NULL)
141                 return (NULL);
142 
143         for (lptr = list, n = 0; lptr != NULL; lptr = lptr->next)
144                 ++n;
145 
146         val = (float *) ralloc((unsigned) n * sizeof(float));
147         key = (int *) ralloc((unsigned) n * sizeof(int));
148         listel = (List **) ralloc((unsigned) n * sizeof(List *));
149 
150         for (i = 0, lptr = list; i < n; ++i, lptr = lptr->next)
151         {
152                 val[i] = (float) valfunc(lptr->to, lptr->type, data);
153                 listel[i] = lptr;
154         }
155 
156         sort_keys_simple(key, val, n);
157 
158         sorted = NULL;
159         for (i = n - 1; i >= 0; --i)
160                 sorted = dd_link_addtostart(sorted, listel[key[i]]);
161 
162         rfree((void *) val);
163         rfree((void *) key);
164         rfree((void *) listel);
165         return (sorted);
166 }
167 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.