PLearn 0.1
heap_utilities.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // heap_utilities.h
00004 //
00005 // Copyright (C) 2005 Nicolas Chapados 
00006 // 
00007 // Redistribution and use in source and binary forms, with or without
00008 // modification, are permitted provided that the following conditions are met:
00009 // 
00010 //  1. Redistributions of source code must retain the above copyright
00011 //     notice, this list of conditions and the following disclaimer.
00012 // 
00013 //  2. Redistributions in binary form must reproduce the above copyright
00014 //     notice, this list of conditions and the following disclaimer in the
00015 //     documentation and/or other materials provided with the distribution.
00016 // 
00017 //  3. The name of the authors may not be used to endorse or promote
00018 //     products derived from this software without specific prior written
00019 //     permission.
00020 // 
00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031 // 
00032 // This file is part of the PLearn library. For more information on the PLearn
00033 // library, go to the PLearn Web site at www.plearn.org
00034 
00035 /* *******************************************************      
00036  * $Id: heap_utilities.h 3994 2005-08-25 13:35:03Z chapados $ 
00037  ******************************************************* */
00038 
00039 // Authors: Nicolas Chapados
00040 
00044 #ifndef heap_utilities_INC
00045 #define heap_utilities_INC
00046 
00047 // From C++ stdlib
00048 #include <algorithm>
00049 #include <iterator>
00050 #include <functional>
00051 
00052 
00053 namespace PLearn {
00054 
00064 template <typename RandomAccessIterator, typename StrictWeakOrdering>
00065 void
00066 update_heap(RandomAccessIterator first, RandomAccessIterator last,
00067             RandomAccessIterator damaged, StrictWeakOrdering comp)
00068 {
00069     typedef typename std::iterator_traits<RandomAccessIterator>::difference_type
00070         difference_type;
00071     difference_type cur = damaged-first;
00072     difference_type size = last-first;
00073     typename
00074         std::iterator_traits<RandomAccessIterator>::value_type value = *damaged;
00075 
00076     // Push down as much as possible, then push up
00077     difference_type second_child = 2*cur+2;
00078     while (second_child < size) {              // there are two children
00079         if (comp(first[second_child], first[second_child-1]))
00080             second_child--;                        // take larger child
00081         first[cur] = first[second_child];        // fill hole
00082         cur = second_child;
00083         second_child = 2 * (second_child+1);
00084     }
00085     if (second_child == size) {
00086         first[cur] = first[second_child-1];      // hole is in first child
00087         cur = second_child-1;
00088     }
00089     first[cur] = value;
00090     push_heap(first,first+cur+1,comp);
00091 }
00092 
00093 
00097 template <typename RandomAccessIterator>
00098 inline
00099 void
00100 update_heap(RandomAccessIterator first, RandomAccessIterator last,
00101             RandomAccessIterator damaged)
00102 {
00103     typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
00104     update_heap(first,last,damaged, std::less<value_type>());
00105 }
00106 
00107 
00113 template <typename RandomAccessIterator, typename StrictWeakOrdering>
00114 bool is_valid_heap(RandomAccessIterator first, RandomAccessIterator last,
00115                    StrictWeakOrdering comp)
00116 {
00117     if (first==last)
00118         return true;
00119 
00120     RandomAccessIterator parent = first;
00121     int i=1;
00122     for (RandomAccessIterator it = first+1 ; it < last ; ++it, ++i) {
00123         if (comp(*parent, *it))
00124             return false;
00125         if ((i & 1) == 0)
00126             ++parent;
00127     }
00128     return true;
00129 }
00130 
00131 
00133 template <typename RandomAccessIterator>
00134 inline
00135 bool is_valid_heap(RandomAccessIterator first, RandomAccessIterator last)
00136 {
00137     typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
00138     return is_valid_heap(first,last,std::less<value_type>());
00139 }
00140 
00141 
00142 } // end namespace PLearn
00143 
00144 #endif
00145 
00146 
00147 /*
00148   Local Variables:
00149   mode:c++
00150   c-basic-offset:4
00151   c-file-style:"stroustrup"
00152   c-file-offsets:((innamespace . 0)(inline-open . 0))
00153   indent-tabs-mode:nil
00154   fill-column:79
00155   End:
00156 */
00157 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines