Instigate Open Source Documentation

---

src/stl/_push_heap.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_PUSH_HEAP_HPP
#define INSTIGATE_STL_PUSH_HEAP_HPP

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

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

// Headers from standard library

// Forward declaration
namespace instigate {
        namespace stl {
                template <typename I>
                void push_heap(I, I);

                template <typename I, typename C>
                void push_heap(I, I, C);
                
                namespace implementation {
                        template <typename I, typename D, typename T>
                        void push_heap_aux(I , D , D, T);

                        template <typename I, typename D, typename T,typename C>
                        void push_heap_aux(I, D, D, T, C);
                }
        }       
}

template <typename I>
void instigate::stl::push_heap(I b, I e)
{
        typedef typename stl::random_access_iterator::interface<I>::
                difference_type D;
        typedef typename stl::readable_iterator::interface<I>::value_type T;
        CHECK(instigate::stl::random_access_iterator::requirements<I>);
        CHECK(instigate::stl::lvalue_iterator::requirements<I>);
        CHECK(instigate::generic::less_than_comparable::requirements<T>);
        D a = stl::distance(b, e) - 1;
        D k = 0;
        char buf[sizeof(I)];
        I* p = 0;
        assign(p, copy_constructor(buf, e));
        assert(0 != p);
        stl::advance(*p, -1);
        T t = dereference(*p);
        implementation::push_heap_aux(b, a, k, t);
}                                       

template <typename I, typename C>
void instigate::stl::push_heap(I b, I e, C c)
{
        typedef typename stl::readable_iterator::interface<I>::value_type T;
        typedef typename stl::random_access_iterator::interface<I>::
                difference_type D;
        CHECK(stl::random_access_iterator::requirements<I>);
        CHECK(stl::lvalue_iterator::requirements<I>);
        CHECK(stl::binary_predicate::requirements<C>);
        CHECK(instigate::generic::less_than_comparable::requirements<T>);
        D a = 0;
        D k = stl::distance(b, e) - 1;
        char buf[sizeof(I)];
        I* p = 0;
        assign(p, copy_constructor(buf, e));
        assert(0 != p);
        stl::advance(*p, -1);
        T o = const_dereference(*p);
        implementation::push_heap_aux(b, k, a, o, c);
} 

template <typename I, typename D, typename T>
void instigate::stl::implementation::push_heap_aux(I b, D h, D t, T v)
{
        D p = (h - 1) / 2;
        char buf[sizeof(I)];
        I* z = 0;
        assign(z, copy_constructor(buf, b));
        assert(0 != z);
        stl::advance(*z, p);
        char buf1[sizeof(I)];
        I* z1 = 0;
        assign(z1, copy_constructor(buf1, b));
        while (less_than(t, h) && less_than(const_dereference(*z), v)) 
        {
                assign(*z, b);
                stl::advance(*z, h);
                assert(0 != z1);
                assign(*z1, b);
                stl::advance(*z1, p);
                dereference_assign((*z), const_dereference(*z1));
                assign(h, p);
                assign(p,  (h - 1) / 2);
                assign(*z, b);
                stl::advance(*z, p);
        }
        assign(*z, b);
        stl::advance(*z, h);
        dereference_assign((*z), v);
}

template <typename I, typename D, typename T, typename C> 
void instigate::stl::implementation::push_heap_aux(I b , D h, D t, T v, C c)
{
        D p = (h - 1) / 2;
        char buf[sizeof(I)];
        I* z = 0;
        assign(z, copy_constructor(buf, b));
        assert(0 != z);
        stl::advance(*z, p);
        char buf1[sizeof(I)];
        I* z1 = 0;
        assign(z1, copy_constructor(buf1, b));
        while (less_than(t, h) && invoke_predicate(c, const_dereference(*z),v)) 
        {
                assign(*z, b);
                stl::advance(*z, h);
                assert(0 != z1);
                assign(*z1, b);
                stl::advance(*z1, p);
                dereference_assign((*z), const_dereference(*z1));
                assign(h, p);
                assign(p,  (h - 1) / 2);
                assign(*z, b);
                stl::advance(*z, p);
        }
        assign(*z, b);
        stl::advance(*z, h);
        dereference_assign((*z), v);
}

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

#endif // INSTIGATE_STL_PUSH_HEAP_HPP 

---

© Instigate CJSC, Open Source