vtkStaticEdgeLocatorTemplate.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkStaticEdgeLocatorTemplate.h
 
  Copyright (c) Kitware, Inc.
  All rights reserved.
  See LICENSE file for details.
 
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.
 
=========================================================================*/
#ifndef vtkStaticEdgeLocatorTemplate_h
#define vtkStaticEdgeLocatorTemplate_h
 
#include <algorithm>
#include <vector>
 
template <typename TId, typename TED>
struct EdgeTuple
{
  TId V0;
  TId V1;
  TED Data;
 
  // Default constructor - nothing needs to be done
  EdgeTuple() = default;
 
  // Construct an edge and ensure that the edge tuple (vo,v1) is
  // specified such that (v0<v1).
  EdgeTuple(TId v0, TId v1, TED data)
    : V0(v0)
    , V1(v1)
    , Data(data)
  {
    if (this->V0 > this->V1)
    {
      std::swap(this->V0, this->V1);
    }
  }
 
  void Define(TId v0, TId v1)
  {
    if (v0 < v1)
    {
      this->V0 = v0;
      this->V1 = v1;
    }
    else
    {
      this->V0 = v1;
      this->V1 = v0;
    }
  }
 
  bool operator==(const EdgeTuple& et) const
  {
    return ((this->V0 == et.V0 && this->V1 == et.V1) ? true : false);
  }
 
  bool operator!=(const EdgeTuple& et) const
  {
    return ((this->V0 != et.V0 || this->V1 != et.V1) ? true : false);
  }
 
  bool IsEdge(TId v0, TId v1) const
  {
    if (v0 < v1) // ordered properly
    {
      return ((this->V0 == v0 && this->V1 == v1) ? true : false);
    }
    else // swap comparison required
    {
      return ((this->V0 == v1 && this->V1 == v0) ? true : false);
    }
  }
  // Sort on v0 first, then v1.
  bool operator<(const EdgeTuple& tup) const
  {
    if (this->V0 < tup.V0)
      return true;
    if (tup.V0 < this->V0)
      return false;
    if (this->V1 < tup.V1)
      return true;
    return false;
  }
};
 
template <typename IDType, typename EdgeData>
class vtkStaticEdgeLocatorTemplate
{
public:
 
  typedef EdgeTuple<IDType, EdgeData> EdgeTupleType;
 
  vtkStaticEdgeLocatorTemplate()
    : NumEdges(0)
    , NumEdgesPerBin(5)
    , EdgeArray(nullptr)
    , EdgeOffsets(nullptr)
    , MinV0(0)
    , MaxV0(0)
    , V0Range(0)
    , NDivs(0)
    , MergeArray(nullptr)
  {
  }
 
  ~vtkStaticEdgeLocatorTemplate() { delete[] this->EdgeOffsets; }
 
  IDType GetNumberOfEdges() { return this->NumEdges; }
 
  const IDType* MergeEdges(vtkIdType numEdges, EdgeTupleType* edgeArray, vtkIdType& numUniqueEdges);
 
  vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType* edgeArray);
 
  IDType IsInsertedEdge(IDType v0, IDType v1) const
  {
    // Ensure that data is consistent with what is expected.
    IDType V0, V1;
    if (v0 < v1)
    {
      V0 = v0;
      V1 = v1;
    }
    else
    {
      V0 = v1;
      V1 = v0;
    }
    if (V0 < this->MinV0 || V0 > this->MaxV0)
    {
      return -1;
    }
 
    // Bin and search for matching edge
    IDType curBin = this->HashBin(V0);
    IDType curId = this->EdgeOffsets[curBin];
    IDType curV0 = this->EdgeArray[curId].V0;
    IDType num = this->GetNumberOfEdgesInBin(curBin);
    for (IDType i = 0; i < num; ++i)
    {
      while (curV0 < V0)
      {
        curId++;
        curV0 = this->EdgeArray[curId].V0;
      }
      if (curV0 > V0)
      {
        return -1;
      }
      else // matched v0, now find v1
      {
        IDType curV1 = this->EdgeArray[curId].V1;
        while (curV1 < V1)
        {
          curId++;
          curV1 = this->EdgeArray[curId].V1;
        }
        if (curV1 > V1)
        {
          return -1;
        }
        else
        {
          return curId;
        }
      }
    } // loop over maximum possible candidates
 
    // Nothing found
    return -1;
  }
 
  const EdgeTupleType& GetEdge(IDType i) const { return (*this->EdgeArray)[i]; }
 
protected:
  vtkIdType NumEdges;
 
  // Support BuildLocator usage pattern
  vtkIdType NumEdgesPerBin;
  EdgeTupleType* EdgeArray;
  IDType* EdgeOffsets;
  IDType MinV0;
  IDType MaxV0;
  IDType V0Range;
  int NDivs;
 
  IDType HashBin(IDType v) const { return ((v - this->MinV0) / this->NumEdgesPerBin); }
 
  IDType GetNumberOfEdgesInBin(IDType bin) const
  {
    return (this->EdgeOffsets[bin + 1] - this->EdgeOffsets[bin]);
  }
 
  // Support MergeEdges usage pattern
  EdgeTupleType* MergeArray;
  std::vector<IDType> MergeOffsets;
 
private:
  vtkStaticEdgeLocatorTemplate(const vtkStaticEdgeLocatorTemplate&) = delete;
  void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
};
 
#include "vtkStaticEdgeLocatorTemplate.txx"
 
#endif
// VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h