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 <vector>
#include <algorithm>

template<typename TId, typename TED>
struct EdgeTuple
{
  TId V0;
  TId V1;
  TED T;

  // Default constructor - nothing needs to be done
  EdgeTuple() {}

  // 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), T(data)
  {
    if ( this->V0 > this->V1 )
    {
      TId tmp = this->V0;
      this->V0 = this->V1;
      this->V1 = tmp;
    }
  }

  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 TId, typename TED>
struct MergeTuple
{
  TId V0;
  TId V1;
  TId EId; //originating edge id
  TED T;

  // Default constructor - nothing needs to be done
  MergeTuple() {}

  // Construct an edge and ensure that the edge tuple (vo,v1) is
  // specified such that (v0<v1).
  MergeTuple(TId v0, TId v1, TId eid, TED data) :
  V0(v0), V1(v1), EId(eid), T(data)
  {
    if ( this->V0 > this->V1 )
    {
      TId tmp = this->V0;
      this->V0 = this->V1;
      this->V1 = tmp;
    }
  }

  bool operator==(const MergeTuple& et) const
  { return ( (this->V0 == et.V0 && this->V1 == et.V1) ? true : false ); }

  bool operator!=(const MergeTuple& et) const
  { return ( (this->V0 != et.V0 || this->V1 != et.V1) ? true : false ); }

  // Sort on v0 first, then v1.
  bool operator<(const MergeTuple& 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;
  typedef MergeTuple<IDType,EdgeData> MergeTupleType;
  //@)

  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, MergeTupleType *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
  MergeTupleType *MergeArray;
  std::vector<IDType> MergeOffsets;

private:
  vtkStaticEdgeLocatorTemplate(const vtkStaticEdgeLocatorTemplate&) = delete;
  void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;

};

#include "vtkStaticEdgeLocatorTemplate.txx"

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