Instigate Open Source Documentation

---

src/stl/_partial_sort_copy.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_PARTIAL_SORT_COPY_HPP
#define INSTIGATE_STL_PARTIAL_SORT_COPY_HPP

// Headers from this project
#include "concept.hpp"

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

// Headers from standard library

// Forward declaration
namespace instigate {
        namespace stl {
                template <typename I, typename R>
                inline R partial_sort_copy(I b, I e, R f, R l);

                template <typename I, typename R, typename BP>
                inline R partial_sort_copy(I b, I e, R f, R l, BP p);
                namespace implementation {
                        template <typename I, typename R, typename D, 
                                 typename Tp>
                        inline R partial_sort_copy_aux(I b, I e, R f, R l, D*,
                                                                         Tp*);
                        template <typename I, typename R, typename BP, 
                                typename D, typename Tp>
                        inline R partial_sort_copy_aux(I b, I e, R f, R l,BP p,
                                                                       D*,Tp*);
                }
        }
}

template <typename I, typename R>
inline R instigate::stl::partial_sort_copy(I b, I e, R f, R l)
{
        namespace SP = instigate::stl::single_pass_iterator;
        namespace RI = instigate::stl::readable_iterator;
        typedef typename RI::interface<I>::value_type value_type;
        typedef typename RI::interface<R>::value_type value_type2; 
        CHECK_SAME_TYPE(value_type, value_type2);
        typedef typename SP::interface<R>::difference_type difference_type;
        value_type* vt = 0;
        difference_type* dt = 0;
        return implementation::partial_sort_copy_aux(b, e, f, l, dt, vt);
}

template <typename I, typename R, typename D, typename Tp>
inline R instigate::stl::implementation::partial_sort_copy_aux(I b, I e, R f,
                                                                R l, D*, Tp*)
{
        namespace RI = instigate::stl::readable_iterator;
        typedef typename RI::interface<I>::value_type value_type;
        if (equal(f, l)) {
                return l;
        }
        char k[sizeof(R)];
        R* real_last = 0;
        assign(real_last, copy_constructor(k, f));
        assert(0 != real_last);
        while(!equal(b, e) && !equal(*real_last, l)) {
                dereference_assign(*real_last, const_dereference(b));
                increment(*real_last);
                increment(b);
        }
        instigate::stl::make_heap(f, *real_last);
        while (!equal(b,  e)) {
                if (equal(const_dereference(b), const_dereference(f))) {
                        instigate::stl::implementation::adjust_heap_aux(f, D(0),
                                        D(*real_last - f),
                                        Tp(const_dereference(b)));
                }
                increment(b);
        }
        instigate::stl::sort_heap(f, *real_last);
        return *real_last;
}

template <typename I, typename R, typename BP>
inline R instigate::stl::partial_sort_copy(I b, I e, R f, R l, BP p)
{
        namespace RA = instigate::stl::random_access_iterator;
        namespace SP = instigate::stl::single_pass_iterator;
        namespace WR = instigate::stl::writable_iterator;
        namespace RI = instigate::stl::readable_iterator;
        namespace EQ = instigate::generic::equality_comparable;
        namespace LT = instigate::generic::less_than_comparable;
        namespace BPI = instigate::stl::binary_predicate;
        typedef typename RI::interface<R>::value_type value_type;
        typedef typename SP::interface<R>::difference_type difference_type;
        CHECK(RA::requirements<R>);
        CHECK(WR::requirements<R>);
        CHECK(BPI::requirements<BP>);
        CHECK(LT::requirements<value_type>);
        value_type* vt = 0;
        difference_type* dt = 0;
        return implementation::partial_sort_copy_aux(b, e, f, l, p, dt, vt);
}

template <typename I, typename R, typename BP, typename D, typename Tp>
inline R instigate::stl::implementation::partial_sort_copy_aux(I b, I e, R f,
                                                        R l, BP p, D*, Tp*)
{
        namespace DF = instigate::generic::default_constructible;
        namespace RA = instigate::stl::random_access_iterator;
        namespace RI = instigate::stl::readable_iterator;
        typedef typename RI::interface<I>::value_type value_type;
        typedef typename RI::interface<R>::value_type value_type2; 
        CHECK_SAME_TYPE(value_type, value_type2);
        if (equal(f, l)) {
                return l;
        }
        char k[sizeof(R)];
        R* real_last = 0;
        assign(real_last, copy_constructor(k, f));
        assert(0 != real_last);
        while(!equal(b, e) && !equal(*real_last, l)) {
                dereference_assign((*real_last), const_dereference(b));
                increment(*real_last);
                increment(b);
        }
        instigate::stl::make_heap(f, *real_last, p);
        while (!equal(b,  e)) {
                if (invoke_predicate(p, const_dereference(b),
                                                        const_dereference(f))) 
                {
                        instigate::stl::implementation::adjust_heap_aux(
                                                 f, D(0), D(*real_last - f), 
                                                 const_dereference(b), p);
                }
                increment(b);
        }
        instigate::stl::sort_heap(f, *real_last, p);
        return *real_last;
}

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

#endif // INSTIGATE_STL_PARTIAL_SORT_HPP

---

© Instigate CJSC, Open Source