vtkGenericDataArrayLookupHelper.h 5.22 KB
Newer Older
1
2
3
/*=========================================================================

  Program:   Visualization Toolkit
4
  Module:    vtkGenericDataArrayLookupHelper.h
5
6
7
8
9
10
11
12
13
14

  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.

=========================================================================*/
15
16
17
18
19
20
/**
 * @class   vtkGenericDataArrayLookupHelper
 * @brief   internal class used by
 * vtkGenericDataArray to support LookupValue.
 *
*/
21

22
23
#ifndef vtkGenericDataArrayLookupHelper_h
#define vtkGenericDataArrayLookupHelper_h
24
25

#include <algorithm>
26
#include <cmath>
27
28
29
30
#include "vtkIdList.h"

namespace detail
{
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// this can be removed when C++11 is required.
template< class T > struct remove_const { typedef T type; };
template< class T > struct remove_const<const T> { typedef T type; };

template <typename T, bool> struct has_NaN;

template <typename T>
struct has_NaN<T, true>
{
static bool isnan(T x)
{
  return std::isnan(x);
}
};

template <typename T>
struct has_NaN<T, false>
{
  static bool isnan(T)
  {
    return false;
  }
};

template <typename T>
bool isnan(T x)
{
  // Select the correct partially specialized type.
  return has_NaN<T, std::numeric_limits<T>::has_quiet_NaN>::isnan(x);
}
61
62
63
}

template <class ArrayTypeT>
64
class vtkGenericDataArrayLookupHelper
65
66
67
{
public:
  typedef ArrayTypeT ArrayType;
68
  typedef typename ArrayType::ValueType ValueType;
69
70

  // Constructor.
71
  vtkGenericDataArrayLookupHelper()
72
73
    : AssociatedArray(nullptr), SortedArray(nullptr),
    FirstValue(nullptr), SortedArraySize(0)
74
75
  {
  }
76
  ~vtkGenericDataArrayLookupHelper()
77
  {
78
    this->ClearLookup();
79
  }
80

81
82
83
  void SetArray(ArrayTypeT *array)
  {
    if (this->AssociatedArray != array)
84
    {
85
86
      this->ClearLookup();
      this->AssociatedArray = array;
87
    }
88
89
  }

90
  vtkIdType LookupValue(ValueType elem)
91
  {
92
    this->UpdateLookup();
93
94
95
96
97
98

    if (this->SortedArraySize == 0)
    {
      return -1;
    }

99
    if(::detail::isnan(elem))
100
    {
101
      if(this->SortedArray && ::detail::isnan(this->SortedArray->Value))
102
103
104
105
106
107
108
109
110
      {
        return this->SortedArray->Index;
      }
      else
      {
        return -1;
      }
    }

111
112
113
    ValueWithIndex temp;
    temp.Value = elem;
    ValueWithIndex* pos =
114
115
      std::lower_bound(this->FirstValue,
                     this->SortedArray + this->SortedArraySize, temp);
116
    if (pos == (this->SortedArray + this->SortedArraySize))
117
    {
118
      return -1;
119
    }
120
    if (pos->Value != elem)
121
    {
122
123
      return -1;
    }
124
125
    return pos->Index;
  }
126

127
  void LookupValue(ValueType elem, vtkIdList* ids)
128
  {
129
    ids->Reset();
130
    this->UpdateLookup();
131
132

    if (this->SortedArraySize == 0)
133
    {
134
135
136
     return;
    }

137
    if(::detail::isnan(elem))
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
    {
      ValueWithIndex *range = this->SortedArray;
      while (range != this->FirstValue)
      {
        ids->InsertNextId(range->Index);
        ++range;
      }
    }
    else
    {
      ValueWithIndex temp;
      temp.Value = elem;
      std::pair<ValueWithIndex*, ValueWithIndex*> range =
        std::equal_range(this->FirstValue,
                         this->SortedArray + this->SortedArraySize, temp);
      while (range.first != range.second)
      {
        // assert(range.first->Value == elem);
        ids->InsertNextId(range.first->Index);
        ++range.first;
      }
159
    }
160
  }
161

162
163
164
165
  //@{
  /**
   * Release any allocated memory for internal data-structures.
   */
166
  void ClearLookup()
167
  {
168
    free(this->SortedArray);
169
    this->SortedArray = nullptr;
170
    this->SortedArraySize = 0;
171
  }
172
  //@}
173
174

private:
175
176
  vtkGenericDataArrayLookupHelper(const vtkGenericDataArrayLookupHelper&) = delete;
  void operator=(const vtkGenericDataArrayLookupHelper&) = delete;
177
178

  struct ValueWithIndex
179
  {
180
    typename ::detail::remove_const<ValueType>::type Value;
181
182
    vtkIdType Index;
    inline bool operator<(const ValueWithIndex& other) const
183
    {
184
      return this->Value < other.Value;
185
186
    }
  };
187

188
189
  static bool isnan(const ValueWithIndex &tmp)
  {
190
    return ::detail::isnan(tmp.Value);
191
192
  }

193
  void UpdateLookup()
194
  {
195
    if (!this->AssociatedArray || this->SortedArray)
196
    {
197
      return;
198
    }
199

200
    int numComps = this->AssociatedArray->GetNumberOfComponents();
201
    this->SortedArraySize =
202
        this->AssociatedArray->GetNumberOfTuples() * numComps;
203

204
    if (this->SortedArraySize == 0)
205
    {
206
      return;
207
    }
208

209
210
    this->SortedArray = reinterpret_cast<ValueWithIndex*>(
          malloc(this->SortedArraySize * sizeof(ValueWithIndex)));
211
    for (vtkIdType cc = 0, max = this->AssociatedArray->GetNumberOfValues();
212
         cc < max; ++cc)
213
    {
214
      ValueWithIndex& item = this->SortedArray[cc];
215
      item.Value = this->AssociatedArray->GetValue(cc);
216
      item.Index = cc;
217
    }
218
219
    this->FirstValue = std::partition(this->SortedArray, this->SortedArray + this->SortedArraySize, isnan);
    std::sort(this->FirstValue, this->SortedArray + this->SortedArraySize);
220
  }
221

222
  ArrayTypeT *AssociatedArray;
223
  ValueWithIndex* SortedArray;
224
  ValueWithIndex* FirstValue;
225
226
227
228
  vtkIdType SortedArraySize;
};

#endif
229
// VTK-HeaderTest-Exclude: vtkGenericDataArrayLookupHelper.h