algorithm.h

Go to the documentation of this file.

/******************************************************************************
The MIT License(MIT)

Embedded Template Library.

Copyright(c) 2014 jwellbelove

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
******************************************************************************/

#ifndef __ETL_ALGORITHM__
#define __ETL_ALGORITHM__


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

#include "type_traits.h"

namespace etl
{
  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TCompare>
  std::pair<TIterator, TIterator> minmax_element(TIterator begin, TIterator end, TCompare compare)
  {
    TIterator minimum = begin;
    TIterator maximum = begin;

    while (begin != end)
    {
      if (compare(*begin, *minimum))
      {
        minimum = begin;
      }

      if (compare(*maximum, *begin))
      {
        maximum = begin;
      }
        
      ++begin;
    }

    return std::pair<TIterator, TIterator>(minimum, maximum);
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator>
  std::pair<TIterator, TIterator> minmax_element(TIterator begin, TIterator end)
  {
      typedef typename std::iterator_traits<TIterator>::value_type value_t;

      return etl::minmax_element(begin, end, std::less<value_t>());
  } 
    
  //***************************************************************************
  //***************************************************************************
  template <typename T> 
  std::pair<const T&, const T&> minmax(const T& a, const T& b)
  {
      return (b < a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
  }

  //***************************************************************************
  //***************************************************************************
  template <typename T, typename TCompare> 
  std::pair<const T&, const T&> minmax(const T& a, const T& b, TCompare compare)
  {
    return compare(b, a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator>
  TIterator is_sorted_until(TIterator begin, TIterator end)
  {
    if (begin != end) 
    {
      TIterator next = begin;

      while (++next != end) 
      {
        if (*next < *begin)
        {
          return next;
        }
            
        ++begin;
      }
    }

    return end;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TCompare>
  TIterator is_sorted_until(TIterator begin, TIterator end, TCompare compare) 
  {
    if (begin != end) 
    {
      TIterator next = begin;

      while (++next != end) 
      {
        if (compare(*next, *begin))
        {
          return next;
        }
            
        ++begin;
      }
    }

    return end;
  }

  //***************************************************************************
  //***************************************************************************
  template<class TIterator>
  bool is_sorted(TIterator begin, TIterator end)
  {
    return etl::is_sorted_until(begin, end) == end;
  }

  //***************************************************************************
  //***************************************************************************
  template<class TIterator, class TCompare>
  bool is_sorted(TIterator begin, TIterator end, TCompare compare)
  {
    return etl::is_sorted_until(begin, end, compare) == end;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TInputIterator, typename Size, typename TOutputIterator>
  TOutputIterator copy_n(TInputIterator begin, Size count, TOutputIterator result)
  {
    if (count > 0)
    {
      for (Size i = 0; i < count; ++i)
      {
        *result++ = *begin++;
      }
    }

    return result;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TOutputIterator, typename TUnaryPredicate>
  TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
  {
    while (begin != end)
    {
      if (predicate(*begin))
      {
        *out++ = *begin;
      }
         
      ++begin;
    }

    return out;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TUnaryPredicate>
  TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    while (begin != end)
    {
      if (!predicate(*begin))
      {
        return begin;
      }

      ++begin;
    }

    return end;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TUnaryPredicate >
  bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    return etl::find_if_not(begin, end, predicate) == end;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TUnaryPredicate >
  bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    return std::find_if(begin, end, predicate) != end;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TUnaryPredicate >
  bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    return std::find_if(begin, end, predicate) == end;
  }
  
  //***************************************************************************
  //***************************************************************************
  template <typename TIterator1, typename TIterator2>
  bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
  {
    if (begin1 != end1)
    {
      TIterator2 end2 = begin2;

      std::advance(end2, std::distance(begin1, end1));

      for (TIterator1 i = begin1; i != end1; ++i) 
      {
        if (i == std::find(begin1, i, *i))
        {
          size_t n = std::count(begin2, end2, *i);

          if (n == 0 || std::count(i, end1, *i) != n)
          {
            return false;
          }
        }
      }
    }

    return true;
  }
  
  //***************************************************************************
  //***************************************************************************
  template <typename TIterator1, typename TIterator2>
  bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2, TIterator2 end2)
  {
    if (begin1 != end1)
    {
      for (TIterator1 i = begin1; i != end1; ++i) 
      {
        if (i == std::find(begin1, i, *i))
        {
          size_t n = std::count(begin2, end2, *i);

          if (n == 0 || std::count(i, end1, *i) != n)
          {
            return false;
          }
        }
      }
    }

    return true;
  } 

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
  bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2, TBinaryPredicate predicate)
  {
    if (begin1 != end1)
    {
      TIterator2 end2 = begin2;

      std::advance(end2, std::distance(begin1, end1));

      for (TIterator1 i = begin1; i != end1; ++i) 
      {
        if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
        {
          size_t n = std::count(begin2, end2, *i);

          if (n == 0 || std::count(i, end1, *i) != n)
          {
            return false;
          }
        }
      }
    }

    return true;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
  bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2, TIterator2 end2, TBinaryPredicate predicate)
  {
    if (begin1 != end1)
    {
      for (TIterator1 i = begin1; i != end1; ++i) 
      {
        if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
        {
          size_t n = std::count(begin2, end2, *i);

          if (n == 0 || std::count(i, end1, *i) != n)
          {
            return false;
          }
        }
      }
    }

    return true;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TIterator, typename TUnaryPredicate>
  bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    while (begin != end)
    {
      if (!predicate(*begin++))
      {
        break;
      }
    }

    while (begin != end)
    {
      if (predicate(*begin++))
      {
        return false;
      }
    }
     
    return true;
  }

  //***************************************************************************
  //***************************************************************************
  template <class TIterator, class TUnaryPredicate>
  TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
  {
    while (begin != end)
    {
      if (!predicate(*begin))
      {
        return begin;
      }

      ++begin;
    }

    return begin;
  }

  //***************************************************************************
  //***************************************************************************
  template <typename TSource, typename TDestinationTrue, typename TDestinationFalse, typename TUnaryPredicate>
  std::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource           begin,
                                                                  TSource           end, 
                                                                  TDestinationTrue  destination_true,
                                                                                                TDestinationFalse destination_false, 
                                                                                                TUnaryPredicate   predicate)
  {
    while (begin != end)
    {
      if (predicate(*begin))
      {
        *destination_true++ = *begin++;
      }
      else
      {
        *destination_false++ = *begin++;
      }
    }

    return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
  }
}

#endif