Saf/Math/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_MATH_RANGE_H
#define SAF_MATH_RANGE_H

#include "../Algo/Range.h"
#include "../Algo/Predicate.h"
#include "../Type/IteratorTraits.h"

namespace Saf
{
    namespace Math
    {
        namespace Range
        {
            template <class FwdIter, class Val, class Comp>
            inline FwdIter LowerBound(FwdIter begin, FwdIter end, const Val& val, Comp comp)
            {
                Size len = Algo::Range::Distance(begin, end);

                while (len > 0)
                {
                    Size halfLen = len / 2;

                    FwdIter mid = begin;
                    Algo::Range::Advance(mid, halfLen);

                    if (comp(*mid, val))
                    {
                        begin = ++mid;
                        len -= halfLen + 1;
                    }
                    else
                    {
                        len = halfLen;
                    }
                }

                return begin;
            }

            template <class FwdIter, class Val>
            inline FwdIter LowerBound(FwdIter begin, FwdIter end, const Val& val)
            {
                return LowerBound(begin, end, val, Algo::Predicate::Less<Val>());
            }

            template <class FwdIter, class Val, class Comp>
            inline FwdIter UpperBound(FwdIter begin, FwdIter end, const Val& val, Comp comp)
            {
                Size len = Algo::Range::Distance(begin, end);

                while (len > 0)
                {
                    Size halfLen = len / 2;

                    FwdIter mid = begin;
                    Algo::Range::Advance(mid, halfLen);

                    if (!comp(val, *mid))
                    {
                        begin = ++mid;
                        len -= halfLen + 1;
                    }
                    else
                    {
                        len = halfLen;
                    }
                }

                return begin;
            }

            template <class FwdIter, class Val>
            inline FwdIter UpperBound(FwdIter begin, FwdIter end, const Val& val)
            {
                return UpperBound(begin, end, val, Algo::Predicate::Less<Val>());
            }

            template <class FwdIter>
            inline typename Type::IteratorTraits<FwdIter>::ValType Sum(FwdIter begin, FwdIter end)
            {
                typename Type::IteratorTraits<FwdIter>::ValType sum = 0;

                while (begin != end)
                {
                    sum += *begin;
                    ++begin;
                }

                return sum;
            }

            template <class FwdIter>
            inline typename Type::IteratorTraits<FwdIter>::ValType Product(FwdIter begin, FwdIter end)
            {
                typename Type::IteratorTraits<FwdIter>::ValType prod = 1;

                while (begin != end)
                {
                    prod *= *begin;
                    ++begin;
                }

                return prod;
            }            
        }
    }
}

#endif