source: NonGTP/Boost/boost/detail/algorithm.hpp @ 857

Revision 857, 7.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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
46namespace 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
Note: See TracBrowser for help on using the repository browser.