PLearn 0.1
|
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 :