Instigate Open Source Documentation

---

src/stl/_upper_bound.hpp

Go to the documentation of this file.

#ifndef _INSTIGATE_STL_INTERNAL_HEADER_IN_ALGORITHM
#error This is an internal header file used to implement Instigate STL.\
        It should never be included directly by a program.
#endif

#ifndef INSTIGATE_STL_UPPER_BOUND_HPP
#define INSTIGATE_STL_UPPER_BOUND_HPP

// Headers from this project
#include "concept.hpp"
#include "_basis.hpp"
#include "_distance.hpp"
#include "_advance.hpp"

// Headers from other project
#include <generic/base.hpp>           

// Headers from standard library

// Forward declaration
namespace instigate {
namespace stl {
        namespace implementation {
                template <typename F, typename L, typename D>
                F upper_bound_aux(F b, F e, const L& v, D*); 
                template <typename F, typename L, typename C, typename D>
                F upper_bound_aux(F b, F e, const L& v, C c, D*); 
        }
        template <typename F, typename L>
        inline F upper_bound(F b, F e, const L& v); 
        template <typename F, typename L, typename C>
        inline F upper_bound(F b, F e, const L& v, C c); 
}       
}

template <typename F, typename L>
inline F instigate::stl::upper_bound(F b, F e, const L& v)
{
        namespace FI = instigate::stl::forward_iterator;
        typedef typename instigate::stl::readable_iterator::interface<F>::
                        value_type value_type;
        CHECK(FI::requirements<F>);
        CHECK(instigate::stl::readable_iterator::requirements<F>);
        CHECK(instigate::generic::less_than_comparable::requirements<L>);
        CHECK_SAME_TYPE(value_type, L);
        typename FI::interface<F>::difference_type* k = 0;
        return instigate::stl::implementation::upper_bound_aux(b, e, v, k);
} 

template <typename F, typename L, typename D>
F instigate::stl::implementation::upper_bound_aux(F b, F e, const L& v, D*)
{
        namespace FI = instigate::stl::forward_iterator;
        typedef typename FI::interface<F>::difference_type difference_type;
        CHECK_CONVERTIBILITY(D, difference_type);
        D len = 0;
        assign(len, instigate::stl::distance(b, e));
        D half;
        char k[sizeof(F)];
        F* middle = 0;
        assign(middle, initialize<F>(k));
        while (0 < len) {
                assert(0 != middle);
                assign(half, len >> 1); 
                assign(*middle, b);
                instigate::stl::advance(*middle, half);
                if (less_than(v, const_dereference(*middle))) {
                        assign(len, half);
                } else {
                        assign(b, *middle);
                        increment(b);
                        assign(len, len - half - 1);
                }
        }
        return b;
}

template <typename F, typename L, typename C>
inline F instigate::stl::upper_bound(F b, F e, const L& v, C c)
{
        namespace FI = instigate::stl::forward_iterator;
        typedef typename instigate::stl::readable_iterator::interface<F>::
                        value_type value_type;
        CHECK(FI::requirements<F>);
        CHECK(instigate::stl::readable_iterator::requirements<F>);
        CHECK(instigate::generic::less_than_comparable::requirements<L>);
        CHECK(instigate::stl::binary_predicate::requirements<C>);
        CHECK_SAME_TYPE(value_type, L);
        typename FI::interface<F>::difference_type* k = 0;
        return instigate::stl::implementation::upper_bound_aux(b, e, v, c, k);
}

template <typename F, typename L, typename C, typename D>
F instigate::stl::implementation::upper_bound_aux(F b, F e, const L& v, C c, D*)
{
        namespace FI = instigate::stl::forward_iterator;
        typedef typename FI::interface<F>::difference_type difference_type;
        CHECK_CONVERTIBILITY(D, difference_type);
        D len = 0;
        assign(len, instigate::stl::distance(b, e));
        D half;
        char k[sizeof(F)];
        F* middle = 0;
        assign(middle, initialize<F>(k));
        while (0 < len) {
                assert(0 != middle);
                assign(half, len >> 1); 
                assign(*middle, b);
                instigate::stl::advance(*middle, half);
                if (invoke_predicate(c, v, const_dereference(*middle))) {
                        assign(len, half);
                } else {
                        assign(b, *middle);
                        increment(b);
                        assign(len, len - half - 1);
                }
        }
        return b;
}

// vim:et:tabstop=8:shiftwidth=8:cindent:fo=croq:textwidth=80:

#endif // INSTIGATE_STL_UPPER_BOUND_HPP

---

© Instigate CJSC, Open Source