Home | History | Annotate | Download | only in parallel 
      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 
     39 namespace __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