Saf/Algo/Range.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_RANGE_H
#define SAF_ALGO_RANGE_H

#include "../Type.h"
#include "../Type/IteratorTraits.h"
#include "../IndexOutOfRangeException.h"

namespace Saf
{
    namespace Internal
    {
        namespace AlgoRange
        {
            template <class RanIter>
            inline Saf::Size Distance(RanIter begin, RanIter end, Saf::Type::IteratorCategory::RandomAccessCategory)
            {
                return end - begin;
            }

            template <class FwdIter>
            inline Saf::Size Distance(FwdIter begin, FwdIter end, Saf::Type::IteratorCategory::ForwardCategory)
            {
                Saf::Size dist = 0;

                while (begin != end)
                {
                    ++begin;
                    ++dist;
                }

                return dist;
            }

            template <class RanIter>
            inline void Advance(RanIter &it, Saf::Size dist, Saf::Type::IteratorCategory::RandomAccessCategory)
            {
                it += dist;
            }

            template <class InpIter>
            inline void Advance(InpIter &it, Saf::Size dist, Saf::Type::IteratorCategory::ForwardCategory)
            {
                while (dist-- > 0)
                {
                    ++it;
                }
            }

            template <class RanIter>
            void Rotate(RanIter begin, RanIter middle, RanIter end, Saf::Type::IteratorCategory::RandomAccessCategory)
            {
                if (middle < begin || end <= middle)
                {
                    throw Saf::IndexOutOfRangeException(SAF_SOURCE_LOCATION);
                }

                Saf::Size step = middle - begin;        

                if (step > 0)
                {
                    Saf::Size len = end - begin;
                    Saf::Size done = 0; 
                    RanIter first = begin, cur, next;
                    typename Saf::Type::IteratorTraits<RanIter>::ValType tmpVal;

                    while (done < len)
                    {
                        cur = first;
                        next = first + step;

                        tmpVal = *first;
                        ++done;
                
                        while (next != first) 
                        {
                            ++done;

                            *cur = *next;
                            cur = next;
                            next += step;
                    
                            if (next >= end)
                            {
                                next -= len;
                            }
                        }

                        *cur = tmpVal;
                        ++first;
                    }
                }
            }

            template <class FwdIter>
            inline void Rotate(FwdIter begin, FwdIter middle, FwdIter end, Saf::Type::IteratorCategory::ForwardCategory)
            {
                FwdIter next = middle;

                while (begin != next)
                {
                    Saf::Algo::Swap(*begin, *next);
                    ++begin;
                    ++next;

                    if (next == end)
                    {
                        next = middle;
                    }
                    else if (begin == middle)
                    {
                        middle = next;
                    }
                }        
            }
        }
    }
    namespace Algo
    {
        namespace Range
        {
            template <class Iter>
            inline Size Distance(Iter begin, Iter end)
            {
                return Internal::AlgoRange::Distance(begin, end, Type::IteratorTraits<Iter>::Category());
            }

            template <class Iter>
            inline void Advance(Iter &it, Size dist)
            {
                Internal::AlgoRange::Advance(it, dist, Type::IteratorTraits<Iter>::Category());
            }

            template <class FwdIter, class Func>
            inline Func ForEach(FwdIter begin, FwdIter end, Func func)
            {
                while (begin != end)
                {
                    func(*begin);
                    ++begin;
                }

                return func;
            }

            template <class FwdIter, class Val>
            inline void Fill(FwdIter begin, FwdIter end, const Val& val)
            {
                while (begin != end)
                {
                    *begin = val;
                    ++begin;
                }
            }

            template <class FwdIter, class Val>
            inline void FillFirst(FwdIter first, Size num, const Val& val)
            {
                while (num-- > 0)
                {
                    *first = val;
                    ++first;
                }
            }

            template <class FwdIter, class Val>
            inline bool AllEqualTo(FwdIter begin, FwdIter end, const Val& val)
            {
                while (begin != end)
                {
                    if (*begin != val)
                    {
                        return false;
                    }

                    ++begin;
                }

                return true;
            }

            template <class FwdIter, class Val>
            inline bool AnyEqualTo(FwdIter begin, FwdIter end, const Val& val)
            {
                while (begin != end)
                {
                    if (*begin == val)
                    {
                        return true;
                    }

                    ++begin;
                }

                return false;
            }

            template <class FwdIter1, class FwdIter2>
            inline bool Equal(FwdIter1 r1Begin, FwdIter1 r1End, FwdIter2 r2Begin)
            {
                while (r1Begin != r1End)
                {
                    if (*r1Begin != *r2Begin)
                    {
                        return false;
                    }

                    ++r1Begin;
                    ++r2Begin;
                }

                return true;
            }

            template <class FwdIter1, class FwdIter2>
            inline bool Identical(FwdIter1 r1Begin, FwdIter1 r1End, FwdIter2 r2Begin, FwdIter2 r2End)
            {
                while (r1Begin != r1End && r2Begin != r2End)
                {
                    if (*r1Begin != *r2Begin)
                    {
                        return false;
                    }

                    ++r1Begin;
                    ++r2Begin;
                }

                return (r1Begin == r1End && r2Begin == r2End);
            }

            template <class FwdIterIn, class FwdIterOut>
            inline FwdIterOut Copy(FwdIterIn begin, FwdIterIn end, FwdIterOut dest)
            {
                while (begin != end)
                {
                    *dest = *begin;
                    ++dest;
                    ++begin;
                }

                return dest;
            }

            template <class FwdIter, class Val>
            inline Size Count(FwdIter begin, FwdIter end, const Val& val)
            {
                Size num = 0;

                while (begin != end)
                {
                    if (*begin == val)
                    {
                        ++num;
                    }
                    ++begin;
                }

                return num;
            }

            template <class FwdIter, class Pred>
            inline Size CountIf(FwdIter begin, FwdIter end, Pred pred)
            {
                Size num = 0;

                while (begin != end)
                {
                    if (pred(*begin))
                    {
                        ++num;
                    }
                    ++begin;
                }

                return num;
            }

            template <class BidIter>
            inline void Reverse(BidIter begin, BidIter end)
            {
                while (begin != end)
                {
                    if (begin == --end)
                    {
                        break;
                    }

                    Swap(*begin, *end);
                    ++begin;
                }
            }

            template <class Iter>
            inline void Rotate(Iter begin, Iter middle, Iter end)
            {
                Internal::AlgoRange::Rotate(begin, middle, end, Type::IteratorTraits<Iter>::Category());
            }
        }
    }
}

#endif