Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Saf/Algo/Struct/Heap.h
Go to the documentation of this file.
00001 /*
00002     This file is part of Simple Application Framework (Saf) library.
00003     Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>
00004 
00005     This library is free software: you can redistribute it and/or modify
00006     it under the terms of the GNU General Public License as published 
00007     by the Free Software Foundation, either version 3 of the License, or
00008     (at your option) any later version.
00009 
00010     Saf is distributed in the hope that it will be useful,
00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013     GNU General Public License for more details.
00014 
00015     You should have received a copy of the GNU General Public License
00016     along with Simple Application Framework library. If not, 
00017     see <http://www.gnu.org/licenses/>.
00018 */
00019 
00028 #ifndef SAF_ALGO_STRUCT_HEAP_H
00029 #define SAF_ALGO_STRUCT_HEAP_H
00030 
00031 #include "../Predicate.h"
00032 #include "../../Type.h"
00033 #include "../../Type/IteratorTraits.h"
00034 #include "../Swap.h"
00035 
00036 namespace Saf
00037 {
00038     namespace Algo
00039     {        
00040         namespace Struct
00041         {
00043             namespace Heap
00044             {
00061                 template <class RanIter, class Pred>
00062                 inline void BalanceUp(RanIter begin, Diff top, Diff node, Pred pred)
00063                 {
00064                     while (top < node)
00065                     {
00066                         Diff parent = (node - 1) / 2;
00067 
00068                         if (!pred(begin[parent], begin[node]))
00069                         {
00070                             break;
00071                         }
00072 
00073                         Algo::Swap(begin[parent], begin[node]);
00074                         node = parent;
00075                     }
00076                 }
00077 
00091                 template <class RanIter, class Pred>
00092                 inline void BalanceDown(RanIter begin, Diff node, Diff bottom, Pred pred)
00093                 {
00094                     Diff top = node;
00095                     Diff child = 2 * node + 2;
00096 
00097                     while (child < bottom)
00098                     {
00099                         // Find the larger child
00100                         if (pred(begin[child], begin[child - 1]))
00101                         {
00102                             --child;
00103                         }
00104 
00105                         // Swap with the larger child
00106                         Algo::Swap(begin[node], begin[child]);
00107 
00108                         // Move down the tree
00109                         node = child;
00110                         child = 2 * child + 2;
00111                     }
00112 
00113                     // Only one child at the bottom
00114                     if (child == bottom)
00115                     {                        
00116                         Algo::Swap(begin[node], begin[child - 1]);
00117                         node = child - 1;
00118                     }
00119 
00120                     BalanceUp(begin, top, node, pred);
00121                 }
00122 
00139                 template <class RanIter, class Pred>
00140                 inline void PushHeap(RanIter begin, RanIter end, Pred pred)
00141                 {
00142                     if (begin != end)
00143                     {
00144                         BalanceUp(begin, Diff(0), Diff(end - begin) - 1, pred);
00145                     }
00146                 }
00147 
00163                 template <class RanIter>
00164                 inline void PushHeap(RanIter begin, RanIter end)
00165                 {
00166                     Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
00167                     PushHeap(begin, end, pred);
00168                 }
00169 
00186                 template <class RanIter, class Pred>
00187                 inline void PopHeap(RanIter begin, RanIter end, Pred pred)
00188                 {
00189                     if (Diff(end - begin) > 1)
00190                     {
00191                         --end;
00192                         Algo::Swap(*begin, *end);                        
00193                         BalanceDown(begin, Diff(0), Diff(end - begin), pred);
00194                     }
00195                 }
00196 
00212                 template <class RanIter, class Pred>
00213                 inline void PopHeap(RanIter begin, RanIter end)
00214                 {
00215                     Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
00216                     PopHeap(begin, end, pred);
00217                 }
00218 
00233                 template <class RanIter, class Pred>
00234                 inline void MakeHeap(RanIter begin, RanIter end, Pred pred)
00235                 {
00236                     // Sequence length
00237                     Diff bottom = end - begin;
00238                     // First leaf index
00239                     Diff node = bottom / 2;
00240 
00241                     while (node > 0)
00242                     {
00243                         --node;                        
00244                         BalanceDown(begin, node, bottom, pred);
00245                     }
00246                 }
00247 
00261                 template <class RanIter>
00262                 inline void MakeHeap(RanIter begin, RanIter end)
00263                 {
00264                     Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
00265                     MakeHeap(begin, end, pred);
00266                 }
00267 
00282                 template <class RanIter, class Pred>
00283                 inline void SortHeap(RanIter begin, RanIter end, Pred pred)
00284                 {
00285                     while (begin != end)
00286                     {
00287                         PopHeap(begin, end, pred);
00288                         --end;
00289                     }
00290                 }
00291 
00305                 template <class RanIter>
00306                 inline void SortHeap(RanIter begin, RanIter end)
00307                 {
00308                     Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
00309                     SortHeap(begin, end, pred);
00310                 }
00311 
00326                 template <class RanIter, class Pred>
00327                 inline bool IsHeap(RanIter begin, RanIter end)
00328                 {
00329                     Size len = Distance(begin, end);
00330 
00331                     for (Size i = 0; i < len; ++i)
00332                     {
00333                         if (pred(begin[(i - 1) / 2], begin[i]))
00334                         {
00335                             return false;
00336                         }
00337                     }
00338 
00339                     return true;
00340                 }
00341 
00355                 template <class RanIter>
00356                 inline bool IsHeap(RanIter begin, RanIter end)
00357                 {
00358                     Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
00359                     return IsHeap(begin, end, pred);
00360                 }
00361             }
00362         }
00363     }
00364 }
00365 
00366 #endif