Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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