contrib/gcc-4.4/libstdc++-v3/include/parallel/checkers.h

   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 */