// -- algorithm.hpp -- Boost Lambda Library ----------------------------------- // Copyright (C) 2002 Jaakko Jarvi (jaakko.jarvi@cs.utu.fi) // Copyright (C) 2002 Gary Powell (gwpowell@hotmail.com) // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // For more information, see http://www.boost.org #ifndef BOOST_LAMBDA_ALGORITHM_HPP #define BOOST_LAMBDA_ALGORITHM_HPP #include "boost/lambda/core.hpp" #include #include // for iterator_traits #include // for std::pair namespace boost { namespace lambda { namespace ll { // for_each --------------------------------- struct for_each { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::for_each(a, b, c); } }; // find --------------------------------- struct find { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, const C& c) const { return ::std::find(a, b, c); } }; // find_if --------------------------------- struct find_if { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c) const { return ::std::find_if(a, b, c); } }; // find_end --------------------------------- struct find_end { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c, C d) const { return ::std::find_end(a, b, c, d); } template A operator()(A a, A b, C c, C d, E e) const { return ::std::find_end(a, b, c, d, e); } }; // find_first_of --------------------------------- struct find_first_of { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c, C d) const { return ::std::find_first_of(a, b, c, d); } template A operator()(A a, A b, C c, C d, E e) const { return ::std::find_first_of(a, b, c, d, e); } }; // adjacent_find --------------------------------- struct adjacent_find { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b) const { return ::std::adjacent_find(a, b); } template A operator()(A a, A b, C c) const { return ::std::adjacent_find(a, b, c); } }; // count --------------------------------- struct count { template struct sig { typedef typename ::std::iterator_traits< typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type >::difference_type type; }; template typename ::std::iterator_traits::difference_type operator()(A a, A b, const C& c) const { return ::std::count(a, b, c); } }; // count_if --------------------------------- struct count_if { template struct sig { typedef typename ::std::iterator_traits< typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type >::difference_type type; }; template typename ::std::iterator_traits ::difference_type operator()(A a, A b, C c) const { return ::std::count_if(a, b, c); } }; // mismatch --------------------------------- struct mismatch { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type element1_type; typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type element2_type; typedef ::std::pair< element1_type, element2_type > type; }; template ::std::pair operator()(A a, A b, C c) const { return ::std::mismatch(a, b, c); } template ::std::pair operator()(A a, A b, C c, D d) const { return ::std::mismatch(a, b, c, d); } }; // equal --------------------------------- struct equal { template struct sig { typedef bool type; }; template bool operator()(A a, A b, C c) const { return ::std::equal(a, b, c); } template bool operator()(A a, A b, C c, D d) const { return ::std::equal(a, b, c, d); } }; // search -------------------------------- struct search { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c, C d) const { return std::search(a, b, c, d);} template A operator()(A a, A b, C c, C d, E e) const { return std::search(a, b, c, d, e);} }; // copy --------------------------------- struct copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::copy(a, b, c); } }; // copy_backward --------------------------------- struct copy_backward { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::copy_backward(a, b, c); } }; // swap --------------------------------- struct swap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::swap(a, b); } }; // swap_ranges --------------------------------- struct swap_ranges { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::swap_ranges(a, b, c); } }; // iter_swap --------------------------------- struct iter_swap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::iter_swap(a, b); } }; // transform -------------------------------- struct transform { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element< boost::tuples::length::value - 2, Args >::type >::type type; }; template C operator()(A a, A b, C c, D d) const { return std::transform(a, b, c, d);} template D operator()(A a, A b, C c, D d, E e) const { return std::transform(a, b, c, d, e);} }; // replace --------------------------------- struct replace { template struct sig { typedef void type; }; template void operator()(A a, A b, const C& c, const C& d) const { ::std::replace(a, b, c, d); } }; // replace_if --------------------------------- struct replace_if { template struct sig { typedef void type; }; template void operator()(A a, A b, C c, const D& d) const { ::std::replace_if(a, b, c, d); } }; // replace_copy --------------------------------- struct replace_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c, const D& d, const D& e) const { return ::std::replace_copy(a, b, c, d, e); } }; // replace_copy_if --------------------------------- struct replace_copy_if { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c, D d, const E& e) const { return ::std::replace_copy_if(a, b, c, d, e); } }; // fill --------------------------------- struct fill { template struct sig { typedef void type; }; template void operator()(A a, A b, const C& c) const { ::std::fill(a, b, c); } }; // fill_n --------------------------------- struct fill_n { template struct sig { typedef void type; }; template void operator()(A a, B b, const C& c) const { ::std::fill_n(a, b, c); } }; // generate --------------------------------- struct generate { template struct sig { typedef void type; }; template void operator()(A a, A b, C c) const { ::std::generate(a, b, c); } }; // generate_n --------------------------------- struct generate_n { template struct sig { typedef void type; }; template void operator()(A a, B b, C c) const { ::std::generate_n(a, b, c); } }; // remove --------------------------------- struct remove { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, const C& c) const { return ::std::remove(a, b, c); } }; // remove_if --------------------------------- struct remove_if { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c) const { return ::std::remove_if(a, b, c); } }; // remove_copy --------------------------------- struct remove_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c, const D& d) const { return ::std::remove_copy(a, b, c, d); } }; // remove_copy_if --------------------------------- struct remove_copy_if { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c, D d) const { return ::std::remove_copy_if(a, b, c, d); } }; // unique --------------------------------- struct unique { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b) const { return ::std::unique(a, b); } template A operator()(A a, A b, C c) const { return ::std::unique(a, b, c); } }; // unique_copy --------------------------------- struct unique_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::unique_copy(a, b, c); } template C operator()(A a, A b, C c, D d) const { return ::std::unique_copy(a, b, c, d); } }; // reverse --------------------------------- struct reverse { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::reverse(a, b); } }; // reverse_copy --------------------------------- struct reverse_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c) const { return ::std::reverse_copy(a, b, c); } }; // rotate --------------------------------- struct rotate { template struct sig { typedef void type; }; template void operator()(A a, A b, A c) const { ::std::rotate(a, b, c); } }; // rotate_copy --------------------------------- struct rotate_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template D operator()(A a, A b, A c, D d) const { return ::std::rotate_copy(a, b, c, d); } }; // random_shuffle --------------------------------- #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE struct random_shuffle { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::random_shuffle(a, b); } template void operator()(A a, A b, const C& c) const { ::std::random_shuffle(a, b, c); } }; #endif // partition --------------------------------- struct partition { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c) const { return ::std::partition(a, b, c); } }; // stable_partition --------------------------------- struct stable_partition { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, C c) const { return ::std::stable_partition(a, b, c); } }; // sort --------------------------------- struct sort { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::sort(a, b); } template void operator()(A a, A b, C c) const { ::std::sort(a, b, c); } }; // stable_sort --------------------------------- struct stable_sort { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::stable_sort(a, b); } template void operator()(A a, A b, C c) const { ::std::stable_sort(a, b, c); } }; // partial_sort --------------------------------- struct partial_sort { template struct sig { typedef void type; }; template void operator()(A a, A b, A c) const { ::std::partial_sort(a, b, c); } template void operator()(A a, A b, A c, D d) const { ::std::partial_sort(a, b, c, d); } }; // partial_sort_copy --------------------------------- struct partial_sort_copy { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<3, Args>::type >::type type; }; template C operator()(A a, A b, C c, C d) const { return ::std::partial_sort_copy(a, b, c, d); } template C operator()(A a, A b, C c, C d, E e) const { return ::std::partial_sort_copy(a, b, c, d, e); } }; // nth_element --------------------------------- struct nth_element { template struct sig { typedef void type; }; template void operator()(A a, A b, A c) const { ::std::nth_element(a, b, c); } template void operator()(A a, A b, A c, D d) const { ::std::nth_element(a, b, c, d); } }; // lower_bound --------------------------------- struct lower_bound { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, const C& c) const { return ::std::lower_bound(a, b, c); } template A operator()(A a, A b, const C& c, D d) const { return ::std::lower_bound(a, b, c, d); } }; // upper_bound --------------------------------- struct upper_bound { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b, const C& c) const { return ::std::upper_bound(a, b, c); } template A operator()(A a, A b, const C& c, D d) const { return ::std::upper_bound(a, b, c, d); } }; // equal_range --------------------------------- struct equal_range { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type element_type; typedef ::std::pair< element_type, element_type > type; }; template ::std::pair operator()(A a, A b, const C& c) const { return ::std::equal_range(a, b, c); } template ::std::pair operator()(A a, A b, const C& c, D d) const { return ::std::equal_range(a, b, c, d); } }; // binary_search --------------------------------- struct binary_search { template struct sig { typedef bool type; }; template bool operator()(A a, A b, const C& c) const { return ::std::binary_search(a, b, c); } template bool operator()(A a, A b, const C& c, D d) const { return ::std::binary_search(a, b, c, d); } }; // merge -------------------------------- struct merge { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<5, Args>::type >::type type; }; template E operator()(A a, A b, C c, C d, E e) const { return std::merge(a, b, c, d, e);} template E operator()(A a, A b, C c, C d, E e, F f) const { return std::merge(a, b, c, d, e, f);} }; // inplace_merge --------------------------------- struct inplace_merge { template struct sig { typedef void type; }; template void operator()(A a, A b, A c) const { ::std::inplace_merge(a, b, c); } template void operator()(A a, A b, A c, D d) const { ::std::inplace_merge(a, b, c, d); } }; // includes --------------------------------- struct includes { template struct sig { typedef bool type; }; template bool operator()(A a, A b, C c, C d) const { return ::std::includes(a, b, c, d); } template bool operator()(A a, A b, C c, C d, E e) const { return ::std::includes(a, b, c, d, e); } }; // set_union -------------------------------- struct set_union { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<5, Args>::type >::type type; }; template E operator()(A a, A b, C c, C d, E e) const { return std::set_union(a, b, c, d, e);} template E operator()(A a, A b, C c, C d, E e, F f) const { return std::set_union(a, b, c, d, e, f);} }; // set_intersection -------------------------------- struct set_intersection { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<5, Args>::type >::type type; }; template E operator()(A a, A b, C c, C d, E e) const { return std::set_intersection(a, b, c, d, e);} template E operator()(A a, A b, C c, C d, E e, F f) const { return std::set_intersection(a, b, c, d, e, f);} }; // set_difference -------------------------------- struct set_difference { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<5, Args>::type >::type type; }; template E operator()(A a, A b, C c, C d, E e) const { return std::set_difference(a, b, c, d, e);} template E operator()(A a, A b, C c, C d, E e, F f) const { return std::set_difference(a, b, c, d, e, f);} }; // set_symmetric_difference -------------------------------- struct set_symmetric_difference { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<5, Args>::type >::type type; }; template E operator()(A a, A b, C c, C d, E e) const { return std::set_symmetric_difference(a, b, c, d, e);} template E operator()(A a, A b, C c, C d, E e, F f) const { return std::set_symmetric_difference(a, b, c, d, e, f);} }; // push_heap --------------------------------- struct push_heap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::push_heap(a, b); } template void operator()(A a, A b, C c) const { ::std::push_heap(a, b, c); } }; // pop_heap --------------------------------- struct pop_heap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::pop_heap(a, b); } template void operator()(A a, A b, C c) const { ::std::pop_heap(a, b, c); } }; // make_heap --------------------------------- struct make_heap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::make_heap(a, b); } template void operator()(A a, A b, C c) const { ::std::make_heap(a, b, c); } }; // sort_heap --------------------------------- struct sort_heap { template struct sig { typedef void type; }; template void operator()(A a, A b) const { ::std::sort_heap(a, b); } template void operator()(A a, A b, C c) const { ::std::sort_heap(a, b, c); } }; // min --------------------------------- struct min { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(const A& a, const A& b) const { return (::std::min)(a, b); } template A operator()(const A& a, const A& b, C c) const { return (::std::min)(a, b, c); } }; // max --------------------------------- struct max { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(const A& a, const A& b) const { return (::std::max)(a, b); } template A operator()(const A& a, const A& b, C c) const { return (::std::max)(a, b, c); } }; struct min_element { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b) const { return ::std::min_element(a, b); } template A operator()(A a, A b, C c) const { return ::std::min_element(a, b, c); } }; // max_element --------------------------------- struct max_element { template struct sig { typedef typename boost::remove_const< typename boost::tuples::element<1, Args>::type >::type type; }; template A operator()(A a, A b) const { return ::std::max_element(a, b); } template A operator()(A a, A b, C c) const { return ::std::max_element(a, b, c); } }; // lexicographical_compare --------------------------------- struct lexicographical_compare { template struct sig { typedef bool type; }; template bool operator()(A a, A b, C c, C d) const { return ::std::lexicographical_compare(a, b, c, d); } template bool operator()(A a, A b, C c, C d, E e) const { return ::std::lexicographical_compare(a, b, c, d, e); } }; // next_permutation --------------------------------- struct next_permutation { template struct sig { typedef bool type; }; template bool operator()(A a, A b) const { return ::std::next_permutation(a, b); } template bool operator()(A a, A b, C c) const { return ::std::next_permutation(a, b, c); } }; // prev_permutation --------------------------------- struct prev_permutation { template struct sig { typedef bool type; }; template bool operator()(A a, A b) const { return ::std::prev_permutation(a, b); } template bool operator()(A a, A b, C c) const { return ::std::prev_permutation(a, b, c); } }; } // end of ll namespace // There is no good way to call an overloaded member function in a // lambda expression. // The macro below defines a function object class for calling a // const_iterator returning member function of a container. #define CALL_MEMBER(X) \ struct call_##X { \ template \ struct sig { \ typedef typename boost::remove_const< \ typename boost::tuples::element<1, Args>::type \ >::type::const_iterator type; \ }; \ \ template \ typename T::const_iterator \ operator()(const T& t) const \ { \ return t.X(); \ } \ }; // create call_begin and call_end classes CALL_MEMBER(begin) CALL_MEMBER(end) #undef CALL_MEMBER } // end of lambda namespace } // end of boost namespace #endif