// (C) Copyright Jeremy Siek 2001.

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

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

 /*

  *

  * Copyright (c) 1994

  * Hewlett-Packard Company

  *

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

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

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

  * that both that copyright notice and this permission notice appear

  * in supporting documentation.  Hewlett-Packard Company makes no

  * representations about the suitability of this software for any

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

  *

  *

  * Copyright (c) 1996

  * Silicon Graphics Computer Systems, Inc.

  *

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

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

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

  * that both that copyright notice and this permission notice appear

  * in supporting documentation.  Silicon Graphics makes no

  * representations about the suitability of this software for any

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

  */

 #ifndef BOOST_ALGORITHM_HPP

 # define BOOST_ALGORITHM_HPP

 # include <boost/detail/iterator.hpp>

 // Algorithms on sequences

 //

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

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

 // They have been checked into the detail directory because

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

 #include <algorithm>

 #include <vector>

 namespace boost {

   template <typename Iter1, typename Iter2>

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

   template <typename Iter1, typename Iter2>

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

   template <typename Iter1, typename Iter2>

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

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

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

   }

 #if 0

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

   template <typename Container>

   typename Container::iterator

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

   template <typename Container>

   typename Container::const_iterator

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

   template <typename Container>

   typename Container::iterator

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

   template <typename Container>

   typename Container::const_iterator

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

   template <typename Container>

   typename Container::size_type

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

 #else

   template <typename T>

   typename std::vector<T>::iterator

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

   template <typename T>

   typename std::vector<T>::const_iterator

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

   template <typename T>

   typename std::vector<T>::iterator

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

   template <typename T>

   typename std::vector<T>::const_iterator

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

   template <typename T>

   typename std::vector<T>::size_type

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

 #endif

   template <class ForwardIterator, class T>

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

   {

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

       *first = value;

   }

   template <typename Container, typename T>

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

   {

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

   }

   // Also do version with 2nd container?

   template <typename Container, typename OutIter>

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

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

   }

   template <typename Container1, typename Container2>

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

   {

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

       return false;

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

   }

   template <typename Container>

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

   template <typename Container, typename Predicate>

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

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

   }

   template <typename Container>

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

   template <typename Container, typename Predicate>

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

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

   }

   template <typename InputIterator, typename Predicate>

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

   {

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

   }

   template <typename Container, typename Predicate>

   bool any_if(const Container& c, Predicate p)

   {

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

   }

   template <typename InputIterator, typename T>

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

   {

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

   }

   template <typename Container, typename T>

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

   {

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

   }

   template <typename InputIterator, typename Predicate>

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

   {

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

       if (!p(*first))

         return false;

     return true;

   }

   template <typename Container, typename Predicate>

   bool all(const Container& c, Predicate p)

   {

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

   }

   template <typename Container, typename T>

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

   {

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

   }

   template <typename Container, typename Predicate>

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

   {

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

   }

   template <typename ForwardIterator>

   bool is_sorted(ForwardIterator first, ForwardIterator last)

   {

     if (first == last)

       return true;

     ForwardIterator next = first;

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

       if (*next < *first)

         return false;

     }

     return true;

   }

   template <typename ForwardIterator, typename StrictWeakOrdering>

   bool is_sorted(ForwardIterator first, ForwardIterator last,

                  StrictWeakOrdering comp)

   {

     if (first == last)

       return true;

     ForwardIterator next = first;

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

       if (comp(*next, *first))

         return false;

     }

     return true;

   }

   template <typename Container>

   bool is_sorted(const Container& c)

   {

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

   }

   template <typename Container, typename StrictWeakOrdering>

   bool is_sorted(const Container& c, StrictWeakOrdering comp)

   {

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

   }

 } // namespace boost

 #endif // BOOST_ALGORITHM_HPP