Instigate Open Source Documentation

---

src/stl/_partial_sort.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_HPP
#define INSTIGATE_STL_PARTIAL_SORT_HPP

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

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

// Headers from standard library

// Forward declaration
namespace instigate {
        namespace stl {
                template <typename R>
                inline void partial_sort(R b, R m, R e);

                template <typename R, typename BP>
                inline void partial_sort(R b, R m, R e, BP p);

                namespace implementation {
                        template <typename R, typename TP>
                        inline void partial_sort_aux(R b, R m, R e, TP*);

                        template <typename R, typename TP, typename BP>
                        inline void partial_sort_aux(R b, R m, R e, TP*, BP p);
                }
        }
}

template <typename R>
inline void instigate::stl::partial_sort(R b, R m, R e)
{
        namespace RI = instigate::stl::readable_iterator;
        typedef typename RI::interface<R>::value_type value_type;
        value_type* vt = 0;
        implementation::partial_sort_aux(b, m, e, vt);
}

template <typename R, typename TP>
inline void instigate::stl::implementation::partial_sort_aux(R b, R m, R e, TP*)
{
        instigate::stl::make_heap(b, m);
        char k[sizeof(R)];
        R* i = 0;
        assign(i, copy_constructor(k, m));
        assert(0 != i);
        for(; less_than(*i, e); increment(*i)) {
                if(less_than(const_dereference(*i), const_dereference(b))) {
                        instigate::stl::implementation::pop_heap_aux(
                                        b, m, *i, TP(*(*i)));
                }
        }
        instigate::stl::sort_heap(b, m);
}

template <typename R, typename BP>
inline void instigate::stl::partial_sort(R b, R m, R e, BP p)
{
        namespace RI = instigate::stl::readable_iterator;
        typedef typename RI::interface<R>::value_type value_type;
        value_type* vt = 0;
        implementation::partial_sort_aux(b, m, e, vt, p);
}

template <typename R, typename TP, typename BP>
inline void instigate::stl::implementation::partial_sort_aux(R b, R m, R e,
                                                                TP*, BP p)
{
        namespace RA = instigate::stl::random_access_iterator;
        instigate::stl::make_heap(b, m, p);
        char* k = new char[sizeof(R)];
        assert(0 != k); 
        R* i = 0;
        assign(i, copy_constructor(k, m));
        assert(0 != i);
        typedef typename RA::interface<R>::difference_type difference_type;
        for(; less_than(*i, e); increment(*i)) {
                if(less_than(const_dereference(*i), const_dereference(b))) {
                        instigate::stl::implementation::pop_heap_aux(
                                        b, m, *i, TP(*(*i)), p);
                }
        }
        instigate::stl::sort_heap(b, m, p);
}

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

#endif // INSTIGATE_STL_PARTIAL_SORT_HPP

---

© Instigate CJSC, Open Source