spatial_sort.h
// Copyright (c) 2007-2011 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL$
// $Id$
// 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 <CGAL/config.h>
#include <CGAL/hilbert_sort.h>
#include <CGAL/Multiscale_sort.h>
#include <boost/random/random_number_generator.hpp>
#include <CGAL/algorithm.h>
#include <boost/random.hpp>
#include <boost/random/linear_congruential.hpp>
#include <algorithm>
namespace CGAL {
namespace internal {
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator, class Policy, class Kernel>
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<RandomAccessIterator> Iterator_traits;
typedef typename Iterator_traits::difference_type Diff_t;
typedef Hilbert_sort_2<Kernel, Policy, ConcurrencyTag> Sort;
boost::rand48 random;
boost::random_number_generator<boost::rand48, Diff_t> 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> (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator, class Policy, class Kernel>
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<RandomAccessIterator> Iterator_traits;
typedef typename Iterator_traits::difference_type Diff_t;
typedef Hilbert_sort_3<Kernel, Policy, ConcurrencyTag> Sort;
boost::rand48 random;
boost::random_number_generator<boost::rand48, Diff_t> 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> (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator, class Policy, class Kernel>
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<RandomAccessIterator> Iterator_traits;
typedef typename Iterator_traits::difference_type Diff_t;
typedef Hilbert_sort_d<Kernel, Policy> Sort;
boost::rand48 random;
boost::random_number_generator<boost::rand48, Diff_t> 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> (Sort (k, threshold_hilbert), threshold_multiscale, ratio)) (begin, end);
}
} //namespace internal
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator, class Policy, class Kernel>
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<RandomAccessIterator> ITraits;
typedef typename ITraits::value_type value_type;
internal::spatial_sort<ConcurrencyTag>(begin, end, k, policy, static_cast<value_type *> (nullptr),
threshold_hilbert,threshold_multiscale,ratio);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator>
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<RandomAccessIterator> ITraits;
typedef typename ITraits::value_type value_type;
typedef CGAL::Kernel_traits<value_type> KTraits;
typedef typename KTraits::Kernel Kernel;
spatial_sort<ConcurrencyTag> (begin, end, Kernel(), policy,
threshold_hilbert,threshold_multiscale,ratio);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator>
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<RandomAccessIterator> ITraits;
typedef typename ITraits::value_type value_type;
typedef CGAL::Kernel_traits<value_type> KTraits;
typedef typename KTraits::Kernel Kernel;
spatial_sort<ConcurrencyTag> (begin, end, Kernel(), policy,
threshold_hilbert,threshold_multiscale,ratio);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator, class Kernel>
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<ConcurrencyTag> (begin, end, k,
Hilbert_sort_median_policy(),
threshold_hilbert,threshold_multiscale,ratio);
}
template <class ConcurrencyTag = Sequential_tag, class RandomAccessIterator>
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<ConcurrencyTag> (begin, end,
Hilbert_sort_median_policy(),
threshold_hilbert,threshold_multiscale,ratio);
}
} // namespace CGAL
#endif//CGAL_SPATIAL_SORT_H