Subversion Repositories Kolibri OS

//

// Copyright 2013 Francisco Jerez

//

// 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 CLOVER_UTIL_ALGORITHM_HPP

#define CLOVER_UTIL_ALGORITHM_HPP

#include 

#include 

#include "util/range.hpp"

#include "util/functional.hpp"

namespace clover {

   namespace detail {

      template

      using preferred_reference_type = decltype(*std::declval().begin());

   }

   ///

   /// Return the first element in a range.

   ///

   template

   detail::preferred_reference_type

   head(R &&r) {

      assert(!r.empty());

      return r.front();

   }

   ///

   /// Return all elements in a range but the first.

   ///

   template

   slice_range

   tail(R &&r) {

      assert(!r.empty());

      return { std::forward(r), 1, r.size() };

   }

   ///

   /// Return the only element in a range.

   ///

   template

   detail::preferred_reference_type

   unique(R &&r) {

      if (r.size() != 1)

         throw std::out_of_range("");

      return r.front();

   }

   ///

   /// Combine a variable number of ranges element-wise in a single

   /// range of tuples.

   ///

   template

   adaptor_range

   zip(Rs &&... rs) {

      return map(zips(), std::forward(rs)...);

   }

   ///

   /// Evaluate the elements of a range.

   ///

   /// Useful because most of the range algorithms evaluate their

   /// result lazily.

   ///

   template

   void

   eval(R &&r) {

      for (auto i = r.begin(), e = r.end(); i != e; ++i)

         *i;

   }

   ///

   /// Apply functor \a f element-wise on a variable number of ranges

   /// \a rs.

   ///

   /// The functor \a f should take as many arguments as ranges are

   /// provided.

   ///

   template

   void

   for_each(F &&f, Rs &&... rs) {

      eval(map(std::forward(f), std::forward(rs)...));

   }

   ///

   /// Copy all elements from range \a r into an output container

   /// starting from iterator \a i.

   ///

   template

   void

   copy(R &&r, I i) {

      for (detail::preferred_reference_type x : r)

         *(i++) = x;

   }

   ///

   /// Reduce the elements of range \a r by applying functor \a f

   /// element by element.

   ///

   /// \a f should take an accumulator value (which is initialized to

   /// \a a) and an element value as arguments, and return an updated

   /// accumulator value.

   ///

   /// \returns The final value of the accumulator.

   ///

   template

   A

   fold(F &&f, A a, R &&r) {

      for (detail::preferred_reference_type x : r)

         a = f(a, x);

      return a;

   }

   ///

   /// Return how many elements of range \a r are equal to \a x.

   ///

   template

   typename std::remove_reference::type::size_type

   count(T &&x, R &&r) {

      typename std::remove_reference::type::size_type n = 0;

      for (detail::preferred_reference_type y : r) {

         if (x == y)

            n++;

      }

      return n;

   }

   ///

   /// Return the first element in range \a r for which predicate \a f

   /// evaluates to true.

   ///

   template

   detail::preferred_reference_type

   find(F &&f, R &&r) {

      for (detail::preferred_reference_type x : r) {

         if (f(x))

            return x;

      }

      throw std::out_of_range("");

   }

   ///

   /// Return true if the element-wise application of predicate \a f

   /// on \a rs evaluates to true for all elements.

   ///

   template

   bool

   all_of(F &&f, Rs &&... rs) {

      for (auto b : map(f, rs...)) {

         if (!b)

            return false;

      }

      return true;

   }

   ///

   /// Return true if the element-wise application of predicate \a f

   /// on \a rs evaluates to true for any element.

   ///

   template

   bool

   any_of(F &&f, Rs &&... rs) {

      for (auto b : map(f, rs...)) {

         if (b)

            return true;

      }

      return false;

   }

   ///

   /// Erase elements for which predicate \a f evaluates to true from

   /// container \a r.

   ///

   template

   void

   erase_if(F &&f, R &&r) {

      auto i = r.begin(), e = r.end();

      for (auto j = r.begin(); j != e; ++j) {

         if (!f(*j)) {

            if (j != i)

               *i = std::move(*j);

            ++i;

         }

      }

      r.erase(i, e);

   }

}

#endif