VTK
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 <vector>
65 #include <algorithm>
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), V1(v1), T(data)
87  {
88  if ( this->V0 > this->V1 )
89  {
90  TId tmp = this->V0;
91  this->V0 = this->V1;
92  this->V1 = tmp;
93  }
94  }
95 
96  bool operator==(const EdgeTuple& et) const
97  { return ( (this->V0 == et.V0 && this->V1 == et.V1) ? true : false ); }
98 
99  bool IsEdge(TId v0, TId v1) const
100  {
101  if ( v0 < v1 ) //ordered properly
102  {
103  return ( (this->V0 == v0 && this->V1 == v1) ? true : false );
104  }
105  else //swap comparison required
106  {
107  return ( (this->V0 == v1 && this->V1 == v0) ? true : false );
108  }
109  }
110  // Sort on v0 first, then v1.
111  bool operator<(const EdgeTuple& tup) const
112  {
113  if ( this->V0 < tup.V0 ) return true;
114  if ( tup.V0 < this->V0 ) return false;
115  if ( this->V1 < tup.V1 ) return true;
116  return false;
117  }
118 };
119 
120 
127 template<typename TId, typename TED>
129 {
130  TId V0;
131  TId V1;
132  TId EId; //originating edge id
133  TED T;
134 
135  // Default constructor - nothing needs to be done
137 
138  // Construct an edge and ensure that the edge tuple (vo,v1) is
139  // specified such that (v0<v1).
140  MergeTuple(TId v0, TId v1, TId eid, TED data) :
141  V0(v0), V1(v1), EId(eid), T(data)
142  {
143  if ( this->V0 > this->V1 )
144  {
145  TId tmp = this->V0;
146  this->V0 = this->V1;
147  this->V1 = tmp;
148  }
149  }
150 
151  bool operator==(const MergeTuple& et) const
152  { return ( (this->V0 == et.V0 && this->V1 == et.V1) ? true : false ); }
153 
154  bool operator!=(const MergeTuple& et) const
155  { return ( (this->V0 != et.V0 || this->V1 != et.V1) ? true : false ); }
156 
157  // Sort on v0 first, then v1.
158  bool operator<(const MergeTuple& tup) const
159  {
160  if ( this->V0 < tup.V0 ) return true;
161  if ( tup.V0 < this->V0 ) return false;
162  if ( this->V1 < tup.V1 ) return true;
163  return false;
164  }
165 };
166 
167 
172 template <typename IDType, typename EdgeData>
174 {
175 public:
177 
182  //@)
183 
188  EdgeArray(nullptr), EdgeOffsets(nullptr), MinV0(0), MaxV0(0), V0Range(0), NDivs(0),
189  MergeArray(nullptr) {}
190 
196  {
197  delete [] this->EdgeOffsets;
198  }
199 
204  { return this->NumEdges; }
205 
217  const IDType *MergeEdges(vtkIdType numEdges, MergeTupleType *edgeArray,
218  vtkIdType &numUniqueEdges);
219 
228  vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray);
229 
236  IDType IsInsertedEdge(IDType v0, IDType v1) const
237  {
238  // Ensure that data is consistent with what is expected.
239  IDType V0, V1;
240  if ( v0 < v1 )
241  {
242  V0 = v0;
243  V1 = v1;
244  }
245  else
246  {
247  V0 = v1;
248  V1 = v0;
249  }
250  if ( V0 < this->MinV0 || V0 > this->MaxV0 )
251  {
252  return -1;
253  }
254 
255  // Bin and search for matching edge
256  IDType curBin = this->HashBin(V0);
257  IDType curId = this->EdgeOffsets[curBin];
258  IDType curV0 = this->EdgeArray[curId].V0;
259  IDType num = this->GetNumberOfEdgesInBin(curBin);
260  for ( IDType i=0; i < num; ++i )
261  {
262  while ( curV0 < V0 )
263  {
264  curId++;
265  curV0 = this->EdgeArray[curId].V0;
266  }
267  if ( curV0 > V0 )
268  {
269  return -1;
270  }
271  else //matched v0, now find v1
272  {
273  IDType curV1 = this->EdgeArray[curId].V1;
274  while ( curV1 < V1 )
275  {
276  curId++;
277  curV1 = this->EdgeArray[curId].V1;
278  }
279  if ( curV1 > V1 )
280  {
281  return -1;
282  }
283  else
284  {
285  return curId;
286  }
287  }
288  } //loop over maximum possible candidates
289 
290  // Nothing found
291  return -1;
292  }
293 
298  const EdgeTupleType& GetEdge(IDType i) const
299  {
300  return (*this->EdgeArray)[i];
301  }
302 
303 protected:
305 
306  // Support BuildLocator usage pattern
309  IDType *EdgeOffsets;
310  IDType MinV0;
311  IDType MaxV0;
312  IDType V0Range;
313  int NDivs;
314 
315  IDType HashBin(IDType v) const
316  { return ( (v - this->MinV0) / this->NumEdgesPerBin ); }
317 
318  IDType GetNumberOfEdgesInBin(IDType bin) const
319  { return (this->EdgeOffsets[bin+1] - this->EdgeOffsets[bin]); }
320 
321 
322  // Support MergeEdges usage pattern
324  std::vector<IDType> MergeOffsets;
325 
326 private:
328  void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
329 
330 };
331 
332 #include "vtkStaticEdgeLocatorTemplate.txx"
333 
334 #endif
335 // VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h
MergeTuple::V0
TId V0
Definition: vtkStaticEdgeLocatorTemplate.h:130
EdgeTuple
Definition of an edge tuple.
Definition: vtkStaticEdgeLocatorTemplate.h:74
MergeTuple::MergeTuple
MergeTuple()
Definition: vtkStaticEdgeLocatorTemplate.h:136
vtkIdType
int vtkIdType
Definition: vtkType.h:347
vtkX3D::data
Definition: vtkX3D.h:315
EdgeTuple::V1
TId V1
Definition: vtkStaticEdgeLocatorTemplate.h:77
vtkStaticEdgeLocatorTemplate
Templated on types of ids defining an edge, and any data associated with the edge.
Definition: vtkStaticEdgeLocatorTemplate.h:173
vtkStaticEdgeLocatorTemplate::NumEdges
vtkIdType NumEdges
Definition: vtkStaticEdgeLocatorTemplate.h:304
EdgeTuple::operator==
bool operator==(const EdgeTuple &et) const
Definition: vtkStaticEdgeLocatorTemplate.h:96
vtkStaticEdgeLocatorTemplate::EdgeTupleType
EdgeTuple< IDType, EdgeData > EdgeTupleType
Some convenient typedefs.
Definition: vtkStaticEdgeLocatorTemplate.h:180
vtkStaticEdgeLocatorTemplate::vtkStaticEdgeLocatorTemplate
vtkStaticEdgeLocatorTemplate()
Construct an empty edge locator.
Definition: vtkStaticEdgeLocatorTemplate.h:187
vtkStaticEdgeLocatorTemplate::MergeEdges
const IDType * MergeEdges(vtkIdType numEdges, MergeTupleType *edgeArray, vtkIdType &numUniqueEdges)
This method sorts (in place) an array of MergeTupleType (of length numEdges) into separate groups,...
MergeTuple::V1
TId V1
Definition: vtkStaticEdgeLocatorTemplate.h:131
EdgeTuple::EdgeTuple
EdgeTuple(TId v0, TId v1, TED data)
Definition: vtkStaticEdgeLocatorTemplate.h:85
vtkStaticEdgeLocatorTemplate::EdgeArray
EdgeTupleType * EdgeArray
Definition: vtkStaticEdgeLocatorTemplate.h:308
MergeTuple::EId
TId EId
Definition: vtkStaticEdgeLocatorTemplate.h:132
vtkStaticEdgeLocatorTemplate::NumEdgesPerBin
vtkIdType NumEdgesPerBin
Definition: vtkStaticEdgeLocatorTemplate.h:307
vtkStaticEdgeLocatorTemplate::EdgeOffsets
IDType * EdgeOffsets
Definition: vtkStaticEdgeLocatorTemplate.h:309
EdgeTuple::T
TED T
Definition: vtkStaticEdgeLocatorTemplate.h:78
MergeTuple::operator!=
bool operator!=(const MergeTuple &et) const
Definition: vtkStaticEdgeLocatorTemplate.h:154
vtkStaticEdgeLocatorTemplate::IsInsertedEdge
IDType IsInsertedEdge(IDType v0, IDType v1) const
Return the id of the edge indicated.
Definition: vtkStaticEdgeLocatorTemplate.h:236
vtkStaticEdgeLocatorTemplate::MaxV0
IDType MaxV0
Definition: vtkStaticEdgeLocatorTemplate.h:311
vtkStaticEdgeLocatorTemplate::GetNumberOfEdgesInBin
IDType GetNumberOfEdgesInBin(IDType bin) const
Definition: vtkStaticEdgeLocatorTemplate.h:318
vtkStaticEdgeLocatorTemplate::MergeOffsets
std::vector< IDType > MergeOffsets
Definition: vtkStaticEdgeLocatorTemplate.h:324
vtkStaticEdgeLocatorTemplate::V0Range
IDType V0Range
Definition: vtkStaticEdgeLocatorTemplate.h:312
EdgeTuple::IsEdge
bool IsEdge(TId v0, TId v1) const
Definition: vtkStaticEdgeLocatorTemplate.h:99
vtkStaticEdgeLocatorTemplate::MergeArray
MergeTupleType * MergeArray
Definition: vtkStaticEdgeLocatorTemplate.h:323
MergeTuple::MergeTuple
MergeTuple(TId v0, TId v1, TId eid, TED data)
Definition: vtkStaticEdgeLocatorTemplate.h:140
vtkStaticEdgeLocatorTemplate::~vtkStaticEdgeLocatorTemplate
~vtkStaticEdgeLocatorTemplate()
Delete internal offset array.
Definition: vtkStaticEdgeLocatorTemplate.h:195
EdgeTuple::operator<
bool operator<(const EdgeTuple &tup) const
Definition: vtkStaticEdgeLocatorTemplate.h:111
MergeTuple::T
TED T
Definition: vtkStaticEdgeLocatorTemplate.h:133
vtkStaticEdgeLocatorTemplate::GetEdge
const EdgeTupleType & GetEdge(IDType i) const
Return the ith edge in the edge array.
Definition: vtkStaticEdgeLocatorTemplate.h:298
vtkStaticEdgeLocatorTemplate::MergeTupleType
MergeTuple< IDType, EdgeData > MergeTupleType
Definition: vtkStaticEdgeLocatorTemplate.h:181
vtkStaticEdgeLocatorTemplate::MinV0
IDType MinV0
Definition: vtkStaticEdgeLocatorTemplate.h:310
vtkStaticEdgeLocatorTemplate::BuildLocator
vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray)
This method contructs the edge locator to be used when searching for edges.
EdgeTuple::EdgeTuple
EdgeTuple()
Definition: vtkStaticEdgeLocatorTemplate.h:81
EdgeTuple::V0
TId V0
Definition: vtkStaticEdgeLocatorTemplate.h:76
MergeTuple::operator<
bool operator<(const MergeTuple &tup) const
Definition: vtkStaticEdgeLocatorTemplate.h:158
vtkStaticEdgeLocatorTemplate::GetNumberOfEdges
IDType GetNumberOfEdges()
Return the number of edges in the edge array.
Definition: vtkStaticEdgeLocatorTemplate.h:203
vtkStaticEdgeLocatorTemplate::NDivs
int NDivs
Definition: vtkStaticEdgeLocatorTemplate.h:313
MergeTuple::operator==
bool operator==(const MergeTuple &et) const
Definition: vtkStaticEdgeLocatorTemplate.h:151
MergeTuple
Definition of an edge tuple using for creating an edge merge table.
Definition: vtkStaticEdgeLocatorTemplate.h:128
vtkStaticEdgeLocatorTemplate::HashBin
IDType HashBin(IDType v) const
Definition: vtkStaticEdgeLocatorTemplate.h:315