2 * folded-ctf is an implementation of the folded hierarchy of
3 * classifiers for object detection, developed by Francois Fleuret
6 * Copyright (c) 2008 Idiap Research Institute, http://www.idiap.ch/
7 * Written by Francois Fleuret <francois.fleuret@idiap.ch>
9 * This file is part of folded-ctf.
11 * folded-ctf is free software: you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published
13 * by the Free Software Foundation, either version 3 of the License,
14 * or (at your option) any later version.
16 * folded-ctf is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
21 * You should have received a copy of the GNU General Public License
22 * along with folded-ctf. If not, see <http://www.gnu.org/licenses/>.
26 #include "fusion_sort.h"
29 inline void indexed_fusion(int na, int *ia, int nb, int *ib, int *ic, scalar_t *values) {
30 int *ma = ia + na, *mb = ib + nb;
31 while(ia < ma && ib < mb)
32 if(values[*ia] <= values[*ib]) *(ic++) = *(ia++);
33 else *(ic++) = *(ib++);
34 while(ia < ma) *(ic++) = *(ia++);
35 while(ib < mb) *(ic++) = *(ib++);
38 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
40 if(n == 1) result[0] = from[0];
43 indexed_fusion_sort(k, from, result, values);
44 indexed_fusion_sort(n - k, from + k, result + k, values);
45 memcpy((void *) from, (void *) result, n * sizeof(int));
46 indexed_fusion(k, from, n - k, from + k, result, values);
50 // Sorting in decreasing order
52 inline void indexed_fusion_dec(int na, int *ia,
54 int *ic, scalar_t *values) {
55 int *ma = ia + na, *mb = ib + nb;
56 while(ia < ma && ib < mb)
57 if(values[*ia] > values[*ib]) *(ic++) = *(ia++);
58 else *(ic++) = *(ib++);
59 while(ia < ma) *(ic++) = *(ia++);
60 while(ib < mb) *(ic++) = *(ib++);
63 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
65 if(n == 1) result[0] = from[0];
68 indexed_fusion_dec_sort(k, from, result, values);
69 indexed_fusion_dec_sort(n - k, from + k, result + k, values);
70 memcpy((void *) from, (void *) result, n * sizeof(int));
71 indexed_fusion_dec(k, from, n - k, from + k, result, values);
75 void fusion_two_cells(int n1, scalar_t *cell1, int n2, scalar_t *cell2, scalar_t *result) {
76 scalar_t *max1 = cell1 + n1, *max2 = cell2 + n2;
77 while(cell1 < max1 && cell2 < max2) {
78 if(*(cell1) <= *(cell2)) *(result++) = *(cell1++);
79 else *(result++) = *(cell2++);
81 while(cell1 < max1) *(result++) = *(cell1++);
82 while(cell2 < max2) *(result++) = *(cell2++);
85 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
87 fusion_sort(n/2, from, result);
88 fusion_sort(n - n/2, from + n/2, result + n/2);
89 memcpy(from, result, sizeof(scalar_t) * n);
90 fusion_two_cells(n/2, from, n - n/2, from + n/2, result);
91 } else result[0] = from[0];