Adding shared_ptr header files back in.
[dyninst.git] / external / 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 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 contains(const Container& c, const T& value)
161   {
162     return contains(begin(c), end(c), value);
163   }
164
165   template <typename InputIterator, typename Predicate>
166   bool all(InputIterator first, InputIterator last, Predicate p)
167   {
168     for (; first != last; ++first)
169       if (!p(*first))
170         return false;
171     return true;
172   }
173   template <typename Container, typename Predicate>
174   bool all(const Container& c, Predicate p)
175   {
176     return all(begin(c), end(c), p);
177   }
178
179   template <typename Container, typename T>
180   std::size_t count(const Container& c, const T& value)
181   {
182     return std::count(begin(c), end(c), value);
183   }
184
185   template <typename Container, typename Predicate>
186   std::size_t count_if(const Container& c, Predicate p)
187   {
188     return std::count_if(begin(c), end(c), p);
189   }
190
191   template <typename ForwardIterator>
192   bool is_sorted(ForwardIterator first, ForwardIterator last)
193   {
194     if (first == last)
195       return true;
196
197     ForwardIterator next = first;
198     for (++next; next != last; first = next, ++next) {
199       if (*next < *first)
200         return false;
201     }
202
203     return true;
204   }
205
206   template <typename ForwardIterator, typename StrictWeakOrdering>
207   bool is_sorted(ForwardIterator first, ForwardIterator last,
208                  StrictWeakOrdering comp)
209   {
210     if (first == last)
211       return true;
212
213     ForwardIterator next = first;
214     for (++next; next != last; first = next, ++next) {
215       if (comp(*next, *first))
216         return false;
217     }
218
219     return true;
220   }
221
222   template <typename Container>
223   bool is_sorted(const Container& c)
224   {
225     return is_sorted(begin(c), end(c));
226   }
227
228   template <typename Container, typename StrictWeakOrdering>
229   bool is_sorted(const Container& c, StrictWeakOrdering comp)
230   {
231     return is_sorted(begin(c), end(c), comp);
232   }
233
234 } // namespace boost
235
236 #endif // BOOST_ALGORITHM_HPP