checkers.h

Go to the documentation of this file.
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 */

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1