container/detail/algorithm.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2014-2014.
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 // (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/container for documentation.
0010 //
0011 //////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_CONTAINER_DETAIL_ALGORITHM_HPP
0014 #define BOOST_CONTAINER_DETAIL_ALGORITHM_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <boost/intrusive/detail/algorithm.hpp>
0025
0026 namespace boost {
0027 namespace container {
0028
0029 using boost::intrusive::algo_equal;
0030 using boost::intrusive::algo_lexicographical_compare;
0031
0032 template<class Func>
0033 class binder1st
0034 {
0035    public:
0036     typedef typename Func::second_argument_type  argument_type;
0037     typedef typename Func::result_type           result_type;
0038
0039     binder1st(const Func& func, const typename Func::first_argument_type& arg)
0040     : op(func), value(arg)
0041     {}
0042
0043     result_type operator()(const argument_type& arg) const
0044    {    return op(value, arg);  }
0045
0046     result_type operator()(argument_type& arg) const
0047    {  return op(value, arg);   }
0048
0049    private:
0050     Func op;
0051     typename Func::first_argument_type value;
0052 };
0053
0054 template<class Func, class T>
0055 inline binder1st<Func> bind1st(const Func& func, const T& arg)
0056 {   return boost::container::binder1st<Func>(func, arg);  }
0057
0058 template<class Func>
0059 class binder2nd
0060 {
0061    public:
0062     typedef typename Func::first_argument_type   argument_type;
0063     typedef typename Func::result_type           result_type;
0064
0065     binder2nd(const Func& func, const typename Func::second_argument_type& arg)
0066        : op(func), value(arg)
0067    {}
0068
0069     result_type operator()(const argument_type& arg) const
0070    {  return op(arg, value);  }
0071
0072     result_type operator()(argument_type& arg) const
0073     {  return op(arg, value);  }
0074
0075    private:
0076     Func op;
0077     typename Func::second_argument_type value;
0078 };
0079
0080 template<class Func, class T>
0081 inline binder2nd<Func> bind2nd(const Func& func, const T& arg)
0082 {
0083    return (boost::container::binder2nd<Func>(func, arg));
0084 }
0085
0086 template<class Func>
0087 class unary_negate
0088 {
0089    public:
0090    typedef typename Func::argument_type   argument_type;
0091    typedef typename Func::result_type     result_type;
0092
0093     explicit unary_negate(const Func& func)
0094         : m_func(func)
0095    {}
0096
0097     bool operator()(const typename Func::argument_type& arg) const
0098     {  return !m_func(arg);  }
0099
0100    private:
0101     Func m_func;
0102 };
0103
0104 template<class Func> inline
0105 unary_negate<Func> not1(const Func& func)
0106 {
0107    return boost::container::unary_negate<Func>(func);
0108 }
0109
0110 template<class InputIt, class UnaryPredicate>
0111 InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
0112 {
0113    for (; first != last; ++first) {
0114       if (p(*first)) {
0115          return first;
0116       }
0117    }
0118    return last;
0119 }
0120
0121 template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
0122   ForwardIt1 find_end (ForwardIt1 first1, ForwardIt1 last1
0123                       ,ForwardIt2 first2, ForwardIt2 last2
0124                       ,BinaryPredicate p)
0125 {
0126    if (first2==last2)
0127       return last1;  // specified in C++11
0128
0129    ForwardIt1 ret = last1;
0130
0131    while (first1!=last1)
0132    {
0133       ForwardIt1 it1 = first1;
0134       ForwardIt2 it2 = first2;
0135       while ( p(*it1, *it2) ) {
0136          ++it1; ++it2;
0137          if (it2==last2) {
0138             ret=first1;
0139             break;
0140          }
0141          if (it1==last1)
0142          return ret;
0143       }
0144       ++first1;
0145    }
0146    return ret;
0147 }
0148
0149 template<class InputIt, class ForwardIt, class BinaryPredicate>
0150 InputIt find_first_of(InputIt first1, InputIt last1, ForwardIt first2, ForwardIt last2, BinaryPredicate p)
0151 {
0152    for (; first1 != last1; ++first1) {
0153       for (ForwardIt it = first2; it != last2; ++it) {
0154          if (p(*first1, *it)) {
0155             return first1;
0156          }
0157       }
0158    }
0159    return last1;
0160 }
0161
0162 template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
0163 ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1,
0164                         ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p)
0165 {
0166    for (; ; ++first1) {
0167       ForwardIt1 it = first1;
0168       for (ForwardIt2 it2 = first2; ; ++it, ++it2) {
0169          if (it2 == last2) {
0170             return first1;
0171          }
0172          if (it == last1) {
0173             return last1;
0174          }
0175          if (!p(*it, *it2)) {
0176             break;
0177          }
0178       }
0179    }
0180 }
0181
0182 }  //namespace container {
0183 }  //namespace boost {
0184
0185 #endif   //#ifndef BOOST_CONTAINER_DETAIL_ALGORITHM_HPP