/* Copyright (c) 1997-2007
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program 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 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program 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.
*/

#ifndef _POLYMAKE_EXTEND_ALGO_H
#define _POLYMAKE_EXTEND_ALGO_H "$Project: polymake $$Id: extend_algo.h 7556 2007-01-12 17:36:36Z gawrilow $"

namespace pm {

template <typename Iterator1, typename Iterator2> inline
Iterator2 _copy(Iterator1& src, Iterator2& dst, cons<True, False>)
{
   for (; !src.at_end(); ++src, ++dst) *dst=*src;
   return dst;
}

template <typename Iterator1, typename Iterator2> inline
Iterator2 _copy(Iterator1& src, Iterator2& dst, cons<False, True>)
{
   for (; !dst.at_end(); ++src, ++dst) *dst=*src;
   return dst;
}

template <typename Iterator1, typename Iterator2> inline
Iterator2 _copy(Iterator1& src, Iterator2& dst, cons<True, True>)
{
   for (; !src.at_end() && !dst.at_end(); ++src, ++dst) *dst=*src;
   return dst;
}

template <typename Iterator1, typename Iterator2> inline
bool _equal(Iterator1& it1, Iterator2& it2, cons<True, False>)
{
   for (; !it1.at_end(); ++it1, ++it2)
      if (*it1 != *it2) return false;
   return true;
}

template <typename Iterator1, typename Iterator2> inline
bool _equal(Iterator1& it1, Iterator2& it2, cons<False, True>)
{
   for (; !it2.at_end(); ++it1, ++it2)
      if (*it1 != *it2) return false;
   return true;
}

template <typename Iterator1, typename Iterator2> inline
bool _equal(Iterator1& it1, Iterator2& it2, cons<True, True>)
{
   for (; !it1.at_end() && !it2.at_end(); ++it1, ++it2)
      if (*it1 != *it2) return false;
   return it1.at_end() && it2.at_end();
}

template <typename Iterator1, typename Iterator2> inline
void _swap_ranges(Iterator1& it1, Iterator2& it2, cons<True, False>)
{
   for (; !it1.at_end(); ++it1, ++it2) std::swap(*it1,*it2);
}

template <typename Iterator1, typename Iterator2> inline
void _swap_ranges(Iterator1& it1, Iterator2& it2, cons<False, True>)
{
   for (; !it2.at_end(); ++it1, ++it2) std::swap(*it1,*it2);
}

template <typename Iterator1, typename Iterator2> inline
void _swap_ranges(Iterator1& it1, Iterator2& it2, cons<True, True>)
{
   for (; !it1.at_end() && !it2.at_end(); ++it1, ++it2) std::swap(*it1,*it2);
}

template <typename Iterator> inline
typename iterator_traits<Iterator>::value_type
first_nonzero(Iterator src)
{
   for (; !src.at_end(); ++src) {
      typename iterator_traits<Iterator>::value_type v=*src;
      if (v) return v;
   }
   return typename iterator_traits<Iterator>::value_type();
}

} // end namespace pm

namespace std {

template <typename Iterator1, typename Iterator2> inline
Iterator2 copy(Iterator1 src, Iterator2 dst)
{
   return pm::_copy(src, dst, pm::cons< pm::bool2type<pm::check_iterator_feature<Iterator1,pm::end_sensitive>::value>,
		                        pm::bool2type<pm::check_iterator_feature<Iterator2,pm::end_sensitive>::value> >());
}

template <typename Iterator, typename T> inline
void fill(Iterator dst, const T& value)
{
   for (; !dst.at_end(); ++dst) *dst=value;
}

template <typename Iterator, typename Value> inline
Iterator find(Iterator src, const Value x)
{
   while (!src.at_end() && *src != x) ++src;
   return src;
}

template <typename Iterator, typename Predicate> inline
Iterator find_if(Iterator src, const Predicate& pred_arg)
{
   typedef pm::unary_helper<Iterator, Predicate> helper;
   const typename helper::operation& pred=helper::create(pred_arg);
   while (!src.at_end() && !pred(*helper::get(src))) ++src;
   return src;
}

template <typename Iterator1, typename Iterator2> inline
void swap_ranges(Iterator1 it1, Iterator2 it2)
{
   pm::_swap_ranges(it1, it2, pm::cons< pm::bool2type<pm::check_iterator_feature<Iterator1,pm::end_sensitive>::value>,
		                        pm::bool2type<pm::check_iterator_feature<Iterator2,pm::end_sensitive>::value> >());
}

// This specialization utilizes the (possibly) optimized swap function.
template <typename Iterator> inline
void iter_swap(const Iterator& a, const Iterator& b) { swap(*a,*b); }

template <typename Iterator1, typename Iterator2> inline
bool equal(Iterator1 it1, Iterator2 it2)
{
   return pm::_equal(it1, it2, pm::cons< pm::bool2type<pm::check_iterator_feature<Iterator1,pm::end_sensitive>::value>,
		                         pm::bool2type<pm::check_iterator_feature<Iterator2,pm::end_sensitive>::value> >());
}

} // end namespace std

#if _POLYMAKE_ICC_ONLY
namespace std_ext {

// copied from the STL version shipped together with gcc

template <typename InputIterator, typename Size, typename OutputIterator> inline
std::pair<InputIterator,OutputIterator>
_copy_n(InputIterator& src, Size count, OutputIterator& dst, std::input_iterator_tag*)
{
   for (; count>0; --count) {
      *dst=*src;  ++src;  ++dst;
   }
   return std::pair<InputIterator,OutputIterator>(src,dst);
}

template <typename InputIterator, typename Size, typename OutputIterator> inline
std::pair<InputIterator,OutputIterator>
_copy_n(InputIterator& src, Size count, OutputIterator& dst, std::random_access_iterator_tag*)
{
   InputIterator src_end=src+count;
   return std::pair<InputIterator,OutputIterator>(src_end, std::copy(src,src_end,dst));
}

template <typename InputIterator, typename Size, typename OutputIterator> inline
std::pair<InputIterator,OutputIterator>
copy_n(InputIterator src, Size count, OutputIterator dst)
{
   return _copy_n(src, count, dst, typename std::iterator_traits<InputIterator>::iterator_category());
}

} // end namespace std_ext
#endif // _POLYMAKE_ICC_ONLY
#endif // _POLYMAKE_EXTEND_ALGO_H

// Local Variables:
// mode:C++
// End:
