1 /*
2 * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3 * Copyright (C) 2010 - DIGITEO - Bernard HUGUENEY
4 *
5  * Copyright (C) 2012 - 2016 - Scilab Enterprises
6  *
7  * This file is hereby licensed under the terms of the GNU GPL v2.0,
8  * pursuant to article 5.3.4 of the CeCILL v.2.1.
9  * This file was originally licensed under the terms of the CeCILL v2.1,
10  * and continues to be available under such terms.
11  * For more information, see the COPYING file which you should have received
12  * along with this program.
13 *
14 */
15 /*-----------------------------------------------------------------------------------*/
16 #ifndef PARTITION_HXX
17 #define PARTITION_HXX
19 #include <iterator>
21 namespace scilab
22 {
23 namespace core
24 {
25 /* generic dichotomy function used to search in the sorted vector
26 precondition :  [f,f+n) is p-partitioned : for any i in [f,f+n)
27 (p(*i) == true) => (p(*j) == true) for every j in [i,f+n]
28 returns the first iterator i in [f,f+n) for which p(*i) is true, or f+n .
29 */
30 template<typename I, typename P>
31 I partition_point_n(I f, typename std::iterator_traits<I>::difference_type n, P p)
32 {
33     while (n)  // when n==0, we have narrowed the interval to the singleton result
34     {
35         typename std::iterator_traits<I>::difference_type h = n >> 1; // n>0 -> n>>1 == n/2
36         I m = f + h; // we test at the middle of the interval
37         if (p(*m)) // partition point is amongst the [f,m]
38         {
39             n = h;
40         }
41         else     // partition point is amongst the ]m,f+n)
42         {
43             n = n - (h + 1);
44             f = m + 1;
45         }
46     }
47     return f;
48 }
49 }
50 }
51 #endif
52 /*-----------------------------------------------------------------------------------*/