// Copyright (c) 2007 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/Multiscale_sort.h $ // $Id: Multiscale_sort.h 5c41b10 2020-01-02T10:26:44+01:00 Mael Rouxel-Labbé // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Christophe Delage #ifndef CGAL_MULTISCALE_SORT_H #define CGAL_MULTISCALE_SORT_H #include #include #include #include namespace CGAL { template class Multiscale_sort { Sort _sort; std::ptrdiff_t _threshold; double _ratio; public: Multiscale_sort (const Sort &sort = Sort(), std::ptrdiff_t threshold = 1, double ratio = 0.5) : _sort (sort), _threshold (threshold), _ratio (ratio) { CGAL_precondition (0. <= ratio && ratio <= 1.); } template void operator() (RandomAccessIterator begin, RandomAccessIterator end) const { typedef typename std::iterator_traits::difference_type difference_type; RandomAccessIterator middle = begin; if (end - begin >= _threshold) { middle = begin + difference_type (double(end - begin) * _ratio); this->operator() (begin, middle); } _sort (middle, end); } }; } // namespace CGAL #endif // CGAL_MULTISCALE_SORT_H