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 
75 template <typename TId, typename TED>
76 struct EdgeTuple
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 
150 template <typename IDType, typename EdgeData>
152 {
153 public:
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 
282 protected:
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 
305 private:
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.
IDType GetNumberOfEdgesInBin(IDType bin) const
Some convenient typedefs.
IDType MaxV0
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,...
~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.
std::vector< IDType > MergeOffsets
Some convenient typedefs.
IDType HashBin(IDType v) const
Some convenient typedefs.
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.
@ 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)
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