// Copyright (c) 2007-2011 INRIA Sophia-Antipolis (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org) // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Spatial_sorting/include/CGAL/spatial_sort.h $ // $Id: spatial_sort.h 7508a6f 2020-02-12T17:05:49+01:00 Laurent Rineau // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Christophe Delage #ifndef CGAL_SPATIAL_SORT_H #define CGAL_SPATIAL_SORT_H #include #include #include #include #include #include #include #include namespace CGAL { namespace internal { template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Kernel &k, Policy /*policy*/, typename Kernel::Point_2 *, std::ptrdiff_t threshold_hilbert, std::ptrdiff_t threshold_multiscale, double ratio) { typedef std::iterator_traits Iterator_traits; typedef typename Iterator_traits::difference_type Diff_t; typedef Hilbert_sort_2 Sort; boost::rand48 random; boost::random_number_generator rng(random); CGAL::cpp98::random_shuffle(begin,end,rng); if (threshold_hilbert==0) threshold_hilbert=4; if (threshold_multiscale==0) threshold_multiscale=16; if (ratio==0.0) ratio=0.25; (Multiscale_sort (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Kernel &k, Policy /*policy*/, typename Kernel::Point_3 *, std::ptrdiff_t threshold_hilbert, std::ptrdiff_t threshold_multiscale, double ratio) { typedef std::iterator_traits Iterator_traits; typedef typename Iterator_traits::difference_type Diff_t; typedef Hilbert_sort_3 Sort; boost::rand48 random; boost::random_number_generator rng(random); CGAL::cpp98::random_shuffle(begin,end, rng); if (threshold_hilbert==0) threshold_hilbert=8; if (threshold_multiscale==0) threshold_multiscale=64; if (ratio==0.0) ratio=0.125; (Multiscale_sort (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Kernel &k, Policy /*policy*/, typename Kernel::Point_d *, std::ptrdiff_t threshold_hilbert, std::ptrdiff_t threshold_multiscale, double ratio) { typedef std::iterator_traits Iterator_traits; typedef typename Iterator_traits::difference_type Diff_t; typedef Hilbert_sort_d Sort; boost::rand48 random; boost::random_number_generator rng(random); CGAL::cpp98::random_shuffle(begin,end, rng); if (threshold_hilbert==0) threshold_hilbert=10; if (threshold_multiscale==0) threshold_multiscale=500; if (ratio==0.0) ratio=0.05; (Multiscale_sort (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end); } } //namespace internal template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Kernel &k, Policy policy, std::ptrdiff_t threshold_hilbert=0, std::ptrdiff_t threshold_multiscale=0, double ratio=0.0) { typedef std::iterator_traits ITraits; typedef typename ITraits::value_type value_type; internal::spatial_sort(begin, end, k, policy, static_cast (nullptr), threshold_hilbert,threshold_multiscale,ratio); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, Hilbert_sort_median_policy policy, std::ptrdiff_t threshold_hilbert=0, std::ptrdiff_t threshold_multiscale=0, double ratio=0.0) { typedef std::iterator_traits ITraits; typedef typename ITraits::value_type value_type; typedef CGAL::Kernel_traits KTraits; typedef typename KTraits::Kernel Kernel; spatial_sort (begin, end, Kernel(), policy, threshold_hilbert,threshold_multiscale,ratio); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, Hilbert_sort_middle_policy policy, std::ptrdiff_t threshold_hilbert=0, std::ptrdiff_t threshold_multiscale=0, double ratio=0.0) { typedef std::iterator_traits ITraits; typedef typename ITraits::value_type value_type; typedef CGAL::Kernel_traits KTraits; typedef typename KTraits::Kernel Kernel; spatial_sort (begin, end, Kernel(), policy, threshold_hilbert,threshold_multiscale,ratio); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, const Kernel &k, std::ptrdiff_t threshold_hilbert=0, std::ptrdiff_t threshold_multiscale=0, double ratio=0.0) { spatial_sort (begin, end, k, Hilbert_sort_median_policy(), threshold_hilbert,threshold_multiscale,ratio); } template void spatial_sort (RandomAccessIterator begin, RandomAccessIterator end, std::ptrdiff_t threshold_hilbert=0, std::ptrdiff_t threshold_multiscale=0, double ratio=0.0) { spatial_sort (begin, end, Hilbert_sort_median_policy(), threshold_hilbert,threshold_multiscale,ratio); } } // namespace CGAL #endif//CGAL_SPATIAL_SORT_H