fusion_sort.cc

   1 /*
   2  *  folded-ctf is an implementation of the folded hierarchy of
   3  *  classifiers for object detection, developed by Francois Fleuret
   4  *  and Donald Geman.
   5  *
   6  *  Copyright (c) 2008 Idiap Research Institute, http://www.idiap.ch/
   7  *  Written by Francois Fleuret <francois.fleuret@idiap.ch>
   8  *
   9  *  This file is part of folded-ctf.
  10  *
  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.
  15  *
  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.
  20  *
  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/>.
  23  *
  24  */
  25
  26 #include "fusion_sort.h"
  27 #include <string.h>
  28
  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++);
  36 }
  37
  38 void indexed_fusion_sort(int n, int *from, int *result, scalar_t *values) {
  39   ASSERT(n > 0);
  40   if(n == 1) result[0] = from[0];
  41   else {
  42     int k = n/2;
  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);
  47   }
  48 }
  49
  50 // Sorting in decreasing order
  51
  52 inline void indexed_fusion_dec(int na, int *ia,
  53                            int nb, int *ib,
  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++);
  61 }
  62
  63 void indexed_fusion_dec_sort(int n, int *from, int *result, scalar_t *values) {
  64   ASSERT(n > 0);
  65   if(n == 1) result[0] = from[0];
  66   else {
  67     int k = n/2;
  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);
  72   }
  73 }
  74
  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++);
  80   }
  81   while(cell1 < max1) *(result++) = *(cell1++);
  82   while(cell2 < max2) *(result++) = *(cell2++);
  83 }
  84
  85 void fusion_sort(int n, scalar_t *from, scalar_t *result) {
  86   if(n > 1) {
  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];
  92 }