VTK  9.0.1
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 =========================================================================*/
61 #ifndef vtkStaticEdgeLocatorTemplate_h
62 #define vtkStaticEdgeLocatorTemplate_h
63 
64 #include <algorithm>
65 #include <vector>
66 
73 template <typename TId, typename TED>
74 struct EdgeTuple
75 {
76  TId V0;
77  TId V1;
78  TED T;
79 
80  // Default constructor - nothing needs to be done
81  EdgeTuple() {}
82 
83  // Construct an edge and ensure that the edge tuple (vo,v1) is
84  // specified such that (v0<v1).
85  EdgeTuple(TId v0, TId v1, TED data)
86  : V0(v0)
87  , V1(v1)
88  , T(data)
89  {
90  if (this->V0 > this->V1)
91  {
92  TId tmp = this->V0;
93  this->V0 = this->V1;
94  this->V1 = tmp;
95  }
96  }
97 
98  bool operator==(const EdgeTuple& et) const
99  {
100  return ((this->V0 == et.V0 && this->V1 == et.V1) ? true : false);
101  }
102 
103  bool IsEdge(TId v0, TId v1) const
104  {
105  if (v0 < v1) // ordered properly
106  {
107  return ((this->V0 == v0 && this->V1 == v1) ? true : false);
108  }
109  else // swap comparison required
110  {
111  return ((this->V0 == v1 && this->V1 == v0) ? true : false);
112  }
113  }
114  // Sort on v0 first, then v1.
115  bool operator<(const EdgeTuple& tup) const
116  {
117  if (this->V0 < tup.V0)
118  return true;
119  if (tup.V0 < this->V0)
120  return false;
121  if (this->V1 < tup.V1)
122  return true;
123  return false;
124  }
125 };
126 
133 template <typename TId, typename TED>
135 {
136  TId V0;
137  TId V1;
138  TId EId; // originating edge id
139  TED T;
140 
141  // Default constructor - nothing needs to be done
143 
144  // Construct an edge and ensure that the edge tuple (vo,v1) is
145  // specified such that (v0<v1).
146  MergeTuple(TId v0, TId v1, TId eid, TED data)
147  : V0(v0)
148  , V1(v1)
149  , EId(eid)
150  , T(data)
151  {
152  if (this->V0 > this->V1)
153  {
154  TId tmp = this->V0;
155  this->V0 = this->V1;
156  this->V1 = tmp;
157  }
158  }
159 
160  bool operator==(const MergeTuple& et) const
161  {
162  return ((this->V0 == et.V0 && this->V1 == et.V1) ? true : false);
163  }
164 
165  bool operator!=(const MergeTuple& et) const
166  {
167  return ((this->V0 != et.V0 || this->V1 != et.V1) ? true : false);
168  }
169 
170  // Sort on v0 first, then v1.
171  bool operator<(const MergeTuple& tup) const
172  {
173  if (this->V0 < tup.V0)
174  return true;
175  if (tup.V0 < this->V0)
176  return false;
177  if (this->V1 < tup.V1)
178  return true;
179  return false;
180  }
181 };
182 
187 template <typename IDType, typename EdgeData>
189 {
190 public:
192 
197  //@)
198 
203  : NumEdges(0)
204  , NumEdgesPerBin(5)
205  , EdgeArray(nullptr)
206  , EdgeOffsets(nullptr)
207  , MinV0(0)
208  , MaxV0(0)
209  , V0Range(0)
210  , NDivs(0)
211  , MergeArray(nullptr)
212  {
213  }
214 
220 
224  IDType GetNumberOfEdges() { return this->NumEdges; }
225 
237  const IDType* MergeEdges(
238  vtkIdType numEdges, MergeTupleType* edgeArray, vtkIdType& numUniqueEdges);
239 
248  vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType* edgeArray);
249 
256  IDType IsInsertedEdge(IDType v0, IDType v1) const
257  {
258  // Ensure that data is consistent with what is expected.
259  IDType V0, V1;
260  if (v0 < v1)
261  {
262  V0 = v0;
263  V1 = v1;
264  }
265  else
266  {
267  V0 = v1;
268  V1 = v0;
269  }
270  if (V0 < this->MinV0 || V0 > this->MaxV0)
271  {
272  return -1;
273  }
274 
275  // Bin and search for matching edge
276  IDType curBin = this->HashBin(V0);
277  IDType curId = this->EdgeOffsets[curBin];
278  IDType curV0 = this->EdgeArray[curId].V0;
279  IDType num = this->GetNumberOfEdgesInBin(curBin);
280  for (IDType i = 0; i < num; ++i)
281  {
282  while (curV0 < V0)
283  {
284  curId++;
285  curV0 = this->EdgeArray[curId].V0;
286  }
287  if (curV0 > V0)
288  {
289  return -1;
290  }
291  else // matched v0, now find v1
292  {
293  IDType curV1 = this->EdgeArray[curId].V1;
294  while (curV1 < V1)
295  {
296  curId++;
297  curV1 = this->EdgeArray[curId].V1;
298  }
299  if (curV1 > V1)
300  {
301  return -1;
302  }
303  else
304  {
305  return curId;
306  }
307  }
308  } // loop over maximum possible candidates
309 
310  // Nothing found
311  return -1;
312  }
313 
318  const EdgeTupleType& GetEdge(IDType i) const { return (*this->EdgeArray)[i]; }
319 
320 protected:
322 
323  // Support BuildLocator usage pattern
326  IDType* EdgeOffsets;
327  IDType MinV0;
328  IDType MaxV0;
329  IDType V0Range;
330  int NDivs;
331 
332  IDType HashBin(IDType v) const { return ((v - this->MinV0) / this->NumEdgesPerBin); }
333 
334  IDType GetNumberOfEdgesInBin(IDType bin) const
335  {
336  return (this->EdgeOffsets[bin + 1] - this->EdgeOffsets[bin]);
337  }
338 
339  // Support MergeEdges usage pattern
341  std::vector<IDType> MergeOffsets;
342 
343 private:
345  void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
346 };
347 
348 #include "vtkStaticEdgeLocatorTemplate.txx"
349 
350 #endif
351 // VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h
~vtkStaticEdgeLocatorTemplate()
Delete internal offset array.
bool IsEdge(TId v0, TId v1) const
bool operator<(const MergeTuple &tup) const
const IDType * MergeEdges(vtkIdType numEdges, MergeTupleType *edgeArray, vtkIdType &numUniqueEdges)
This method sorts (in place) an array of MergeTupleType (of length numEdges) into separate groups...
bool operator==(const MergeTuple &et) const
Templated on types of ids defining an edge, and any data associated with the edge.
Definition of an edge tuple using for creating an edge merge table.
const EdgeTupleType & GetEdge(IDType i) const
Return the ith edge in the edge array.
vtkIdType NumEdgesPerBin
Some convenient typedefs.
IDType GetNumberOfEdges()
Return the number of edges in the edge array.
vtkIdType NumEdges
Some convenient typedefs.
int vtkIdType
Definition: vtkType.h:338
IDType GetNumberOfEdgesInBin(IDType bin) const
Some convenient typedefs.
std::vector< IDType > MergeOffsets
Some convenient typedefs.
EdgeTuple< IDType, EdgeData > EdgeTupleType
Some convenient typedefs.
EdgeTupleType * EdgeArray
Some convenient typedefs.
EdgeTuple(TId v0, TId v1, TED data)
IDType MinV0
Some convenient typedefs.
vtkStaticEdgeLocatorTemplate()
Construct an empty edge locator.
vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray)
This method constructs the edge locator to be used when searching for edges.
MergeTuple< IDType, EdgeData > MergeTupleType
Some convenient typedefs.
Definition of an edge tuple.
IDType IsInsertedEdge(IDType v0, IDType v1) const
Return the id of the edge indicated.
IDType * EdgeOffsets
Some convenient typedefs.
bool operator==(const EdgeTuple &et) const
int NDivs
Some convenient typedefs.
bool operator!=(const MergeTuple &et) const
IDType V0Range
Some convenient typedefs.
bool operator<(const EdgeTuple &tup) const
MergeTuple(TId v0, TId v1, TId eid, TED data)
IDType MaxV0
Some convenient typedefs.
IDType HashBin(IDType v) const
Some convenient typedefs.
MergeTupleType * MergeArray
Some convenient typedefs.