2 * svrt is the ``Synthetic Visual Reasoning Test'', an image
3 * generator for evaluating classification performance of machine
4 * learning systems, humans and primates.
6 * Copyright (c) 2009 Idiap Research Institute, http://www.idiap.ch/
7 * Written by Francois Fleuret <francois.fleuret@idiap.ch>
9 * This file is part of svrt.
11 * svrt is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License version 3 as
13 * published by the Free Software Foundation.
15 * svrt is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with selector. If not, see <http://www.gnu.org/licenses/>.
25 #include "fusion_sort.h"
28 inline void indexed_fusion(int na, int *ia, int nb, int *ib, int *ic, scalar_t *values) {
29 int *ma = ia + na, *mb = ib + nb;
30 while(ia < ma && ib < mb)
31 if(values[*ia] <= values[*ib]) *(ic++) = *(ia++);
32 else *(ic++) = *(ib++);
33 while(ia < ma) *(ic++) = *(ia++);
34 while(ib < mb) *(ic++) = *(ib++);
37 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
39 if(n == 1) result[0] = from[0];
42 indexed_fusion_sort(k, from, result, values);
43 indexed_fusion_sort(n - k, from + k, result + k, values);
44 memcpy((void *) from, (void *) result, n * sizeof(int));
45 indexed_fusion(k, from, n - k, from + k, result, values);
49 // Sorting in decreasing order
51 inline void indexed_fusion_dec(int na, int *ia,
53 int *ic, scalar_t *values) {
54 int *ma = ia + na, *mb = ib + nb;
55 while(ia < ma && ib < mb)
56 if(values[*ia] > values[*ib]) *(ic++) = *(ia++);
57 else *(ic++) = *(ib++);
58 while(ia < ma) *(ic++) = *(ia++);
59 while(ib < mb) *(ic++) = *(ib++);
62 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
64 if(n == 1) result[0] = from[0];
67 indexed_fusion_dec_sort(k, from, result, values);
68 indexed_fusion_dec_sort(n - k, from + k, result + k, values);
69 memcpy((void *) from, (void *) result, n * sizeof(int));
70 indexed_fusion_dec(k, from, n - k, from + k, result, values);
74 void fusion_two_cells(int n1, scalar_t *cell1, int n2, scalar_t *cell2, scalar_t *result) {
75 scalar_t *max1 = cell1 + n1, *max2 = cell2 + n2;
76 while(cell1 < max1 && cell2 < max2) {
77 if(*(cell1) <= *(cell2)) *(result++) = *(cell1++);
78 else *(result++) = *(cell2++);
80 while(cell1 < max1) *(result++) = *(cell1++);
81 while(cell2 < max2) *(result++) = *(cell2++);
84 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
86 fusion_sort(n/2, from, result);
87 fusion_sort(n - n/2, from + n/2, result + n/2);
88 memcpy(from, result, sizeof(scalar_t) * n);
89 fusion_two_cells(n/2, from, n - n/2, from + n/2, result);
90 } else result[0] = from[0];