Instigate Open Source Documentation

---

src/stl/_pop_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_POP_HEAP_HPP
#define INSTIGATE_STL_POP_HEAP_HPP

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

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

// Headers from standard library

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

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

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

                        template <typename I, typename T>
                        void pop_heap_aux(I, I, I, T);

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

        }
}

template <typename I>
void instigate::stl::pop_heap(I b, I e)
{
        char buf[sizeof(I)];
        I* buf_p = 0;
        typedef typename stl::readable_iterator::interface<I>::value_type Tp;
        CHECK(stl::random_access_iterator::requirements<I>);
        CHECK(stl::lvalue_iterator::requirements<I>);
        CHECK(instigate::generic::less_than_comparable::requirements<Tp>);
        assign(buf_p, copy_constructor(buf, e));
        stl::advance(*buf_p, -1);
        implementation::pop_heap_aux(b, *buf_p, *buf_p, dereference(*buf_p));
}

template <typename I, typename T>
void instigate::stl::implementation::pop_heap_aux(I b, I e, I r, T v)
{
        typedef typename stl::random_access_iterator::interface<I>::
                difference_type D;
        stl::iter_swap(r, b);
        D a = 0;
        D k = stl::distance(b, e);
        implementation::adjust_heap_aux(b, a, k, v);
}

template <typename I, typename D, typename T>
void instigate::stl::implementation::adjust_heap_aux(I b, D holeIndex, D len,
                                                                     T value)
{
        D topIndex;
        assign(topIndex, holeIndex);
        D secondChild;
        assign(secondChild, 2 * holeIndex + 2);
        char buf[sizeof(I)];
        I* buf_p = 0;
        assign(buf_p, initialize<I>(buf));
        char buf1[sizeof(I)];
        I* buf_p1 = 0;
        assign(buf_p1, initialize<I>(buf1));
        while (less_than(secondChild, len)) {
                assert(0 != buf_p);
                assign(*buf_p, b);
                stl::advance(*buf_p, secondChild);
                assert(0 != buf_p1);
                assign(*buf_p1, b);
                stl::advance(*buf_p1, secondChild - 1);
                if (less_than(const_dereference(*buf_p), 
                        const_dereference(*buf_p1))) 
                {
                        --secondChild;
                }
                assign(*buf_p, b);
                stl::advance(*buf_p, holeIndex);
                assign(*buf_p1, b);
                stl::advance(*buf_p1, secondChild);
                stl::iter_swap(*buf_p, *buf_p1);
                assign(holeIndex, secondChild);
                assign(secondChild, 2 * (secondChild + 1));
        }
        if (equal(secondChild, len)) {
                assert(0 != buf_p);
                assign(*buf_p, b);
                stl::advance(*buf_p, holeIndex);
                assert(0 != buf_p1);
                assign(*buf_p1, b);
                stl::advance(*buf_p1, secondChild - 1);
                stl::iter_swap(*buf_p, *buf_p1);
                assign(holeIndex, secondChild - 1);
        }
        implementation::push_heap_aux(b, holeIndex, topIndex, value);   
}

template <typename I, typename C>
void instigate::stl::pop_heap(I b, I e, C c)
{
        CHECK(instigate::stl::random_access_iterator::requirements<I>);
        CHECK(instigate::stl::lvalue_iterator::requirements<I>);
        char buf[sizeof(I)];
        I* buf_p = 0;
        assign(buf_p, copy_constructor(buf, e));
        assert(0 != buf_p);
        stl::advance(*buf_p, -1);
        implementation::pop_heap_aux(b, *buf_p, *buf_p, dereference(*buf_p), c);
}

template <typename I, typename T, typename C>
void instigate::stl::implementation::pop_heap_aux(I b, I e, I r, T v, C c)
{
        typedef typename stl::random_access_iterator::interface<I>::
                difference_type D;
        stl::iter_swap(r, b);
        D a = 0;
        D k = stl::distance(b, e);
        implementation::adjust_heap_aux(b, a, k, v, c);
}

template <typename I, typename D, typename T, typename C>
void instigate::stl::implementation::adjust_heap_aux(I b, D h,D l, T v, C c)
{
        D t;
        assign(t, h);
        D secondChild;
        assign(secondChild, 2 * h + 2);
        char buf[sizeof(I)];
        I* buf_p = 0;
        assign(buf_p, initialize<I>(buf));
        char buf1[sizeof(I)];
        I* buf_p1 = 0;
        assign(buf_p1, initialize<I>(buf1));
        while (less_than(secondChild, l)) {
                assert(0 != buf_p);
                assign(*buf_p, b);
                stl::advance(*buf_p, secondChild);
                assign(*buf_p1, b);
                assert(0 != buf_p1);
                stl::advance(*buf_p1, secondChild - 1);
                if (invoke_predicate(c, dereference(*buf_p), 
                        dereference(*buf_p1)))
                {
                        --secondChild;
                }
                assign(*buf_p, b);
                stl::advance(*buf_p, h);
                assign(*buf_p1, b);
                stl::advance(*buf_p1, secondChild);
                stl::iter_swap(*buf_p, *buf_p1);
                assign(h, secondChild);
                assign(secondChild, 2 * (secondChild + 1));
        }
        if (equal(secondChild, l)) {
                assert(0 != buf_p);
                assign(*buf_p, b);
                stl::advance(*buf_p, h);
                assign(*buf_p1, b);
                assert(0 != buf_p1);
                stl::advance(*buf_p1, secondChild - 1);
                stl::iter_swap(*buf_p, *buf_p1);
                assign(h, secondChild - 1);
        }
        implementation::push_heap_aux(b, h, t, v, c);   
}


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

#endif // INSTIGATE_STL_POP_HEAP_HPP

---

© Instigate CJSC, Open Source