Merge c:/dyninst/pc_bluegene/dyninst into dyn_pc_integration
[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 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