Saf/Algo/Sort/SortInternal.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

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

    Saf 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_ALGO_SORT_SORTINTERNAL_H
#define SAF_ALGO_SORT_SORTINTERNAL_H

#include "../../Type.h"
#include "../Swap.h"
#include "../Predicate.h"
#include "../Selection/Median.h"
#include "../../Collection/Pair.h"

namespace Saf
{
    namespace Internal
    {
        namespace AlgoSort
        {
            template <class Iter, class Pred>
            class PredicateOverIterators
            {
            private:
                Pred m_pred;

            public:
                PredicateOverIterators(const Pred &p)
                    : m_pred(p)
                {}

                bool operator()(const Iter& x, const Iter& y) const
                {
                    return m_pred(*x, *y);
                }
            };

            template <class RanIter, class Pred>
            inline RanIter ChoosePivot(RanIter first, RanIter last, Pred pred)
            {
                // Modified predicate that works on iterators
                PredicateOverIterators<RanIter,Pred> pa(pred);
        
                // Median-of-3
                RanIter mid = first + (last - first) / 2;
                return Saf::Algo::Selection::Median(first, mid, last, pa);
            }

            template <class RanIter, class Pred>
            Saf::Collection::Pair<RanIter,RanIter> PartitionGeneric(RanIter begin, RanIter end, Pred pred)
            {
                --end;
                RanIter pivot = ChoosePivot(begin, end, pred);

                // Store pivot at the end of the sequence
                if (pivot != end)
                {
                    Saf::Algo::Swap(*pivot, *end);
                    pivot = end;
                }            

                // Reorder the rest of the sequence
                while (begin != end)
                {
                    if (pred(*begin, *pivot))
                    {
                        ++begin;
                    }
                    else
                    {
                        --end;
                        Saf::Algo::Swap(*begin, *end);
                    }
                }

                // Put pivot between the two partitions and return ranges
                if (begin == pivot)
                {
                    return Saf::Collection::Pair<RanIter,RanIter>(begin, begin);
                }

                Saf::Algo::Swap(*begin, *pivot);
                return Saf::Collection::Pair<RanIter,RanIter>(begin, begin + 1);
            }

            template <class RanIter, class Pred>
            Saf::Collection::Pair<RanIter,RanIter> PartitionSmart(RanIter begin, RanIter end, Pred pred)
            {        
                // Choose pivot and put it to the middle
                RanIter pivot = ChoosePivot(begin, end - 1, pred);            
                RanIter mid = begin + (end - begin) / 2;
                Saf::Algo::Swap(*mid, *pivot);

                // Partitioning
                RanIter mFirst, mLast;
            
                for (mFirst = mid; mFirst != begin; --mFirst)
                {
                    if (pred(*(mFirst - 1), *mid) || pred(*mid, *(mFirst - 1)))
                    {
                        break;
                    }
                }

                for (mLast = mid + 1; mLast != end; ++mLast)
                {
                    if (pred(*mLast, *mid) || pred(*mid, *mLast))
                    {
                        break;
                    }
                }

                RanIter cLeft = mFirst;
                RanIter cRight = mLast;

                while (true)
                {
                    while (cRight != end && !pred(*cRight, *mFirst))
                    {
                        if (!pred(*mFirst, *cRight))
                        {
                            Saf::Algo::Swap(*mLast, *cRight);
                            ++mLast;
                        } 
                    
                        ++cRight;
                    }

                    while (cLeft != begin && !pred(*mFirst, *(cLeft - 1)))
                    {
                        --cLeft;

                        if (!pred(*cLeft, *mFirst))
                        {
                            --mFirst;
                            Saf::Algo::Swap(*mFirst, *cLeft);
                        }                     
                    }

                    if (cLeft == begin && cRight == end)
                    {
                        return Saf::Collection::Pair<RanIter,RanIter>(mFirst, mLast);
                    }

                    if (cLeft == begin)
                    {
                        if (mLast != cRight)
                        {
                            Saf::Algo::Swap(*mFirst, *mLast);
                        }                    
                        Saf::Algo::Swap(*mFirst, *cRight);

                        ++mFirst;
                        ++mLast;
                        ++cRight;
                    }
                    else if (cRight == end)
                    {
                        --cLeft;
                        --mFirst;
                        --mLast;

                        if (cLeft != mFirst)
                        {
                            Saf::Algo::Swap(*cLeft, *mFirst);
                        }
                        Saf::Algo::Swap(*mFirst, *mLast);
                    }
                    else
                    {
                        --cLeft;
                        Saf::Algo::Swap(*cLeft, *cRight);
                        ++cRight;
                    }
                }
            }
        }
    }
}

#endif