1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2014-2014.
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/container for documentation.
10 //
11 //////////////////////////////////////////////////////////////////////////////
12
13 #ifndef BOOST_CONTAINER_DETAIL_ALGORITHM_HPP
14 #define BOOST_CONTAINER_DETAIL_ALGORITHM_HPP
15
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
18 #endif
19
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 # pragma once
22 #endif
23
24 #include <boost/intrusive/detail/algorithm.hpp>
25
26 namespace boost {
27 namespace container {
28
29 using boost::intrusive::algo_equal;
30 using boost::intrusive::algo_lexicographical_compare;
31
32 template<class Func>
33 class binder1st
34 {
35 public:
36 typedef typename Func::second_argument_type argument_type;
37 typedef typename Func::result_type result_type;
38
binder1st(const Func & func,const typename Func::first_argument_type & arg)39 binder1st(const Func& func, const typename Func::first_argument_type& arg)
40 : op(func), value(arg)
41 {}
42
operator ()(const argument_type & arg) const43 result_type operator()(const argument_type& arg) const
44 { return op(value, arg); }
45
operator ()(argument_type & arg) const46 result_type operator()(argument_type& arg) const
47 { return op(value, arg); }
48
49 private:
50 Func op;
51 typename Func::first_argument_type value;
52 };
53
54 template<class Func, class T>
bind1st(const Func & func,const T & arg)55 inline binder1st<Func> bind1st(const Func& func, const T& arg)
56 { return boost::container::binder1st<Func>(func, arg); }
57
58 template<class Func>
59 class binder2nd
60 {
61 public:
62 typedef typename Func::first_argument_type argument_type;
63 typedef typename Func::result_type result_type;
64
binder2nd(const Func & func,const typename Func::second_argument_type & arg)65 binder2nd(const Func& func, const typename Func::second_argument_type& arg)
66 : op(func), value(arg)
67 {}
68
operator ()(const argument_type & arg) const69 result_type operator()(const argument_type& arg) const
70 { return op(arg, value); }
71
operator ()(argument_type & arg) const72 result_type operator()(argument_type& arg) const
73 { return op(arg, value); }
74
75 private:
76 Func op;
77 typename Func::second_argument_type value;
78 };
79
80 template<class Func, class T>
bind2nd(const Func & func,const T & arg)81 inline binder2nd<Func> bind2nd(const Func& func, const T& arg)
82 {
83 return (boost::container::binder2nd<Func>(func, arg));
84 }
85
86 template<class Func>
87 class unary_negate
88 {
89 public:
90 typedef typename Func::argument_type argument_type;
91 typedef typename Func::result_type result_type;
92
unary_negate(const Func & func)93 explicit unary_negate(const Func& func)
94 : m_func(func)
95 {}
96
operator ()(const typename Func::argument_type & arg) const97 bool operator()(const typename Func::argument_type& arg) const
98 { return !m_func(arg); }
99
100 private:
101 Func m_func;
102 };
103
104 template<class Func> inline
not1(const Func & func)105 unary_negate<Func> not1(const Func& func)
106 {
107 return boost::container::unary_negate<Func>(func);
108 }
109
110 template<class InputIt, class UnaryPredicate>
find_if(InputIt first,InputIt last,UnaryPredicate p)111 InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
112 {
113 for (; first != last; ++first) {
114 if (p(*first)) {
115 return first;
116 }
117 }
118 return last;
119 }
120
121 template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
find_end(ForwardIt1 first1,ForwardIt1 last1,ForwardIt2 first2,ForwardIt2 last2,BinaryPredicate p)122 ForwardIt1 find_end (ForwardIt1 first1, ForwardIt1 last1
123 ,ForwardIt2 first2, ForwardIt2 last2
124 ,BinaryPredicate p)
125 {
126 if (first2==last2)
127 return last1; // specified in C++11
128
129 ForwardIt1 ret = last1;
130
131 while (first1!=last1)
132 {
133 ForwardIt1 it1 = first1;
134 ForwardIt2 it2 = first2;
135 while ( p(*it1, *it2) ) {
136 ++it1; ++it2;
137 if (it2==last2) {
138 ret=first1;
139 break;
140 }
141 if (it1==last1)
142 return ret;
143 }
144 ++first1;
145 }
146 return ret;
147 }
148
149 template<class InputIt, class ForwardIt, class BinaryPredicate>
find_first_of(InputIt first1,InputIt last1,ForwardIt first2,ForwardIt last2,BinaryPredicate p)150 InputIt find_first_of(InputIt first1, InputIt last1, ForwardIt first2, ForwardIt last2, BinaryPredicate p)
151 {
152 for (; first1 != last1; ++first1) {
153 for (ForwardIt it = first2; it != last2; ++it) {
154 if (p(*first1, *it)) {
155 return first1;
156 }
157 }
158 }
159 return last1;
160 }
161
162 template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
search(ForwardIt1 first1,ForwardIt1 last1,ForwardIt2 first2,ForwardIt2 last2,BinaryPredicate p)163 ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1,
164 ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p)
165 {
166 for (; ; ++first1) {
167 ForwardIt1 it = first1;
168 for (ForwardIt2 it2 = first2; ; ++it, ++it2) {
169 if (it2 == last2) {
170 return first1;
171 }
172 if (it == last1) {
173 return last1;
174 }
175 if (!p(*it, *it2)) {
176 break;
177 }
178 }
179 }
180 }
181
182 } //namespace container {
183 } //namespace boost {
184
185 #endif //#ifndef BOOST_CONTAINER_DETAIL_ALGORITHM_HPP
186