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