GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/mindtct/sort.c
Date: 2024-09-16 14:36:32
Exec Total Coverage
Lines: 73 73 100.0%
Functions: 5 5 100.0%
Branches: 26 26 100.0%
Line Branch Exec Source
1 /*******************************************************************************
2
3 License:
4 This software and/or related materials was developed at the National Institute
5 of Standards and Technology (NIST) by employees of the Federal Government
6 in the course of their official duties. Pursuant to title 17 Section 105
7 of the United States Code, this software is not subject to copyright
8 protection and is in the public domain.
9
10 This software and/or related materials have been determined to be not subject
11 to the EAR (see Part 734.3 of the EAR for exact details) because it is
12 a publicly available technology and software, and is freely distributed
13 to any interested party with no licensing requirements. Therefore, it is
14 permissible to distribute this software as a free download from the internet.
15
16 Disclaimer:
17 This software and/or related materials was developed to promote biometric
18 standards and biometric technology testing for the Federal Government
19 in accordance with the USA PATRIOT Act and the Enhanced Border Security
20 and Visa Entry Reform Act. Specific hardware and software products identified
21 in this software were used in order to perform the software development.
22 In no case does such identification imply recommendation or endorsement
23 by the National Institute of Standards and Technology, nor does it imply that
24 the products and equipment identified are necessarily the best available
25 for the purpose.
26
27 This software and/or related materials are provided "AS-IS" without warranty
28 of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
29 NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
30 or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
31 licensed product, however used. In no event shall NIST be liable for any
32 damages and/or costs, including but not limited to incidental or consequential
33 damages of any kind, including economic damage or injury to property and lost
34 profits, regardless of whether NIST shall be advised, have reason to know,
35 or in fact shall know of the possibility.
36
37 By using this software, you agree to bear all risk relating to quality,
38 use and performance of the software and/or related materials. You agree
39 to hold the Government harmless from any claim arising from your use
40 of the software.
41
42 *******************************************************************************/
43
44
45 /***********************************************************************
46 LIBRARY: LFS - NIST Latent Fingerprint System
47
48 FILE: SORT.C
49 AUTHOR: Michael D. Garris
50 DATE: 03/16/1999
51 UPDATED: 03/16/2005 by MDG
52
53 Contains sorting routines required by the NIST Latent Fingerprint
54 System (LFS).
55
56 ***********************************************************************
57 ROUTINES:
58 sort_indices_int_inc()
59 sort_indices_double_inc()
60 bubble_sort_int_inc_2()
61 bubble_sort_double_inc_2()
62 bubble_sort_double_dec_2()
63 bubble_sort_int_inc()
64 ***********************************************************************/
65
66 #include <stdio.h>
67 #include <lfs.h>
68
69 /*************************************************************************
70 **************************************************************************
71 #cat: sort_indices_int_inc - Takes a list of integers and returns a list of
72 #cat: indices referencing the integer list in increasing order.
73 #cat: The original list of integers is also returned in sorted
74 #cat: order.
75
76 Input:
77 ranks - list of integers to be sorted
78 num - number of integers in the list
79 Output:
80 optr - list of indices referencing the integer list in sorted order
81 ranks - list of integers in increasing order
82 Return Code:
83 Zero - successful completion
84 Negative - system error
85 **************************************************************************/
86 96 int sort_indices_int_inc(int **optr, int *ranks, const int num)
87 {
88 96 int *order;
89 96 int i;
90
91 /* Allocate list of sequential indices. */
92 96 order = (int *)g_malloc(num * sizeof(int));
93 /* Initialize list of sequential indices. */
94
2/2
✓ Branch 1 taken 35205 times.
✓ Branch 2 taken 96 times.
 35397 for(i = 0; i < num; i++)
95 35205 order[i] = i;
96
97 /* Sort the indecies into rank order. */
98 96 bubble_sort_int_inc_2(ranks, order, num);
99
100 /* Set output pointer to the resulting order of sorted indices. */
101 96 *optr = order;
102 /* Return normally. */
103 96 return(0);
104 }
105
106 /*************************************************************************
107 **************************************************************************
108 #cat: sort_indices_double_inc - Takes a list of doubles and returns a list of
109 #cat: indices referencing the double list in increasing order.
110 #cat: The original list of doubles is also returned in sorted
111 #cat: order.
112
113 Input:
114 ranks - list of doubles to be sorted
115 num - number of doubles in the list
116 Output:
117 optr - list of indices referencing the double list in sorted order
118 ranks - list of doubles in increasing order
119 Return Code:
120 Zero - successful completion
121 Negative - system error
122 **************************************************************************/
123
124 /*************************************************************************
125 **************************************************************************
126 #cat: bubble_sort_int_inc_2 - Takes a list of integer ranks and a corresponding
127 #cat: list of integer attributes, and sorts the ranks
128 #cat: into increasing order moving the attributes
129 #cat: correspondingly.
130
131 Input:
132 ranks - list of integers to be sort on
133 items - list of corresponding integer attributes
134 len - number of items in list
135 Output:
136 ranks - list of integers sorted in increasing order
137 items - list of attributes in corresponding sorted order
138 **************************************************************************/
139 96 void bubble_sort_int_inc_2(int *ranks, int *items, const int len)
140 {
141 96 int done = 0;
142 96 int i, p, n, trank, titem;
143
144 /* Set counter to the length of the list being sorted. */
145 96 n = len;
146
147 /* While swaps in order continue to occur from the */
148 /* previous iteration... */
149
2/2
✓ Branch 0 taken 32367 times.
✓ Branch 1 taken 96 times.
 32463 while(!done){
150 /* Reset the done flag to TRUE. */
151 done = TRUE;
152 /* Foreach rank in list up to current end index... */
153 /* ("p" points to current rank and "i" points to the next rank.) */
154
2/2
✓ Branch 0 taken 11929103 times.
✓ Branch 1 taken 32367 times.
 11961470 for (i=1, p = 0; i<n; i++, p++){
155 /* If previous rank is < current rank ... */
156
2/2
✓ Branch 0 taken 4241842 times.
✓ Branch 1 taken 7687261 times.
 11929103 if(ranks[p] > ranks[i]){
157 /* Swap ranks. */
158 4241842 trank = ranks[i];
159 4241842 ranks[i] = ranks[p];
160 4241842 ranks[p] = trank;
161 /* Swap items. */
162 4241842 titem = items[i];
163 4241842 items[i] = items[p];
164 4241842 items[p] = titem;
165 /* Changes were made, so set done flag to FALSE. */
166 4241842 done = FALSE;
167 }
168 /* Otherwise, rank pair is in order, so continue. */
169 }
170 /* Decrement the ending index. */
171 32367 n--;
172 }
173 96 }
174
175 /*************************************************************************
176 **************************************************************************
177 #cat: bubble_sort_double_inc_2 - Takes a list of double ranks and a
178 #cat: corresponding list of integer attributes, and sorts the
179 #cat: ranks into increasing order moving the attributes
180 #cat: correspondingly.
181
182 Input:
183 ranks - list of double to be sort on
184 items - list of corresponding integer attributes
185 len - number of items in list
186 Output:
187 ranks - list of doubles sorted in increasing order
188 items - list of attributes in corresponding sorted order
189 **************************************************************************/
190 3447 void bubble_sort_double_inc_2(double *ranks, int *items, const int len)
191 {
192 3447 int done = 0;
193 3447 int i, p, n, titem;
194 3447 double trank;
195
196 /* Set counter to the length of the list being sorted. */
197 3447 n = len;
198
199 /* While swaps in order continue to occur from the */
200 /* previous iteration... */
201
2/2
✓ Branch 0 taken 12003 times.
✓ Branch 1 taken 3447 times.
 15450 while(!done){
202 /* Reset the done flag to TRUE. */
203 done = TRUE;
204 /* Foreach rank in list up to current end index... */
205 /* ("p" points to current rank and "i" points to the next rank.) */
206
2/2
✓ Branch 0 taken 30567 times.
✓ Branch 1 taken 12003 times.
 42570 for (i=1, p = 0; i<n; i++, p++){
207 /* If previous rank is < current rank ... */
208
2/2
✓ Branch 0 taken 16577 times.
✓ Branch 1 taken 13990 times.
 30567 if(ranks[p] > ranks[i]){
209 /* Swap ranks. */
210 16577 trank = ranks[i];
211 16577 ranks[i] = ranks[p];
212 16577 ranks[p] = trank;
213 /* Swap items. */
214 16577 titem = items[i];
215 16577 items[i] = items[p];
216 16577 items[p] = titem;
217 /* Changes were made, so set done flag to FALSE. */
218 16577 done = FALSE;
219 }
220 /* Otherwise, rank pair is in order, so continue. */
221 }
222 /* Decrement the ending index. */
223 12003 n--;
224 }
225 3447 }
226
227 /***************************************************************************
228 **************************************************************************
229 #cat: bubble_sort_double_dec_2 - Conducts a simple bubble sort returning a list
230 #cat: of ranks in decreasing order and their associated items in sorted
231 #cat: order as well.
232
233 Input:
234 ranks - list of values to be sorted
235 items - list of items, each corresponding to a particular rank value
236 len - length of the lists to be sorted
237 Output:
238 ranks - list of values sorted in descending order
239 items - list of items in the corresponding sorted order of the ranks.
240 If these items are indices, upon return, they may be used as
241 indirect addresses reflecting the sorted order of the ranks.
242 ****************************************************************************/
243 46139 void bubble_sort_double_dec_2(double *ranks, int *items, const int len)
244 {
245 46139 int done = 0;
246 46139 int i, p, n, titem;
247 46139 double trank;
248
249 46139 n = len;
250
2/2
✓ Branch 0 taken 103239 times.
✓ Branch 1 taken 46139 times.
 149378 while(!done){
251 done = 1;
252
2/2
✓ Branch 0 taken 127873 times.
✓ Branch 1 taken 103239 times.
 231112 for (i=1, p = 0;i<n;i++, p++){
253 /* If previous rank is < current rank ... */
254
2/2
✓ Branch 0 taken 71472 times.
✓ Branch 1 taken 56401 times.
 127873 if(ranks[p] < ranks[i]){
255 /* Swap ranks */
256 71472 trank = ranks[i];
257 71472 ranks[i] = ranks[p];
258 71472 ranks[p] = trank;
259 /* Swap corresponding items */
260 71472 titem = items[i];
261 71472 items[i] = items[p];
262 71472 items[p] = titem;
263 71472 done = 0;
264 }
265 }
266 103239 n--;
267 }
268 46139 }
269
270 /*************************************************************************
271 **************************************************************************
272 #cat: bubble_sort_int_inc - Takes a list of integers and sorts them into
273 #cat: increasing order using a simple bubble sort.
274
275 Input:
276 ranks - list of integers to be sort on
277 len - number of items in list
278 Output:
279 ranks - list of integers sorted in increasing order
280 **************************************************************************/
281 14050 void bubble_sort_int_inc(int *ranks, const int len)
282 {
283 14050 int done = 0;
284 14050 int i, p, n;
285 14050 int trank;
286
287 /* Set counter to the length of the list being sorted. */
288 14050 n = len;
289
290 /* While swaps in order continue to occur from the */
291 /* previous iteration... */
292
2/2
✓ Branch 0 taken 33424 times.
✓ Branch 1 taken 14050 times.
 47474 while(!done){
293 /* Reset the done flag to TRUE. */
294 done = TRUE;
295 /* Foreach rank in list up to current end index... */
296 /* ("p" points to current rank and "i" points to the next rank.) */
297
2/2
✓ Branch 0 taken 62271 times.
✓ Branch 1 taken 33424 times.
 95695 for (i=1, p = 0; i<n; i++, p++){
298 /* If previous rank is < current rank ... */
299
2/2
✓ Branch 0 taken 45314 times.
✓ Branch 1 taken 16957 times.
 62271 if(ranks[p] > ranks[i]){
300 /* Swap ranks. */
301 45314 trank = ranks[i];
302 45314 ranks[i] = ranks[p];
303 45314 ranks[p] = trank;
304 /* Changes were made, so set done flag to FALSE. */
305 45314 done = FALSE;
306 }
307 /* Otherwise, rank pair is in order, so continue. */
308 }
309 /* Decrement the ending index. */
310 33424 n--;
311 }
312 14050 }
313
314