boost/boost/detail/algorithm.hpp

   1 // (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify,
   2 // sell and distribute this software is granted provided this
   3 // copyright notice appears in all copies. This software is provided
   4 // "as is" without express or implied warranty, and with no claim as
   5 // to its suitability for any purpose.
   6
   7 /*
   8  *
   9  * Copyright (c) 1994
  10  * Hewlett-Packard Company
  11  *
  12  * Permission to use, copy, modify, distribute and sell this software
  13  * and its documentation for any purpose is hereby granted without fee,
  14  * provided that the above copyright notice appear in all copies and
  15  * that both that copyright notice and this permission notice appear
  16  * in supporting documentation.  Hewlett-Packard Company makes no
  17  * representations about the suitability of this software for any
  18  * purpose.  It is provided "as is" without express or implied warranty.
  19  *
  20  *
  21  * Copyright (c) 1996
  22  * Silicon Graphics Computer Systems, Inc.
  23  *
  24  * Permission to use, copy, modify, distribute and sell this software
  25  * and its documentation for any purpose is hereby granted without fee,
  26  * provided that the above copyright notice appear in all copies and
  27  * that both that copyright notice and this permission notice appear
  28  * in supporting documentation.  Silicon Graphics makes no
  29  * representations about the suitability of this software for any
  30  * purpose.  It is provided "as is" without express or implied warranty.
  31  */
  32
  33 #ifndef BOOST_ALGORITHM_HPP
  34 # define BOOST_ALGORITHM_HPP
  35 # include <boost/detail/iterator.hpp>
  36 // Algorithms on sequences
  37 //
  38 // The functions in this file have not yet gone through formal
  39 // review, and are subject to change. This is a work in progress.
  40 // They have been checked into the detail directory because
  41 // there are some graph algorithms that use these functions.
  42
  43 #include <algorithm>
  44 #include <vector>
  45
  46 namespace boost {
  47
  48   template <typename Iter1, typename Iter2>
  49   Iter1 begin(const std::pair<Iter1, Iter2>& p) { return p.first; }
  50
  51   template <typename Iter1, typename Iter2>
  52   Iter2 end(const std::pair<Iter1, Iter2>& p) { return p.second; }
  53
  54   template <typename Iter1, typename Iter2>
  55   typename boost::detail::iterator_traits<Iter1>::difference_type
  56   size(const std::pair<Iter1, Iter2>& p) {
  57     return std::distance(p.first, p.second);
  58   }
  59
  60 #if 0
  61   // These seem to interfere with the std::pair overloads :(
  62   template <typename Container>
  63   typename Container::iterator
  64   begin(Container& c) { return c.begin(); }
  65
  66   template <typename Container>
  67   typename Container::const_iterator
  68   begin(const Container& c) { return c.begin(); }
  69
  70   template <typename Container>
  71   typename Container::iterator
  72   end(Container& c) { return c.end(); }
  73
  74   template <typename Container>
  75   typename Container::const_iterator
  76   end(const Container& c) { return c.end(); }
  77
  78   template <typename Container>
  79   typename Container::size_type
  80   size(const Container& c) { return c.size(); }
  81 #else
  82   template <typename T>
  83   typename std::vector<T>::iterator
  84   begin(std::vector<T>& c) { return c.begin(); }
  85
  86   template <typename T>
  87   typename std::vector<T>::const_iterator
  88   begin(const std::vector<T>& c) { return c.begin(); }
  89
  90   template <typename T>
  91   typename std::vector<T>::iterator
  92   end(std::vector<T>& c) { return c.end(); }
  93
  94   template <typename T>
  95   typename std::vector<T>::const_iterator
  96   end(const std::vector<T>& c) { return c.end(); }
  97
  98   template <typename T>
  99   typename std::vector<T>::size_type
 100   size(const std::vector<T>& c) { return c.size(); }
 101 #endif
 102
 103   template <class ForwardIterator, class T>
 104   void iota(ForwardIterator first, ForwardIterator last, T value)
 105   {
 106     for (; first != last; ++first, ++value)
 107       *first = value;
 108   }
 109   template <typename Container, typename T>
 110   void iota(Container& c, const T& value)
 111   {
 112     iota(begin(c), end(c), value);
 113   }
 114
 115   // Also do version with 2nd container?
 116   template <typename Container, typename OutIter>
 117   OutIter copy(const Container& c, OutIter result) {
 118     return std::copy(begin(c), end(c), result);
 119   }
 120
 121   template <typename Container1, typename Container2>
 122   bool equal(const Container1& c1, const Container2& c2)
 123   {
 124     if (size(c1) != size(c2))
 125       return false;
 126     return std::equal(begin(c1), end(c1), begin(c2));
 127   }
 128
 129   template <typename Container>
 130   void sort(Container& c) { std::sort(begin(c), end(c)); }
 131
 132   template <typename Container, typename Predicate>
 133   void sort(Container& c, const Predicate& p) {
 134     std::sort(begin(c), end(c), p);
 135   }
 136
 137   template <typename Container>
 138   void stable_sort(Container& c) { std::stable_sort(begin(c), end(c)); }
 139
 140   template <typename Container, typename Predicate>
 141   void stable_sort(Container& c, const Predicate& p) {
 142     std::stable_sort(begin(c), end(c), p);
 143   }
 144
 145   template <typename InputIterator, typename Predicate>
 146   bool any_if(InputIterator first, InputIterator last, Predicate p)
 147   {
 148     return std::find_if(first, last, p) != last;
 149   }
 150   template <typename Container, typename Predicate>
 151   bool any_if(const Container& c, Predicate p)
 152   {
 153     return any_if(begin(c), end(c), p);
 154   }
 155
 156   template <typename InputIterator, typename T>
 157   bool contains(InputIterator first, InputIterator last, T value)
 158   {
 159     return std::find(first, last, value) != last;
 160   }
 161   template <typename Container, typename T>
 162   bool contains(const Container& c, const T& value)
 163   {
 164     return contains(begin(c), end(c), value);
 165   }
 166
 167   template <typename InputIterator, typename Predicate>
 168   bool all(InputIterator first, InputIterator last, Predicate p)
 169   {
 170     for (; first != last; ++first)
 171       if (!p(*first))
 172         return false;
 173     return true;
 174   }
 175   template <typename Container, typename Predicate>
 176   bool all(const Container& c, Predicate p)
 177   {
 178     return all(begin(c), end(c), p);
 179   }
 180
 181   template <typename InputIterator, typename Predicate>
 182   bool none(InputIterator first, InputIterator last, Predicate p)
 183   {
 184     return std::find_if(first, last, p) == last;
 185   }
 186   template <typename Container, typename Predicate>
 187   bool none(const Container& c, Predicate p)
 188   {
 189     return none(begin(c), end(c), p);
 190   }
 191
 192   template <typename Container, typename T>
 193   std::size_t count(const Container& c, const T& value)
 194   {
 195     return std::count(begin(c), end(c), value);
 196   }
 197
 198   template <typename Container, typename Predicate>
 199   std::size_t count_if(const Container& c, Predicate p)
 200   {
 201     return std::count_if(begin(c), end(c), p);
 202   }
 203
 204   template <typename ForwardIterator>
 205   bool is_sorted(ForwardIterator first, ForwardIterator last)
 206   {
 207     if (first == last)
 208       return true;
 209
 210     ForwardIterator next = first;
 211     for (++next; next != last; first = next, ++next) {
 212       if (*next < *first)
 213         return false;
 214     }
 215
 216     return true;
 217   }
 218
 219   template <typename ForwardIterator, typename StrictWeakOrdering>
 220   bool is_sorted(ForwardIterator first, ForwardIterator last,
 221                  StrictWeakOrdering comp)
 222   {
 223     if (first == last)
 224       return true;
 225
 226     ForwardIterator next = first;
 227     for (++next; next != last; first = next, ++next) {
 228       if (comp(*next, *first))
 229         return false;
 230     }
 231
 232     return true;
 233   }
 234
 235   template <typename Container>
 236   bool is_sorted(const Container& c)
 237   {
 238     return is_sorted(begin(c), end(c));
 239   }
 240
 241   template <typename Container, typename StrictWeakOrdering>
 242   bool is_sorted(const Container& c, StrictWeakOrdering comp)
 243   {
 244     return is_sorted(begin(c), end(c), comp);
 245   }
 246
 247 } // namespace boost
 248
 249 #endif // BOOST_ALGORITHM_HPP