1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkAbstractArray.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 #include "vtkAbstractArray.h"
16
17 #include "vtkBitArray.h"
18 #include "vtkCharArray.h"
19 #include "vtkDoubleArray.h"
20 #include "vtkFloatArray.h"
21 #include "vtkIdList.h"
22 #include "vtkIdTypeArray.h"
23 #include "vtkInformation.h"
24 #include "vtkIntArray.h"
25 #include "vtkLongArray.h"
26 #include "vtkMath.h"
27 #include "vtkMinimalStandardRandomSequence.h"
28 #include "vtkShortArray.h"
29 #include "vtkSignedCharArray.h"
30 #include "vtkStringArray.h"
31 #include "vtkUnicodeStringArray.h"
32 #include "vtkUnsignedCharArray.h"
33 #include "vtkUnsignedIntArray.h"
34 #include "vtkUnsignedLongArray.h"
35 #include "vtkUnsignedShortArray.h"
36 #include "vtkVariantArray.h"
37 #include "vtkInformationVector.h"
38 #include "vtkInformationDoubleVectorKey.h"
39 #include "vtkInformationIntegerKey.h"
40 #include "vtkInformationInformationVectorKey.h"
41 #include "vtkInformationVariantVectorKey.h"
42 #include "vtkNew.h"
43 #include "vtkUnicodeString.h" // for vtkSuperExtraExtendedTemplateMacro
44
45 #if defined(VTK_TYPE_USE_LONG_LONG)
46 # include "vtkLongLongArray.h"
47 # include "vtkUnsignedLongLongArray.h"
48 #endif
49
50 #if defined(VTK_TYPE_USE___INT64)
51 # include "vtk__Int64Array.h"
52 # if defined(VTK_TYPE_CONVERT_UI64_TO_DOUBLE)
53 # include "vtkUnsigned__Int64Array.h"
54 # endif
55 #endif
56
57 #include <algorithm>
58 #include <iterator>
59 #include <set>
60 #include <cmath>
61
62 vtkInformationKeyMacro(vtkAbstractArray, GUI_HIDE, Integer);
63 vtkInformationKeyMacro(vtkAbstractArray, PER_COMPONENT, InformationVector);
64 vtkInformationKeyMacro(vtkAbstractArray, DISCRETE_VALUES, VariantVector);
65 vtkInformationKeyRestrictedMacro(vtkAbstractArray, DISCRETE_VALUE_SAMPLE_PARAMETERS, DoubleVector, 2);
66
67 namespace
68 {
69 typedef std::vector< vtkStdString* > vtkInternalComponentNameBase;
70 }
71 class vtkAbstractArray::vtkInternalComponentNames : public vtkInternalComponentNameBase {};
72
73 //----------------------------------------------------------------------------
74 // Construct object with sane defaults.
vtkAbstractArray()75 vtkAbstractArray::vtkAbstractArray()
76 {
77 this->Size = 0;
78 this->MaxId = -1;
79 this->NumberOfComponents = 1;
80 this->Name = NULL;
81 this->RebuildArray = false;
82 this->Information = NULL;
83 this->ComponentNames = NULL;
84
85 this->MaxDiscreteValues = vtkAbstractArray::MAX_DISCRETE_VALUES; //32
86 }
87
88 //----------------------------------------------------------------------------
~vtkAbstractArray()89 vtkAbstractArray::~vtkAbstractArray()
90 {
91 if ( this->ComponentNames )
92 {
93 for ( unsigned int i=0; i < this->ComponentNames->size(); ++i)
94 {
95 delete this->ComponentNames->at(i);
96 }
97 this->ComponentNames->clear();
98 delete this->ComponentNames;
99 this->ComponentNames = NULL;
100 }
101
102 this->SetName(NULL);
103 this->SetInformation(NULL);
104 }
105
106 //----------------------------------------------------------------------------
SetComponentName(vtkIdType component,const char * name)107 void vtkAbstractArray::SetComponentName( vtkIdType component, const char *name )
108 {
109 if ( component < 0 || name == NULL )
110 {
111 return;
112 }
113 unsigned int index = static_cast<unsigned int>( component );
114 if ( this->ComponentNames == NULL )
115 {
116 //delayed allocate
117 this->ComponentNames = new vtkAbstractArray::vtkInternalComponentNames();
118 }
119
120 if ( index == this->ComponentNames->size() )
121 {
122 //the array isn't large enough, so we will resize
123 this->ComponentNames->push_back( new vtkStdString(name) );
124 return;
125 }
126 else if ( index > this->ComponentNames->size() )
127 {
128 this->ComponentNames->resize( index+1, NULL );
129 }
130
131 //replace an exisiting element
132 vtkStdString *compName = this->ComponentNames->at(index);
133 if ( !compName )
134 {
135 compName = new vtkStdString(name);
136 this->ComponentNames->at(index) = compName;
137 }
138 else
139 {
140 compName->assign( name );
141 }
142 }
143
144 //----------------------------------------------------------------------------
GetComponentName(vtkIdType component)145 const char* vtkAbstractArray::GetComponentName( vtkIdType component )
146 {
147 unsigned int index = static_cast<unsigned int>( component );
148 if ( !this->ComponentNames || component < 0 ||
149 index >= this->ComponentNames->size() )
150 {
151 //make sure we have valid vector
152 return NULL;
153 }
154
155 vtkStdString *compName = this->ComponentNames->at( index );
156 return ( compName ) ? compName->c_str() : NULL;
157 }
158
159 //----------------------------------------------------------------------------
HasAComponentName()160 bool vtkAbstractArray::HasAComponentName()
161 {
162 return (this->ComponentNames) ? ( this->ComponentNames->size() > 0 ) : 0;
163 }
164
165 //----------------------------------------------------------------------------
CopyComponentNames(vtkAbstractArray * da)166 int vtkAbstractArray::CopyComponentNames( vtkAbstractArray *da )
167 {
168 if ( da && da != this && da->ComponentNames )
169 {
170 //clear the vector of the all data
171 if ( !this->ComponentNames )
172 {
173 this->ComponentNames = new vtkAbstractArray::vtkInternalComponentNames();
174 }
175
176 //copy the passed in components
177 for ( unsigned int i=0; i < this->ComponentNames->size(); ++i)
178 {
179 delete this->ComponentNames->at(i);
180 }
181 this->ComponentNames->clear();
182 this->ComponentNames->reserve( da->ComponentNames->size() );
183 const char *name;
184 for ( unsigned int i = 0; i < da->ComponentNames->size(); ++i )
185 {
186 name = da->GetComponentName(i);
187 if ( name )
188 {
189 this->SetComponentName(i, name);
190 }
191 }
192 return 1;
193 }
194 return 0;
195 }
196
197
198 //----------------------------------------------------------------------------
SetInformation(vtkInformation * args)199 void vtkAbstractArray::SetInformation(vtkInformation *args)
200 {
201 // Same as in vtkCxxSetObjectMacro, but no Modified() so that
202 // this doesn't cause extra pipeline updates.
203 vtkDebugMacro(<< this->GetClassName() << " (" << this
204 << "): setting Information to " << args );
205 if (this->Information != args)
206 {
207 vtkInformation* tempSGMacroVar = this->Information;
208 this->Information = args;
209 if (this->Information != NULL) { this->Information->Register(this); }
210 if (tempSGMacroVar != NULL)
211 {
212 tempSGMacroVar->UnRegister(this);
213 }
214 }
215 }
216
217 //----------------------------------------------------------------------------
GetTuples(vtkIdList * ptIds,vtkAbstractArray * aa)218 void vtkAbstractArray::GetTuples(vtkIdList* ptIds, vtkAbstractArray* aa)
219 {
220 if (aa->GetNumberOfComponents() != this->GetNumberOfComponents())
221 {
222 vtkWarningMacro("Number of components for input and output do not match.");
223 return;
224 }
225 // Here we give the slowest implementation. Subclasses can override
226 // to use the knowledge about the data.
227 vtkIdType num = ptIds->GetNumberOfIds();
228 for (vtkIdType i = 0; i < num; i++)
229 {
230 aa->SetTuple(i, ptIds->GetId(i), this);
231 }
232 }
233
234 //----------------------------------------------------------------------------
GetTuples(vtkIdType p1,vtkIdType p2,vtkAbstractArray * aa)235 void vtkAbstractArray::GetTuples(vtkIdType p1, vtkIdType p2,
236 vtkAbstractArray* aa)
237 {
238 if (aa->GetNumberOfComponents() != this->GetNumberOfComponents())
239 {
240 vtkWarningMacro("Number of components for input and output do not match.");
241 return;
242 }
243
244 // Here we give the slowest implementation. Subclasses can override
245 // to use the knowledge about the data.
246 vtkIdType num = p2 - p1 + 1;
247 for (vtkIdType i = 0; i < num; i++)
248 {
249 aa->SetTuple(i, (p1+i), this);
250 }
251 }
252
253 //----------------------------------------------------------------------------
HasStandardMemoryLayout()254 bool vtkAbstractArray::HasStandardMemoryLayout()
255 {
256 return true;
257 }
258
259 //----------------------------------------------------------------------------
DeepCopy(vtkAbstractArray * da)260 void vtkAbstractArray::DeepCopy( vtkAbstractArray* da )
261 {
262 if (da && da->HasInformation() && da!=this)
263 {
264 this->CopyInformation(da->GetInformation(),/*deep=*/1);
265 }
266 this->CopyComponentNames( da );
267 }
268
269 //----------------------------------------------------------------------------
CopyInformation(vtkInformation * infoFrom,int deep)270 int vtkAbstractArray::CopyInformation(vtkInformation* infoFrom, int deep)
271 {
272 // Copy all keys. NOTE: subclasses rely on this.
273 vtkInformation* myInfo=this->GetInformation();
274 myInfo->Copy(infoFrom,deep);
275
276 // Remove any keys we own that are not to be copied here.
277 // For now, remove per-component metadata.
278 if (myInfo->Has(PER_COMPONENT()))
279 {
280 myInfo->Remove(PER_COMPONENT());
281 }
282 if (myInfo->Has(DISCRETE_VALUES()))
283 {
284 myInfo->Remove(DISCRETE_VALUES());
285 }
286
287 return 1;
288 }
289
290 //----------------------------------------------------------------------------
GetInformation()291 vtkInformation* vtkAbstractArray::GetInformation()
292 {
293 if ( ! this->Information )
294 {
295 vtkInformation* info = vtkInformation::New();
296 this->SetInformation( info );
297 info->FastDelete();
298 }
299 return this->Information;
300 }
301
302 //----------------------------------------------------------------------------
303 template <class T>
vtkAbstractArrayGetDataTypeSize(T *)304 int vtkAbstractArrayGetDataTypeSize(T*)
305 {
306 return sizeof(T);
307 }
308
GetDataTypeSize(int type)309 int vtkAbstractArray::GetDataTypeSize(int type)
310 {
311 switch (type)
312 {
313 vtkTemplateMacro(
314 return vtkAbstractArrayGetDataTypeSize(static_cast<VTK_TT*>(0))
315 );
316
317 case VTK_BIT:
318 case VTK_STRING:
319 case VTK_UNICODE_STRING:
320 return 0;
321
322 default:
323 vtkGenericWarningMacro(<<"Unsupported data type!");
324 }
325
326 return 1;
327 }
328
329 // ----------------------------------------------------------------------
CreateArray(int dataType)330 vtkAbstractArray* vtkAbstractArray::CreateArray(int dataType)
331 {
332 switch (dataType)
333 {
334 case VTK_BIT:
335 return vtkBitArray::New();
336
337 case VTK_CHAR:
338 return vtkCharArray::New();
339
340 case VTK_SIGNED_CHAR:
341 return vtkSignedCharArray::New();
342
343 case VTK_UNSIGNED_CHAR:
344 return vtkUnsignedCharArray::New();
345
346 case VTK_SHORT:
347 return vtkShortArray::New();
348
349 case VTK_UNSIGNED_SHORT:
350 return vtkUnsignedShortArray::New();
351
352 case VTK_INT:
353 return vtkIntArray::New();
354
355 case VTK_UNSIGNED_INT:
356 return vtkUnsignedIntArray::New();
357
358 case VTK_LONG:
359 return vtkLongArray::New();
360
361 case VTK_UNSIGNED_LONG:
362 return vtkUnsignedLongArray::New();
363
364 #if defined(VTK_TYPE_USE_LONG_LONG)
365 case VTK_LONG_LONG:
366 return vtkLongLongArray::New();
367
368 case VTK_UNSIGNED_LONG_LONG:
369 return vtkUnsignedLongLongArray::New();
370 #endif
371
372 #if defined(VTK_TYPE_USE___INT64)
373 case VTK___INT64:
374 return vtk__Int64Array::New();
375
376 # if defined(VTK_TYPE_CONVERT_UI64_TO_DOUBLE)
377 case VTK_UNSIGNED___INT64:
378 return vtkUnsigned__Int64Array::New();
379 # endif
380 #endif
381
382 case VTK_FLOAT:
383 return vtkFloatArray::New();
384
385 case VTK_DOUBLE:
386 return vtkDoubleArray::New();
387
388 case VTK_ID_TYPE:
389 return vtkIdTypeArray::New();
390
391 case VTK_STRING:
392 return vtkStringArray::New();
393
394 case VTK_UNICODE_STRING:
395 return vtkUnicodeStringArray::New();
396
397 case VTK_VARIANT:
398 return vtkVariantArray::New();
399
400 default:
401 break;
402 }
403
404 vtkGenericWarningMacro("Unsupported data type: " << dataType
405 << "! Setting to VTK_DOUBLE");
406 return vtkDoubleArray::New();
407 }
408
409 //---------------------------------------------------------------------------
410 template <typename T>
vtkAbstractArrayGetVariantValue(T * arr,vtkIdType index)411 vtkVariant vtkAbstractArrayGetVariantValue(T* arr, vtkIdType index)
412 {
413 return vtkVariant(arr[index]);
414 }
415
416 //----------------------------------------------------------------------------
GetVariantValue(vtkIdType i)417 vtkVariant vtkAbstractArray::GetVariantValue(vtkIdType i)
418 {
419 vtkVariant val;
420 switch(this->GetDataType())
421 {
422 vtkExtraExtendedTemplateMacro(val = vtkAbstractArrayGetVariantValue(
423 static_cast<VTK_TT*>(this->GetVoidPointer(0)), i));
424 }
425 return val;
426 }
427
428 //----------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)429 void vtkAbstractArray::PrintSelf(ostream& os, vtkIndent indent)
430 {
431 this->Superclass::PrintSelf(os,indent);
432
433 const char* name = this->GetName();
434 if (name)
435 {
436 os << indent << "Name: " << name << "\n";
437 }
438 else
439 {
440 os << indent << "Name: (none)\n";
441 }
442 os << indent << "Data type: " << this->GetDataTypeAsString() << "\n";
443 os << indent << "Size: " << this->Size << "\n";
444 os << indent << "MaxId: " << this->MaxId << "\n";
445 os << indent << "NumberOfComponents: " << this->NumberOfComponents << endl;
446 if ( this->ComponentNames )
447 {
448 os << indent << "ComponentNames: " << endl;
449 vtkIndent nextIndent = indent.GetNextIndent();
450 for ( unsigned int i=0; i < this->ComponentNames->size(); ++i )
451 {
452 os << nextIndent << i << " : " << this->ComponentNames->at(i) << endl;
453 }
454 }
455 os << indent << "Information: " << this->Information << endl;
456 if ( this->Information )
457 {
458 this->Information->PrintSelf( os, indent.GetNextIndent() );
459 }
460 }
461
462 //--------------------------------------------------------------------------
InsertVariantValue(vtkIdType id,vtkVariant value)463 void vtkAbstractArray::InsertVariantValue(vtkIdType id, vtkVariant value)
464 {
465 if ( id >= this->Size )
466 {
467 int status = this->Resize(id+1);
468 if (!status)
469 {
470 vtkErrorMacro(<<"FAILED to extend array to accommodate new ID "
471 << id);
472 return;
473 }
474 }
475 if ( id > this->MaxId )
476 {
477 this->MaxId = id;
478 }
479 this->SetVariantValue(id, value);
480 }
481
482 //--------------------------------------------------------------------------
GetProminentComponentValues(int comp,vtkVariantArray * values,double uncertainty,double minimumProminence)483 void vtkAbstractArray::GetProminentComponentValues(
484 int comp, vtkVariantArray* values,
485 double uncertainty, double minimumProminence)
486 {
487 if (!values || comp < -1 || comp >= this->NumberOfComponents)
488 {
489 return;
490 }
491
492 values->Initialize();
493 values->SetNumberOfComponents(comp < 0 ? this->NumberOfComponents : 1);
494
495 bool justCreated = false;
496 vtkInformation* info = this->GetInformation();
497 const double* lastParams = info ?
498 (info->Has(DISCRETE_VALUE_SAMPLE_PARAMETERS()) ?
499 info->Get(DISCRETE_VALUE_SAMPLE_PARAMETERS()) : 0) : 0;
500 if (comp >= 0 && info)
501 {
502 vtkInformationVector* infoVec = info->Get(PER_COMPONENT());
503 if (!infoVec ||
504 infoVec->GetNumberOfInformationObjects() < this->NumberOfComponents)
505 {
506 infoVec = vtkInformationVector::New();
507 infoVec->SetNumberOfInformationObjects(this->NumberOfComponents);
508 info->Set(PER_COMPONENT(), infoVec);
509 infoVec->FastDelete();
510 justCreated = true;
511 }
512 info = infoVec->GetInformationObject(comp);
513 }
514 if (info)
515 {
516 // Any insane parameter values map to
517 // deterministic, exhaustive enumeration of all
518 // distinct values:
519 if (uncertainty < 0. || uncertainty > 1.)
520 {
521 uncertainty = 0.;
522 }
523 if (minimumProminence < 0. || minimumProminence > 1.)
524 {
525 minimumProminence = 0.;
526 }
527 // Are parameter values requesting more certainty in reporting or
528 // that less-prominent values be reported? If so, recompute.
529 bool tighterParams = lastParams ?
530 (lastParams[0] > uncertainty ||
531 lastParams[1] > minimumProminence ?
532 true :
533 false)
534 : true;
535 // Recompute discrete value set when the array has been
536 // modified since the information was written.
537 if (
538 !info->Has(DISCRETE_VALUES()) || tighterParams ||
539 this->GetMTime() > info->GetMTime() || justCreated)
540 {
541 this->UpdateDiscreteValueSet(uncertainty, minimumProminence);
542 }
543 }
544 else
545 {
546 return;
547 }
548
549 vtkIdType len;
550 const vtkVariant* vals = info->Get(DISCRETE_VALUES());
551 if (vals != NULL)
552 {
553 len = info->Length(DISCRETE_VALUES());
554 values->SetNumberOfTuples(len / values->GetNumberOfComponents());
555 for (vtkIdType i = 0; i < len; ++i)
556 {
557 values->SetVariantValue(i, vals[i]);
558 }
559 }
560 }
561
562 //-----------------------------------------------------------------------------
563 namespace
564 {
565 template<typename T>
AccumulateSampleValues(T * array,int nc,vtkIdType begin,vtkIdType end,std::vector<std::set<T>> & uniques,std::set<std::vector<T>> & tupleUniques,unsigned int maxDiscreteValues)566 bool AccumulateSampleValues(
567 T* array, int nc, vtkIdType begin, vtkIdType end,
568 std::vector<std::set<T> >& uniques, std::set<std::vector<T> >& tupleUniques,
569 unsigned int maxDiscreteValues)
570 {
571 // number of discrete components remaining (tracked during iteration):
572 int ndc = nc;
573 std::pair<typename std::set<T>::iterator,bool> result;
574 std::pair<typename std::set<std::vector<T> >::iterator,bool> tresult;
575 std::vector<T> tuple;
576 tuple.resize(nc);
577 // Here we iterate over the components and add to their respective lists
578 // of previously encountered values -- as long as there are not too many
579 // values already in the list. We also accumulate each component's value
580 // into a vtkVariantArray named tuple, which is added to the list of
581 // unique vectors -- again assuming it is not already too long.
582 for (vtkIdType i = begin; i < end && ndc; ++i)
583 {
584 // First, attempt a per-component insert.
585 for (int j = 0; j < nc; ++ j)
586 {
587 if (uniques[j].size() > maxDiscreteValues)
588 continue;
589 T& val(array[i * nc + j]);
590 tuple[j] = val;
591 result = uniques[j].insert(val);
592 if (result.second)
593 {
594 if (uniques[j].size() == maxDiscreteValues + 1)
595 {
596 -- ndc;
597 }
598 }
599 }
600 // Now, as long as no component has exceeded maxDiscreteValues unique
601 // values, it is worth seeing whether the tuple as a whole is unique:
602 if ( nc > 1 && ndc == nc )
603 {
604 tresult = tupleUniques.insert(tuple);
605 (void)tresult; // nice to have when debugging.
606 }
607 }
608 return ndc == 0;
609 }
610
611 //-----------------------------------------------------------------------------
612 template<typename U>
SampleProminentValues(std::vector<std::vector<vtkVariant>> & uniques,vtkIdType maxId,int nc,vtkIdType nt,int blockSize,vtkIdType numberOfBlocks,U * ptr,unsigned int maxDiscreteValues)613 void SampleProminentValues(
614 std::vector<std::vector<vtkVariant> >& uniques, vtkIdType maxId,
615 int nc, vtkIdType nt, int blockSize, vtkIdType numberOfBlocks, U* ptr,
616 unsigned int maxDiscreteValues)
617 {
618 std::vector<std::set<U> > typeSpecificUniques;
619 std::set<std::vector<U> > typeSpecificUniqueTuples;
620 typeSpecificUniques.resize(nc);
621 // I. Accumulate samples for all components plus the tuple,
622 // either for the full array or a random subset.
623 if (numberOfBlocks * blockSize > maxId / 2)
624 { // Awwww, just do the whole array already!
625 AccumulateSampleValues(
626 ptr, nc, 0, nt,
627 typeSpecificUniques, typeSpecificUniqueTuples, maxDiscreteValues);
628 }
629 else
630 { // Choose random blocks
631 vtkNew<vtkMinimalStandardRandomSequence> seq;
632 // test different blocks each time we're called:
633 seq->SetSeed(seq->GetMTime() ^ 0xdeadbeef);
634 vtkIdType totalBlockCount =
635 nt / blockSize +
636 (nt % blockSize ? 1 : 0);
637 std::set<vtkIdType> startTuples;
638 // Sort the list of blocks we'll search to maintain cache coherence.
639 for (int i = 0; i < numberOfBlocks; ++ i, seq->Next())
640 {
641 vtkIdType startTuple =
642 static_cast<vtkIdType>(seq->GetValue() * totalBlockCount) * blockSize;
643 startTuples.insert(startTuple);
644 }
645 // Now iterate over the blocks, accumulating unique values and tuples.
646 std::set<vtkIdType>::iterator blkIt;
647 for (blkIt = startTuples.begin(); blkIt != startTuples.end(); ++blkIt)
648 {
649 vtkIdType startTuple = *blkIt;
650 vtkIdType endTuple = startTuple + blockSize;
651 endTuple = endTuple < nt ? endTuple : nt;
652 bool endEarly = AccumulateSampleValues(
653 ptr, nc, startTuple, endTuple,
654 typeSpecificUniques, typeSpecificUniqueTuples, maxDiscreteValues);
655 if (endEarly)
656 break;
657 }
658 }
659
660 // II. Convert type-specific sets of unique values into non-type-specific
661 // vectors of vtkVariants for storage in array information.
662
663 // Handle per-component uniques first
664 for (int i = 0; i < nc; ++i)
665 {
666 std::back_insert_iterator<std::vector<vtkVariant> > bi(uniques[i]);
667 std::copy(typeSpecificUniques[i].begin(), typeSpecificUniques[i].end(), bi);
668 }
669
670 // Now squash any tuple-wide uniques into
671 // the final entry of the outer vector.
672 typename std::set<std::vector<U> >::iterator si;
673 for (
674 si = typeSpecificUniqueTuples.begin();
675 si != typeSpecificUniqueTuples.end();
676 ++si)
677 {
678 std::back_insert_iterator<std::vector<vtkVariant> > bi(uniques[nc]);
679 std::copy(si->begin(), si->end(), bi);
680 }
681 }
682 } // End anonymous namespace.
683
684 //-----------------------------------------------------------------------------
UpdateDiscreteValueSet(double uncertainty,double minimumProminence)685 void vtkAbstractArray::UpdateDiscreteValueSet(
686 double uncertainty, double minimumProminence)
687 {
688 // For an array with T tuples and given uncertainty U and mininumum
689 // prominence P, we sample N blocks of M tuples each, with
690 // M*N = f(T; P, U) and f some sublinear function of T.
691 // If every component plus all components taken together each have more than
692 // MaxDiscreteValues distinct values, then we exit early.
693 // M is chosen based on the number of bytes per tuple to maximize use of a
694 // cache line (assuming a 64-byte cache line until kwsys::SystemInformation
695 // or the like can provide a platform-independent way to query it).
696 //
697 // N is chosen to satisfy the requested uncertainty and prominence criteria
698 // specified.
699 #define VTK_CACHE_LINE_SIZE 64
700 #define VTK_SAMPLE_FACTOR 5
701 // I. Determine the granularity at which the array should be sampled.
702 int numberOfComponentsWithProminentValues = 0;
703 int nc = this->NumberOfComponents;
704 int blockSize = VTK_CACHE_LINE_SIZE / (this->GetDataTypeSize() * nc);
705 if (!blockSize) blockSize = 4;
706 double logfac = 1.;
707 vtkIdType nt = this->GetNumberOfTuples();
708 if (this->MaxId > 0)
709 {
710 logfac = -log(uncertainty * minimumProminence) / minimumProminence;
711 if (logfac < 0)
712 {
713 logfac = -logfac;
714 }
715 }
716 vtkIdType numberOfSampleTuples;
717 if (vtkMath::IsInf(logfac))
718 {
719 numberOfSampleTuples = nt;
720 }
721 else
722 {
723 numberOfSampleTuples = static_cast<vtkIdType>(VTK_SAMPLE_FACTOR * logfac);
724 }
725 /*
726 // Theoretically, we should discard values or tuples that recur fewer
727 // than minFreq times in our sample, but in practice this involves
728 // counting and communication that slow us down.
729 vtkIdType minFreq = static_cast<vtkIdType>(
730 numberOfSampleTuples * minimumProminence / 2);
731 */
732 vtkIdType numberOfBlocks =
733 numberOfSampleTuples / blockSize +
734 (numberOfSampleTuples % blockSize ? 1 : 0);
735 if (static_cast<unsigned int>(numberOfBlocks * blockSize) <
736 2 * this->MaxDiscreteValues)
737 {
738 numberOfBlocks =
739 2 * this->MaxDiscreteValues / blockSize +
740 (2 * this->MaxDiscreteValues % blockSize ? 1 : 0);
741 }
742 // II. Sample the array.
743 std::vector<std::vector<vtkVariant> > uniques(nc > 1 ? nc + 1 : nc);
744 switch(this->GetDataType())
745 {
746 vtkSuperExtraExtendedTemplateMacro(
747 SampleProminentValues(
748 uniques, this->MaxId, nc, nt, blockSize, numberOfBlocks,
749 static_cast<VTK_TT*>(this->GetVoidPointer(0)),
750 this->MaxDiscreteValues));
751 default:
752 vtkErrorMacro("Array type " << this->GetClassName() << " not supported.");
753 break;
754 }
755
756 // III. Store the results in the array's vtkInformation.
757 int c;
758 vtkInformationVector* iv;
759 for (c = 0; c < nc; ++c)
760 {
761 if (uniques[c].size() <= this->MaxDiscreteValues)
762 {
763 ++ numberOfComponentsWithProminentValues;
764 iv = this->GetInformation()->Get(PER_COMPONENT());
765 if (!iv)
766 {
767 vtkNew<vtkInformationVector> infoVec;
768 infoVec->SetNumberOfInformationObjects(this->NumberOfComponents);
769 this->GetInformation()->Set(PER_COMPONENT(), infoVec.GetPointer());
770 iv = this->GetInformation()->Get(PER_COMPONENT());
771 }
772 iv->GetInformationObject(c)->Set(
773 DISCRETE_VALUES(), &uniques[c][0],
774 static_cast<int>(uniques[c].size()));
775 }
776 else
777 {
778 iv = this->GetInformation()->Get(PER_COMPONENT());
779 if (iv)
780 {
781 iv->GetInformationObject(c)->Remove(
782 DISCRETE_VALUES());
783 }
784 }
785 }
786 if (nc > 1 &&
787 uniques[nc].size() <= this->MaxDiscreteValues * nc)
788 {
789 ++ numberOfComponentsWithProminentValues;
790 this->GetInformation()->Set(
791 DISCRETE_VALUES(), &uniques[nc][0],
792 static_cast<int>(uniques[nc].size()));
793 }
794 else
795 { // Remove the key
796 this->GetInformation()->Remove(DISCRETE_VALUES());
797 }
798
799 // Always store the sample parameters; this lets us know not to
800 // re-run the sampling algorithm.
801 double params[2];
802 params[0] = uncertainty;
803 params[1] = minimumProminence;
804 this->GetInformation()->Set(
805 DISCRETE_VALUE_SAMPLE_PARAMETERS(), params, 2);
806 }
807