1// -*- C++ -*- 2 3// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file parallel/checkers.h 26 * @brief Routines for checking the correctness of algorithm results. 27 * This file is a GNU parallel extension to the Standard C++ Library. 28 */ 29 30// Written by Johannes Singler. 31 32#ifndef _GLIBCXX_PARALLEL_CHECKERS_H 33#define _GLIBCXX_PARALLEL_CHECKERS_H 1 34 35#include <functional> 36#include <cstdio> 37#include <bits/stl_algobase.h> 38 39namespace __gnu_parallel 40{ 41 /** 42 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 43 * @param begin Begin iterator of sequence. 44 * @param end End iterator of sequence. 45 * @param comp Comparator. 46 * @return @c true if sorted, @c false otherwise. 47 */ 48 // XXX Comparator default template argument 49 template<typename InputIterator, typename Comparator> 50 bool 51 is_sorted(InputIterator begin, InputIterator end, 52 Comparator comp 53 = std::less<typename std::iterator_traits<InputIterator>:: 54 value_type>()) 55 { 56 if (begin == end) 57 return true; 58 59 InputIterator current(begin), recent(begin); 60 61 unsigned long long position = 1; 62 for (current++; current != end; current++) 63 { 64 if (comp(*current, *recent)) 65 { 66 printf("is_sorted: check failed before position %i.\n", 67 position); 68 return false; 69 } 70 recent = current; 71 position++; 72 } 73 74 return true; 75 } 76 77 /** 78 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 79 * Prints the position in case an unordered pair is found. 80 * @param begin Begin iterator of sequence. 81 * @param end End iterator of sequence. 82 * @param first_failure The first failure is returned in this variable. 83 * @param comp Comparator. 84 * @return @c true if sorted, @c false otherwise. 85 */ 86 // XXX Comparator default template argument 87 template<typename InputIterator, typename Comparator> 88 bool 89 is_sorted_failure(InputIterator begin, InputIterator end, 90 InputIterator& first_failure, 91 Comparator comp 92 = std::less<typename std::iterator_traits<InputIterator>:: 93 value_type>()) 94 { 95 if (begin == end) 96 return true; 97 98 InputIterator current(begin), recent(begin); 99 100 unsigned long long position = 1; 101 for (current++; current != end; current++) 102 { 103 if (comp(*current, *recent)) 104 { 105 first_failure = current; 106 printf("is_sorted: check failed before position %lld.\n", 107 position); 108 return false; 109 } 110 recent = current; 111 position++; 112 } 113 114 first_failure = end; 115 return true; 116 } 117 118 /** 119 * @brief Check whether @c [begin, @c end) is sorted according to @c comp. 120 * Prints all unordered pair, including the surrounding two elements. 121 * @param begin Begin iterator of sequence. 122 * @param end End iterator of sequence. 123 * @param comp Comparator. 124 * @return @c true if sorted, @c false otherwise. 125 */ 126 template<typename InputIterator, typename Comparator> 127 bool 128 // XXX Comparator default template argument 129 is_sorted_print_failures(InputIterator begin, InputIterator end, 130 Comparator comp 131 = std::less<typename std::iterator_traits 132 <InputIterator>::value_type>()) 133 { 134 if (begin == end) 135 return true; 136 137 InputIterator recent(begin); 138 bool ok = true; 139 140 for (InputIterator pos(begin + 1); pos != end; pos++) 141 { 142 if (comp(*pos, *recent)) 143 { 144 printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2), 145 *(pos- 1), *pos, *(pos + 1)); 146 ok = false; 147 } 148 recent = pos; 149 } 150 return ok; 151 } 152} 153 154#endif /* _GLIBCXX_PARALLEL_CHECKERS_H */ 155