1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkSortDataArray.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15
16 /*
17 * Copyright 2003 Sandia Corporation.
18 * Under the terms of Contract DE-AC04-94AL85000, there is a non-exclusive
19 * license for use of this work by or on behalf of the
20 * U.S. Government. Redistribution and use in source and binary forms, with
21 * or without modification, are permitted provided that this Notice and any
22 * statement of authorship are reproduced on all copies.
23 */
24
25 #include "vtkSortDataArray.h"
26
27 #include "vtkAbstractArray.h"
28 #include "vtkMath.h"
29 #include "vtkObjectFactory.h"
30 #include "vtkIdList.h"
31 #include "vtkStdString.h"
32 #include "vtkStringArray.h"
33 #include "vtkVariant.h"
34 #include "vtkVariantArray.h"
35
36 #include <algorithm>
37
38 // -------------------------------------------------------------------------
39
40 vtkStandardNewMacro(vtkSortDataArray);
41
vtkSortDataArray()42 vtkSortDataArray::vtkSortDataArray()
43 {
44 }
45
~vtkSortDataArray()46 vtkSortDataArray::~vtkSortDataArray()
47 {
48 }
49
PrintSelf(ostream & os,vtkIndent indent)50 void vtkSortDataArray::PrintSelf(ostream &os, vtkIndent indent)
51 {
52 this->Superclass::PrintSelf(os, indent);
53 }
54
55 // ---------------------------------------------------------------------------
56 // Sorting templates using operator <
57
58 template<class TKey, class TValue>
vtkSortDataArraySwap(TKey * keys,TValue * values,int tupleSize,vtkIdType index1,vtkIdType index2)59 inline void vtkSortDataArraySwap(TKey *keys, TValue *values, int tupleSize,
60 vtkIdType index1, vtkIdType index2)
61 {
62 TKey tmpkey;
63 TValue tmpvalue;
64 TKey *k1 = keys + index1;
65 TValue *v1 = values + index1*tupleSize;
66 TKey *k2 = keys + index2;
67 TValue *v2 = values + index2*tupleSize;
68
69 tmpkey = *k1;
70 *k1 = *k2;
71 *k2 = tmpkey;
72
73 for (int i = 0; i < tupleSize; i++)
74 {
75 tmpvalue = v1[i];
76 v1[i] = v2[i];
77 v2[i] = tmpvalue;
78 }
79 }
80
81 template<class TKey, class TValue>
vtkSortDataArrayBubbleSort(TKey * keys,TValue * values,vtkIdType size,int tupleSize)82 void vtkSortDataArrayBubbleSort(TKey *keys, TValue *values,
83 vtkIdType size, int tupleSize)
84 {
85 for (int i = 1; i < size; i++)
86 {
87 for (int j = i; (j > 0) && (keys[j] < keys[j-1]); j--)
88 {
89 vtkSortDataArraySwap(keys, values, tupleSize, j, j-1);
90 }
91 }
92 }
93
94 template<class TKey, class TValue>
vtkSortDataArrayQuickSort(TKey * keys,TValue * values,vtkIdType size,int tupleSize)95 void vtkSortDataArrayQuickSort(TKey *keys, TValue *values,
96 vtkIdType size, int tupleSize)
97 {
98 while (1)
99 {
100 if (size < 8)
101 {
102 vtkSortDataArrayBubbleSort(keys, values, size, tupleSize);
103 return;
104 }
105
106 vtkIdType pivot = static_cast<vtkIdType>(vtkMath::Random(0,
107 static_cast<double>(size)));
108 //vtkIdType pivot = size/2;
109 vtkSortDataArraySwap(keys, values, tupleSize, 0, pivot);
110 // Pivot now stored at index 0.
111
112 vtkIdType left = 1;
113 vtkIdType right = size - 1;
114 while (1)
115 {
116 while ((left <= right) && (keys[left] <= keys[0])) left++;
117 while ((left <= right) && (keys[right] >= keys[0])) right--;
118 if (left > right) break;
119 vtkSortDataArraySwap(keys, values, tupleSize, left, right);
120 }
121
122 // Place the pivot back in the middle
123 vtkSortDataArraySwap(keys, values, tupleSize, 0, left-1);
124
125 // Recurse
126 vtkSortDataArrayQuickSort(keys + left, values + left*tupleSize,
127 size-left, tupleSize);
128 size = left-1;
129 }
130 }
131
132 // ---------------------------------------------------------------------------
133 // Sorting templates using user-defined comparison operation
134
135 template<class TKey, class TValue, class TComp>
vtkSortDataArrayBubbleSort(TKey * keys,TValue * values,vtkIdType size,int tupleSize,TComp comp)136 void vtkSortDataArrayBubbleSort(TKey *keys, TValue *values,
137 vtkIdType size, int tupleSize, TComp comp)
138 {
139 for (int i = 1; i < size; i++)
140 {
141 for (int j = i; (j > 0) && comp(keys[j],keys[j-1]); j--)
142 {
143 vtkSortDataArraySwap(keys, values, tupleSize, j, j-1);
144 }
145 }
146 }
147
148 template<class TKey, class TValue, class TComp>
vtkSortDataArrayQuickSort(TKey * keys,TValue * values,vtkIdType size,int tupleSize,TComp comp)149 void vtkSortDataArrayQuickSort(TKey *keys, TValue *values,
150 vtkIdType size, int tupleSize, TComp comp)
151 {
152 while (1)
153 {
154 if (size < 8)
155 {
156 vtkSortDataArrayBubbleSort(keys, values, size, tupleSize, comp);
157 return;
158 }
159
160 vtkIdType pivot = static_cast<vtkIdType>(vtkMath::Random(0,
161 static_cast<double>(size)));
162 //vtkIdType pivot = size/2;
163 vtkSortDataArraySwap(keys, values, tupleSize, 0, pivot);
164 // Pivot now stored at index 0.
165
166 vtkIdType left = 1;
167 vtkIdType right = size - 1;
168 while (1)
169 {
170 while ((left <= right) && !comp(keys[0],keys[left])) left++;
171 while ((left <= right) && !comp(keys[right],keys[0])) right--;
172 if (left > right) break;
173 vtkSortDataArraySwap(keys, values, tupleSize, left, right);
174 }
175
176 // Place the pivot back in the middle
177 vtkSortDataArraySwap(keys, values, tupleSize, 0, left-1);
178
179 // Recurse
180 vtkSortDataArrayQuickSort(keys + left, values + left*tupleSize,
181 size-left, tupleSize, comp);
182 size = left-1;
183 }
184 }
185
186 // ---------------------------------------------------------------------------
187 // Data array to raw array template helper functions
188
189 template<class TKey, class TValue, class TComp>
vtkSortDataArraySort00(TKey * keys,TValue * values,vtkIdType array_size,int tuple_size,TComp comp)190 inline void vtkSortDataArraySort00(TKey *keys, TValue *values,
191 vtkIdType array_size, int tuple_size, TComp comp)
192 {
193 vtkSortDataArrayQuickSort(keys, values, array_size, tuple_size, comp);
194 }
195
196 template<class TKey, class TValue>
vtkSortDataArraySort00(TKey * keys,TValue * values,vtkIdType array_size,int tuple_size)197 inline void vtkSortDataArraySort00(TKey *keys, TValue *values,
198 vtkIdType array_size, int tuple_size)
199 {
200 vtkSortDataArrayQuickSort(keys, values, array_size, tuple_size);
201 }
202
203 template<class TKey, class TComp>
vtkSortDataArraySort01(TKey * keys,vtkAbstractArray * values,vtkIdType array_size,TComp comp)204 void vtkSortDataArraySort01(TKey *keys, vtkAbstractArray *values, vtkIdType array_size,
205 TComp comp)
206 {
207 if (array_size != values->GetNumberOfTuples())
208 {
209 vtkGenericWarningMacro("Could not sort arrays. Key and value arrays have different sizes.");
210 return;
211 }
212
213 switch (values->GetDataType())
214 {
215 vtkExtraExtendedTemplateMacro(
216 vtkSortDataArraySort00(keys, static_cast<VTK_TT *>(values->GetVoidPointer(0)),
217 array_size, values->GetNumberOfComponents(), comp));
218 }
219 }
220
221 template<class TKey>
vtkSortDataArraySort01(TKey * keys,vtkAbstractArray * values,vtkIdType array_size)222 void vtkSortDataArraySort01(TKey *keys, vtkAbstractArray *values, vtkIdType array_size)
223 {
224 if (array_size != values->GetNumberOfTuples())
225 {
226 vtkGenericWarningMacro("Could not sort arrays. Key and value arrays have different sizes.");
227 return;
228 }
229
230 switch (values->GetDataType())
231 {
232 vtkExtraExtendedTemplateMacro(
233 vtkSortDataArraySort00(keys, static_cast<VTK_TT *>(values->GetVoidPointer(0)),
234 array_size, values->GetNumberOfComponents()));
235 }
236 }
237
238 template<class TValue>
vtkSortDataArraySort10(vtkAbstractArray * keys,TValue * values,vtkIdType array_size,int tuple_size)239 void vtkSortDataArraySort10(vtkAbstractArray *keys, TValue *values,
240 vtkIdType array_size, int tuple_size)
241 {
242 if (array_size != keys->GetNumberOfTuples())
243 {
244 vtkGenericWarningMacro("Could not sort arrays. Key and value arrays have different sizes.");
245 return;
246 }
247
248 if (keys->GetNumberOfComponents() != 1)
249 {
250 vtkGenericWarningMacro("Could not sort arrays. Keys must be 1-tuples.");
251 return;
252 }
253
254 switch (keys->GetDataType())
255 {
256 vtkExtendedTemplateMacro(
257 vtkSortDataArraySort00(static_cast<VTK_TT*>(keys->GetVoidPointer(0)),
258 values, array_size, tuple_size));
259 }
260 }
261
vtkSortDataArraySort11(vtkAbstractArray * keys,vtkAbstractArray * values)262 static void vtkSortDataArraySort11(vtkAbstractArray *keys, vtkAbstractArray *values)
263 {
264 switch (values->GetDataType())
265 {
266 vtkExtraExtendedTemplateMacro(
267 vtkSortDataArraySort10(keys, static_cast<VTK_TT *>(values->GetVoidPointer(0)),
268 values->GetNumberOfTuples(),
269 values->GetNumberOfComponents()));
270 }
271 }
272
273 // The component that qsort should use to compare tuples.
274 // This is ugly and not thread-safe but it works.
275 static int vtkSortDataArrayComp = 0;
276
277 // Key comparison functions for qsort must be in an extern "C"
278 // or some compilers will be unable to use their function pointers
279 // as arguments to qsort.
280 extern "C" {
vtkSortDataArrayComponentCompare_VTK_DOUBLE(const void * a,const void * b)281 static int vtkSortDataArrayComponentCompare_VTK_DOUBLE( const void* a, const void* b )
282 {
283 return ((double*)a)[vtkSortDataArrayComp] < ((double*)b)[vtkSortDataArrayComp] ? -1 :
284 (((double*)a)[vtkSortDataArrayComp] == ((double*)b)[vtkSortDataArrayComp] ? 0 : 1);
285 }
286
vtkSortDataArrayComponentCompare_VTK_FLOAT(const void * a,const void * b)287 static int vtkSortDataArrayComponentCompare_VTK_FLOAT( const void* a, const void* b )
288 {
289 return ((float*)a)[vtkSortDataArrayComp] < ((float*)b)[vtkSortDataArrayComp] ? -1 :
290 (((float*)a)[vtkSortDataArrayComp] == ((float*)b)[vtkSortDataArrayComp] ? 0 : 1);
291 }
292
293 #ifdef VTK_TYPE_USE_LONG_LONG
vtkSortDataArrayComponentCompare_VTK_LONG_LONG(const void * a,const void * b)294 static int vtkSortDataArrayComponentCompare_VTK_LONG_LONG( const void* a, const void* b )
295 {
296 return ((long long*)a)[vtkSortDataArrayComp] < ((long long*)b)[vtkSortDataArrayComp] ? -1 :
297 (((long long*)a)[vtkSortDataArrayComp] == ((long long*)b)[vtkSortDataArrayComp] ? 0 : 1);
298 }
299
vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG_LONG(const void * a,const void * b)300 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG_LONG( const void* a, const void* b )
301 {
302 return ((unsigned long long*)a)[vtkSortDataArrayComp] < ((unsigned long long*)b)[vtkSortDataArrayComp] ? -1 :
303 (((unsigned long long*)a)[vtkSortDataArrayComp] == ((unsigned long long*)b)[vtkSortDataArrayComp] ? 0 : 1);
304 }
305 #endif // VTK_TYPE_USE_LONG_LONG
306
307 #ifdef VTK_TYPE_USE___INT64
vtkSortDataArrayComponentCompare_VTK___INT64(const void * a,const void * b)308 static int vtkSortDataArrayComponentCompare_VTK___INT64( const void* a, const void* b )
309 {
310 return ((vtkTypeInt64*)a)[vtkSortDataArrayComp] < ((vtkTypeInt64*)b)[vtkSortDataArrayComp] ? -1 :
311 (((vtkTypeInt64*)a)[vtkSortDataArrayComp] == ((vtkTypeInt64*)b)[vtkSortDataArrayComp] ? 0 : 1);
312 }
313
vtkSortDataArrayComponentCompare_VTK_UNSIGNED___INT64(const void * a,const void * b)314 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED___INT64( const void* a, const void* b )
315 {
316 return ((vtkTypeUInt64*)a)[vtkSortDataArrayComp] < ((vtkTypeUInt64*)b)[vtkSortDataArrayComp] ? -1 :
317 (((vtkTypeUInt64*)a)[vtkSortDataArrayComp] == ((vtkTypeUInt64*)b)[vtkSortDataArrayComp] ? 0 : 1);
318 }
319 #endif // VTK_TYPE_USE___INT64
320
vtkSortDataArrayComponentCompare_VTK_ID_TYPE(const void * a,const void * b)321 static int vtkSortDataArrayComponentCompare_VTK_ID_TYPE( const void* a, const void* b )
322 {
323 return ((vtkIdType*)a)[vtkSortDataArrayComp] < ((vtkIdType*)b)[vtkSortDataArrayComp] ? -1 :
324 (((vtkIdType*)a)[vtkSortDataArrayComp] == ((vtkIdType*)b)[vtkSortDataArrayComp] ? 0 : 1);
325 }
326
vtkSortDataArrayComponentCompare_VTK_LONG(const void * a,const void * b)327 static int vtkSortDataArrayComponentCompare_VTK_LONG( const void* a, const void* b )
328 {
329 return ((long*)a)[vtkSortDataArrayComp] < ((long*)b)[vtkSortDataArrayComp] ? -1 :
330 (((long*)a)[vtkSortDataArrayComp] == ((long*)b)[vtkSortDataArrayComp] ? 0 : 1);
331 }
332
vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG(const void * a,const void * b)333 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG( const void* a, const void* b )
334 {
335 return ((unsigned long*)a)[vtkSortDataArrayComp] < ((unsigned long*)b)[vtkSortDataArrayComp] ? -1 :
336 (((unsigned long*)a)[vtkSortDataArrayComp] == ((unsigned long*)b)[vtkSortDataArrayComp] ? 0 : 1);
337 }
338
vtkSortDataArrayComponentCompare_VTK_INT(const void * a,const void * b)339 static int vtkSortDataArrayComponentCompare_VTK_INT( const void* a, const void* b )
340 {
341 return ((int*)a)[vtkSortDataArrayComp] < ((int*)b)[vtkSortDataArrayComp] ? -1 :
342 (((int*)a)[vtkSortDataArrayComp] == ((int*)b)[vtkSortDataArrayComp] ? 0 : 1);
343 }
344
vtkSortDataArrayComponentCompare_VTK_UNSIGNED_INT(const void * a,const void * b)345 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED_INT( const void* a, const void* b )
346 {
347 return ((unsigned int*)a)[vtkSortDataArrayComp] < ((unsigned int*)b)[vtkSortDataArrayComp] ? -1 :
348 (((unsigned int*)a)[vtkSortDataArrayComp] == ((unsigned int*)b)[vtkSortDataArrayComp] ? 0 : 1);
349 }
350
vtkSortDataArrayComponentCompare_VTK_SHORT(const void * a,const void * b)351 static int vtkSortDataArrayComponentCompare_VTK_SHORT( const void* a, const void* b )
352 {
353 return ((short*)a)[vtkSortDataArrayComp] < ((short*)b)[vtkSortDataArrayComp] ? -1 :
354 (((short*)a)[vtkSortDataArrayComp] == ((short*)b)[vtkSortDataArrayComp] ? 0 : 1);
355 }
356
vtkSortDataArrayComponentCompare_VTK_UNSIGNED_SHORT(const void * a,const void * b)357 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED_SHORT( const void* a, const void* b )
358 {
359 return ((unsigned short*)a)[vtkSortDataArrayComp] < ((unsigned short*)b)[vtkSortDataArrayComp] ? -1 :
360 (((unsigned short*)a)[vtkSortDataArrayComp] == ((unsigned short*)b)[vtkSortDataArrayComp] ? 0 : 1);
361 }
362
vtkSortDataArrayComponentCompare_VTK_CHAR(const void * a,const void * b)363 static int vtkSortDataArrayComponentCompare_VTK_CHAR( const void* a, const void* b )
364 {
365 return ((char*)a)[vtkSortDataArrayComp] < ((char*)b)[vtkSortDataArrayComp] ? -1 :
366 (((char*)a)[vtkSortDataArrayComp] == ((char*)b)[vtkSortDataArrayComp] ? 0 : 1);
367 }
368
vtkSortDataArrayComponentCompare_VTK_SIGNED_CHAR(const void * a,const void * b)369 static int vtkSortDataArrayComponentCompare_VTK_SIGNED_CHAR( const void* a, const void* b )
370 {
371 return ((signed char*)a)[vtkSortDataArrayComp] < ((signed char*)b)[vtkSortDataArrayComp] ? -1 :
372 (((signed char*)a)[vtkSortDataArrayComp] == ((signed char*)b)[vtkSortDataArrayComp] ? 0 : 1);
373 }
374
vtkSortDataArrayComponentCompare_VTK_UNSIGNED_CHAR(const void * a,const void * b)375 static int vtkSortDataArrayComponentCompare_VTK_UNSIGNED_CHAR( const void* a, const void* b )
376 {
377 return ((unsigned char*)a)[vtkSortDataArrayComp] < ((unsigned char*)b)[vtkSortDataArrayComp] ? -1 :
378 (((unsigned char*)a)[vtkSortDataArrayComp] == ((unsigned char*)b)[vtkSortDataArrayComp] ? 0 : 1);
379 }
380
vtkSortDataArrayComponentCompare_VTK_STRING(const void * a,const void * b)381 static int vtkSortDataArrayComponentCompare_VTK_STRING( const void* a, const void* b )
382 {
383 return ((vtkStdString*)a)[vtkSortDataArrayComp] < ((vtkStdString*)b)[vtkSortDataArrayComp] ? -1 :
384 (((vtkStdString*)a)[vtkSortDataArrayComp] == ((vtkStdString*)b)[vtkSortDataArrayComp] ? 0 : 1);
385 }
386
vtkSortDataArrayComponentCompare_VTK_VARIANT(const void * a,const void * b)387 static int vtkSortDataArrayComponentCompare_VTK_VARIANT( const void* a, const void* b )
388 {
389 vtkVariantLessThan comp;
390 return comp(((vtkVariant*)a)[vtkSortDataArrayComp], ((vtkVariant*)b)[vtkSortDataArrayComp]) ? -1 :
391 (comp(((vtkVariant*)b)[vtkSortDataArrayComp], ((vtkVariant*)a)[vtkSortDataArrayComp]) ? 1 : 0);
392 }
393 }
394
395 // vtkSortDataArray methods -------------------------------------------------------
396
Sort(vtkIdList * keys)397 void vtkSortDataArray::Sort(vtkIdList *keys)
398 {
399 vtkIdType *data = keys->GetPointer(0);
400 vtkIdType numKeys = keys->GetNumberOfIds();
401 std::sort(data, data + numKeys);
402 }
403
Sort(vtkAbstractArray * keys)404 void vtkSortDataArray::Sort(vtkAbstractArray *keys)
405 {
406 if (keys->GetNumberOfComponents() != 1)
407 {
408 vtkGenericWarningMacro("Can only sort keys that are 1-tuples.");
409 return;
410 }
411
412 void *data = keys->GetVoidPointer(0);
413 vtkIdType numKeys = keys->GetNumberOfTuples();
414
415 switch (keys->GetDataType())
416 {
417 vtkExtendedTemplateMacro(std::sort(static_cast<VTK_TT *>(data), static_cast<VTK_TT *>(data) + numKeys));
418 }
419 }
420
SortArrayByComponent(vtkAbstractArray * arr,int k)421 void vtkSortDataArray::SortArrayByComponent( vtkAbstractArray* arr, int k )
422 {
423 int nc = arr->GetNumberOfComponents();
424 if ( nc <= k )
425 {
426 vtkGenericWarningMacro( "Cannot sort by column " << k <<
427 " since the array only has columns 0 through " << (nc-1) );
428 return;
429 }
430
431 // This global variable is what makes the method unsafe for threads:
432 vtkSortDataArrayComp = k;
433
434 switch(arr->GetDataType())
435 {
436 case VTK_DOUBLE:
437 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
438 static_cast<size_t>(arr->GetNumberOfTuples()),
439 static_cast<size_t>(arr->GetDataTypeSize()*nc),
440 vtkSortDataArrayComponentCompare_VTK_DOUBLE);
441 break;
442 case VTK_FLOAT:
443 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
444 static_cast<size_t>(arr->GetNumberOfTuples()),
445 static_cast<size_t>(arr->GetDataTypeSize()*nc),
446 vtkSortDataArrayComponentCompare_VTK_FLOAT);
447 break;
448 #ifdef VTK_TYPE_USE_LONG_LONG
449 case VTK_LONG_LONG:
450 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
451 static_cast<size_t>(arr->GetNumberOfTuples()),
452 static_cast<size_t>(arr->GetDataTypeSize()*nc),
453 vtkSortDataArrayComponentCompare_VTK_LONG_LONG);
454 break;
455 case VTK_UNSIGNED_LONG_LONG:
456 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
457 static_cast<size_t>(arr->GetNumberOfTuples()),
458 static_cast<size_t>(arr->GetDataTypeSize()*nc),
459 vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG_LONG);
460 break;
461 #endif // VTK_TYPE_USE_LONG_LONG
462 #ifdef VTK_TYPE_USE___INT64
463 case VTK___INT64:
464 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
465 static_cast<size_t>(arr->GetNumberOfTuples()),
466 static_cast<size_t>(arr->GetDataTypeSize()*nc),
467 vtkSortDataArrayComponentCompare_VTK___INT64);
468 break;
469 case VTK_UNSIGNED___INT64:
470 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
471 static_cast<size_t>(arr->GetNumberOfTuples()),
472 static_cast<size_t>(arr->GetDataTypeSize()*nc),
473 vtkSortDataArrayComponentCompare_VTK_UNSIGNED___INT64);
474 break;
475 #endif // VTK_TYPE_USE___INT64
476 case VTK_ID_TYPE:
477 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
478 static_cast<size_t>(arr->GetNumberOfTuples()),
479 static_cast<size_t>(arr->GetDataTypeSize()*nc),
480 vtkSortDataArrayComponentCompare_VTK_ID_TYPE);
481 break;
482 case VTK_LONG:
483 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
484 static_cast<size_t>(arr->GetNumberOfTuples()),
485 static_cast<size_t>(arr->GetDataTypeSize()*nc),
486 vtkSortDataArrayComponentCompare_VTK_LONG);
487 break;
488 case VTK_UNSIGNED_LONG:
489 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
490 static_cast<size_t>(arr->GetNumberOfTuples()),
491 static_cast<size_t>(arr->GetDataTypeSize()*nc),
492 vtkSortDataArrayComponentCompare_VTK_UNSIGNED_LONG);
493 break;
494 case VTK_INT:
495 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
496 static_cast<size_t>(arr->GetNumberOfTuples()),
497 static_cast<size_t>(arr->GetDataTypeSize()*nc),
498 vtkSortDataArrayComponentCompare_VTK_INT);
499 break;
500 case VTK_UNSIGNED_INT:
501 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
502 static_cast<size_t>(arr->GetNumberOfTuples()),
503 static_cast<size_t>(arr->GetDataTypeSize()*nc),
504 vtkSortDataArrayComponentCompare_VTK_UNSIGNED_INT);
505 break;
506 case VTK_SHORT:
507 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
508 static_cast<size_t>(arr->GetNumberOfTuples()),
509 static_cast<size_t>(arr->GetDataTypeSize()*nc),
510 vtkSortDataArrayComponentCompare_VTK_SHORT);
511 break;
512 case VTK_UNSIGNED_SHORT:
513 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
514 static_cast<size_t>(arr->GetNumberOfTuples()),
515 static_cast<size_t>(arr->GetDataTypeSize()*nc),
516 vtkSortDataArrayComponentCompare_VTK_UNSIGNED_SHORT);
517 break;
518 case VTK_CHAR:
519 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
520 static_cast<size_t>(arr->GetNumberOfTuples()),
521 static_cast<size_t>(arr->GetDataTypeSize()*nc),
522 vtkSortDataArrayComponentCompare_VTK_CHAR);
523 break;
524 case VTK_SIGNED_CHAR:
525 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
526 static_cast<size_t>(arr->GetNumberOfTuples()),
527 static_cast<size_t>(arr->GetDataTypeSize()*nc),
528 vtkSortDataArrayComponentCompare_VTK_SIGNED_CHAR);
529 break;
530 case VTK_UNSIGNED_CHAR:
531 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
532 static_cast<size_t>(arr->GetNumberOfTuples()),
533 static_cast<size_t>(arr->GetDataTypeSize()*nc),
534 vtkSortDataArrayComponentCompare_VTK_UNSIGNED_CHAR);
535 break;
536 case VTK_STRING:
537 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
538 static_cast<size_t>(arr->GetNumberOfTuples()),
539 static_cast<size_t>(arr->GetDataTypeSize()*nc),
540 vtkSortDataArrayComponentCompare_VTK_STRING);
541 break;
542 case VTK_VARIANT:
543 qsort(static_cast<void*>(arr->GetVoidPointer(0)),
544 static_cast<size_t>(arr->GetNumberOfTuples()),
545 static_cast<size_t>(arr->GetDataTypeSize()*nc),
546 vtkSortDataArrayComponentCompare_VTK_VARIANT);
547 break;
548 }
549 }
550
Sort(vtkIdList * keys,vtkIdList * values)551 void vtkSortDataArray::Sort(vtkIdList *keys, vtkIdList *values)
552 {
553 vtkIdType size = keys->GetNumberOfIds();
554 if (size != values->GetNumberOfIds())
555 {
556 vtkGenericWarningMacro("Cannot sort arrays. Sizes of keys and values do not agree");
557 return;
558 }
559
560 vtkSortDataArraySort00(keys->GetPointer(0), values->GetPointer(0), size, 1);
561 }
562
Sort(vtkIdList * keys,vtkAbstractArray * values)563 void vtkSortDataArray::Sort(vtkIdList *keys, vtkAbstractArray *values)
564 {
565 vtkSortDataArraySort01(keys->GetPointer(0), values, keys->GetNumberOfIds());
566 }
567
Sort(vtkAbstractArray * keys,vtkIdList * values)568 void vtkSortDataArray::Sort(vtkAbstractArray *keys, vtkIdList *values)
569 {
570 if (keys->GetDataType() == VTK_VARIANT)
571 {
572 vtkVariantLessThan comp;
573 vtkSortDataArraySort00(
574 static_cast<vtkVariant*>(keys->GetVoidPointer(0)),
575 values->GetPointer(0), values->GetNumberOfIds(), 1, comp);
576 }
577 else
578 {
579 vtkSortDataArraySort10(keys, values->GetPointer(0),
580 values->GetNumberOfIds(), 1);
581 }
582 }
583
Sort(vtkAbstractArray * keys,vtkAbstractArray * values)584 void vtkSortDataArray::Sort(vtkAbstractArray *keys, vtkAbstractArray *values)
585 {
586 if (keys->GetDataType() == VTK_VARIANT)
587 {
588 vtkVariantLessThan comp;
589 vtkSortDataArraySort01(
590 static_cast<vtkVariant*>(keys->GetVoidPointer(0)), values, keys->GetNumberOfTuples(), comp);
591 }
592 else
593 {
594 vtkSortDataArraySort11(keys, values);
595 }
596 }
597