hash.hpp

Go to the documentation of this file.

#pragma once
 
#include "visualization/canvas.hpp"

 
#include <cstddef>
#include <cstdint>
#include <functional>
#include <type_traits>
#include "forward.hpp"
#include "numeric.hpp"
 
namespace pgl::detail {
 
template <class T>
inline void hashCombine(std::size_t& seed, const T& value) {
#if defined(__SIZEOF_INT128__)
    // libstdc++ does not provide std::hash for the 128-bit integer extension
    // types under strict ISO modes (-std=c++NN), so hash their two 64-bit
    // halves instead of relying on std::hash<__int128>.
    if constexpr (std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>) {
        const auto bits = static_cast<__uint128_t>(value);
        hashCombine(seed, static_cast<std::uint64_t>(bits));
        hashCombine(seed, static_cast<std::uint64_t>(bits >> 64));
    } else
#endif
    {
        seed ^= std::hash<T>{}(value) + 0x9e3779b9u + (seed << 6u) + (seed >> 2u);
    }
}
 
}  // namespace pgl::detail
 
 
namespace std {

    template <class Number, class Label>
    struct hash<pgl::Point<Number, Label>> {
        std::size_t operator()(const pgl::Point<Number, Label>& point) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Point<Number, Label>>;
            pgl::detail::hashCombine(seed, point.x());
            pgl::detail::hashCombine(seed, point.y());
            return seed;
        }
    };
 

    template <class Int>
    struct hash<pgl::Rational<Int>> {
        size_t operator()(const pgl::Rational<Int>& r) const noexcept {
            // Equal values must hash equally, and a Rational may hold its value
            // unreduced, so the hash has to be taken over the reduced parts.
            // Simplify once and read both from that: asking the value itself for
            // numerator() and denominator() would run the same gcd twice.
            const pgl::Rational<Int> reduced = r.simplified();
            std::size_t seed = 1;
            pgl::detail::hashCombine(seed, reduced.numerator());
            pgl::detail::hashCombine(seed, reduced.denominator());
            return seed;
        }
    };

    template <>
    struct hash<pgl::BigInt> {
        std::size_t operator()(const pgl::BigInt& b) const noexcept {
            std::size_t seed = 15;
            pgl::detail::hashCombine(seed, b.negative_);
            pgl::detail::hashCombine(seed, b.small_);
            for (const auto& limb : b.limbs_) {
                pgl::detail::hashCombine(seed, limb);
            }
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Segment<PointType, LabelType>> {
        std::size_t operator()(const pgl::Segment<PointType, LabelType>& segment) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Segment<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, segment.min());
            pgl::detail::hashCombine(seed, segment.max());
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::OrientedSegment<PointType, LabelType>> {
        std::size_t operator()(const pgl::OrientedSegment<PointType, LabelType>& segment) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::OrientedSegment<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, segment.source());
            pgl::detail::hashCombine(seed, segment.target());
            return seed;
        }
    };
 

    template <class PointType, class LabelType>
    struct hash<pgl::Line<PointType, LabelType>> {
        std::size_t operator()(const pgl::Line<PointType, LabelType>& line) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Line<PointType, LabelType>>;
            if (line.isDegenerate()) {
                pgl::detail::hashCombine(seed, line.min());
            }
            else if (line.isVertical()) {
                pgl::detail::hashCombine(seed, line.min().x());
            }
            else {
                using N = typename pgl::Line<PointType>::NumberType;
                if constexpr (pgl::is_Rational_v<N>) {
                    // Coordinates are already exact rationals, so the dual
                    // slope/intercept are rationals too: divide and hash the
                    // reduced values directly (a nested Rational<Rational> is
                    // neither needed nor well-formed).
                    const auto [anum,bnum,den] = line.template dualCoordinates<N>();
                    pgl::detail::hashCombine(seed, anum / den);
                    pgl::detail::hashCombine(seed, bnum / den);
                }
                else {
                    // Match the precision used by Line::operator<=> (see
                    // predicates.hpp): dualCoordinates computes bnum = anum*px - py*den,
                    // a product of two coordinate-magnitude values, which overflows at
                    // the input width. Promote so equal lines hash equal.
                    using IntRational = pgl::detail::promoted_number_t<N>;
                    using RationalKey = pgl::Rational<IntRational>;
                    const auto [anum,bnum,den] = line.template dualCoordinates<IntRational>();
 
                    pgl::detail::hashCombine(seed, RationalKey(anum,den));
                    pgl::detail::hashCombine(seed, RationalKey(bnum,den));
                }
            }
            return seed;
        }
    };
 

    template <class PointType, class LabelType>
    struct hash<pgl::OrientedLine<PointType, LabelType>> {
        std::size_t operator()(const pgl::OrientedLine<PointType, LabelType>& line) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::OrientedLine<PointType, LabelType>>
                             + (line.source() < line.target() ? 0u : 1u);
            using T = pgl::Line<PointType>;
            pgl::detail::hashCombine(seed, static_cast<T>(line));
            return seed;
        }
    };
 

    template <class PointType, class LabelType>
    struct hash<pgl::Ray<PointType, LabelType>> {
        std::size_t operator()(const pgl::Ray<PointType, LabelType>& ray) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Ray<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, ray.source());
            using T = pgl::Line<PointType>;
            pgl::detail::hashCombine(seed, static_cast<T>(ray));
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Halfplane<PointType, LabelType>> {
        std::size_t operator()(const pgl::Halfplane<PointType, LabelType>& halfplane) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Halfplane<PointType, LabelType>>
                             + (halfplane.source() < halfplane.target() ? 0u : 1u);
            using T = pgl::Line<PointType>;
            pgl::detail::hashCombine(seed, static_cast<T>(halfplane));
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Rectangle<PointType, LabelType>> {
        std::size_t operator()(const pgl::Rectangle<PointType, LabelType>& rectangle) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Rectangle<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, rectangle.min());
            pgl::detail::hashCombine(seed, rectangle.max());
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Triangle<PointType, LabelType>> {
        std::size_t operator()(const pgl::Triangle<PointType, LabelType>& triangle) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Triangle<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, triangle.a());
            pgl::detail::hashCombine(seed, triangle.b());
            pgl::detail::hashCombine(seed, triangle.c());
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Disk<PointType, LabelType>> {
        std::size_t operator()(const pgl::Disk<PointType, LabelType>& disk) const {
            std::size_t seed = pgl::detail::shapeRank<pgl::Disk<PointType, LabelType>>;
            pgl::detail::hashCombine(seed, disk.isDegenerate());
            if (disk.isDegenerate()) {
                pgl::detail::hashCombine(seed, disk.a());
                pgl::detail::hashCombine(seed, disk.b());
                pgl::detail::hashCombine(seed, disk.c());
            } else {
                using Number = typename std::decay_t<decltype(disk)>::NumberType;
                pgl::detail::hashCombine(seed, disk.template center<Number>());
                pgl::detail::hashCombine(seed, disk.template squaredRadius<Number>());
            }
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Convex<PointType, LabelType>> {
        std::size_t operator()(const pgl::Convex<PointType, LabelType>& convex) const {
            using Shape = pgl::Convex<PointType, LabelType>;
            if (convex.hash_ != Shape::hashUnset_) {
                return convex.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            for (const auto& vertex : convex) {
                pgl::detail::hashCombine(seed, vertex);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            convex.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Polygon<PointType, LabelType>> {
        std::size_t operator()(const pgl::Polygon<PointType, LabelType>& polygon) const {
            using Shape = pgl::Polygon<PointType, LabelType>;
            if (polygon.hash_ != Shape::hashUnset_) {
                return polygon.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            for (const auto& vertex : polygon) {
                pgl::detail::hashCombine(seed, vertex);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            polygon.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::PolygonWithHoles<PointType, LabelType>> {
        std::size_t operator()(const pgl::PolygonWithHoles<PointType, LabelType>& region) const {
            using Shape = pgl::PolygonWithHoles<PointType, LabelType>;
            if (region.hash_ != Shape::hashUnset_) {
                return region.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            pgl::detail::hashCombine(seed, region.outer());
            for (const auto& hole : region.holes()) {
                pgl::detail::hashCombine(seed, hole);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            region.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::PolygonSet<PointType, LabelType>> {
        std::size_t operator()(const pgl::PolygonSet<PointType, LabelType>& set) const {
            using Shape = pgl::PolygonSet<PointType, LabelType>;
            if (set.hash_ != Shape::hashUnset_) {
                return set.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            for (const auto& component : set.components()) {
                pgl::detail::hashCombine(seed, component);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            set.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::HalfplaneIntersection<PointType, LabelType>> {
        std::size_t operator()(const pgl::HalfplaneIntersection<PointType, LabelType>& region) const {
            using Shape = pgl::HalfplaneIntersection<PointType, LabelType>;
            if (region.hash_ != Shape::hashUnset_) {
                return region.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            pgl::detail::hashCombine(seed, region.empty());
            for (const auto& halfplane : region) {
                pgl::detail::hashCombine(seed, halfplane);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            region.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType, class Storage>
    struct hash<pgl::MonotoneChain<PointType, LabelType, Storage>> {
        std::size_t operator()(const pgl::MonotoneChain<PointType, LabelType, Storage>& chain) const {
            using Shape = pgl::MonotoneChain<PointType, LabelType, Storage>;
            if (chain.hash_ != Shape::hashUnset_) {
                return chain.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            for (const auto& vertex : chain) {
                pgl::detail::hashCombine(seed, vertex);
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            chain.hash_ = seed;
            return seed;
        }
    };

    template <class PointType, class LabelType>
    struct hash<pgl::Polyline<PointType, LabelType>> {
        std::size_t operator()(const pgl::Polyline<PointType, LabelType>& polyline) const {
            using Shape = pgl::Polyline<PointType, LabelType>;
            if (polyline.hash_ != Shape::hashUnset_) {
                return polyline.hash_;
            }
            std::size_t seed = pgl::detail::shapeRank<Shape>;
            // A polyline equals its reversal, so the vertices are hashed in
            // canonical direction rather than in the stored traversal order.
            const bool reversed = !polyline.storedIsCanonical();
            for (std::size_t i = 0; i < polyline.size(); ++i) {
                pgl::detail::hashCombine(seed, polyline.canonicalAt(i, reversed));
            }
            // Never store the sentinel: remap the single colliding value so the
            // cache can always distinguish "computed" from "not computed".
            if (seed == Shape::hashUnset_) {
                seed = Shape::hashUnset_ - 1;
            }
            polyline.hash_ = seed;
            return seed;
        }
    };

    template <class PointType>
    struct hash<pgl::EmptyShape<PointType>> {
        std::size_t operator()(const pgl::EmptyShape<PointType>&) const {
            return pgl::detail::shapeRank<pgl::EmptyShape<PointType>>;
        }
    };

    template <class PointType>
    struct hash<pgl::Shape<PointType>> {
        std::size_t operator()(const pgl::Shape<PointType>& shape) const {
            std::size_t seed = 12;
            pgl::detail::hashCombine(seed, shape.variant().index());
            std::visit(
                [&seed](const auto& value) {
                    pgl::detail::hashCombine(seed, value);
                },
                shape.variant());
            return seed;
        }
    };
 
}//std