#ifndef _STDEXT_ALGORITHM_H
#define _STDEXT_ALGORITHM_H

#ifndef UPPER_BOUND
#define UPPER_BOUND(x) ((x==NULL)? 0: sizeof(x)/sizeof(x[0]))
#endif

#include <vector>
#include <utility>
#include <algorithm>
#include <assert.h>


namespace stdext
{


template<class _InIt1,
  class _InIt2, class T> inline
void set_intersection_to_vector(_InIt1 _First1, _InIt1 _Last1,
                      _InIt2 _First2, _InIt2 _Last2, std::vector<T> &vec)
{
  vec.insert(vec.begin(), min(_Last1 - _First1, _Last2 - _First2), std::vector<T>::value_type());
  vec.erase(set_intersection(_First1, _Last1, _First2, _Last2, vec.begin()), vec.end());
}


template<
  class _InIt1,
  class _InIt2, 
  class T,
  class _Pr
> inline
void set_intersection_to_vector(_InIt1 _First1, _InIt1 _Last1,
                      _InIt2 _First2, _InIt2 _Last2, 
                      _Pr _Pred, std::vector<T> &vec)
{
  vec.insert(vec.begin(), min(_Last1 - _First1, _Last2 - _First2), std::vector<T>::value_type());
  vec.erase(set_intersection(_First1, _Last1, _First2, _Last2, vec.begin(), _Pred), vec.end());
}


template<class _InIt1,
  class _InIt2, 
  class T> inline
void set_difference_to_vector(_InIt1 _First1, _InIt1 _Last1,
                                  _InIt2 _First2, _InIt2 _Last2, std::vector<T> &vec)
{
  vec.insert(vec.begin(), _Last1 - _First1, std::vector<T>::value_type());
  vec.erase(std::set_difference(_First1, _Last1, _First2, _Last2, vec.begin()), vec.end());
}

template<class _InIt1,
  class _InIt2, 
  class T,
  class _Pr
> inline
void set_difference_to_vector(_InIt1 _First1, _InIt1 _Last1,
                                  _InIt2 _First2, _InIt2 _Last2, 
                                  _Pr _Pred, std::vector<T> &vec)
{
  vec.insert(vec.begin(), _Last1 - _First1, std::vector<T>::value_type());
  vec.erase(std::set_difference(_First1, _Last1, _First2, _Last2, vec.begin(), _Pred), vec.end());
}

template<class _InIt1,
  class _InIt2, 
  class _OutIt1,
  class _OutIt2,
  class _OutIt3,
  class _Pr
> inline
void set_full_difference(_InIt1 _First1, _InIt1 _Last1,
               _InIt2 _First2, _InIt2 _Last2, 
               _OutIt1 &_LeftOnly,
               _OutIt2 &_RightOnly,
               _OutIt3 &_Stable,
               _Pr _Pred) 
{
  for (; _First1 != _Last1 && _First2 != _Last2; )
    if (_Pred(*_First1, *_First2))
      *_LeftOnly++ = *_First1, ++_First1;
    else if (_Pred(*_First2, *_First1))
      *_RightOnly++= *_First2, ++_First2;
    else
      *_Stable++= std::make_pair(*_First1, *_First2), ++_First1, ++_First2;

  for (; _First1 != _Last1; ++_First1)
    *_LeftOnly++ = *_First1;

  for (; _First2 != _Last2; ++_First2)
    *_RightOnly++ = *_First2;
}

template<
  class T, 
  class _InIt1,
  class _InIt2, 
  class _Pr> inline
void set_full_difference_to_vectors(_InIt1 _First1, _InIt1 _Last1,
                                    _InIt2 _First2, _InIt2 _Last2, 
                                    std::vector<T> &left_only, 
                                    std::vector<T> &right_only,
                                    std::vector<std::pair<T, T> > &stable,
                                    _Pr _Pred)
{
  typedef typename std::vector<T>::iterator OIter1;
  typedef typename std::vector<T>::iterator OIter2;
  typedef typename std::vector<std::pair<T, T> >::iterator OIter3;

  OIter1 lfirst= left_only.begin();
  OIter2 rfirst= right_only.begin();
  OIter3 sfirst= stable.begin();

  left_only.insert (lfirst, _Last1 - _First1, T());
  right_only.insert(rfirst, _Last2 - _First2, T());
  stable.insert    (sfirst, std::min(_Last1 - _First1, _Last2 - _First2), std::make_pair(T(), T()));

  lfirst= left_only.begin();
  rfirst= right_only.begin();
  sfirst= stable.begin();

  set_full_difference(_First1, _Last1, _First2, _Last2, lfirst, rfirst, sfirst, _Pred);

  left_only.erase(lfirst, left_only.end());
  right_only.erase(rfirst, right_only.end());
  stable.erase(sfirst, stable.end());
}



}

#endif
