BWAPI: SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Hilbert_sort

Go to the documentation of this file.
00001 // Copyright (c) 2007  INRIA Sophia-Antipolis (France).
00002 // All rights reserved.
00003 //
00004 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or
00005 // modify it under the terms of the GNU Lesser General Public License as
00006 // published by the Free Software Foundation; version 2.1 of the License.
00007 // See the file LICENSE.LGPL distributed with CGAL.
00008 //
00009 // Licensees holding a valid commercial license may use this file in
00010 // accordance with the commercial license agreement provided with the software.
00011 //
00012 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00013 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00014 //
00015 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Spatial_sorting/include/CGAL/Hilbert_sort_base.h $
00016 // $Id: Hilbert_sort_base.h 36875 2007-03-07 11:37:05Z spion $
00017 //
00018 // Author(s)     : Christophe Delage
00019 
00020 #ifndef CGAL_HILBERT_SORT_BASE_H
00021 #define CGAL_HILBERT_SORT_BASE_H
00022 
00023 #include <CGAL/basic.h>
00024 #include <algorithm>
00025 
00026 CGAL_BEGIN_NAMESPACE
00027 
00028 namespace CGALi {
00029 
00030     template <class RandomAccessIterator, class Cmp>
00031     RandomAccessIterator
00032     hilbert_split (RandomAccessIterator begin, RandomAccessIterator end,
00033                    Cmp cmp = Cmp ())
00034     {
00035         if (begin >= end) return begin;
00036 
00037         RandomAccessIterator middle = begin + (end - begin) / 2;
00038         std::nth_element (begin, middle, end, cmp);
00039         return middle;
00040     }
00041 }
00042 
00043 CGAL_END_NAMESPACE
00044 
00045 #endif//CGAL_HILBERT_SORT_BASE_H