VTK  9.0.3
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 
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
Templated on types of ids defining an edge, and any data associated with the edge.
vtkStaticEdgeLocatorTemplate()
Construct an empty edge locator.
const IDType * MergeEdges(vtkIdType numEdges, MergeTupleType *edgeArray, vtkIdType &numUniqueEdges)
This method sorts (in place) an array of MergeTupleType (of length numEdges) into separate groups,...
IDType GetNumberOfEdgesInBin(IDType bin) const
~vtkStaticEdgeLocatorTemplate()
Delete internal offset array.
IDType IsInsertedEdge(IDType v0, IDType v1) const
Return the id of the edge indicated.
const EdgeTupleType & GetEdge(IDType i) const
Return the ith edge in the edge array.
MergeTuple< IDType, EdgeData > MergeTupleType
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.
EdgeTuple< IDType, EdgeData > EdgeTupleType
Some convenient typedefs.
@ data
Definition: vtkX3D.h:321
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)
bool operator<(const EdgeTuple &tup) const
Definition of an edge tuple using for creating an edge merge table.
bool operator==(const MergeTuple &et) const
MergeTuple(TId v0, TId v1, TId eid, TED data)
bool operator<(const MergeTuple &tup) const
bool operator!=(const MergeTuple &et) const
int vtkIdType
Definition: vtkType.h:338