1 #ifndef BOOST_ALGORITHM_RG071801_HPP

     1 // (C) Copyright Jeremy Siek 2001.

     2 #define BOOST_ALGORITHM_RG071801_HPP

     2 // Distributed under the Boost Software License, Version 1.0. (See accompany-

     3 

     3 // ing file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

     4 

     5 /*

     6  *

     7  * Copyright (c) 1994

     8  * Hewlett-Packard Company

     9  *

    10  * Permission to use, copy, modify, distribute and sell this software

    11  * and its documentation for any purpose is hereby granted without fee,

    12  * provided that the above copyright notice appear in all copies and

    13  * that both that copyright notice and this permission notice appear

    14  * in supporting documentation.  Hewlett-Packard Company makes no

    15  * representations about the suitability of this software for any

    16  * purpose.  It is provided "as is" without express or implied warranty.

    17  *

    18  *

    19  * Copyright (c) 1996

    20  * Silicon Graphics Computer Systems, Inc.

    21  *

    22  * Permission to use, copy, modify, distribute and sell this software

    23  * and its documentation for any purpose is hereby granted without fee,

    24  * provided that the above copyright notice appear in all copies and

    25  * that both that copyright notice and this permission notice appear

    26  * in supporting documentation.  Silicon Graphics makes no

    27  * representations about the suitability of this software for any

    28  * purpose.  It is provided "as is" without express or implied warranty.

    29  */

    30 

    31 #ifndef BOOST_ALGORITHM_HPP

    32 # define BOOST_ALGORITHM_HPP

    33 # include <boost/detail/iterator.hpp>

    34 // Algorithms on sequences

     5 //

    36 // The functions in this file have not yet gone through formal

     6 // Copyright (c) 1994

    37 // review, and are subject to change. This is a work in progress.

     7 // Hewlett-Packard Company

    38 // They have been checked into the detail directory because

     8 //

    39 // there are some graph algorithms that use these functions.

     9 // Permission to use, copy, modify, distribute and sell this software

    40 

    10 // and its documentation for any purpose is hereby granted without fee,

    41 #include <algorithm>

    11 // provided that the above copyright notice appear in all copies and

    42 #include <vector>

    12 // that both that copyright notice and this permission notice appear

    13 // in supporting documentation.  Hewlett-Packard Company makes no

    14 // representations about the suitability of this software for any

    15 // purpose.  It is provided "as is" without express or implied warranty.

    16 //

    17 //

    18 // Copyright (c) 1996-1998

    19 // Silicon Graphics Computer Systems, Inc.

    20 //

    21 // Permission to use, copy, modify, distribute and sell this software

    22 // and its documentation for any purpose is hereby granted without fee,

    23 // provided that the above copyright notice appear in all copies and

    24 // that both that copyright notice and this permission notice appear

    25 // in supporting documentation.  Silicon Graphics makes no

    26 // representations about the suitability of this software for any

    27 // purpose.  It is provided "as is" without express or implied warranty.

    28 //

    29 

    30 // Copyright 2002 The Trustees of Indiana University.

    31 

    32 // Use, modification and distribution is subject to the Boost Software 

    33 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

    34 // http://www.boost.org/LICENSE_1_0.txt)

    35 

    36 //  Boost.MultiArray Library

    37 //  Authors: Ronald Garcia

    38 //           Jeremy Siek

    39 //           Andrew Lumsdaine

    40 //  See http://www.boost.org/libs/multi_array for documentation.

    41 

    42 

    43 #include "boost/iterator.hpp"

    46 namespace detail {

    45 

    47 namespace multi_array {

    46   template <typename Iter1, typename Iter2>

    48 //--------------------------------------------------

    47   Iter1 begin(const std::pair<Iter1, Iter2>& p) { return p.first; }

    49 // copy_n (not part of the C++ standard)

    48 

    50 #if 1

    49   template <typename Iter1, typename Iter2>

    51 

    50   Iter2 end(const std::pair<Iter1, Iter2>& p) { return p.second; }

    52 template <class InputIter, class Size, class OutputIter>

    51 

    53 OutputIter copy_n(InputIter first, Size count,

    52   template <typename Iter1, typename Iter2>

    54                   OutputIter result) {

    53   typename boost::detail::iterator_traits<Iter1>::difference_type

    55   for ( ; count > 0; --count) {

    54   size(const std::pair<Iter1, Iter2>& p) {

    56     *result = *first;

    55     return std::distance(p.first, p.second);

    57     ++first;

    56   }

    58     ++result;

    57 

    59   }

    58 #if 0

    60   return result;

    59   // These seem to interfere with the std::pair overloads :(

    61 }

    60   template <typename Container>

    62 #else // !1

    61   typename Container::iterator

    63 

    62   begin(Container& c) { return c.begin(); }

    64 template <class InputIter, class Size, class OutputIter>

    63 

    65 OutputIter copy_n__(InputIter first, Size count,

    64   template <typename Container>

    66                                        OutputIter result,

    65   typename Container::const_iterator

    67                                        std::input_iterator_tag) {

    66   begin(const Container& c) { return c.begin(); }

    68   for ( ; count > 0; --count) {

    67 

    69     *result = *first;

    68   template <typename Container>

    70     ++first;

    69   typename Container::iterator

    71     ++result;

    70   end(Container& c) { return c.end(); }

    72   }

    71 

    73   return result;

    72   template <typename Container>

    74 }

    73   typename Container::const_iterator

    75 

    74   end(const Container& c) { return c.end(); }

    76 template <class RAIter, class Size, class OutputIter>

    75 

    77 inline OutputIter

    76   template <typename Container>

    78 copy_n__(RAIter first, Size count,

    77   typename Container::size_type

    79          OutputIter result,

    78   size(const Container& c) { return c.size(); }

    80          std::random_access_iterator_tag) {

    79 #else

    81   RAIter last = first + count;

    80   template <typename T>

    82   return std::copy(first, last, result);

    81   typename std::vector<T>::iterator

    83 }

    82   begin(std::vector<T>& c) { return c.begin(); }

    84 

    83 

    85 template <class InputIter, class Size, class OutputIter>

    84   template <typename T>

    86 inline OutputIter

    85   typename std::vector<T>::const_iterator

    87 copy_n__(InputIter first, Size count, OutputIter result) {

    86   begin(const std::vector<T>& c) { return c.begin(); }

    88   typedef typename std::iterator_traits<InputIter>::iterator_category cat;

    87 

    89   return copy_n__(first, count, result, cat());

    88   template <typename T>

    90 }

    89   typename std::vector<T>::iterator

    91 

    90   end(std::vector<T>& c) { return c.end(); }

    92 template <class InputIter, class Size, class OutputIter>

    91 

    93 inline OutputIter

    92   template <typename T>

    94 copy_n(InputIter first, Size count, OutputIter result) {

    93   typename std::vector<T>::const_iterator

    95   return copy_n__(first, count, result);

    94   end(const std::vector<T>& c) { return c.end(); }

    96 }

    95 

    97 

    96   template <typename T>

    98 #endif // 1

    97   typename std::vector<T>::size_type

    99 } // namespace multi_array

    98   size(const std::vector<T>& c) { return c.size(); }

   100 } // namespace detail

    99 #endif

   100   

   101   template <class ForwardIterator, class T>

   102   void iota(ForwardIterator first, ForwardIterator last, T value)

   103   {

   104     for (; first != last; ++first, ++value)

   105       *first = value;

   106   }

   107   template <typename Container, typename T>

   108   void iota(Container& c, const T& value)

   109   {

   110     iota(begin(c), end(c), value);

   111   }

   112  

   113   // Also do version with 2nd container?

   114   template <typename Container, typename OutIter>

   115   OutIter copy(const Container& c, OutIter result) {

   116     return std::copy(begin(c), end(c), result);

   117   }

   118 

   119   template <typename Container1, typename Container2>

   120   bool equal(const Container1& c1, const Container2& c2)

   121   {

   122     if (size(c1) != size(c2))

   123       return false;

   124     return std::equal(begin(c1), end(c1), begin(c2));

   125   }

   126 

   127   template <typename Container>

   128   void sort(Container& c) { std::sort(begin(c), end(c)); }

   129 

   130   template <typename Container, typename Predicate>

   131   void sort(Container& c, const Predicate& p) { 

   132     std::sort(begin(c), end(c), p);

   133   }

   134 

   135   template <typename Container>

   136   void stable_sort(Container& c) { std::stable_sort(begin(c), end(c)); }

   137 

   138   template <typename Container, typename Predicate>

   139   void stable_sort(Container& c, const Predicate& p) { 

   140     std::stable_sort(begin(c), end(c), p);

   141   }

   142 

   143   template <typename InputIterator, typename Predicate>

   144   bool any_if(InputIterator first, InputIterator last, Predicate p)

   145   {

   146     return std::find_if(first, last, p) != last;

   147   }

   148   template <typename Container, typename Predicate>

   149   bool any_if(const Container& c, Predicate p)

   150   {

   151     return any_if(begin(c), end(c), p);

   152   }

   153 

   154   template <typename InputIterator, typename T>

   155   bool contains(InputIterator first, InputIterator last, T value)

   156   {

   157     return std::find(first, last, value) != last;

   158   }

   159   template <typename Container, typename T>

   160   bool contains(const Container& c, const T& value)

   161   {

   162     return contains(begin(c), end(c), value);

   163   }

   164 

   165   template <typename InputIterator, typename Predicate>

   166   bool all(InputIterator first, InputIterator last, Predicate p)

   167   {

   168     for (; first != last; ++first)

   169       if (!p(*first))

   170         return false;

   171     return true;

   172   }

   173   template <typename Container, typename Predicate>

   174   bool all(const Container& c, Predicate p)

   175   {

   176     return all(begin(c), end(c), p);

   177   }

   178 

   179   template <typename Container, typename T>

   180   std::size_t count(const Container& c, const T& value)

   181   {

   182     return std::count(begin(c), end(c), value);

   183   }

   184 

   185   template <typename Container, typename Predicate>

   186   std::size_t count_if(const Container& c, Predicate p)

   187   {

   188     return std::count_if(begin(c), end(c), p);

   189   }

   190 

   191   template <typename ForwardIterator>

   192   bool is_sorted(ForwardIterator first, ForwardIterator last)

   193   {

   194     if (first == last)

   195       return true;

   196 

   197     ForwardIterator next = first;

   198     for (++next; next != last; first = next, ++next) {

   199       if (*next < *first)

   200         return false;

   201     }

   202 

   203     return true;

   204   }

   205 

   206   template <typename ForwardIterator, typename StrictWeakOrdering>

   207   bool is_sorted(ForwardIterator first, ForwardIterator last,

   208                  StrictWeakOrdering comp)

   209   {

   210     if (first == last)

   211       return true;

   212 

   213     ForwardIterator next = first;

   214     for (++next; next != last; first = next, ++next) {

   215       if (comp(*next, *first))

   216         return false;

   217     }

   218 

   219     return true;

   220   }

   221 

   222   template <typename Container>

   223   bool is_sorted(const Container& c)

   224   {

   225     return is_sorted(begin(c), end(c));

   226   }

   227 

   228   template <typename Container, typename StrictWeakOrdering>

   229   bool is_sorted(const Container& c, StrictWeakOrdering comp)

   230   {

   231     return is_sorted(begin(c), end(c), comp);

   232   }

   233 

   103 #endif // BOOST_ALGORITHM_RG071801_HPP

   236 #endif // BOOST_ALGORITHM_HPP