williamr@4: // (C) Copyright Jeremy Siek 2001.
williamr@4: // Distributed under the Boost Software License, Version 1.0. (See accompany-
williamr@4: // ing file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@4: /*
williamr@4:  *
williamr@4:  * Copyright (c) 1994
williamr@4:  * Hewlett-Packard Company
williamr@4:  *
williamr@4:  * Permission to use, copy, modify, distribute and sell this software
williamr@4:  * and its documentation for any purpose is hereby granted without fee,
williamr@4:  * provided that the above copyright notice appear in all copies and
williamr@4:  * that both that copyright notice and this permission notice appear
williamr@4:  * in supporting documentation.  Hewlett-Packard Company makes no
williamr@4:  * representations about the suitability of this software for any
williamr@4:  * purpose.  It is provided "as is" without express or implied warranty.
williamr@4:  *
williamr@4:  *
williamr@4:  * Copyright (c) 1996
williamr@4:  * Silicon Graphics Computer Systems, Inc.
williamr@4:  *
williamr@4:  * Permission to use, copy, modify, distribute and sell this software
williamr@4:  * and its documentation for any purpose is hereby granted without fee,
williamr@4:  * provided that the above copyright notice appear in all copies and
williamr@4:  * that both that copyright notice and this permission notice appear
williamr@4:  * in supporting documentation.  Silicon Graphics makes no
williamr@4:  * representations about the suitability of this software for any
williamr@4:  * purpose.  It is provided "as is" without express or implied warranty.
williamr@4:  */
williamr@4: 
williamr@4: #ifndef BOOST_ALGORITHM_HPP
williamr@4: # define BOOST_ALGORITHM_HPP
williamr@4: # include <boost/detail/iterator.hpp>
williamr@4: // Algorithms on sequences
williamr@2: //
williamr@4: // The functions in this file have not yet gone through formal
williamr@4: // review, and are subject to change. This is a work in progress.
williamr@4: // They have been checked into the detail directory because
williamr@4: // there are some graph algorithms that use these functions.
williamr@2: 
williamr@4: #include <algorithm>
williamr@4: #include <vector>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@4:   template <typename Iter1, typename Iter2>
williamr@4:   Iter1 begin(const std::pair<Iter1, Iter2>& p) { return p.first; }
williamr@4: 
williamr@4:   template <typename Iter1, typename Iter2>
williamr@4:   Iter2 end(const std::pair<Iter1, Iter2>& p) { return p.second; }
williamr@4: 
williamr@4:   template <typename Iter1, typename Iter2>
williamr@4:   typename boost::detail::iterator_traits<Iter1>::difference_type
williamr@4:   size(const std::pair<Iter1, Iter2>& p) {
williamr@4:     return std::distance(p.first, p.second);
williamr@2:   }
williamr@2: 
williamr@4: #if 0
williamr@4:   // These seem to interfere with the std::pair overloads :(
williamr@4:   template <typename Container>
williamr@4:   typename Container::iterator
williamr@4:   begin(Container& c) { return c.begin(); }
williamr@4: 
williamr@4:   template <typename Container>
williamr@4:   typename Container::const_iterator
williamr@4:   begin(const Container& c) { return c.begin(); }
williamr@4: 
williamr@4:   template <typename Container>
williamr@4:   typename Container::iterator
williamr@4:   end(Container& c) { return c.end(); }
williamr@4: 
williamr@4:   template <typename Container>
williamr@4:   typename Container::const_iterator
williamr@4:   end(const Container& c) { return c.end(); }
williamr@4: 
williamr@4:   template <typename Container>
williamr@4:   typename Container::size_type
williamr@4:   size(const Container& c) { return c.size(); }
williamr@4: #else
williamr@4:   template <typename T>
williamr@4:   typename std::vector<T>::iterator
williamr@4:   begin(std::vector<T>& c) { return c.begin(); }
williamr@4: 
williamr@4:   template <typename T>
williamr@4:   typename std::vector<T>::const_iterator
williamr@4:   begin(const std::vector<T>& c) { return c.begin(); }
williamr@4: 
williamr@4:   template <typename T>
williamr@4:   typename std::vector<T>::iterator
williamr@4:   end(std::vector<T>& c) { return c.end(); }
williamr@4: 
williamr@4:   template <typename T>
williamr@4:   typename std::vector<T>::const_iterator
williamr@4:   end(const std::vector<T>& c) { return c.end(); }
williamr@4: 
williamr@4:   template <typename T>
williamr@4:   typename std::vector<T>::size_type
williamr@4:   size(const std::vector<T>& c) { return c.size(); }
williamr@4: #endif
williamr@4:   
williamr@4:   template <class ForwardIterator, class T>
williamr@4:   void iota(ForwardIterator first, ForwardIterator last, T value)
williamr@4:   {
williamr@4:     for (; first != last; ++first, ++value)
williamr@4:       *first = value;
williamr@2:   }
williamr@4:   template <typename Container, typename T>
williamr@4:   void iota(Container& c, const T& value)
williamr@4:   {
williamr@4:     iota(begin(c), end(c), value);
williamr@4:   }
williamr@4:  
williamr@4:   // Also do version with 2nd container?
williamr@4:   template <typename Container, typename OutIter>
williamr@4:   OutIter copy(const Container& c, OutIter result) {
williamr@4:     return std::copy(begin(c), end(c), result);
williamr@4:   }
williamr@2: 
williamr@4:   template <typename Container1, typename Container2>
williamr@4:   bool equal(const Container1& c1, const Container2& c2)
williamr@4:   {
williamr@4:     if (size(c1) != size(c2))
williamr@4:       return false;
williamr@4:     return std::equal(begin(c1), end(c1), begin(c2));
williamr@4:   }
williamr@2: 
williamr@4:   template <typename Container>
williamr@4:   void sort(Container& c) { std::sort(begin(c), end(c)); }
williamr@2: 
williamr@4:   template <typename Container, typename Predicate>
williamr@4:   void sort(Container& c, const Predicate& p) { 
williamr@4:     std::sort(begin(c), end(c), p);
williamr@4:   }
williamr@2: 
williamr@4:   template <typename Container>
williamr@4:   void stable_sort(Container& c) { std::stable_sort(begin(c), end(c)); }
williamr@4: 
williamr@4:   template <typename Container, typename Predicate>
williamr@4:   void stable_sort(Container& c, const Predicate& p) { 
williamr@4:     std::stable_sort(begin(c), end(c), p);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename InputIterator, typename Predicate>
williamr@4:   bool any_if(InputIterator first, InputIterator last, Predicate p)
williamr@4:   {
williamr@4:     return std::find_if(first, last, p) != last;
williamr@4:   }
williamr@4:   template <typename Container, typename Predicate>
williamr@4:   bool any_if(const Container& c, Predicate p)
williamr@4:   {
williamr@4:     return any_if(begin(c), end(c), p);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename InputIterator, typename T>
williamr@4:   bool contains(InputIterator first, InputIterator last, T value)
williamr@4:   {
williamr@4:     return std::find(first, last, value) != last;
williamr@4:   }
williamr@4:   template <typename Container, typename T>
williamr@4:   bool contains(const Container& c, const T& value)
williamr@4:   {
williamr@4:     return contains(begin(c), end(c), value);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename InputIterator, typename Predicate>
williamr@4:   bool all(InputIterator first, InputIterator last, Predicate p)
williamr@4:   {
williamr@4:     for (; first != last; ++first)
williamr@4:       if (!p(*first))
williamr@4:         return false;
williamr@4:     return true;
williamr@4:   }
williamr@4:   template <typename Container, typename Predicate>
williamr@4:   bool all(const Container& c, Predicate p)
williamr@4:   {
williamr@4:     return all(begin(c), end(c), p);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename Container, typename T>
williamr@4:   std::size_t count(const Container& c, const T& value)
williamr@4:   {
williamr@4:     return std::count(begin(c), end(c), value);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename Container, typename Predicate>
williamr@4:   std::size_t count_if(const Container& c, Predicate p)
williamr@4:   {
williamr@4:     return std::count_if(begin(c), end(c), p);
williamr@4:   }
williamr@4: 
williamr@4:   template <typename ForwardIterator>
williamr@4:   bool is_sorted(ForwardIterator first, ForwardIterator last)
williamr@4:   {
williamr@4:     if (first == last)
williamr@4:       return true;
williamr@4: 
williamr@4:     ForwardIterator next = first;
williamr@4:     for (++next; next != last; first = next, ++next) {
williamr@4:       if (*next < *first)
williamr@4:         return false;
williamr@4:     }
williamr@4: 
williamr@4:     return true;
williamr@4:   }
williamr@4: 
williamr@4:   template <typename ForwardIterator, typename StrictWeakOrdering>
williamr@4:   bool is_sorted(ForwardIterator first, ForwardIterator last,
williamr@4:                  StrictWeakOrdering comp)
williamr@4:   {
williamr@4:     if (first == last)
williamr@4:       return true;
williamr@4: 
williamr@4:     ForwardIterator next = first;
williamr@4:     for (++next; next != last; first = next, ++next) {
williamr@4:       if (comp(*next, *first))
williamr@4:         return false;
williamr@4:     }
williamr@4: 
williamr@4:     return true;
williamr@4:   }
williamr@4: 
williamr@4:   template <typename Container>
williamr@4:   bool is_sorted(const Container& c)
williamr@4:   {
williamr@4:     return is_sorted(begin(c), end(c));
williamr@4:   }
williamr@4: 
williamr@4:   template <typename Container, typename StrictWeakOrdering>
williamr@4:   bool is_sorted(const Container& c, StrictWeakOrdering comp)
williamr@4:   {
williamr@4:     return is_sorted(begin(c), end(c), comp);
williamr@4:   }
williamr@4: 
williamr@2: } // namespace boost
williamr@2: 
williamr@4: #endif // BOOST_ALGORITHM_HPP