Saf/Algo/Sort/InsertionSort.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_INSERTIONSORT_H
#define SAF_ALGO_SORT_INSERTIONSORT_H

#include "../../Type.h"
#include "../../Type/IteratorTraits.h"
#include "../Swap.h"
#include "../Predicate.h"

namespace Saf
{
    namespace Internal
    {
        namespace AlgoSort
        {
            template <class FwdIter, class Pred>
            void InsertionSort(FwdIter begin, FwdIter end, Pred pred, 
                Saf::Type::IteratorCategory::ForwardCategory)
            {
                if (begin != end)
                {
                    FwdIter next = begin;

                    while (++next != end)
                    {
                        // Find new position for the next element
                        FwdIter newPos = begin;

                        while (newPos != next && !pred(*next, *newPos))
                        {
                            ++newPos;
                        }

                        // Put the next element into its place and shift the rest
                        while (newPos != next)
                        {
                            Saf::Algo::Swap(*newPos, *next);
                            ++newPos;
                        }
                    }
                }
            }

            template <class BidIter, class Pred>
            void InsertionSort(BidIter begin, BidIter end, Pred pred, 
                Saf::Type::IteratorCategory::BidirectionalCategory)
            {
                if (begin != end)
                {
                    BidIter next = begin;

                    while (++next != end)
                    {
                        // Shift the current element back to its position
                        BidIter cur = next, prev = next;

                        while (cur != begin)
                        {
                            --prev;

                            if (!pred(*cur, *prev))
                            {
                                break;
                            }

                            Saf::Algo::Swap(*cur, *prev);
                            --cur;
                        }
                    }
                }
            }
        }
    }
    namespace Algo
    {        
        namespace Sort
        {
            template <class Iter, class Pred>
            void InsertionSort(Iter begin, Iter end, Pred pred)
            {
                Internal::AlgoSort::InsertionSort(begin, end, pred, Type::IteratorTraits<Iter>::Category());
            }

            template <class Iter>
            void InsertionSort(Iter begin, Iter end)
            {
                Predicate::Less<typename Type::IteratorTraits<Iter>::ValType> pred;
                InsertionSort(begin, end, pred);
            }
        }
    }
}

#endif