// -*- C++ -*-
/***************************************************************************
 *
 * _heap.h - declarations and inline definitions of the C++ Standard
 *           Library Heap operations
 *
 * This is an internal header file used to implement the C++ Standard
 * Library. It should never be #included directly by a program.
 *
 * $Id$
 *
 ***************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 ***************************************************************************
 *
 * Licensed to the Apache Software  Foundation (ASF) under one or more
 * contributor  license agreements.  See  the NOTICE  file distributed
 * with  this  work  for  additional information  regarding  copyright
 * ownership.   The ASF  licenses this  file to  you under  the Apache
 * License, Version  2.0 (the  "License"); you may  not use  this file
 * except in  compliance with the License.   You may obtain  a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the  License is distributed on an  "AS IS" BASIS,
 * WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
 * implied.   See  the License  for  the  specific language  governing
 * permissions and limitations under the License.
 *
 * Copyright 1994-2006 Rogue Wave Software.
 * 
 **************************************************************************/

#ifndef _RWSTD_RW_HEAP_H_INCLUDED
#define _RWSTD_RW_HEAP_H_INCLUDED

#ifndef _RWSTD_RW_ALGOBASE_H_INCLUDED
#  include <rw/_algobase.h>
#endif   // _RWSTD_RW_ALGOBASE_H_INCLUDED

#ifndef _RWSTD_RW_ITERBASE_H_INCLUDED
#  include <rw/_iterbase.h>
#endif   // _RWSTD_RW_ITERBASE_H_INCLUDED


_RWSTD_NAMESPACE (std) {


// 25.3.6 - Heap operations

// helper to work around the lack of iterator_traits
_EXPORT
template <class _RandomAccessIter, class _Dist, class _TypeT,
          class _Compare>
void __push_heap (_RandomAccessIter, _Dist, _Dist, _TypeT, _Compare);


template <class _RandomAccessIter, class _Dist, class _Compare>
inline void
__push_heap (_RandomAccessIter __first, _RandomAccessIter __last,
             _Dist*, _Compare __comp)
{
    __push_heap (__first, _Dist (__last - __first), _Dist (), *__last, __comp);
}

// 25.3.6.1
template <class _RandomAccessIter, class _Compare>
inline void push_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                       _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (!(__first == __last))
        __push_heap (__first, --__last,
                     _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter), __comp);
}


// 25.3.6.1
template <class _RandomAccessIter>
inline void push_heap (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::push_heap (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


_EXPORT
template <class _RandomAccessIter, class _Dist, class _TypeT,
          class _Compare>
void __adjust_heap (_RandomAccessIter, _Dist, _Dist, _TypeT, _Compare);


// helper to work around the lack of iterator_traits
template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist>
inline void
__pop_heap (_RandomAccessIter __first, _RandomAccessIter __last,
            _RandomAccessIter __res, _TypeT __val, _Compare __cmp, _Dist*)
{
    *__res = *__first;
    __adjust_heap (__first, _Dist (), _Dist (__last - __first), __val, __cmp);
}


// 25.3.6.2
template <class _RandomAccessIter, class _Compare>
inline void
pop_heap (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (!(__first == __last)) {
        --__last;
        __pop_heap (__first, __last, __last, *__last, __comp,
                    _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter));
    }
}


// 25.3.6.2
template <class _RandomAccessIter>
inline void pop_heap (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::pop_heap (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


_EXPORT
template <class _RandomAccessIter, class _Compare, class _Dist>
void __make_heap (_RandomAccessIter, _RandomAccessIter, _Compare, _Dist*);


// 25.3.6.3
template <class _RandomAccessIter, class _Compare>
inline void make_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                       _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (!(__last - __first < 2))
        __make_heap (__first, __last, __comp,
                     _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter));
}


// 25.3.6.3
template <class _RandomAccessIter>
inline void make_heap (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::make_heap (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


// 25.3.6.4
template <class _RandomAccessIter, class _Compare>
inline void sort_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                       _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; __last - __first > 1; --__last)
        _STD::pop_heap (__first, __last, __comp);
}


// 25.3.6.4
template <class _RandomAccessIter>
inline void sort_heap (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::sort_heap (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


}   // namespace std


#ifdef _RWSTD_NO_IMPLICIT_INCLUSION
#  include <rw/_heap.cc>
#endif


#endif   // _RWSTD_RW_HEAP_H_INCLUDED