sorting_algo.h

mptl和omptl一样

// Copyright (C) 2006 Didier Baertschiger
// e-mail contact: [e-mail]

// The MPTL library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.

// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

/// \file   sorting_algo.h
/// \brief  Impl閙entation multithread des algorithmes standard de la STL.
/// \author Didier Baertschiger
/// \date   07-11-2005
///
/// 

#ifndef _SORTING_ALGO
#define _SORTING_ALGO 1

#include <algorithm>
#include <iterator>
#include <utility>

namespace mptl
{
    template <typename Iterator, typename LessThanComparable>
    class MPTLLowerBound
    {
    private:
        Iterator first1, last1;
        const LessThanComparable& value;
    
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef FindPolicy reduction;
        typedef TwoIterators nIterators;
    
        MPTLLowerBound(Iterator first1_, Iterator last1_,
                       const LessThanComparable& value_)
            : first1(first1_), last1(last1_), value(value_) { }
    
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
    
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            if (last != last1) ++last;
            Iterator it = std::lower_bound(first, last, value);
            if (it == last) return last1;
            return it;
        }
    };

    template <typename Iterator, typename LessThanComparable>
    MPTLLowerBound<Iterator, LessThanComparable> lower_bound(Iterator first,
                                                             Iterator last,
                                                             const LessThanComparable& value)
    {
        return MPTLLowerBound<Iterator, LessThanComparable>(first, last, value);
    }


    template <typename Iterator, typename T, typename StrictWeakOrdering>
    class MPTLLowerBoundComp
    {
    private:
        Iterator first1, last1;
        const T& value;
        StrictWeakOrdering comp;
    
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef FindPolicy reduction;
        typedef TwoIterators nIterators;
        
        MPTLLowerBoundComp(Iterator first1_, Iterator last1_, const T& value_,
                           StrictWeakOrdering comp_)
            : first1(first1_), last1(last1_), value(value_), comp(comp_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            if (last != last1) ++last;
            Iterator it = std::lower_bound(first, last, value, comp);
            if (it == last) return last1;
            return it;
        }
    };
    
    template <typename Iterator, typename T, typename StrictWeakOrdering>
    MPTLLowerBoundComp<Iterator, T, StrictWeakOrdering> lower_bound(Iterator first,
                                                                    Iterator last,
                                                                    const T& value,
                                                                    StrictWeakOrdering comp)
    {
        return MPTLLowerBoundComp<Iterator, T, StrictWeakOrdering>(first, last,
                                                                   value, comp);
    }
    
    
    template <typename Iterator, typename LessThanComparable>
    class MPTLUpperBound
    {
    private:
        Iterator first1, last1;
        const LessThanComparable& value;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef FindPolicy reduction;
        typedef TwoIterators nIterators;
        
        MPTLUpperBound(Iterator first1_, Iterator last1_,
                       const LessThanComparable& value_)
            : first1(first1_), last1(last1_), value(value_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            if (last != last1) ++last;
            Iterator it = std::upper_bound(first, last, value);
            if (it == last) return last1;
            return it;
        }
    };
    
    template <typename Iterator, typename LessThanComparable>
    MPTLUpperBound<Iterator, LessThanComparable> upper_bound(Iterator first,
                                                             Iterator last,
                                                             const LessThanComparable& value)
    {
        return MPTLUpperBound<Iterator, LessThanComparable>(first, last, value);
    }
    
    
    template <typename Iterator, typename T, typename StrictWeakOrdering>
    class MPTLUpperBoundComp
    {
    private:
        Iterator first1, last1;
        const T& value;
        StrictWeakOrdering comp;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef FindPolicy reduction;
        typedef TwoIterators nIterators;
        
        MPTLUpperBoundComp(Iterator first1_, Iterator last1_, const T& value_,
                           StrictWeakOrdering comp_)
            : first1(first1_), last1(last1_), value(value_), comp(comp_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            if (last != last1) ++last;
            Iterator it = std::upper_bound(first, last, value, comp);
            if (it == last) return last1;
            return it;
        }
    };
    
    template <typename Iterator, typename T, typename StrictWeakOrdering>
    MPTLUpperBoundComp<Iterator, T, StrictWeakOrdering> upper_bound(Iterator first,
                                                                    Iterator last,
                                                                    const T& value,
                                                                    StrictWeakOrdering comp)
    {
        return MPTLUpperBoundComp<Iterator, T, StrictWeakOrdering>(first, last,
                                                                   value, comp);
    }
    
    
    template <typename Iterator, typename LessThanComparable>
    class MPTLBinarySearch
    {
    private:
        Iterator first1, last1;
        const LessThanComparable& value;
        
    public:
        typedef Iterator iterator1;
        typedef bool resultType;
        typedef OneTruePolicy reduction;
        typedef TwoIterators nIterators;
        
        MPTLBinarySearch(Iterator first1_, Iterator last1_,
                         const LessThanComparable& value_) 
            : first1(first1_), last1(last1_), value(value_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::binary_search(first, last, value);
        }
    };
    
    template <typename Iterator, typename LessThanComparable>
    MPTLBinarySearch<Iterator, LessThanComparable> binary_search(Iterator first,
                                                                 Iterator last,
                                                                 const LessThanComparable& value)
    {
        return MPTLBinarySearch<Iterator, LessThanComparable>(first, last,
                                                              value);
    }
    
    
    template <typename Iterator, typename T, typename StrictWeakOrdering>
    class MPTLBinarySearchComp
    {
    private:
        Iterator first1, last1;
        const T& value;
        StrictWeakOrdering comp;
        
    public:
        typedef Iterator iterator1;
        typedef bool resultType;
        typedef OneTruePolicy reduction;
        typedef TwoIterators nIterators;
        
        MPTLBinarySearchComp(Iterator first1_, Iterator last1_,
                             const T& value_, StrictWeakOrdering comp_) 
            : first1(first1_), last1(last1_), value(value_), comp(comp_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::binary_search(first, last, value, comp);
        }
    };
    
    template <typename Iterator, typename T, typename StrictWeakOrdering>
    MPTLBinarySearchComp<Iterator, T, 
                         StrictWeakOrdering> binary_search(Iterator first,
                                                           Iterator last,
                                                           const T& value,
                                                           StrictWeakOrdering comp)
    {
        return MPTLBinarySearchComp<Iterator, T, StrictWeakOrdering>(first,
                                                                     last,
                                                                     value,
                                                                     comp);
    }
    
    
    template <typename Iterator>
    class MPTLMinElement
    {
    private:
        Iterator first1, last1;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef ComparisonPolicy<std::less<typename std::iterator_traits<Iterator>::value_type> > reduction;
        typedef TwoIterators nIterators;
        
        MPTLMinElement(Iterator first1_, Iterator last1_) 
            : first1(first1_), last1(last1_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::min_element(first, last);
        }
    };
    
    template <typename Iterator>
    MPTLMinElement<Iterator> min_element(Iterator first, Iterator last)
    {
        return MPTLMinElement<Iterator>(first, last);
    }
    
    
    template <typename Iterator, typename BinaryPredicate>
    class MPTLMinElementComp
    {
    private:
        Iterator first1, last1;
        BinaryPredicate comp;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef ComparisonPolicy<BinaryPredicate> reduction;
        typedef TwoIterators nIterators;
        
        MPTLMinElementComp(Iterator first1_, Iterator last1_, 
                           BinaryPredicate comp_)
            : first1(first1_), last1(last1_), comp(comp_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::min_element(first, last, comp);
        }
    };
    
    template <typename Iterator, typename BinaryPredicate>
    MPTLMinElementComp<Iterator, BinaryPredicate> min_element(Iterator first,
                                                              Iterator last,
                                                              BinaryPredicate comp)
    {
        return MPTLMinElementComp<Iterator, BinaryPredicate>(first, last, comp);
    }
    
    
    template <typename Iterator>
    class MPTLMaxElement
    {
    private:
        Iterator first1, last1;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef ComparisonPolicy<std::greater<typename std::iterator_traits<Iterator>::value_type> > reduction;
        typedef TwoIterators nIterators;
        
        MPTLMaxElement(Iterator first1_, Iterator last1_) 
            : first1(first1_), last1(last1_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::max_element(first, last);
        }
    };
    
    template <typename Iterator>
    MPTLMaxElement<Iterator> max_element(Iterator first, Iterator last)
    {
        return MPTLMaxElement<Iterator>(first, last);
    }
    
    
    template <typename Iterator, typename BinaryPredicate>
    class MPTLMaxElementComp
    {
    private:
        Iterator first1, last1;
        BinaryPredicate comp;
        
    public:
        typedef Iterator iterator1;
        typedef Iterator resultType;
        typedef ComparisonPolicy<BinaryPredicate> reduction;
        typedef TwoIterators nIterators;
        
        MPTLMaxElementComp(Iterator first1_, Iterator last1_, 
                           BinaryPredicate comp_)
            : first1(first1_), last1(last1_), comp(comp_) { }
        
        Iterator getFirst1() { return first1; }
        Iterator getLast1() { return last1; }
        
        resultType applyAlgorithm(Iterator first, Iterator last)
        {
            return std::max_element(first, last, comp);
        }
    };
    
    template <typename Iterator, typename BinaryPredicate>
    MPTLMaxElementComp<Iterator, BinaryPredicate> max_element(Iterator first,
                                                              Iterator last,
                                                              BinaryPredicate comp)
    {
        return MPTLMaxElementComp<Iterator, BinaryPredicate>(first, last, comp);
    }
    
} // namespace mptl

#endif /* _SORTING_ALGO */