VTK  9.1.0
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=========================================================================*/
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
Templated on types of ids defining an edge, and any data associated with the edge.
int NDivs
Some convenient typedefs.
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