2 ///////////////////////////////////////////////////////////////////////////
3 // This program is free software: you can redistribute it and/or modify //
4 // it under the terms of the version 3 of the GNU General Public License //
5 // as published by the Free Software Foundation. //
7 // This program is distributed in the hope that it will be useful, but //
8 // WITHOUT ANY WARRANTY; without even the implied warranty of //
9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU //
10 // General Public License for more details. //
12 // You should have received a copy of the GNU General Public License //
13 // along with this program. If not, see <http://www.gnu.org/licenses/>. //
15 // Written by Francois Fleuret //
16 // (C) Idiap Research Institute //
18 // Contact <francois.fleuret@idiap.ch> for comments & bug reports //
19 ///////////////////////////////////////////////////////////////////////////
21 #include "fusion_sort.h"
24 inline void indexed_fusion(int na, int *ia, int nb, int *ib, int *ic, scalar_t *values) {
25 int *ma = ia + na, *mb = ib + nb;
26 while(ia < ma && ib < mb)
27 if(values[*ia] <= values[*ib]) *(ic++) = *(ia++);
28 else *(ic++) = *(ib++);
29 while(ia < ma) *(ic++) = *(ia++);
30 while(ib < mb) *(ic++) = *(ib++);
33 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
35 if(n == 1) result[0] = from[0];
38 indexed_fusion_sort(k, from, result, values);
39 indexed_fusion_sort(n - k, from + k, result + k, values);
40 memcpy((void *) from, (void *) result, n * sizeof(int));
41 indexed_fusion(k, from, n - k, from + k, result, values);
45 // Sorting in decreasing order
47 inline void indexed_fusion_dec(int na, int *ia,
49 int *ic, scalar_t *values) {
50 int *ma = ia + na, *mb = ib + nb;
51 while(ia < ma && ib < mb)
52 if(values[*ia] > values[*ib]) *(ic++) = *(ia++);
53 else *(ic++) = *(ib++);
54 while(ia < ma) *(ic++) = *(ia++);
55 while(ib < mb) *(ic++) = *(ib++);
58 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
60 if(n == 1) result[0] = from[0];
63 indexed_fusion_dec_sort(k, from, result, values);
64 indexed_fusion_dec_sort(n - k, from + k, result + k, values);
65 memcpy((void *) from, (void *) result, n * sizeof(int));
66 indexed_fusion_dec(k, from, n - k, from + k, result, values);
70 void fusion_two_cells(int n1, scalar_t *cell1, int n2, scalar_t *cell2, scalar_t *result) {
71 scalar_t *max1 = cell1 + n1, *max2 = cell2 + n2;
72 while(cell1 < max1 && cell2 < max2) {
73 if(*(cell1) <= *(cell2)) *(result++) = *(cell1++);
74 else *(result++) = *(cell2++);
76 while(cell1 < max1) *(result++) = *(cell1++);
77 while(cell2 < max2) *(result++) = *(cell2++);
80 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
82 fusion_sort(n/2, from, result);
83 fusion_sort(n - n/2, from + n/2, result + n/2);
84 memcpy(from, result, sizeof(scalar_t) * n);
85 fusion_two_cells(n/2, from, n - n/2, from + n/2, result);
86 } else result[0] = from[0];