// heapalgs.h
// Glenn G. Chappell
// 25 April 2008
//
// For CS 311
// Header for Heap algorithms

#ifndef FILE_HEAPALGS_H_INCLUDED
#define FILE_HEAPALGS_H_INCLUDED

#include <cstdlib>    // for std::size_t
#include <algorithm>  // for std::swap


// heapInsert
// Heap insert operation on a random-access range.
// Inserts *(last-1) into Heap [first, last-1).
// Pre:
//     [first, last) is a valid range.
//     [first, last-1) forms a Heap.
// Post:
//     [first, last) forms a Heap with the items formerly in [first, last).
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <, copy ctor, copy =.
// Exception Neutral
// Basic Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
void heapInsert(RAIter first, RAIter last)
{
    std::size_t curr = (last-first)-1;    // index of item to "trickle up"
    while (curr != 0)
    {
        std::size_t parent = (curr-1)/2;  // index of parent
        if (!(first[parent] < first[curr]))
            break;

        std::swap(first[curr], first[parent]);
        curr = parent;
    }
}


// trickleDown
// Internal-use function for heapDelete, heapMake.
// Does "trickle down" of item in (partial) Heap.
// Pre:
//     [first, last) is a valid nonempty range.
//     theItem lies in [first, last).
//     (theItem, last) is a partial Heap.
//      That is, !(first[(k-1)/2] < first[k]), whenever both first+(k-1)/2
//      and first+k lie in (theItem, last).
// Post:
//     [theItem, last) is a partial Heap (see above) containing the same
//      items as initially.
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <, copy ctor, copy =.
// Exception Neutral
// Basic Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
void trickleDown(RAIter first, RAIter last, RAIter theItem)
{
    std::size_t size = last - first;
    std::size_t curr = theItem - first;
    std::size_t lchild = 2 * curr + 1;
    while (lchild < size)  // There is at least one 1 child
    {
        if (lchild + 1 < size) // 2 children
        {
            std::size_t toSwap;  // child item to swap with
            if (first[curr] < first[lchild]
              && !(first[lchild] < first[lchild+1]))
                toSwap = lchild;
            else if (first[curr] < first[lchild+1]
              && !(first[lchild+1] < first[lchild]))
                toSwap = lchild+1;
            else  // No more trickling; we are done
                break;

            // Trickle down 1 level
            std::swap(first[curr], first[toSwap]);
            curr = toSwap;
        }
        else                   // 1 child
        {
            if (first[curr] < first[lchild])
            {
                // Trickle down 1 level
                std::swap(first[curr], first[lchild]);
                curr = lchild;
            }
            else
                break;
        }
        lchild = 2 * curr + 1;
    }
}


// heapDelete
// Heap delete operation on a random-access range.
// Pre:
//     [first, last) is a valid nonempty range.
//     [first, last) forms a Heap.
// Post:
//     *(last-1) is the former *first.
//     [first, last-1) forms a Heap with the remaining items.
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <, copy ctor, copy =.
// Exception Neutral
// Basic Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
void heapDelete(RAIter first, RAIter last)
{
    // Check for empty range.
    // (Our preconditions say this never happens, but ... why not?)
    if (first == last)
        return;

    std::iter_swap(first, last-1);
    trickleDown(first, last-1, first);
}


// makeHeap
// Turns the given random-access range into a Heap in linear time.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) is a Heap containing the same items as initially.
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <, copy ctor, copy =.
// Exception Neutral
// Basic Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
void makeHeap(RAIter first, RAIter last)
{
    RAIter theItem = last;
    for (--theItem; first <= theItem; --theItem)
        trickleDown(first, last, theItem);
}


// sortHeap
// Sorts the given Heap.
// Pre:
//     [first, last) is a valid range.
//     [first, last) is a Heap.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by <.
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <, copy ctor, copy =.
// Exception Neutral
// Basic Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
void sortHeap(RAIter first, RAIter last)
{
    while (first < last)  // Executes 1 time more than necessary
    {
        heapDelete(first, last);
        --last;
    }
}


// heapTest
// Determines whether given random-access range is a Heap.
// Pre:
//     [first, last) is a valid range.
// Post:
//     Return value is true iff given range is a Heap.
// Requirements on Types:
//     RAIter is a random-access iterator type.
//     The value type of RAIter must have <.
// Exception Neutral
// Strong Guarantee
// If <, std::swap do not throw, then No-Throw Guarantee.
template<typename RAIter>
bool heapTest(RAIter first, RAIter last)
{
    std::size_t size = last - first;
    // Compare each non-root item with its parent
    for (std::size_t index = 1;
        index < size;
        ++index)
    {
        // Comapare with parent
        if (first[(index-1)/2] < first[index])
            return false;
    }
    return true;
}



#endif  //#ifndef FILE_HEAPALGS_H_INCLUDED