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
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.