blob: 329368f5894ce778ccac1a23600ee44f8c341253 [file] [log] [blame]
// -*- 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