GA_Edge.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:     GA_Edge.h (GA Library, C++)
 *
 * COMMENTS: This class represents an edge as two point offsets.
 *           Comparisons treat the edge as undirected.
 */

#pragma once

#ifndef __GA_Edge__
#define __GA_Edge__

#include "GA_API.h"
#include "GA_Types.h"
#include <SYS/SYS_Hash.h>

#include <limits.h>
#include <stddef.h>
#include <stdint.h>

template<typename T,bool DIRECTED>
class GA_EdgeT
{
public:
    typedef GA_EdgeT<T,DIRECTED> ThisType;

    GA_EdgeT() : myP0(T(-1)), myP1(T(-1)) {}
    GA_EdgeT(T pt0, T pt1) : myP0(pt0), myP1(pt1) {}

    T  p0()  const { return myP0; }
    T &p0()        { return myP0; }
    T  p1()  const { return myP1; }
    T &p1()        { return myP1; }

    int64 getMemoryUsage() const
    {
        return sizeof(*this);
    }

    bool isValid() const
    { return GAisValid(myP0) && GAisValid(myP1); }

    /// Return whether this edge is the same undirected edge as the given edge.
    bool operator==(const ThisType & e) const
    {
        if (DIRECTED)
        {
            return (myP0 == e.myP0 && myP1 == e.myP1);
        }
        else
        {
            return (myP0 == e.myP0 && myP1 == e.myP1)
                || (myP0 == e.myP1 && myP1 == e.myP0);
        }
    }
    bool operator!=(const ThisType & e) const
    {
        return !(*this == e);
    }

    /// Hash function
    size_t hash() const
    {
        size_t hash_val;
        if (DIRECTED || myP0 < myP1)
        {
            hash_val = GA_Size(myP0);
            GA_EdgeT::hashCombine(hash_val, GA_Size(myP1));
        }
        else
        {
            hash_val = GA_Size(myP1);
            GA_EdgeT::hashCombine(hash_val, GA_Size(myP0));
        }
        return hash_val;
    }

private:

    ///
    /// Old Boost hash_combine() implementation, prior to Boost 1.81.
    /// For backwards compatibility of edge hash values.
    ///
    static void hashCombine(size_t &seed, GA_Size const &value)
    {
        auto hash_value = GA_EdgeT::hashValueSigned(value);

        // On macOS, size_t != hboost::uint64_t
        const size_t m = UINT64_C(0xc6a4a7935bd1e995);
        const int r = 47;

        hash_value *= m;
        hash_value ^= hash_value >> r;
        hash_value *= m;

        seed ^= hash_value;
        seed *= m;

        // Completely arbitrary number, to prevent 0's
        // from hashing to 0.
        seed += 0xe6546b64;
    }

    static size_t hashValueSigned(GA_Size val)
    {
        const unsigned int size_t_bits = 
           std::numeric_limits<size_t>::digits;
        // ceiling(std::numeric_limits<T>::digits / size_t_bits) - 1
        const int length = (std::numeric_limits<T>::digits - 1)
            / static_cast<int>(size_t_bits);

        size_t seed = 0;
        GA_Size positive = val < 0 ? -1 - val : val;

        // Hopefully, this loop can be unrolled.
        for(unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits)
        { 
            seed ^= (size_t) (positive >> i) + (seed<<6) + (seed>>2);
        }
        seed ^= (size_t) val + (seed<<6) + (seed>>2);

        return seed;
    }

    T myP0;
    T myP1;
};

template<typename T,bool DIRECTED>
SYS_FORCE_INLINE size_t hash_value(const GA_EdgeT<T,DIRECTED> &edge)
{
    return edge.hash();
}

// Specialize the GA_EdgeT template for the known edge types
using GA_Edge = GA_EdgeT<GA_Offset, false>;
using GA_DirectedEdge = GA_EdgeT<GA_Offset, true>;

using GA_IndexEdge = GA_EdgeT<GA_Index, false>;
using GA_DirectedIndexEdge = GA_EdgeT<GA_Index, true>;

namespace std {
template<typename T,bool DIRECTED>
struct hash<GA_EdgeT<T,DIRECTED> >
{
    typedef GA_EdgeT<T,DIRECTED> argument_type;
    typedef size_t result_type;

    size_t operator()(const GA_EdgeT<T,DIRECTED> &edge) const
    {
        return edge.hash();
    }
};
}

#endif