VTK  9.2.6
vtkStaticEdgeLocatorTemplate.h
Go to the documentation of this file.
1/*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkStaticEdgeLocatorTemplate.h
5
6 Copyright (c) Kitware, Inc.
7 All rights reserved.
8 See LICENSE file 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=========================================================================*/
62
63#ifndef vtkStaticEdgeLocatorTemplate_h
64#define vtkStaticEdgeLocatorTemplate_h
65
66#include <algorithm>
67#include <vector>
68
75template <typename TId, typename TED>
77{
78 TId V0;
79 TId V1;
80 TED Data;
81
82 // Default constructor - nothing needs to be done
83 EdgeTuple() = default;
84
85 // Construct an edge and ensure that the edge tuple (vo,v1) is
86 // specified such that (v0<v1).
87 EdgeTuple(TId v0, TId v1, TED data)
88 : V0(v0)
89 , V1(v1)
90 , Data(data)
91 {
92 if (this->V0 > this->V1)
93 {
94 std::swap(this->V0, this->V1);
95 }
96 }
97
98 void Define(TId v0, TId v1)
99 {
100 if (v0 < v1)
101 {
102 this->V0 = v0;
103 this->V1 = v1;
104 }
105 else
106 {
107 this->V0 = v1;
108 this->V1 = v0;
109 }
110 }
111
112 bool operator==(const EdgeTuple& et) const
113 {
114 return ((this->V0 == et.V0 && this->V1 == et.V1) ? true : false);
115 }
116
117 bool operator!=(const EdgeTuple& et) const
118 {
119 return ((this->V0 != et.V0 || this->V1 != et.V1) ? true : false);
120 }
121
122 bool IsEdge(TId v0, TId v1) const
123 {
124 if (v0 < v1) // ordered properly
125 {
126 return ((this->V0 == v0 && this->V1 == v1) ? true : false);
127 }
128 else // swap comparison required
129 {
130 return ((this->V0 == v1 && this->V1 == v0) ? true : false);
131 }
132 }
133 // Sort on v0 first, then v1.
134 bool operator<(const EdgeTuple& tup) const
135 {
136 if (this->V0 < tup.V0)
137 return true;
138 if (tup.V0 < this->V0)
139 return false;
140 if (this->V1 < tup.V1)
141 return true;
142 return false;
143 }
144};
145
150template <typename IDType, typename EdgeData>
152{
153public:
155
160
165 : NumEdges(0)
166 , NumEdgesPerBin(5)
167 , EdgeArray(nullptr)
168 , EdgeOffsets(nullptr)
169 , MinV0(0)
170 , MaxV0(0)
171 , V0Range(0)
172 , NDivs(0)
173 , MergeArray(nullptr)
174 {
175 }
176
182
186 IDType GetNumberOfEdges() { return this->NumEdges; }
187
200 const IDType* MergeEdges(vtkIdType numEdges, EdgeTupleType* edgeArray, vtkIdType& numUniqueEdges);
201
211
218 IDType IsInsertedEdge(IDType v0, IDType v1) const
219 {
220 // Ensure that data is consistent with what is expected.
221 IDType V0, V1;
222 if (v0 < v1)
223 {
224 V0 = v0;
225 V1 = v1;
226 }
227 else
228 {
229 V0 = v1;
230 V1 = v0;
231 }
232 if (V0 < this->MinV0 || V0 > this->MaxV0)
233 {
234 return -1;
235 }
236
237 // Bin and search for matching edge
238 IDType curBin = this->HashBin(V0);
239 IDType curId = this->EdgeOffsets[curBin];
240 IDType curV0 = this->EdgeArray[curId].V0;
241 IDType num = this->GetNumberOfEdgesInBin(curBin);
242 for (IDType i = 0; i < num; ++i)
243 {
244 while (curV0 < V0)
245 {
246 curId++;
247 curV0 = this->EdgeArray[curId].V0;
248 }
249 if (curV0 > V0)
250 {
251 return -1;
252 }
253 else // matched v0, now find v1
254 {
255 IDType curV1 = this->EdgeArray[curId].V1;
256 while (curV1 < V1)
257 {
258 curId++;
259 curV1 = this->EdgeArray[curId].V1;
260 }
261 if (curV1 > V1)
262 {
263 return -1;
264 }
265 else
266 {
267 return curId;
268 }
269 }
270 } // loop over maximum possible candidates
271
272 // Nothing found
273 return -1;
274 }
275
280 const EdgeTupleType& GetEdge(IDType i) const { return (*this->EdgeArray)[i]; }
281
282protected:
284
285 // Support BuildLocator usage pattern
288 IDType* EdgeOffsets;
289 IDType MinV0;
290 IDType MaxV0;
291 IDType V0Range;
292 int NDivs;
293
294 IDType HashBin(IDType v) const { return ((v - this->MinV0) / this->NumEdgesPerBin); }
295
296 IDType GetNumberOfEdgesInBin(IDType bin) const
297 {
298 return (this->EdgeOffsets[bin + 1] - this->EdgeOffsets[bin]);
299 }
300
301 // Support MergeEdges usage pattern
303 std::vector<IDType> MergeOffsets;
304
305private:
307 void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
308};
309
310#include "vtkStaticEdgeLocatorTemplate.txx"
311
312#endif
313// VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h
IDType V0Range
Some convenient typedefs.
IDType MinV0
Some convenient typedefs.
vtkIdType NumEdgesPerBin
Some convenient typedefs.
IDType * EdgeOffsets
Some convenient typedefs.
const IDType * MergeEdges(vtkIdType numEdges, EdgeTupleType *edgeArray, vtkIdType &numUniqueEdges)
This method sorts (in place) an array of EdgeTupleType (of length numEdges) into separate groups,...
IDType GetNumberOfEdgesInBin(IDType bin) const
Some convenient typedefs.
IDType MaxV0
Some convenient typedefs.
~vtkStaticEdgeLocatorTemplate()
Delete internal offset array.
IDType IsInsertedEdge(IDType v0, IDType v1) const
Return the id of the edge indicated.
std::vector< IDType > MergeOffsets
Some convenient typedefs.
IDType HashBin(IDType v) const
Some convenient typedefs.
const EdgeTupleType & GetEdge(IDType i) const
Return the ith edge in the edge array.
IDType GetNumberOfEdges()
Return the number of edges in the edge array.
vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray)
This method constructs the edge locator to be used when searching for edges.
vtkIdType NumEdges
Some convenient typedefs.
EdgeTupleType * EdgeArray
Some convenient typedefs.
EdgeTuple< IDType, EdgeData > EdgeTupleType
Some convenient typedefs.
EdgeTupleType * MergeArray
Some convenient typedefs.
Definition of an edge tuple.
bool IsEdge(TId v0, TId v1) const
bool operator==(const EdgeTuple &et) const
EdgeTuple(TId v0, TId v1, TED data)
EdgeTuple()=default
bool operator<(const EdgeTuple &tup) const
bool operator!=(const EdgeTuple &et) const
void Define(TId v0, TId v1)
int vtkIdType
Definition vtkType.h:332