/**************************************************************************
===========================================================================
Copyright (C) 2000-2005 Harry Kalogirou

This file is part of Sylphis3D source code.

This program is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
**************************************************************************/

#ifndef _HEAP_EXTRA_
#define _HEAP_EXTRA_

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _up_heap(CRanIt first, CRanIt last, CRanIt pos, CDiff *, CType *, CPred pred){	
    CDiff parent = (pos - first - 1) / 2;
    CDiff index = pos - first;
    CType mov = *pos;

    while(index > 0 && pred(*(first + parent),mov) ){
        *(first + index) = *(first + parent);
        index = parent;
        parent = (parent - 1) / 2;
    }

    if(index != pos - first)
        *(first + index) = mov;
}

template<class CRanIt> inline
void up_heap(CRanIt first, CRanIt last, CRanIt pos)
{	
    if (first == last)
        return;

    _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CPred> inline
void up_heap(CRanIt first, CRanIt last, CRanIt pos, CPred pred)
{	
    if (first == last)
        return;

    _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred );
}

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _down_heap(CRanIt first, CRanIt last, CRanIt pos, CDiff *, CType *, CPred pred){	
    CType mov = *pos;
    CDiff index = pos - first;
    CDiff left = 2 * index + 1;
    CDiff right = 2 * index + 2;
    CDiff len = last - first;
    CDiff largest;
   
    while(left < len){
        if( right < len && pred(*(first + left), *(first + right)) ){
            largest = right;
        } else {
            largest = left;
        }
        if( pred(mov, *(first + largest)) ){
            *(first + index) = *(first + largest);
            index = largest;
            left = 2 * index + 1;
            right = 2 * index + 2;
        } else {
            break;
        }
    }

    if(index != pos - first)
        *(first + index) = mov;
}

template<class CRanIt> inline
void down_heap(CRanIt first, CRanIt last, CRanIt pos)
{	
    if (first == last)
        return;

    _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CPred> inline
void down_heap(CRanIt first, CRanIt last, CRanIt pos, CPred pred)
{	
    if (first == last)
        return;

    _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred );
}

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CDiff *, CPred pred){	
    CDiff index = pos - first;
    CDiff parent = ( index - 1 ) / 2;
    *(first + index) = newval;
    if(index > 0 && pred(*(first + parent), newval)){
        _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred);
    } else {
        _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred);
    }
}


template<class CRanIt, class CType> inline
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval)
{	
    if (first == last)
        return;

    _update_heap(first, last, pos, newval, _Dist_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CType, class CPred> inline
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CPred pred)
{	
    if (first == last)
        return;

    _update_heap(first, last, pos, newval, _Dist_type(first),  pred );
}



#endif