checkers.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/checkers.h
00032  *  @brief Routines for checking the correctness of algorithm results.
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_CHECKERS
00039 #define _GLIBCXX_PARALLEL_CHECKERS 1
00040 
00041 #include <functional>
00042 #include <cstdio>
00043 #include <bits/stl_algobase.h>
00044 
00045 namespace __gnu_parallel
00046 {
00047   /**
00048    * @brief Check whether @c [begin, @c end) is sorted according to @c comp.
00049    * @param begin Begin iterator of sequence.
00050    * @param end End iterator of sequence.
00051    * @param comp Comparator.
00052    * @return @c true if sorted, @c false otherwise.
00053    */
00054   // XXX Comparator default template argument
00055   template<typename InputIterator, typename Comparator>
00056     bool
00057     is_sorted(InputIterator begin, InputIterator end,
00058           Comparator comp
00059           = std::less<typename std::iterator_traits<InputIterator>::
00060           value_type>())
00061     {
00062       if (begin == end)
00063     return true;
00064 
00065       InputIterator current(begin), recent(begin);
00066 
00067       unsigned long long position = 1;
00068       for (current++; current != end; current++)
00069     {
00070       if (comp(*current, *recent))
00071         {
00072           printf("is_sorted: check failed before position %i.\n",
00073              position);
00074           return false;
00075         }
00076       recent = current;
00077       position++;
00078     }
00079 
00080       return true;
00081     }
00082 
00083   /**
00084    * @brief Check whether @c [begin, @c end) is sorted according to @c comp.
00085    * Prints the position in case an unordered pair is found.
00086    * @param begin Begin iterator of sequence.
00087    * @param end End iterator of sequence.
00088    * @param first_failure The first failure is returned in this variable.
00089    * @param comp Comparator.
00090    * @return @c true if sorted, @c false otherwise.
00091    */
00092   // XXX Comparator default template argument
00093   template<typename InputIterator, typename Comparator>
00094     bool
00095     is_sorted_failure(InputIterator begin, InputIterator end,
00096               InputIterator& first_failure,
00097               Comparator comp
00098               = std::less<typename std::iterator_traits<InputIterator>::
00099               value_type>())
00100     {
00101       if (begin == end)
00102     return true;
00103 
00104       InputIterator current(begin), recent(begin);
00105 
00106       unsigned long long position = 1;
00107       for (current++; current != end; current++)
00108     {
00109       if (comp(*current, *recent))
00110         {
00111           first_failure = current;
00112           printf("is_sorted: check failed before position %lld.\n",
00113              position);
00114           return false;
00115         }
00116       recent = current;
00117       position++;
00118     }
00119 
00120       first_failure = end;
00121       return true;
00122     }
00123 
00124   /**
00125    * @brief Check whether @c [begin, @c end) is sorted according to @c comp.
00126    * Prints all unordered pair, including the surrounding two elements.
00127    * @param begin Begin iterator of sequence.
00128    * @param end End iterator of sequence.
00129    * @param comp Comparator.
00130    * @return @c true if sorted, @c false otherwise.
00131    */
00132   template<typename InputIterator, typename Comparator>
00133     bool
00134     // XXX Comparator default template argument
00135     is_sorted_print_failures(InputIterator begin, InputIterator end,
00136                  Comparator comp
00137                  = std::less<typename std::iterator_traits
00138                  <InputIterator>::value_type>())
00139     {
00140       if (begin == end)
00141     return true;
00142 
00143       InputIterator recent(begin);
00144       bool ok = true;
00145 
00146       for (InputIterator pos(begin + 1); pos != end; pos++)
00147     {
00148       if (comp(*pos, *recent))
00149         {
00150           printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2),
00151              *(pos- 1), *pos, *(pos + 1));
00152           ok = false;
00153         }
00154       recent = pos;
00155     }
00156       return ok;
00157     }
00158 }
00159 
00160 #endif

Generated on Sat Dec 12 09:40:09 2009 for libstdc++ by  doxygen 1.5.6