vtkStaticEdgeLocatorTemplate.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkStaticEdgeLocatorTemplate_h
#define vtkStaticEdgeLocatorTemplate_h

#include "vtkABINamespace.h"
#include "vtkType.h" // For vtkIdType

#include <algorithm>
#include <vector>

VTK_ABI_NAMESPACE_BEGIN
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; }

  bool operator!=(const EdgeTuple& et) const { return this->V0 != et.V0 || this->V1 != et.V1; }

  bool IsEdge(TId v0, TId v1) const
  {
    if (v0 < v1) // ordered properly
    {
      return this->V0 == v0 && this->V1 == v1;
    }
    else // swap comparison required
    {
      return this->V0 == v1 && this->V1 == v0;
    }
  }
  // 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(-1)
    , MaxV0(-1)
    , 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 BuildLocator has been called by checking MinV0, MaxV0
    if (this->MinV0 < 0 || this->MaxV0 < 0)
    {
      return -1;
    }
    // Ensure that data is consistent with what is expected.
    if (v0 > v1)
    {
      std::swap(v0, v1);
    }
    if (v0 < this->MinV0 || v0 > this->MaxV0)
    {
      return -1;
    }

    // Bin and search for matching edge. All edges sharing the vertex v0
    // live in the same bin, so both scans below are bounded by the end of
    // the bin: without the bound, a query absent from the locator could
    // scan past the end of the edge array.
    const IDType curBin = this->HashBin(v0);
    const IDType num = this->GetNumberOfEdgesInBin(curBin);
    // check if there are no edges
    if (num < 1)
    {
      return -1;
    }
    IDType curId = this->EdgeOffsets[curBin];
    const IDType binEnd = this->EdgeOffsets[curBin + 1];
    while (curId < binEnd && this->EdgeArray[curId].V0 < v0)
    {
      curId++;
    }
    if (curId >= binEnd || this->EdgeArray[curId].V0 > v0)
    {
      return -1;
    }
    // matched v0, now find v1 among the edges sharing v0
    while (curId < binEnd && this->EdgeArray[curId].V0 == v0 && this->EdgeArray[curId].V1 < v1)
    {
      curId++;
    }
    if (curId >= binEnd || this->EdgeArray[curId].V0 != v0 || this->EdgeArray[curId].V1 > v1)
    {
      return -1;
    }
    return curId;
  }

  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;
};

VTK_ABI_NAMESPACE_END
#include "vtkStaticEdgeLocatorTemplate.txx"

#endif
// VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h