8.1
general documentation
cs_sort.h
Go to the documentation of this file.
1 #ifndef __CS_SORT_H__
2 #define __CS_SORT_H__
3 
4 /*============================================================================
5  * Functions related to in-place sorting of arrays.
6  *===========================================================================*/
7 
8 /*
9  This file is part of code_saturne, a general-purpose CFD tool.
10 
11  Copyright (C) 1998-2023 EDF S.A.
12 
13  This program is free software; you can redistribute it and/or modify it under
14  the terms of the GNU General Public License as published by the Free Software
15  Foundation; either version 2 of the License, or (at your option) any later
16  version.
17 
18  This program is distributed in the hope that it will be useful, but WITHOUT
19  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20  FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
21  details.
22 
23  You should have received a copy of the GNU General Public License along with
24  this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
25  Street, Fifth Floor, Boston, MA 02110-1301, USA.
26 */
27 
28 /*----------------------------------------------------------------------------*/
29 
30 #include "cs_defs.h"
31 
32 /*----------------------------------------------------------------------------
33  * Local headers
34  *---------------------------------------------------------------------------*/
35 
36 #include "cs_base.h"
37 
38 /*---------------------------------------------------------------------------*/
39 
41 
42 /*=============================================================================
43  * Macro definitions
44  *===========================================================================*/
45 
46 /*============================================================================
47  * Type definitions
48  *===========================================================================*/
49 
50 /*=============================================================================
51  * Static global variables
52  *===========================================================================*/
53 
54 /*=============================================================================
55  * Public function prototypes
56  *===========================================================================*/
57 
58 /*----------------------------------------------------------------------------
59  * Sort an array "a" between its left bound "l" and its right bound "r"
60  * thanks to a shell sort (Knuth algorithm).
61  * Index location of the sorted array are stored in loc. a is unchanged.
62  *
63  * parameters:
64  * l <-- left bound
65  * r <-- right bound
66  * a <-> array to sort (not modified)
67  * loc <-> position by increasing order (size = r-l)
68  *---------------------------------------------------------------------------*/
69 
70 void
72  cs_lnum_t r,
73  const cs_lnum_t a[],
74  cs_lnum_t loc[]);
75 
76 /*----------------------------------------------------------------------------
77  * Sort an array "a" between its left bound "l" and its right bound "r"
78  * thanks to a shell sort (Knuth algorithm).
79  *
80  * parameters:
81  * l <-- left bound
82  * r <-- right bound
83  * a <-> array to sort
84  *---------------------------------------------------------------------------*/
85 
86 void
88  cs_lnum_t r,
89  cs_lnum_t a[]);
90 
91 /*----------------------------------------------------------------------------
92  * Sort an array of integers "a" between its left bound "l" and its
93  * right bound "r" using a shell sort (Knuth algorithm).
94  *
95  * parameters:
96  * l <-- left bound
97  * r <-- right bound
98  * a <-> array to sort
99  *---------------------------------------------------------------------------*/
100 
101 void
103  cs_lnum_t r,
104  int a[]);
105 
106 /*----------------------------------------------------------------------------
107  * Sort a global array "a" between its left bound "l" and its right bound "r"
108  * thanks to a shell sort (Knuth algorithm).
109  *
110  * parameters:
111  * l <-- left bound
112  * r <-- right bound
113  * a <-> array to sort
114  *---------------------------------------------------------------------------*/
115 
116 void
118  cs_lnum_t r,
119  cs_gnum_t a[]);
120 
121 /*----------------------------------------------------------------------------
122  * Sort an array "a" and apply the sort to its associated array "b" (local
123  * numbering)
124  * Sort is realized thanks to a shell sort (Knuth algorithm).
125  *
126  * parameters:
127  * l --> left bound
128  * r --> right bound
129  * a <-> array to sort
130  * b <-> associated array
131  *---------------------------------------------------------------------------*/
132 
133 void
135  cs_lnum_t r,
136  cs_lnum_t a[],
137  cs_lnum_t b[]);
138 
139 /*----------------------------------------------------------------------------
140  * Sort an array "a" and apply the sort to its associated array "b" (local
141  * numbering)
142  * Sort is realized thanks to a shell sort (Knuth algorithm).
143  *
144  * parameters:
145  * l --> left bound
146  * r --> right bound
147  * a <-> array to sort
148  * b <-> associated array
149  *---------------------------------------------------------------------------*/
150 
151 void
153  int r,
154  int a[],
155  double b[]);
156 
157 /*----------------------------------------------------------------------------
158  * Sort an array "a" and apply the sort to its associated array "b" (local
159  * numbering)
160  * Sort is realized thanks to a shell sort (Knuth algorithm).
161  *
162  * parameters:
163  * l --> left bound
164  * r --> right bound
165  * a <-> array to sort
166  * b <-> associated array
167  *---------------------------------------------------------------------------*/
168 
169 void
171  int r,
172  cs_lnum_t a[],
173  short int b[]);
174 
175 /*----------------------------------------------------------------------------
176  * Sort an array "a" and apply the sort to its associated array "b" (local
177  * numbering)
178  * Sort is realized thanks to a shell sort (Knuth algorithm).
179  *
180  * parameters:
181  * l --> left bound
182  * r --> right bound
183  * a <-> array to sort
184  * b <-> associated array
185  *---------------------------------------------------------------------------*/
186 
187 void
189  cs_lnum_t r,
190  cs_gnum_t a[],
191  cs_gnum_t b[]);
192 
193 /*----------------------------------------------------------------------------
194  * Order an array of local numbers.
195  *
196  * parameters:
197  * number <-> array of numbers to sort
198  * n_elts <-- number of elements considered
199  *----------------------------------------------------------------------------*/
200 
201 void
202 cs_sort_lnum(cs_lnum_t number[],
203  size_t n_elts);
204 
205 /*----------------------------------------------------------------------------
206  * Sort rows of an indexed structure.
207  *
208  * parameters:
209  * n_elts <-- number of indexed elements
210  * elt_idx <-- element index (size: n_elts+1)
211  * elts <-> indexed values
212  *
213  * returns:
214  * true if no values were encountered multiple times in a given row
215  *---------------------------------------------------------------------------*/
216 
217 bool
219  const cs_lnum_t elt_idx[],
220  cs_lnum_t elts[]);
221 
222 /*----------------------------------------------------------------------------
223  * Sort rows of an indexed structure of global ids
224  *
225  * parameters:
226  * n_elts <-- number of indexed elements
227  * elt_idx <-- element index (size: n_elts+1)
228  * elts <-> indexed values
229  *
230  * returns:
231  * true if no values were encountered multiple times in a given row
232  *---------------------------------------------------------------------------*/
233 
234 bool
236  const cs_lnum_t elt_idx[],
237  cs_gnum_t elts[]);
238 
239 /*----------------------------------------------------------------------------
240  * Sort an array of global number and remove duplicate entries.
241  *
242  * The calling code may choose to reallocate the array to the new, compacted
243  * size; this is not done automatically, to avoid the overhead of memory
244  * management in cases where it is not useful (i.e. when the array is
245  * discarded soon after use).
246  *
247  * parameters:
248  * n_elts <-- initial number of elements
249  * elts <-> elements to sort
250  *
251  * returns:
252  * number of compacted elements
253  *---------------------------------------------------------------------------*/
254 
255 cs_lnum_t
257  cs_gnum_t elts[]);
258 
259 /*----------------------------------------------------------------------------
260  * Sort an array of global number couples and remove duplicate entries.
261  *
262  * Lexicographical ordering is considered.
263  *
264  * The calling code may choose to reallocate the array to the new, compacted
265  * size; this is not done automatically, to avoid the overhead of memory
266  * management in cases where it is not useful (i.e. when the array is
267  * discarded soon after use).
268  *
269  * parameters:
270  * n_elts <-- initial number of elements
271  * elts <-> elements to sort (size: n_elts*2, interleaved)
272  *
273  * returns:
274  * number of compacted elements
275  *---------------------------------------------------------------------------*/
276 
277 cs_lnum_t
279  cs_gnum_t elts[]);
280 
281 /*---------------------------------------------------------------------------*/
282 
284 
285 #endif /* __CS_SORT_H__ */
#define BEGIN_C_DECLS
Definition: cs_defs.h:514
unsigned long cs_gnum_t
global mesh entity number
Definition: cs_defs.h:298
#define END_C_DECLS
Definition: cs_defs.h:515
int cs_lnum_t
local mesh entity id
Definition: cs_defs.h:313
void cs_sort_dcoupled_shell(int l, int r, int a[], double b[])
Definition: cs_sort.c:472
void cs_sort_int_shell(cs_lnum_t l, cs_lnum_t r, int a[])
Definition: cs_sort.c:345
void cs_sort_coupled_gnum_shell(cs_lnum_t l, cs_lnum_t r, cs_gnum_t a[], cs_gnum_t b[])
Definition: cs_sort.c:573
void cs_sort_shell(cs_lnum_t l, cs_lnum_t r, cs_lnum_t a[])
Definition: cs_sort.c:310
void cs_sort_sicoupled_shell(int l, int r, cs_lnum_t a[], short int b[])
Definition: cs_sort.c:523
void cs_sort_coupled_shell(cs_lnum_t l, cs_lnum_t r, cs_lnum_t a[], cs_lnum_t b[])
Definition: cs_sort.c:422
cs_lnum_t cs_sort_and_compact_gnum_2(cs_lnum_t n_elts, cs_gnum_t elts[])
Definition: cs_sort.c:860
void cs_sort_shell_inplace(cs_lnum_t l, cs_lnum_t r, const cs_lnum_t a[], cs_lnum_t loc[])
Definition: cs_sort.c:268
bool cs_sort_indexed_gnum(cs_lnum_t n_elts, const cs_lnum_t elt_idx[], cs_gnum_t elts[])
Definition: cs_sort.c:725
void cs_sort_lnum(cs_lnum_t number[], size_t n_elts)
Definition: cs_sort.c:623
void cs_sort_gnum_shell(cs_lnum_t l, cs_lnum_t r, cs_gnum_t a[])
Definition: cs_sort.c:380
cs_lnum_t cs_sort_and_compact_gnum(cs_lnum_t n_elts, cs_gnum_t elts[])
Definition: cs_sort.c:764
bool cs_sort_indexed(cs_lnum_t n_elts, const cs_lnum_t elt_idx[], cs_lnum_t elts[])
Definition: cs_sort.c:688