VTK  9.3.20240328
vtkStaticEdgeLocatorTemplate.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-License-Identifier: BSD-3-CLAUSE
51 #ifndef vtkStaticEdgeLocatorTemplate_h
52 #define vtkStaticEdgeLocatorTemplate_h
53 
54 #include "vtkABINamespace.h"
55 
56 #include <algorithm>
57 #include <vector>
58 
65 VTK_ABI_NAMESPACE_BEGIN
66 template <typename TId, typename TED>
67 struct EdgeTuple
68 {
69  TId V0;
70  TId V1;
71  TED Data;
72 
73  // Default constructor - nothing needs to be done
74  EdgeTuple() = default;
75 
76  // Construct an edge and ensure that the edge tuple (vo,v1) is
77  // specified such that (v0<v1).
78  EdgeTuple(TId v0, TId v1, TED data)
79  : V0(v0)
80  , V1(v1)
81  , Data(data)
82  {
83  if (this->V0 > this->V1)
84  {
85  std::swap(this->V0, this->V1);
86  }
87  }
88 
89  void Define(TId v0, TId v1)
90  {
91  if (v0 < v1)
92  {
93  this->V0 = v0;
94  this->V1 = v1;
95  }
96  else
97  {
98  this->V0 = v1;
99  this->V1 = v0;
100  }
101  }
102 
103  bool operator==(const EdgeTuple& et) const { return this->V0 == et.V0 && this->V1 == et.V1; }
104 
105  bool operator!=(const EdgeTuple& et) const { return this->V0 != et.V0 || this->V1 != et.V1; }
106 
107  bool IsEdge(TId v0, TId v1) const
108  {
109  if (v0 < v1) // ordered properly
110  {
111  return this->V0 == v0 && this->V1 == v1;
112  }
113  else // swap comparison required
114  {
115  return this->V0 == v1 && this->V1 == v0;
116  }
117  }
118  // Sort on v0 first, then v1.
119  bool operator<(const EdgeTuple& tup) const
120  {
121  if (this->V0 < tup.V0)
122  return true;
123  if (tup.V0 < this->V0)
124  return false;
125  if (this->V1 < tup.V1)
126  return true;
127  return false;
128  }
129 };
130 
135 template <typename IDType, typename EdgeData>
137 {
138 public:
140 
145 
150  : NumEdges(0)
151  , NumEdgesPerBin(5)
152  , EdgeArray(nullptr)
153  , EdgeOffsets(nullptr)
154  , MinV0(-1)
155  , MaxV0(-1)
156  , V0Range(0)
157  , NDivs(0)
158  , MergeArray(nullptr)
159  {
160  }
161 
167 
171  IDType GetNumberOfEdges() { return this->NumEdges; }
172 
185  const IDType* MergeEdges(vtkIdType numEdges, EdgeTupleType* edgeArray, vtkIdType& numUniqueEdges);
186 
196 
203  IDType IsInsertedEdge(IDType v0, IDType v1) const
204  {
205  // Ensure that BuildLocator has been called by checking MinV0, MaxV0
206  if (this->MinV0 < 0 || this->MaxV0 < 0)
207  {
208  return -1;
209  }
210  // Ensure that data is consistent with what is expected.
211  if (v0 > v1)
212  {
213  std::swap(v0, v1);
214  }
215  if (v0 < this->MinV0 || v0 > this->MaxV0)
216  {
217  return -1;
218  }
219 
220  // Bin and search for matching edge
221  const IDType curBin = this->HashBin(v0);
222  const IDType num = this->GetNumberOfEdgesInBin(curBin);
223  // check if there are no edges
224  if (num < 1)
225  {
226  return -1;
227  }
228  IDType curId = this->EdgeOffsets[curBin];
229  IDType curV0 = this->EdgeArray[curId].V0;
230  while (curV0 < v0)
231  {
232  curId++;
233  curV0 = this->EdgeArray[curId].V0;
234  }
235  if (curV0 > v0)
236  {
237  return -1;
238  }
239  else // matched v0, now find v1
240  {
241  IDType curV1 = this->EdgeArray[curId].V1;
242  while (curV1 < v1)
243  {
244  curId++;
245  curV1 = this->EdgeArray[curId].V1;
246  }
247  if (curV1 > v1)
248  {
249  return -1;
250  }
251  else
252  {
253  return curId;
254  }
255  }
256  }
257 
262  const EdgeTupleType& GetEdge(IDType i) const { return (*this->EdgeArray)[i]; }
263 
264 protected:
266 
267  // Support BuildLocator usage pattern
270  IDType* EdgeOffsets;
271  IDType MinV0;
272  IDType MaxV0;
273  IDType V0Range;
274  int NDivs;
275 
276  IDType HashBin(IDType v) const { return ((v - this->MinV0) / this->NumEdgesPerBin); }
277 
278  IDType GetNumberOfEdgesInBin(IDType bin) const
279  {
280  return (this->EdgeOffsets[bin + 1] - this->EdgeOffsets[bin]);
281  }
282 
283  // Support MergeEdges usage pattern
285  std::vector<IDType> MergeOffsets;
286 
287 private:
289  void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
290 };
291 
292 VTK_ABI_NAMESPACE_END
293 #include "vtkStaticEdgeLocatorTemplate.txx"
294 
295 #endif
296 // 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:315
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:315