libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/checkers.h 00026 * @brief Routines for checking the correctness of algorithm results. 00027 * This file is a GNU parallel extension to the Standard C++ Library. 00028 */ 00029 00030 // Written by Johannes Singler. 00031 00032 #ifndef _GLIBCXX_PARALLEL_CHECKERS_H 00033 #define _GLIBCXX_PARALLEL_CHECKERS_H 1 00034 00035 #include <functional> 00036 #include <cstdio> 00037 #include <bits/stl_algobase.h> 00038 00039 namespace __gnu_parallel 00040 { 00041 /** 00042 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 00043 * @param begin Begin iterator of sequence. 00044 * @param end End iterator of sequence. 00045 * @param comp Comparator. 00046 * @return @c true if sorted, @c false otherwise. 00047 */ 00048 // XXX Comparator default template argument 00049 template<typename InputIterator, typename Comparator> 00050 bool 00051 is_sorted(InputIterator begin, InputIterator end, 00052 Comparator comp 00053 = std::less<typename std::iterator_traits<InputIterator>:: 00054 value_type>()) 00055 { 00056 if (begin == end) 00057 return true; 00058 00059 InputIterator current(begin), recent(begin); 00060 00061 unsigned long long position = 1; 00062 for (current++; current != end; current++) 00063 { 00064 if (comp(*current, *recent)) 00065 { 00066 printf("is_sorted: check failed before position %i.\n", 00067 position); 00068 return false; 00069 } 00070 recent = current; 00071 position++; 00072 } 00073 00074 return true; 00075 } 00076 00077 /** 00078 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 00079 * Prints the position in case an unordered pair is found. 00080 * @param begin Begin iterator of sequence. 00081 * @param end End iterator of sequence. 00082 * @param first_failure The first failure is returned in this variable. 00083 * @param comp Comparator. 00084 * @return @c true if sorted, @c false otherwise. 00085 */ 00086 // XXX Comparator default template argument 00087 template<typename InputIterator, typename Comparator> 00088 bool 00089 is_sorted_failure(InputIterator begin, InputIterator end, 00090 InputIterator& first_failure, 00091 Comparator comp 00092 = std::less<typename std::iterator_traits<InputIterator>:: 00093 value_type>()) 00094 { 00095 if (begin == end) 00096 return true; 00097 00098 InputIterator current(begin), recent(begin); 00099 00100 unsigned long long position = 1; 00101 for (current++; current != end; current++) 00102 { 00103 if (comp(*current, *recent)) 00104 { 00105 first_failure = current; 00106 printf("is_sorted: check failed before position %lld.\n", 00107 position); 00108 return false; 00109 } 00110 recent = current; 00111 position++; 00112 } 00113 00114 first_failure = end; 00115 return true; 00116 } 00117 00118 /** 00119 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 00120 * Prints all unordered pair, including the surrounding two elements. 00121 * @param begin Begin iterator of sequence. 00122 * @param end End iterator of sequence. 00123 * @param comp Comparator. 00124 * @return @c true if sorted, @c false otherwise. 00125 */ 00126 template<typename InputIterator, typename Comparator> 00127 bool 00128 // XXX Comparator default template argument 00129 is_sorted_print_failures(InputIterator begin, InputIterator end, 00130 Comparator comp 00131 = std::less<typename std::iterator_traits 00132 <InputIterator>::value_type>()) 00133 { 00134 if (begin == end) 00135 return true; 00136 00137 InputIterator recent(begin); 00138 bool ok = true; 00139 00140 for (InputIterator pos(begin + 1); pos != end; pos++) 00141 { 00142 if (comp(*pos, *recent)) 00143 { 00144 printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2), 00145 *(pos- 1), *pos, *(pos + 1)); 00146 ok = false; 00147 } 00148 recent = pos; 00149 } 00150 return ok; 00151 } 00152 } 00153 00154 #endif /* _GLIBCXX_PARALLEL_CHECKERS_H */