source: soft/giet_vm/applications/rosenfeld/nrc2/src/nrsort2.c @ 772

Last change on this file since 772 was 772, checked in by meunier, 8 years ago
  • Ajout de l'application rosenfeld
  • Changement du nom du flag O_CREATE en O_CREAT
File size: 16.1 KB
Line 
1/* ----------------- */
2/* --- nrsort2.c --- */
3/* ----------------- */
4
5/*
6 * Copyright (c) 2000-2014, Lionel Lacassagne, All rights reserved
7 * Univ Paris Sud XI, CNRS
8 *
9 * Distributed under the Boost Software License, Version 1.0
10 * see accompanying file LICENSE.txt or copy it at
11 * http://www.boost.org/LICENSE_1_0.txt
12 */
13
14
15#include <stdio.h>
16#include <stddef.h>
17#include <stdlib.h>
18#include <math.h> // fabs
19
20#include "mypredef.h"
21#include "nrtype.h"
22#include "nrdef.h"
23#include "nrmacro.h"
24#include "nrkernel.h"
25
26#include "nrset1.h"
27#include "nrset2.h"
28
29#include "nrsort1.h"
30#include "nrsort2.h"
31
32/* ------------------------------------------------------------------------------------------------------ */
33IMAGE_EXPORT(void) extractnz_boundaries_ui8matrix(uint8 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz)
34/* ------------------------------------------------------------------------------------------------------ */
35{
36    int i;
37    long a, b;
38    long left, right;
39   
40    extractnz_boundaries_ui8vector(m[nrl], ncl, nch, &left, &right); // premier intervalle
41    for(i=nrl+1; i<=nrh; i++) {
42        extractnz_boundaries_ui8vector(m[i], ncl, nch, &a, &b);
43        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
44        if(b > right) right = b;
45    }
46    *nclnz = left;
47    *nchnz = right;
48}
49/* ------------------------------------------------------------------------------------------------------- */
50IMAGE_EXPORT(void) extractnz_boundaries_si16matrix(sint16 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz)
51/* ------------------------------------------------------------------------------------------------------- */
52{
53    int i;
54    long a, b;
55    long left, right;
56   
57    extractnz_boundaries_si16vector(m[nrl], ncl, nch, &left, &right); // premier intervalle
58    for(i=nrl+1; i<=nrh; i++) {
59        extractnz_boundaries_si16vector(m[i], ncl, nch, &a, &b);
60        if(a < left)
61            left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
62        if(b > right)
63            right = b;
64    }
65    *nclnz = left;
66    *nchnz = right;
67}
68/* --------------------------------------------------------------------------------------------------------- */
69IMAGE_EXPORT(void) extractnz_boundaries_ui16matrix(uint16 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz)
70/* --------------------------------------------------------------------------------------------------------- */
71{
72    int i;
73    long a, b;
74    long left, right;
75   
76    extractnz_boundaries_ui16vector(m[nrl], ncl, nch, &left, &right); // premier intervalle
77    for(i=nrl+1; i<=nrh; i++) {
78        extractnz_boundaries_ui16vector(m[i], ncl, nch, &a, &b);
79        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
80        if(b > right) right = b;
81    }
82    *nclnz = left;
83    *nchnz = right;
84}
85/* ------------------------------------------------------------------------------------------------------ */
86IMAGE_EXPORT(void) extractnz_boundaries_si32matrix (sint32 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz)
87/* ------------------------------------------------------------------------------------------------------ */
88{
89    int i;
90    long a, b;
91    long left, right;
92   
93    extractnz_boundaries_si32vector(m[nrl], ncl, nch, &left, &right); // premier intervalle
94    for(i=nrl+1; i<=nrh; i++) {
95        extractnz_boundaries_si32vector(m[i], ncl, nch, &a, &b);
96        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
97        if(b > right) right = b;
98    }
99    *nclnz = left;
100    *nchnz = right;
101}
102/* ------------------------------------------------------------------------------------------------------- */
103IMAGE_EXPORT(void) extractnz_boundaries_ui32matrix(uint32 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz)
104/* ------------------------------------------------------------------------------------------------------- */
105{
106    int i;
107    long a, b;
108    long left, right;
109   
110    extractnz_boundaries_ui32vector(m[nrl], ncl, nch, &left, &right); // premier intervalle
111    for(i=nrl+1; i<=nrh; i++) {
112        extractnz_boundaries_ui32vector(m[i], ncl, nch, &a, &b);
113        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
114        if(b > right) right = b;
115    }
116    *nclnz = left;
117    *nchnz = right;
118}
119/* ----------------------------------------------------------------------------------------------------------------------- */
120IMAGE_EXPORT(void) extractnz_boundaries_f32matrix(float32 **m, long nrl,long nrh, long ncl, long nch, long *nclnz, long *nchnz, float32 epsillon)
121/* ----------------------------------------------------------------------------------------------------------------------- */
122{
123    int i;
124    long a, b;
125    long left, right;
126   
127    extractnz_boundaries_f32vector(m[nrl], ncl, nch, &left, &right, epsillon); // premier intervalle
128    for(i=nrl+1; i<=nrh; i++) {
129        extractnz_boundaries_f32vector(m[i], ncl, nch, &a, &b, epsillon);
130        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
131        if(b > right) right = b;
132    }
133    *nclnz = left;
134    *nchnz = right;
135}
136/* ------------------------------------------------------------------------------------------------------------------------- */
137IMAGE_EXPORT(void) extractnz_boundaries_f64matrix(float64 **m, long nrl,long nrh,long ncl, long nch, long *nclnz, long *nchnz, float64 epsillon)
138/* ------------------------------------------------------------------------------------------------------------------------- */
139{
140    int i;
141    long a, b;
142    long left, right;
143   
144    extractnz_boundaries_f64vector(m[nrl], ncl, nch, &left, &right, epsillon); // premier intervalle
145    for(i=nrl+1; i<=nrh; i++) {
146        extractnz_boundaries_f64vector(m[i], ncl, nch, &a, &b, epsillon);
147        if(a < left) left = a; // agrandissement de l'intervalle SI necessaire (et non le contraire)
148        if(b > right) right = b;
149    }
150    *nclnz = left;
151    *nchnz = right;
152}
153/* --------------------------------------------------------------- */
154IMAGE_EXPORT(void) sort_si32matrix_selection2(sint32 **m, long nl, long nh)
155/* --------------------------------------------------------------- */
156/*
157* sort an matrix of int with the selection algorithm
158* the key is supposed to be in row 1
159* the flag associated, in row 0
160*/
161{
162        int i, j;
163        sint32 x, min, pos, tmp;
164       
165        //display_imatrix(m, 0, 1, nl, nh, "%10d", "Before");
166       
167        for(i=nl; i<nh; i++) {
168                min = m[1][i];
169                pos = i;
170                for(j=i+1; j<=nh; j++) {
171                        x = m[1][j];
172                        if(x < min) {
173                                min = x;
174                                pos = j;
175                        }
176                }
177                m[1][pos] = m[1][i];
178                m[1][i]   = min;
179               
180                tmp       = m[0][i];
181                m[0][i]   = m[0][pos];
182                m[0][pos] = tmp;
183        }
184        //display_imatrix(m, 0, 1, nl, nh, "%10d", "After");
185}
186/* ---------------------------------------------------------------------------------- */
187IMAGE_EXPORT(void) sort_si32matrix_leftpart_selection2(sint32 **m, long nl, long nh, long len)
188/* ---------------------------------------------------------------------------------- */
189/*
190* sort an matrix of int with the selection algorithm
191* the key is supposed to be in row 1
192* the flag associated, in row 0
193* the sort is performed only on the len first items
194* for selecting the len first smallest values (for Tracking algo)
195*/
196{
197        int i, j;
198        sint32 x, min, pos, tmp;
199        long ih = nl + len - 1;
200        int *X, *F;
201       
202        //display_imatrix(m, 0, 1, nl, nh, "%10d", "Before");
203       
204        F = m[0];
205        X = m[1];
206       
207       
208        for(i=nl; i<=ih; i++) {
209                min = X[i];
210                pos = i;
211                for(j=i+1; j<=nh; j++) {
212                        x = X[j];
213                        if(x < min) {
214                                min = x;
215                                pos = j;
216                        }
217                }
218                X[pos] = X[i];
219                X[i]   = min;
220               
221                tmp    = F[i];
222                F[i]   = F[pos];
223                F[pos] = tmp;
224        }
225}
226/* ---------------------------------------------------------------- */
227IMAGE_EXPORT(void) sort_f64matrix_selection(float64 *m, long nl, long nh)
228/* ---------------------------------------------------------------- */
229{
230        int i, j, pos;
231        float64 x, min;
232       
233        for(i=nl; i<nh; i++) {
234                min = m[i];
235                pos = i;
236                for(j=i+1; j<=nh; j++) {
237                        x = m[j];
238                        if(x < min) {
239                                min = x;
240                                pos = j;
241                        }
242                }
243                m[pos] = m[i];
244                m[i]   = min;
245        }
246}
247/* ----------------------------------------------------------------------------------------------- */
248IMAGE_EXPORT(void) sort_si32matrix_selection(sint32 **m, long nrl, long nrh, long ncl, long nch, long nrow)
249/* ----------------------------------------------------------------------------------------------- */
250/*
251* sort an matrix of int with the selection algorithm
252* the key is supposed to be in row nrow
253*/
254{
255        int i, j, k;
256        sint32 x, min, pos, tmp;
257       
258        //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
259        for(i=ncl; i<nch; i++) {
260                min = m[nrow][i];
261                pos = i;
262                for(j=i+1; j<=nch; j++) {
263                        x = m[nrow][j];
264                        if(x < min) {
265                                min = x;
266                                pos = j;
267                        }
268                }
269               
270                // big swap
271                for(k=nrl; k<=nrh; k++) {
272                        tmp = m[k][i];
273                        m[k][i] = m[k][pos];
274                        m[k][pos] = tmp;
275                } // k
276                //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
277               
278        } // i
279}   
280/* -------------------------------------------------------------------------------------------------- */
281IMAGE_EXPORT(void) sortv_si32matrix_selection_min(sint32 **m, long nrl, long nrh, long ncl, long nch, long nc)
282/* -------------------------------------------------------------------------------------------------- */
283{
284/*
285* sort an matrix of int, with the selection algorithm.
286* the key is in column nc
287* the sort is performed, by doing a purmutation on the lines,
288* instead of copying the lines.
289        */
290        int i, j;
291       
292        sint32 x, min, pos;
293        sint32 *ptr;
294       
295        //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
296        for(i=nrl; i<nrh; i++) {
297                min = m[i][nc];
298                pos = i;
299                for(j=i+1; j<=nrh; j++) {
300                        x = m[j][nc];
301                        if(x < min) {
302                                min = x;
303                                pos = j;
304                        }
305                } // j
306               
307                /* permutation des pointeurs de ligne de la matrice */
308                ptr    = m[i];
309                m[i]   = m[pos];
310                m[pos] = ptr;
311               
312        } // i
313}
314/* ---------------------------------------------------------------------------------------------------------- */
315IMAGE_EXPORT(void) sortv_si32matrix_selection_kmin(sint32 **m, long nrl, long nrh, long ncl, long nch, long nc, int k)
316/* ---------------------------------------------------------------------------------------------------------- */
317{
318/*
319* sort an matrix of int, with the selection algorithm.
320* the key is in column nc
321* the sort is performed, by doing a purmutation on the lines,
322* instead of copying the lines.
323        */
324        int i, j;
325        int il = nrl;
326        int ih = nrl + k;
327       
328        sint32 x, min, pos;
329        sint32 *ptr;
330       
331        //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
332        for(i=il; i<ih; i++) {
333                min = m[i][nc];
334                pos = i;
335                for(j=i+1; j<=nrh; j++) {
336                        x = m[j][nc];
337                        if(x < min) {
338                                min = x;
339                                pos = j;
340                        }
341                } // j
342               
343                /* permutation des pointeurs de ligne de la matrice */
344                ptr    = m[i];
345                m[i]   = m[pos];
346                m[pos] = ptr;
347               
348        } // i
349}
350/* -------------------------------------------------------------------------------------------------- */
351IMAGE_EXPORT(void) sortv_si32matrix_selection_max(sint32 **m, long nrl, long nrh, long ncl, long nch, long nc)
352/* -------------------------------------------------------------------------------------------------- */
353{
354/*
355* sort an matrix of int, with the selection algorithm.
356* from max to min
357* the key is in column nc
358* the sort is performed, by doing a purmutation on the lines,
359* instead of copying the lines.
360        */
361        int i, j;
362       
363        sint32 x, max, pos;
364        sint32 *ptr;
365       
366        //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
367        for(i=nrl; i<nrh; i++) {
368                max = m[i][nc];
369                pos = i;
370                for(j=i+1; j<=nrh; j++) {
371                        x = m[j][nc];
372                        if(x > max) {
373                                max = x;
374                                pos = j;
375                        }
376                } // j
377               
378                /* permutation des pointeurs de ligne de la matrice */
379                ptr    = m[i];
380                m[i]   = m[pos];
381                m[pos] = ptr;
382               
383        } // i
384}
385/* ---------------------------------------------------------------------------------------------------------- */
386IMAGE_EXPORT(void) sortv_si32matrix_selection_kmax(sint32 **m, long nrl, long nrh, long ncl, long nch, long nc, sint32 k)
387/* ---------------------------------------------------------------------------------------------------------- */
388{
389/*
390* sort an matrix of int, with the selection algorithm.
391* from max to min
392* the key is in column nc
393* the sort is performed, by doing a purmutation on the lines,
394* instead of copying the lines.
395        */
396        int i, j;
397        //int il = nrl;
398        //int ik = nrl + k;
399       
400        sint32 x, max, pos;
401        sint32 *ptr;
402       
403        //display_imatrix(m, nrl, nrh, ncl, nch, "%10d", NULL);
404        for(i=nrl; i<nrh; i++) {
405                max = m[i][nc];
406                pos = i;
407                for(j=i+1; j<=nrh; j++) {
408                        x = m[j][nc];
409                        if(x > max) {
410                                max = x;
411                                pos = j;
412                        }
413                } // j
414               
415                /* permutation des pointeurs de ligne de la matrice */
416                ptr    = m[i];
417                m[i]   = m[pos];
418                m[pos] = ptr;
419               
420        } // i
421}
422
423/* ------------------------------------------------------------------------------------------------------------------- */
424IMAGE_EXPORT(void) sort_index_si32matrix_selection_kmin(sint32 **key, long nrl,long nrh,long ncl, long nch, sint32 **index, int k)
425/* ------------------------------------------------------------------------------------------------------------------- */
426{
427        int i;
428       
429        set_si32matrix_j(index, nrl,nrh, ncl,nch);
430       
431        for(i=nrl; i<=nrh; i++) {
432                //printf("-------------------- %d --------------------\n", i);
433                //display_ivector(key[i],   ncl, nch, "%4d", "key0");
434                //display_ivector(index[i], ncl, nch, "%4d", "index0");
435               
436                sort_index_ivector_selection_kmin(key[i], ncl, nch, index[i], k);
437               
438                //display_ivector(key[i],   ncl, nch, "%4d", "key1");
439                //display_ivector(index[i], ncl, nch, "%4d", "index1");
440               
441        }
442}
443/* ------------------------------------------------------------------------------------------------------------------- */
444IMAGE_EXPORT(void) sort_index_si32matrix_selection_kmax(sint32 **key, long nrl,long nrh,long ncl, long nch, sint32 **index, int k)
445/* ------------------------------------------------------------------------------------------------------------------- */
446{
447        int i;
448       
449        set_si32matrix_j(index, nrl,nrh, ncl,nch);
450       
451        for(i=nrl; i<=nrh; i++) {
452                //printf("-------------------- %d --------------------\n", i);
453                //display_ivector(key[i],   ncl, nch, "%4d", "key0\n");
454                //display_ivector(index[i], ncl, nch, "%4d", "index0\n");
455               
456                sort_index_ivector_selection_kmax(key[i], ncl, nch, index[i], k);
457               
458                //display_ivector(key[i],   ncl, nch, "%4d", "key1\n");
459                //display_ivector(index[i], ncl, nch, "%4d", "index1\n");
460        }
461}
462/* ------------------------------------------------------------------------------------------------------------------- */
463IMAGE_EXPORT(void) sortv_index_imatrix_selection_max(int **key, long nrl,long nrh,long ncl, long nch, int *index, int nc)
464/* ------------------------------------------------------------------------------------------------------------------- */
465{
466        int i, j, pos, tmp, il, ih;
467        int x, max;
468        int *ptr;
469       
470        il = nrl;
471        ih = nrh;
472       
473        for(i=il; i<=ih; i++) {
474                index[i] = i;
475        }/**/
476       
477        for(i=il; i<ih; i++) {
478                max = key[i][nc];
479                pos = i;
480                for(j=i+1; j<=nrh; j++) {
481                        x = key[j][nc];
482                        if(x > max) {
483                                max = x;
484                                pos = j;
485                        }
486                }
487                //printf("Max = %d, swap (%d, %d)\n", max, i, pos);
488                /* permutation des pointeurs de ligne de la matrice */
489                ptr      = key[i];
490                key[i]   = key[pos];
491                key[pos] = ptr;
492               
493                /* permutation des indices de l'index */
494                tmp        = index[i];
495                index[i]   = index[pos];
496                index[pos] = tmp;
497        }
498}
499/* ------------------------------------------------------------------------------------------------------------------- */
500IMAGE_EXPORT(void) sortv_index_imatrix_selection_min(int **key, long nrl,long nrh,long ncl, long nch, int *index, int nc)
501/* ------------------------------------------------------------------------------------------------------------------- */
502{
503        int i, j, pos, tmp, il, ih;
504        int x, min;
505        int *ptr;
506       
507        il = nrl;
508        ih = nrh;
509       
510        for(i=il; i<=ih; i++) {
511                index[i] = i;
512        }/**/
513       
514        for(i=il; i<ih; i++) {
515                min = key[i][nc];
516                pos = i;
517                for(j=i+1; j<=nrh; j++) {
518                        x = key[j][nc];
519                        if(x < min) {
520                                min = x;
521                                pos = j;
522                        }
523                }
524                //printf("Max = %d, swap (%d, %d)\n", max, i, pos);
525                /* permutation des pointeurs de ligne de la matrice */
526                ptr      = key[i];
527                key[i]   = key[pos];
528                key[pos] = ptr;
529               
530                /* permutation des indices de l'index */
531                tmp        = index[i];
532                index[i]   = index[pos];
533                index[pos] = tmp;
534        }
535}
Note: See TracBrowser for help on using the repository browser.