Saf/Algo/Struct/Heap.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library 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 3 of the License, or
    (at your option) any later version.

    Saf 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 Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_ALGO_STRUCT_HEAP_H
#define SAF_ALGO_STRUCT_HEAP_H

#include "../Predicate.h"
#include "../../Type.h"
#include "../../Type/IteratorTraits.h"
#include "../Swap.h"

namespace Saf
{
    namespace Algo
    {        
        namespace Struct
        {
            namespace Heap
            {
                template <class RanIter, class Pred>
                inline void BalanceUp(RanIter begin, Diff top, Diff node, Pred pred)
                {
                    while (top < node)
                    {
                        Diff parent = (node - 1) / 2;

                        if (!pred(begin[parent], begin[node]))
                        {
                            break;
                        }

                        Algo::Swap(begin[parent], begin[node]);
                        node = parent;
                    }
                }

                template <class RanIter, class Pred>
                inline void BalanceDown(RanIter begin, Diff node, Diff bottom, Pred pred)
                {
                    Diff top = node;
                    Diff child = 2 * node + 2;

                    while (child < bottom)
                    {
                        // Find the larger child
                        if (pred(begin[child], begin[child - 1]))
                        {
                            --child;
                        }

                        // Swap with the larger child
                        Algo::Swap(begin[node], begin[child]);

                        // Move down the tree
                        node = child;
                        child = 2 * child + 2;
                    }

                    // Only one child at the bottom
                    if (child == bottom)
                    {                        
                        Algo::Swap(begin[node], begin[child - 1]);
                        node = child - 1;
                    }

                    BalanceUp(begin, top, node, pred);
                }

                template <class RanIter, class Pred>
                inline void PushHeap(RanIter begin, RanIter end, Pred pred)
                {
                    if (begin != end)
                    {
                        BalanceUp(begin, Diff(0), Diff(end - begin) - 1, pred);
                    }
                }

                template <class RanIter>
                inline void PushHeap(RanIter begin, RanIter end)
                {
                    Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                    PushHeap(begin, end, pred);
                }

                template <class RanIter, class Pred>
                inline void PopHeap(RanIter begin, RanIter end, Pred pred)
                {
                    if (Diff(end - begin) > 1)
                    {
                        --end;
                        Algo::Swap(*begin, *end);                        
                        BalanceDown(begin, Diff(0), Diff(end - begin), pred);
                    }
                }

                template <class RanIter, class Pred>
                inline void PopHeap(RanIter begin, RanIter end)
                {
                    Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                    PopHeap(begin, end, pred);
                }

                template <class RanIter, class Pred>
                inline void MakeHeap(RanIter begin, RanIter end, Pred pred)
                {
                    // Sequence length
                    Diff bottom = end - begin;
                    // First leaf index
                    Diff node = bottom / 2;

                    while (node > 0)
                    {
                        --node;                        
                        BalanceDown(begin, node, bottom, pred);
                    }
                }

                template <class RanIter>
                inline void MakeHeap(RanIter begin, RanIter end)
                {
                    Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                    MakeHeap(begin, end, pred);
                }

                template <class RanIter, class Pred>
                inline void SortHeap(RanIter begin, RanIter end, Pred pred)
                {
                    while (begin != end)
                    {
                        PopHeap(begin, end, pred);
                        --end;
                    }
                }

                template <class RanIter>
                inline void SortHeap(RanIter begin, RanIter end)
                {
                    Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                    SortHeap(begin, end, pred);
                }

                template <class RanIter, class Pred>
                inline bool IsHeap(RanIter begin, RanIter end)
                {
                    Size len = Distance(begin, end);

                    for (Size i = 0; i < len; ++i)
                    {
                        if (pred(begin[(i - 1) / 2], begin[i]))
                        {
                            return false;
                        }
                    }

                    return true;
                }

                template <class RanIter>
                inline bool IsHeap(RanIter begin, RanIter end)
                {
                    Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                    return IsHeap(begin, end, pred);
                }
            }
        }
    }
}

#endif