boost/detail/algorithm.hpp

   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