vtkAbstractArray.cxx 23.9 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkAbstractArray.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
#include "vtkAbstractArray.h"

#include "vtkBitArray.h"
#include "vtkCharArray.h"
#include "vtkDoubleArray.h"
#include "vtkFloatArray.h"
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
21
#include "vtkIdList.h"
22
#include "vtkIdTypeArray.h"
23
24
#include "vtkInformation.h"
#include "vtkIntArray.h"
25
#include "vtkLongArray.h"
26
#include "vtkMath.h"
27
#include "vtkMinimalStandardRandomSequence.h"
28
#include "vtkShortArray.h"
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
29
30
#include "vtkSignedCharArray.h"
#include "vtkStringArray.h"
31
#include "vtkUnicodeStringArray.h"
32
33
34
35
#include "vtkUnsignedCharArray.h"
#include "vtkUnsignedIntArray.h"
#include "vtkUnsignedLongArray.h"
#include "vtkUnsignedShortArray.h"
36
#include "vtkVariantArray.h"
37
#include "vtkInformationVector.h"
38
#include "vtkInformationDoubleVectorKey.h"
39
#include "vtkInformationIntegerKey.h"
40
41
#include "vtkInformationInformationVectorKey.h"
#include "vtkInformationVariantVectorKey.h"
42
#include "vtkNew.h"
43
#include "vtkUnicodeString.h" // for vtkSuperExtraExtendedTemplateMacro
44

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
45
46
47
48
#if defined(VTK_TYPE_USE_LONG_LONG)
# include "vtkLongLongArray.h"
# include "vtkUnsignedLongLongArray.h"
#endif
49

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
50
51
52
53
54
55
#if defined(VTK_TYPE_USE___INT64)
# include "vtk__Int64Array.h"
# if defined(VTK_TYPE_CONVERT_UI64_TO_DOUBLE)
#  include "vtkUnsigned__Int64Array.h"
# endif
#endif
56

57
58
#include <algorithm>
#include <iterator>
59
60
61
#include <set>
#include <cmath>

62
vtkInformationKeyMacro(vtkAbstractArray, GUI_HIDE, Integer);
63
64
vtkInformationKeyMacro(vtkAbstractArray, PER_COMPONENT, InformationVector);
vtkInformationKeyMacro(vtkAbstractArray, DISCRETE_VALUES, VariantVector);
65
vtkInformationKeyRestrictedMacro(vtkAbstractArray, DISCRETE_VALUE_SAMPLE_PARAMETERS, DoubleVector, 2);
66

67
68
namespace
{
69
  typedef  std::vector< vtkStdString* > vtkInternalComponentNameBase;
70
71
72
}
class vtkAbstractArray::vtkInternalComponentNames : public vtkInternalComponentNameBase {};

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
73
//----------------------------------------------------------------------------
74
75
76
77
78
// Construct object with sane defaults.
vtkAbstractArray::vtkAbstractArray(vtkIdType vtkNotUsed(numComp))
{
  this->Size = 0;
  this->MaxId = -1;
79
  this->NumberOfComponents = 1;
80
  this->Name = NULL;
81
  this->Information = NULL;
82

83
  this->ComponentNames = NULL;
84
85

  this->MaxDiscreteValues = vtkAbstractArray::MAX_DISCRETE_VALUES; //32
86
87
}

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
88
//----------------------------------------------------------------------------
89
90
vtkAbstractArray::~vtkAbstractArray()
{
91
92
  if ( this->ComponentNames )
    {
93
94
95
96
97
98
99
    for ( unsigned int i=0; i < this->ComponentNames->size(); ++i)
      {
      if ( this->ComponentNames->at(i) )
        {
        delete this->ComponentNames->at(i);
        }
      }
100
101
102
103
    this->ComponentNames->clear();
    delete this->ComponentNames;
    this->ComponentNames = NULL;
    }
104

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
105
  this->SetName(NULL);
106
  this->SetInformation(NULL);
107
108
}

109
//----------------------------------------------------------------------------
110
void vtkAbstractArray::SetComponentName( vtkIdType component, const char *name )
111
  {
112
113
114
115
  if ( component < 0 || name == NULL )
    {
    return;
    }
116
  unsigned int index = static_cast<unsigned int>( component );
117
118
119
  if ( this->ComponentNames == NULL )
    {
    //delayed allocate
120
    this->ComponentNames = new vtkAbstractArray::vtkInternalComponentNames();
121
122
    }

123
  if ( index == this->ComponentNames->size() )
124
125
126
127
128
    {
    //the array isn't large enough, so we will resize
    this->ComponentNames->push_back( new vtkStdString(name) );
    return;
    }
129
  else if ( index > this->ComponentNames->size() )
130
    {
131
    this->ComponentNames->resize( index+1, NULL );
132
133
    }

134
  //replace an exisiting element
135
  vtkStdString *compName = this->ComponentNames->at(index);
136
137
138
  if ( !compName )
    {
    compName = new vtkStdString(name);
139
140
    this->ComponentNames->at(index) = compName;
    }
141
142
143
144
145
146
147
  else
    {
    compName->assign( name );
    }
  }

//----------------------------------------------------------------------------
148
const char* vtkAbstractArray::GetComponentName( vtkIdType component )
149
{
150
  unsigned int index = static_cast<unsigned int>( component );
151
  if ( !this->ComponentNames || component < 0 ||
152
    index >= this->ComponentNames->size() )
153
154
155
156
    {
    //make sure we have valid vector
    return NULL;
    }
157

158
  vtkStdString *compName = this->ComponentNames->at( index );
159
  return ( compName ) ? compName->c_str() : NULL;
160
  }
161

162
163
//----------------------------------------------------------------------------
bool vtkAbstractArray::HasAComponentName()
164
{
165
  return (this->ComponentNames) ? ( this->ComponentNames->size() > 0 ) : 0;
166
167
168
169
170
171
}

//----------------------------------------------------------------------------
int vtkAbstractArray::CopyComponentNames( vtkAbstractArray *da )
{
  if (  da && da != this && da->ComponentNames )
172
    {
173
174
175
    //clear the vector of the all data
    if ( !this->ComponentNames )
      {
176
      this->ComponentNames = new vtkAbstractArray::vtkInternalComponentNames();
177
178
179
      }

    //copy the passed in components
180
181
182
183
184
185
186
    for ( unsigned int i=0; i < this->ComponentNames->size(); ++i)
      {
      if ( this->ComponentNames->at(i) )
        {
        delete this->ComponentNames->at(i);
        }
      }
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
    this->ComponentNames->clear();
    this->ComponentNames->reserve( da->ComponentNames->size() );
    const char *name;
    for ( unsigned int i = 0; i < da->ComponentNames->size(); ++i )
      {
      name = da->GetComponentName(i);
      if ( name )
        {
        this->SetComponentName(i, name);
        }
      }
    return 1;
    }
  return 0;
}

203

Jeff Baumes's avatar
Jeff Baumes committed
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
//----------------------------------------------------------------------------
void vtkAbstractArray::SetInformation(vtkInformation *args)
{
  // Same as in vtkCxxSetObjectMacro, but no Modified() so that
  // this doesn't cause extra pipeline updates.
  vtkDebugMacro(<< this->GetClassName() << " (" << this
      << "): setting Information to " << args );
  if (this->Information != args)
    {
    vtkInformation* tempSGMacroVar = this->Information;
    this->Information = args;
    if (this->Information != NULL) { this->Information->Register(this); }
    if (tempSGMacroVar != NULL)
      {
      tempSGMacroVar->UnRegister(this);
      }
    }
}

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
223
224
//----------------------------------------------------------------------------
void vtkAbstractArray::GetTuples(vtkIdList* ptIds, vtkAbstractArray* aa)
225
{
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
226
  if (aa->GetNumberOfComponents() != this->GetNumberOfComponents())
227
    {
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
228
229
    vtkWarningMacro("Number of components for input and output do not match.");
    return;
230
    }
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
231
232
233
234
  // Here we give the slowest implementation. Subclasses can override
  // to use the knowledge about the data.
  vtkIdType num = ptIds->GetNumberOfIds();
  for (vtkIdType i = 0; i < num; i++)
235
    {
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
236
    aa->SetTuple(i, ptIds->GetId(i), this);
237
238
239
    }
}

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
240
//----------------------------------------------------------------------------
241
void vtkAbstractArray::GetTuples(vtkIdType p1, vtkIdType p2,
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
242
  vtkAbstractArray* aa)
243
{
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
244
  if (aa->GetNumberOfComponents() != this->GetNumberOfComponents())
245
    {
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
246
247
    vtkWarningMacro("Number of components for input and output do not match.");
    return;
248
    }
249

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
250
251
252
253
  // Here we give the slowest implementation. Subclasses can override
  // to use the knowledge about the data.
  vtkIdType num = p2 - p1 + 1;
  for (vtkIdType i = 0; i < num; i++)
254
    {
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
255
    aa->SetTuple(i, (p1+i), this);
256
    }
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
257
258
}

259
260
261
//----------------------------------------------------------------------------
void vtkAbstractArray::DeepCopy( vtkAbstractArray* da )
{
Burlen Loring's avatar
   
Burlen Loring committed
262
  if (da && da->HasInformation() && da!=this)
263
    {
Burlen Loring's avatar
   
Burlen Loring committed
264
    this->CopyInformation(da->GetInformation(),/*deep=*/1);
265
    }
266
  this->CopyComponentNames( da );
267
268
}

Burlen Loring's avatar
   
Burlen Loring committed
269
//----------------------------------------------------------------------------
270
int vtkAbstractArray::CopyInformation(vtkInformation* infoFrom, int deep)
Burlen Loring's avatar
   
Burlen Loring committed
271
272
{
  // Copy all keys. NOTE: subclasses rely on this.
273
  vtkInformation* myInfo=this->GetInformation();
Burlen Loring's avatar
   
Burlen Loring committed
274
275
  myInfo->Copy(infoFrom,deep);

276
277
278
279
280
281
282
283
284
285
  // Remove any keys we own that are not to be copied here.
  // For now, remove per-component metadata.
  if (myInfo->Has(PER_COMPONENT()))
    {
    myInfo->Remove(PER_COMPONENT());
    }
  if (myInfo->Has(DISCRETE_VALUES()))
    {
    myInfo->Remove(DISCRETE_VALUES());
    }
Burlen Loring's avatar
   
Burlen Loring committed
286
287
288
289

  return 1;
}

290
291
292
293
294
295
296
297
298
299
300
//----------------------------------------------------------------------------
vtkInformation* vtkAbstractArray::GetInformation()
{
  if ( ! this->Information )
    {
    vtkInformation* info = vtkInformation::New();
    this->SetInformation( info );
    info->FastDelete();
    }
  return this->Information;
}
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
301
302
303

//----------------------------------------------------------------------------
template <class T>
304
int vtkAbstractArrayGetDataTypeSize(T*)
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
305
306
{
  return sizeof(T);
307
308
}

309
int vtkAbstractArray::GetDataTypeSize(int type)
310
311
312
{
  switch (type)
    {
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
313
314
315
    vtkTemplateMacro(
      return vtkAbstractArrayGetDataTypeSize(static_cast<VTK_TT*>(0))
      );
316

317
    case VTK_BIT:
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
318
      return 0;
319
320
321
322
323
324
      break;

    case VTK_STRING:
      return 0;
      break;

325
326
327
328
    case VTK_UNICODE_STRING:
      return 0;
      break;

329
330
331
    default:
      vtkGenericWarningMacro(<<"Unsupported data type!");
    }
332

333
334
335
336
337
338
339
340
341
342
343
344
345
346
  return 1;
}

// ----------------------------------------------------------------------
vtkAbstractArray* vtkAbstractArray::CreateArray(int dataType)
{
  switch (dataType)
    {
    case VTK_BIT:
      return vtkBitArray::New();

    case VTK_CHAR:
      return vtkCharArray::New();

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
347
348
349
    case VTK_SIGNED_CHAR:
      return vtkSignedCharArray::New();

350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
    case VTK_UNSIGNED_CHAR:
      return vtkUnsignedCharArray::New();

    case VTK_SHORT:
      return vtkShortArray::New();

    case VTK_UNSIGNED_SHORT:
      return vtkUnsignedShortArray::New();

    case VTK_INT:
      return vtkIntArray::New();

    case VTK_UNSIGNED_INT:
      return vtkUnsignedIntArray::New();

    case VTK_LONG:
      return vtkLongArray::New();

    case VTK_UNSIGNED_LONG:
      return vtkUnsignedLongArray::New();

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
#if defined(VTK_TYPE_USE_LONG_LONG)
    case VTK_LONG_LONG:
      return vtkLongLongArray::New();

    case VTK_UNSIGNED_LONG_LONG:
      return vtkUnsignedLongLongArray::New();
#endif

#if defined(VTK_TYPE_USE___INT64)
    case VTK___INT64:
      return vtk__Int64Array::New();
      break;

# if defined(VTK_TYPE_CONVERT_UI64_TO_DOUBLE)
    case VTK_UNSIGNED___INT64:
      return vtkUnsigned__Int64Array::New();
      break;
# endif
#endif

391
392
393
394
395
396
397
398
    case VTK_FLOAT:
      return vtkFloatArray::New();

    case VTK_DOUBLE:
      return vtkDoubleArray::New();

    case VTK_ID_TYPE:
      return vtkIdTypeArray::New();
399

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
400
401
    case VTK_STRING:
      return vtkStringArray::New();
402

403
404
405
    case VTK_UNICODE_STRING:
      return vtkUnicodeStringArray::New();

406
407
408
    case VTK_VARIANT:
      return vtkVariantArray::New();

409
    default:
410
      break;
411
    }
412
413
414
415

  vtkGenericWarningMacro("Unsupported data type: " << dataType
                         << "! Setting to VTK_DOUBLE");
  return vtkDoubleArray::New();
416
}
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
417

418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
//---------------------------------------------------------------------------
template <typename T>
vtkVariant vtkAbstractArrayGetVariantValue(T* arr, vtkIdType index)
{
  return vtkVariant(arr[index]);
}

//----------------------------------------------------------------------------
vtkVariant vtkAbstractArray::GetVariantValue(vtkIdType i)
{
  vtkVariant val;
  switch(this->GetDataType())
    {
    vtkExtraExtendedTemplateMacro(val = vtkAbstractArrayGetVariantValue(
      static_cast<VTK_TT*>(this->GetVoidPointer(0)), i));
    }
  return val;
}

Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
437
438
439
440
441
442
443
444
445
446
447
448
449
450
//----------------------------------------------------------------------------
void vtkAbstractArray::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os,indent);

  const char* name = this->GetName();
  if (name)
    {
    os << indent << "Name: " << name << "\n";
    }
  else
    {
    os << indent << "Name: (none)\n";
    }
451
  os << indent << "Data type: " << this->GetDataTypeAsString() << "\n";
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
452
453
454
  os << indent << "Size: " << this->Size << "\n";
  os << indent << "MaxId: " << this->MaxId << "\n";
  os << indent << "NumberOfComponents: " << this->NumberOfComponents << endl;
455
456
457
458
  if ( this->ComponentNames )
    {
    os << indent << "ComponentNames: " << endl;
    vtkIndent nextIndent = indent.GetNextIndent();
459
    for ( unsigned int i=0; i < this->ComponentNames->size(); ++i )
460
461
462
463
      {
      os << nextIndent << i << " : " << this->ComponentNames->at(i) << endl;
      }
    }
464
465
466
467
468
  os << indent << "Information: " << this->Information << endl;
  if ( this->Information )
    {
    this->Information->PrintSelf( os, indent.GetNextIndent() );
    }
Utkarsh Ayachit's avatar
ENH:    
Utkarsh Ayachit committed
469
}
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489

//--------------------------------------------------------------------------
void vtkAbstractArray::InsertVariantValue(vtkIdType id, vtkVariant value)
{
  if ( id >= this->Size )
    {
    int status = this->Resize(id+1);
    if (!status)
      {
      vtkErrorMacro(<<"FAILED to extend array to accommodate new ID "
                    << id);
      return;
      }
    }
  if ( id > this->MaxId )
    {
    this->MaxId = id;
    }
  this->SetVariantValue(id, value);
}
490
491

//--------------------------------------------------------------------------
492
493
494
void vtkAbstractArray::GetProminentComponentValues(
  int comp, vtkVariantArray* values,
  double uncertainty, double minimumProminence)
495
{
496
  if (!values || comp < -1 || comp >= this->NumberOfComponents)
497
    {
498
    return;
499
    }
500
501
502
503
504
505

  values->Initialize();
  values->SetNumberOfComponents(comp < 0 ? this->NumberOfComponents : 1);

  bool justCreated = false;
  vtkInformation* info = this->GetInformation();
506
507
508
  const double* lastParams = info ?
    (info->Has(DISCRETE_VALUE_SAMPLE_PARAMETERS()) ?
     info->Get(DISCRETE_VALUE_SAMPLE_PARAMETERS()) : 0) : 0;
509
510
511
  if (comp >= 0 && info)
    {
    vtkInformationVector* infoVec = info->Get(PER_COMPONENT());
512
513
    if (!infoVec ||
      infoVec->GetNumberOfInformationObjects() < this->NumberOfComponents)
514
515
516
517
518
519
520
521
522
523
524
      {
      infoVec = vtkInformationVector::New();
      infoVec->SetNumberOfInformationObjects(this->NumberOfComponents);
      info->Set(PER_COMPONENT(), infoVec);
      infoVec->FastDelete();
      justCreated = true;
      }
    info = infoVec->GetInformationObject(comp);
    }
  if (info)
    {
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
    // Any insane parameter values map to
    // deterministic, exhaustive enumeration of all
    // distinct values:
    if (uncertainty < 0. || uncertainty > 1.)
      {
      uncertainty = 0.;
      }
    if (minimumProminence < 0. || minimumProminence > 1.)
      {
      minimumProminence = 0.;
      }
    // Are parameter values requesting more certainty in reporting or
    // that less-prominent values be reported? If so, recompute.
    bool tighterParams = lastParams ?
      (lastParams[0] > uncertainty ||
       lastParams[1] > minimumProminence ?
       true :
       false)
      : true;
544
545
    // Recompute discrete value set when the array has been
    // modified since the information was written.
546
547
548
    if (
      !info->Has(DISCRETE_VALUES()) || tighterParams ||
      this->GetMTime() > info->GetMTime() || justCreated)
549
      {
550
      this->UpdateDiscreteValueSet(uncertainty, minimumProminence);
551
552
553
554
555
556
557
558
559
      }
    }
  else
    {
    return;
    }

  vtkIdType len;
  const vtkVariant* vals = info->Get(DISCRETE_VALUES());
Sean McBride's avatar
Sean McBride committed
560
  if (vals != NULL)
561
562
563
564
565
566
567
568
569
570
    {
    len = info->Length(DISCRETE_VALUES());
    values->SetNumberOfTuples(len / values->GetNumberOfComponents());
    for (vtkIdType i = 0; i < len; ++i)
      {
      values->SetVariantValue(i, vals[i]);
      }
    }
}

571
//-----------------------------------------------------------------------------
572
573
namespace
{
574
575
template<typename T>
bool AccumulateSampleValues(
576
  T* array, int nc, vtkIdType begin, vtkIdType end,
577
578
  std::vector<std::set<T> >& uniques, std::set<std::vector<T> >& tupleUniques,
  unsigned int maxDiscreteValues)
579
580
581
{
  // number of discrete components remaining (tracked during iteration):
  int ndc = nc;
582
583
584
585
  std::pair<typename std::set<T>::iterator,bool> result;
  std::pair<typename std::set<std::vector<T> >::iterator,bool> tresult;
  std::vector<T> tuple;
  tuple.resize(nc);
586
587
588
589
590
591
592
593
594
595
  // Here we iterate over the components and add to their respective lists
  // of previously encountered values -- as long as there are not too many
  // values already in the list. We also accumulate each component's value
  // into a vtkVariantArray named tuple, which is added to the list of
  // unique vectors -- again assuming it is not already too long.
  for (vtkIdType i = begin; i < end && ndc; ++i)
    {
    // First, attempt a per-component insert.
    for (int j = 0; j < nc; ++ j)
      {
596
      if (uniques[j].size() > maxDiscreteValues)
597
        continue;
598
599
600
      T& val(array[i * nc + j]);
      tuple[j] = val;
      result = uniques[j].insert(val);
601
602
      if (result.second)
        {
603
        if (uniques[j].size() == maxDiscreteValues + 1)
604
605
606
607
608
          {
          -- ndc;
          }
        }
      }
609
    // Now, as long as no component has exceeded maxDiscreteValues unique
610
611
612
    // values, it is worth seeing whether the tuple as a whole is unique:
    if ( nc > 1 && ndc == nc )
      {
613
614
      tresult = tupleUniques.insert(tuple);
      (void)tresult; // nice to have when debugging.
615
616
617
618
      }
    }
  return ndc == 0;
}
619
620
621
622
623

//-----------------------------------------------------------------------------
template<typename U>
void SampleProminentValues(
  std::vector<std::vector<vtkVariant> >& uniques, vtkIdType maxId,
624
625
  int nc, vtkIdType nt, int blockSize, vtkIdType numberOfBlocks, U* ptr,
  unsigned int maxDiscreteValues)
626
627
628
629
630
631
632
633
634
635
{
  std::vector<std::set<U> > typeSpecificUniques;
  std::set<std::vector<U> > typeSpecificUniqueTuples;
  typeSpecificUniques.resize(nc);
  // I. Accumulate samples for all components plus the tuple,
  //    either for the full array or a random subset.
  if (numberOfBlocks * blockSize > maxId / 2)
    { // Awwww, just do the whole array already!
    AccumulateSampleValues(
      ptr, nc, 0, nt,
636
      typeSpecificUniques, typeSpecificUniqueTuples, maxDiscreteValues);
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
    }
  else
    { // Choose random blocks
    vtkNew<vtkMinimalStandardRandomSequence> seq;
    // test different blocks each time we're called:
    seq->SetSeed(seq->GetMTime() ^ 0xdeadbeef);
    vtkIdType totalBlockCount =
      nt / blockSize +
      (nt % blockSize ? 1 : 0);
    std::set<vtkIdType> startTuples;
    // Sort the list of blocks we'll search to maintain cache coherence.
    for (int i = 0; i < numberOfBlocks; ++ i, seq->Next())
      {
      vtkIdType startTuple =
        static_cast<vtkIdType>(seq->GetValue() * totalBlockCount) * blockSize;
      startTuples.insert(startTuple);
      }
    // Now iterate over the blocks, accumulating unique values and tuples.
    std::set<vtkIdType>::iterator blkIt;
    for (blkIt = startTuples.begin(); blkIt != startTuples.end(); ++blkIt)
      {
      vtkIdType startTuple = *blkIt;
      vtkIdType endTuple = startTuple + blockSize;
      endTuple = endTuple < nt ? endTuple : nt;
      bool endEarly = AccumulateSampleValues(
        ptr, nc, startTuple, endTuple,
663
        typeSpecificUniques, typeSpecificUniqueTuples, maxDiscreteValues);
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
      if (endEarly)
        break;
      }
    }

  // II. Convert type-specific sets of unique values into non-type-specific
  //     vectors of vtkVariants for storage in array information.

  // Handle per-component uniques first
  for (int i = 0; i < nc; ++i)
    {
    std::back_insert_iterator<std::vector<vtkVariant> > bi(uniques[i]);
    std::copy(typeSpecificUniques[i].begin(), typeSpecificUniques[i].end(), bi);
    }

  // Now squash any tuple-wide uniques into
  // the final entry of the outer vector.
  typename std::set<std::vector<U> >::iterator si;
  for (
    si = typeSpecificUniqueTuples.begin();
    si != typeSpecificUniqueTuples.end();
    ++si)
    {
    std::back_insert_iterator<std::vector<vtkVariant> > bi(uniques[nc]);
    std::copy(si->begin(), si->end(), bi);
    }
}
691
} // End anonymous namespace.
692

693
//-----------------------------------------------------------------------------
694
695
void vtkAbstractArray::UpdateDiscreteValueSet(
  double uncertainty, double minimumProminence)
696
{
697
698
699
  // For an array with T tuples and given uncertainty U and mininumum
  // prominence P, we sample N blocks of M tuples each, with
  // M*N = f(T; P, U) and f some sublinear function of T.
700
  // If every component plus all components taken together each have more than
701
  // MaxDiscreteValues distinct values, then we exit early.
702
703
704
  // M is chosen based on the number of bytes per tuple to maximize use of a
  // cache line (assuming a 64-byte cache line until kwsys::SystemInformation
  // or the like can provide a platform-independent way to query it).
705
  //
706
707
  // N is chosen to satisfy the requested uncertainty and prominence criteria
  // specified.
708
#define VTK_CACHE_LINE_SIZE 64
709
#define VTK_SAMPLE_FACTOR 5
710
  // I. Determine the granularity at which the array should be sampled.
711
  int numberOfComponentsWithProminentValues = 0;
712
713
714
  int nc = this->NumberOfComponents;
  int blockSize = VTK_CACHE_LINE_SIZE / (this->GetDataTypeSize() * nc);
  if (!blockSize) blockSize = 4;
715
  double logfac = 1.;
716
  vtkIdType nt = this->GetNumberOfTuples();
717
718
  if (this->MaxId > 0)
    {
719
    logfac = -log(uncertainty * minimumProminence) / minimumProminence;
720
721
722
723
724
725
726
727
728
    if (logfac < 0)
      {
      logfac = -logfac;
      }
    }
  vtkIdType numberOfSampleTuples;
  if (vtkMath::IsInf(logfac))
    {
    numberOfSampleTuples = nt;
729
    }
730
731
732
733
  else
    {
    numberOfSampleTuples = VTK_SAMPLE_FACTOR * logfac;
    }
734
735
736
737
  /*
  // Theoretically, we should discard values or tuples that recur fewer
  // than minFreq times in our sample, but in practice this involves
  // counting and communication that slow us down.
738
739
  vtkIdType minFreq = static_cast<vtkIdType>(
    numberOfSampleTuples * minimumProminence / 2);
740
    */
741
742
743
  vtkIdType numberOfBlocks =
    numberOfSampleTuples / blockSize +
    (numberOfSampleTuples % blockSize ? 1 : 0);
Zack Galbreath's avatar
Zack Galbreath committed
744
745
  if (static_cast<unsigned int>(numberOfBlocks * blockSize) <
      2 * this->MaxDiscreteValues)
746
747
    {
    numberOfBlocks =
748
749
      2 * this->MaxDiscreteValues / blockSize +
      (2 * this->MaxDiscreteValues % blockSize ? 1 : 0);
750
    }
751
752
753
754
755
756
757
  // II. Sample the array.
  std::vector<std::vector<vtkVariant> > uniques(nc > 1 ? nc + 1 : nc);
  switch(this->GetDataType())
    {
    vtkSuperExtraExtendedTemplateMacro(
      SampleProminentValues(
        uniques, this->MaxId, nc, nt, blockSize, numberOfBlocks,
758
759
        static_cast<VTK_TT*>(this->GetVoidPointer(0)),
        this->MaxDiscreteValues));
760
761
762
  default:
    vtkErrorMacro("Array type " << this->GetClassName() << " not supported.");
    break;
763
    }
764
765

  // III. Store the results in the array's vtkInformation.
766
  int c;
767
  vtkInformationVector* iv;
768
769
  for (c = 0; c < nc; ++c)
    {
770
    if (uniques[c].size() <= this->MaxDiscreteValues)
771
      {
772
      ++ numberOfComponentsWithProminentValues;
773
774
775
776
777
778
779
780
781
      iv = this->GetInformation()->Get(PER_COMPONENT());
      if (!iv)
        {
        vtkNew<vtkInformationVector> infoVec;
        infoVec->SetNumberOfInformationObjects(this->NumberOfComponents);
        this->GetInformation()->Set(PER_COMPONENT(), infoVec.GetPointer());
        iv = this->GetInformation()->Get(PER_COMPONENT());
        }
      iv->GetInformationObject(c)->Set(
782
783
        DISCRETE_VALUES(), &uniques[c][0],
        static_cast<int>(uniques[c].size()));
784
785
786
      }
    else
      {
787
788
789
790
791
792
      iv = this->GetInformation()->Get(PER_COMPONENT());
      if (iv)
        {
        iv->GetInformationObject(c)->Remove(
          DISCRETE_VALUES());
        }
793
794
      }
    }
795
  if (nc > 1 &&
796
    uniques[nc].size() <= this->MaxDiscreteValues * nc)
797
    {
798
    ++ numberOfComponentsWithProminentValues;
799
    this->GetInformation()->Set(
800
801
      DISCRETE_VALUES(), &uniques[nc][0],
      static_cast<int>(uniques[nc].size()));
802
803
804
805
806
    }
  else
    { // Remove the key
    this->GetInformation()->Remove(DISCRETE_VALUES());
    }
807
808
809
810
811
812
813
814

  // Always store the sample parameters; this lets us know not to
  // re-run the sampling algorithm.
  double params[2];
  params[0] = uncertainty;
  params[1] = minimumProminence;
  this->GetInformation()->Set(
    DISCRETE_VALUE_SAMPLE_PARAMETERS(), params, 2);
815
}