1 // (C) Copyright Jeremy Siek 2001.

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

     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

    35 //

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

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

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

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

    40 

    41 #include <algorithm>

    42 #include <vector>

    43 

    44 namespace boost {

    45 

    46   template <typename Iter1, typename Iter2>

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

    48 

    49   template <typename Iter1, typename Iter2>

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

    51 

    52   template <typename Iter1, typename Iter2>

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

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

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

    56   }

    57 

    58 #if 0

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

    60   template <typename Container>

    61   typename Container::iterator

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

    63 

    64   template <typename Container>

    65   typename Container::const_iterator

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

    67 

    68   template <typename Container>

    69   typename Container::iterator

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

    71 

    72   template <typename Container>

    73   typename Container::const_iterator

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

    75 

    76   template <typename Container>

    77   typename Container::size_type

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

    79 #else

    80   template <typename T>

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

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

    83 

    84   template <typename T>

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

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

    87 

    88   template <typename T>

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

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

    91 

    92   template <typename T>

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

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

    95 

    96   template <typename T>

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

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

    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 container_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 container_contains(const Container& c, const T& value)

   161   {

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

   163   }

   164 

   165   template <typename Container, typename T>

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

   167   {

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

   169   }

   170 

   171   template <typename Container, typename Predicate>

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

   173   {

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

   175   }

   176 

   177   template <typename ForwardIterator>

   178   bool is_sorted(ForwardIterator first, ForwardIterator last)

   179   {

   180     if (first == last)

   181       return true;

   182 

   183     ForwardIterator next = first;

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

   185       if (*next < *first)

   186         return false;

   187     }

   188 

   189     return true;

   190   }

   191 

   192   template <typename ForwardIterator, typename StrictWeakOrdering>

   193   bool is_sorted(ForwardIterator first, ForwardIterator last,

   194                  StrictWeakOrdering comp)

   195   {

   196     if (first == last)

   197       return true;

   198 

   199     ForwardIterator next = first;

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

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

   202         return false;

   203     }

   204 

   205     return true;

   206   }

   207 

   208   template <typename Container>

   209   bool is_sorted(const Container& c)

   210   {

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

   212   }

   213 

   214   template <typename Container, typename StrictWeakOrdering>

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

   216   {

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

   218   }

   219 

   220 } // namespace boost

   221 

   222 #endif // BOOST_ALGORITHM_HPP