Instigate Open Source Documentation

---

src/stl/_equal_range.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_EQUAL_RANGE_HPP
#define INSTIGATE_STL_EQUAL_RANGE_HPP

// headers from this project
#include "concept.hpp"
#include "_basis.hpp"
#include "_advance.hpp"
#include "_distance.hpp"
#include "_lower_bound.hpp"
#include "_upper_bound.hpp"
// headers from other project

// headers from standard library

// forward declaration
namespace instigate {
namespace stl {
        namespace implementation {
                template <typename F, typename L, typename D, typename P>
                void equal_range_aux(F b, F e, const L& v, D*, 
                                P& p);
                template <typename F, typename L, typename C, typename D, 
                         typename P>
                void equal_range_aux(F b, F e, const L& v, C c, 
                                D*, P& p); 
        }
        template <typename F, typename L, typename P>
        inline void equal_range(F b, F e, const L& v, P& p); 
        template <typename F, typename L, typename C, typename P>
        inline void equal_range(F b, F e, const L& v, C c, P& p);
}       
}

template <typename F, typename L, typename P>
inline void instigate::stl::equal_range(F b, F e, const L& v, P& p)
{
        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_SAME_TYPE(value_type, L);
        CHECK(instigate::stl::pair::requirements<P>);
        typename FI::interface<F>::difference_type* k = 0;
        instigate::stl::implementation::equal_range_aux(b, e, v, k, p);
} 

template <typename F, typename L, typename D, typename P>
void instigate::stl::implementation::
        equal_range_aux(F b, F e, const L& v, D*, P& p)
{
        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));
        char k1[sizeof(F)];
        F* left = 0;
        assign(left, initialize<F>(k1));
        char k2[sizeof(F)];
        F* right = 0;
        assign(right, initialize<F>(k2));
        while (0 < len) {
                assign(half, len >> 1); 
                assert(0 != middle);
                assign(*middle, b);
                instigate::stl::advance(*middle, half);
                if (less_than(const_dereference(*middle), v)) {
                        assign(b, *middle);
                        increment(b);
                        assign(len, len - half -1);
                } else {
                        if (less_than(v, const_dereference(*middle))) {
                        assign(len, half);
                        } else {
                                assert(0 != left);
                                assign(*left, instigate::stl::lower_bound(b,
                                                        *middle, v));
                                instigate::stl::advance(b, len);
                                increment(*middle);
                                assert(0 != right);
                                assign(*right, instigate::stl::
                                                upper_bound(*middle, b, v));
                                assign(p.first, *left);
                                assign(p.second, *right);
                                return;
                        }
                }
        }
        assign(p.first, b);
        assign(p.second, b);
}

template <typename F, typename L, typename C, typename P>
inline void instigate::stl::
        equal_range(F b, F e, const L& v, C c, P& p)
{
        namespace FI = instigate::stl::forward_iterator;
        namespace PR = instigate::stl::pair;
        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::stl::pair::requirements<P>);
        CHECK_SAME_TYPE(value_type, L);
        typename FI::interface<F>::difference_type* k = 0;
        instigate::stl::implementation::equal_range_aux(b, e, v, c, k, p);
}

template <typename F, typename L, typename C, typename D, typename P>
void instigate::stl::implementation::equal_range_aux(F b, F e, const L& v, C c,
                D*, P& p)
{
        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 = 0;
        char k[sizeof(F)];
        F* middle = 0;
        assign(middle, initialize<F>(k));
        char k1[sizeof(F)];
        F* left = 0;
        assign(left, initialize<F>(k1));
        char k2[sizeof(F)];
        F* right = 0;
        assign(right, initialize<F>(k2));
        while (0 < len) {
                assign(half, len >> 1); 
                assert(0 != middle);
                assign(*middle, b);
                instigate::stl::advance(*middle, half);
                if (invoke_predicate(c, const_dereference(*middle), v)) {
                        assign(b, *middle);
                        increment(b);
                        assign(len, len - half - 1);
                } else {
                        if (invoke_predicate(c, v, const_dereference(*middle))){
                                assign(len, half);
                        } else {
                                assert(0 != left);
                                assign(*left, instigate::stl::lower_bound(
                                                        b, *middle, v));
                                instigate::stl::advance(b, len);
                                increment(*middle);
                                assert(0 != right);
                                assign(*right, instigate::stl::upper_bound(
                                                        *middle, b, v));
                                assign(p.first, *left);
                                assign(p.second, *right);
                                return;
                        }
                }
        }
        assign(p.first, b);
        assign(p.second, b);
}

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

#endif // INSTIGATE_STL_EQUAL_RANGE_HPP

---

© Instigate CJSC, Open Source