VTK  9.3.1
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 
195  vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType* edgeArray);
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
269  EdgeTupleType* EdgeArray;
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
284  EdgeTupleType* MergeArray;
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
~vtkStaticEdgeLocatorTemplate()
Delete internal offset array.
bool IsEdge(TId v0, TId v1) const
IDType IsInsertedEdge(IDType v0, IDType v1) const
Return the id of the edge indicated.
Templated on types of ids defining an edge, and any data associated with the edge.
EdgeTuple()=default
const IDType * MergeEdges(vtkIdType numEdges, EdgeTupleType *edgeArray, vtkIdType &numUniqueEdges)
This method sorts (in place) an array of EdgeTupleType (of length numEdges) into separate groups...
void Define(TId v0, TId v1)
vtkIdType NumEdgesPerBin
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 NumEdges
Some convenient typedefs.
bool operator<(const EdgeTuple &tup) const
int vtkIdType
Definition: vtkType.h:315
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)
bool operator!=(const EdgeTuple &et) const
IDType MinV0
Some convenient typedefs.
vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray)
This method constructs the edge locator to be used when searching for edges.
IDType GetNumberOfEdgesInBin(IDType bin) const
Some convenient typedefs.
EdgeTupleType * MergeArray
Some convenient typedefs.
bool operator==(const EdgeTuple &et) const
Definition of an edge tuple.
IDType * EdgeOffsets
Some convenient typedefs.
int NDivs
Some convenient typedefs.
IDType V0Range
Some convenient typedefs.
IDType HashBin(IDType v) const
Some convenient typedefs.
IDType MaxV0
Some convenient typedefs.