/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 */


#ifndef SEQUENTIAL_ITERATOR_H
#define SEQUENTIAL_ITERATOR_H

#include <stddef.h>

/*

The template functions in this file work with any SequentialIterator class
which allows forward move and dereferencing. The following piece of
C++ like pseudocode gives a formal description of what we expect from 
these classes:

template <class T>
class SequentialIterator
{
    int isEnd(); // not always defined
public:
    T& operator*() 
    {
	ASSERT(!isEnd());
	... ;
    }
    int operator==(SequentialIterator<T> x)
    {
	if (isEnd())
	    return x.isEnd();
	else if (x.isEnd())
	    return 0;
	else
	    return &*x == &**this;
    }
    int operator!=(SequentialIterator<T> x)
    {
	return !(*this == x);
    }
    SequentialIterator<T> operator++() 
    {
	ASSERT(!isEnd()); 
	... ;
    }
    SequentialIterator<T> operator++(int)
    {
	ASSERT(!isEnd());
	SequentialIterator<T> tmp = *this;
	*this++;
	return tmp;
    }
};

*/

template <class Iterator>
size_t distance(Iterator first, Iterator last)
{
    size_t n = 0;
    
    while (first != last) {
	first++;
	n++;
    }
    return n;
}

template <class Iterator>
Iterator advance(Iterator i, size_t n)
{
    while (n--) i++;
    return i;
}
    
template <class Iterator1, class Iterator2>
inline Iterator2 move(Iterator1 first, Iterator1 last, Iterator2 result)
{
    while (first != last) 
	*result++ = *first++;

    return result;
}

template <class Iterator1, class Iterator2>
inline Iterator2 move(Iterator1 first, size_t n, Iterator2 result)
{
    while (n--) 
	*result++ = *first++;

    return result;
}

template <class Iterator1, class Iterator2>
Iterator1 mismatch(Iterator1 first, Iterator1 last, Iterator2 otherFirst)
{
    while (first != last && *first == *otherFirst++) first++;
    return first;
}
	
template <class Iterator1, class Iterator2, class Equality>
Iterator1 mismatch(Iterator1 first, Iterator1 last, Iterator2 otherFirst, 
		   Equality eq)
{
    while (first != last && eq(*first, *otherFirst++)) first++;
    return first;
}

template <class Iterator1, class Iterator2>
Iterator1 search(Iterator1 first, Iterator1 last, 
		 Iterator2 otherFirst, Iterator2 otherLast)
{
    size_t d1 = distance(first, last);
    size_t d2 = distance(otherFirst, otherLast);

    if (d1 < d2) return last;

    Iterator1 current = first;
    Iterator2 otherCurrent = otherFirst;

    while (otherCurrent != otherLast)
	if (*current++ != *otherCurrent++)
	    if (d1-- == d2)
		return last;
	    else {
		current = ++first;
		otherCurrent = otherFirst;
	    }

    return (otherCurrent == otherLast) ? first : last;
}

template <class Iterator1, class Iterator2, class Equality>
Iterator1 search(Iterator1 first, Iterator1 last, 
		 Iterator2 otherFirst, Iterator2 otherLast, Equality eq)
{
    size_t d1 = distance(first, last);
    size_t d2 = distance(otherFirst, otherLast);

    if (d1 < d2) return last;

    Iterator1 current = first;
    Iterator2 otherCurrent = otherFirst;

    while (otherCurrent != otherLast)
	if (!eq(*current++, *otherCurrent++))
	    if (d1-- == d2)
		return last;
	    else {
		current = ++first;
		otherCurrent = otherFirst;
	    }

    return (otherCurrent == otherLast) ? first : last;
}
	
template <class Iterator1, class Iterator2>
inline int equal(Iterator1 first, Iterator1 last, Iterator2 otherFirst)
{
    return mismatch(first, last, otherFirst) == last;
}
	
template <class Iterator1, class Iterator2, class Equality>
inline int equal(Iterator1 first, Iterator1 last, Iterator2 otherFirst, 
		 Equality eq)
{
    return mismatch(first, last, otherFirst, eq) == last;
}

template <class Iterator1, class Iterator2>
int lexicographicalDifference(Iterator1 first1, Iterator1 last1,
			      Iterator2 first2, Iterator2 last2)
{
    while (first1 != last1 && first2 != last2) {
	int tmp = *first1++ - *first2++;
	if (tmp != 0)
	    return tmp;
    }

    if (first1 != last1)
	return 1;
    else if (first2 != last2)
	return -1;
    else
	return 0;
}

template <class Iterator1, class Iterator2, class Compare>
int lexicographicalDifference(Iterator1 first1, Iterator1 last1,
			      Iterator2 first2, Iterator2 last2, 
			      Compare comp)
{
    while (first1 != last1 && first2 != last2) {
	int tmp = comp(*first1++, *first2++);
	if (tmp != 0)
	    return tmp;
    }

    if (first1 != last1)
	return 1;
    else if (first2 != last2)
	return -1;
    else
	return 0;
}

template <class Iterator, class Function>
void forEach(Iterator first, Iterator last, Function f)
{
    while (first != last) 
	f(*first++);
}

template <class Iterator1, class Iterator2, class Function>
void forEach(Iterator1 first, Iterator1 last, Iterator2 otherFirst, Function f)
{
    while (first != last) 
	f(*first++, *otherFirst++);
}

template <class Iterator1, class Iterator2, class Iterator3, class Function>
void forEach(Iterator1 first, Iterator1 last, Iterator2 otherFirst, 
	     Iterator3 thirdFirst, Function f)
{
    while (first != last) 
	f(*first++, *otherFirst++, *thirdFirst++);
}

template <class Iterator, class T>
Iterator find(Iterator first, Iterator last, T element)
{
    while (first != last && *first != element) first++;
    return first;
}

template <class Iterator, class T, class Equality>
Iterator find(Iterator first, Iterator last, T element, Equality eq)
{
    while (first != last && !eq(*first, element)) first++;
    return first;
}

template <class Iterator, class T>
Iterator findNot(Iterator first, Iterator last, T element)
{
    while (first != last && *first == element) first++;
    return first;
}

template <class Iterator, class T, class Equality>
Iterator findNot(Iterator first, Iterator last, T element, Equality eq)
{
    while (first != last && eq(*first, element)) first++;
    return first;
}

template <class Iterator, class Predicate>
Iterator findIf(Iterator first, Iterator last, Predicate p)
{
    while (first != last && !p(*first)) first++;
    return first;
}

template <class Iterator, class Predicate>
Iterator findIfNot(Iterator first, Iterator last, Predicate p)
{
    while (first != last && p(*first)) first++;
    return first;
}

template <class Iterator, class Predicate>
inline int some(Iterator first, Iterator last, Predicate p)
{
    return findIf(first, last, p) != last;
}

template <class Iterator, class Predicate>
inline int every(Iterator first, Iterator last, Predicate p)
{
    return findIfNot(first, last, p) == last;
}

template <class Iterator, class Predicate>
inline int notAny(Iterator first, Iterator last, Predicate p)
{
    return findIf(first, last, p) == last;
}

template <class Iterator, class Predicate>
inline int notEvery(Iterator first, Iterator last, Predicate p)
{
    return findIfNot(first, last, p) != last;
}

template <class Iterator, class T>
size_t count(Iterator first, Iterator last, T element)
{
    size_t n = 0;
    
    while (first != last)
	if (*first++ == element) n++;

    return n;
}

template <class Iterator, class T, class Equality>
size_t count(Iterator first, Iterator last, T element, Equality eq)
{
    size_t n = 0;

    while (first != last)
	if (eq(*first++, element)) n++;

    return n;
}

template <class Iterator, class Predicate>
size_t countIf(Iterator first, Iterator last, Predicate p)
{
    size_t n = 0;

    while (first != last)
	if (p(*first++)) n++;

    return n;
}

template <class Iterator, class Predicate>
size_t countIfNot(Iterator first, Iterator last, Predicate p)
{
    size_t n = 0;

    while (first != last)
	if (!p(*first++)) n++;

    return n;
}

template <class Iterator, class T>
void replace(Iterator first, Iterator last, T oldValue, T newValue)
{
    while (first != last) {
        if (*first == oldValue) *first = newValue;
        first++;
    }
}

template <class Iterator, class T, class Equality>
void replace(Iterator first, Iterator last, T oldValue, T newValue, 
	     Equality eq)
{
    while (first != last) {
        if (eq(*first, oldValue)) *first = newValue;
        first++;
    }
}

template <class Iterator, class Predicate, class T>
void replaceIf(Iterator first, Iterator last, Predicate p, T newValue)
{
    while (first != last) {
        if (p(*first)) *first = newValue;
        first++;
    }
}

template <class Iterator, class Predicate, class T>
void replaceIfNot(Iterator first, Iterator last, Predicate p, T newValue)
{
    while (first != last) {
        if (!p(*first)) *first = newValue;
        first++;
    }
}

template <class Iterator1, class Iterator2, class T>
Iterator2 replaceCopy(Iterator1 first, Iterator1 last, Iterator2 result,
		      T oldValue, T newValue)
{
    while (first != last) {
	*result++ = (*first == oldValue) ? newValue : *first;
	first++;
    }
    return result;
}

template <class Iterator1, class Iterator2, class T, class Equality>
Iterator2 replaceCopy(Iterator1 first, Iterator1 last, Iterator2 result,
		      T oldValue, T newValue, Equality eq)
{
    while (first != last) {
	*result++ = (eq(*first, oldValue)) ? newValue : *first;
	first++;
    }
    return result;
}

template <class Iterator1, class Iterator2, class Predicate, class T>
Iterator2 replaceCopyIf(Iterator1 first, Iterator1 last, Iterator2 result,
			Predicate p, T newValue)
{
    while (first != last) {
	*result++ = (p(*first)) ? newValue : *first;
	first++;
    }
    return result;
}

template <class Iterator1, class Iterator2, class Predicate, class T>
Iterator2 replaceCopyIfNot(Iterator1 first, Iterator1 last, 
			   Iterator2 result, Predicate p, T newValue)
{
    while (first != last) {
	*result++ = (!p(*first)) ? newValue : *first;
	first++;
    }
    return result;
}

// this remove is stable

template <class Iterator, class T>
Iterator remove(Iterator first, Iterator last, T element)
{
    while (first != last && *first != element) first++; 

    if (first == last) return first;

    Iterator current = first;

    while (++first != last)
        if (*first != element) 
	    *current++ = *first;

    return current;
}

template <class Iterator, class T, class Equality>
Iterator remove(Iterator first, Iterator last, T element, Equality eq)
{
    while (first != last && !eq(*first, element)) first++; 

    if (first == last) return first;

    Iterator current = first;

    while (++first != last)
        if (!eq(*first, element))
	    *current++ = *first;

    return current;
}

template <class Iterator, class Predicate>
Iterator removeIf(Iterator first, Iterator last, Predicate p)
{
    while (first != last && !p(*first)) first++; 

    if (first == last) return first;

    Iterator current = first;

    while (++first != last)
        if (!p(*first))
	    *current++ = *first;

    return current;
}

template <class Iterator, class Predicate>
Iterator removeIfNot(Iterator first, Iterator last, Predicate p)
{
    while (first != last && p(*first)) first++; 

    if (first == last) return first;

    Iterator current = first;

    while (++first != last)
        if (p(*first))
	    *current++ = *first;

    return current;
}

template <class Iterator1, class Iterator2, class T>
Iterator2 removeCopy(Iterator1 first, Iterator1 last, Iterator2 result,
		     T element)
{
    while (first != last) {
	if (*first != element)
	    *result++ = *first;
	first++;
    }
    return result;
}

template <class Iterator1, class Iterator2, class T, class Equality>
Iterator2 removeCopy(Iterator1 first, Iterator1 last, Iterator2 result,
		     T element, Equality eq)
{
    while (first != last) {
	if (!eq(*first, element))
	    *result++ = *first;
	first++;
    }
    return result;
}

template <class Iterator1, class Iterator2, class Predicate>
Iterator2 removeCopyIf(Iterator1 first, Iterator1 last, Iterator2 result,
		       Predicate p)
{
    while (first != last) {
        if (!p(*first))
	    *result++ = *first;
	first++;
    }
    return result;
}

template <class Iterator, class Iterator2, class Predicate>
Iterator2 removeCopyIfNot(Iterator first, Iterator last, Iterator2 result,
			  Predicate p)
{
    while (first != last) {
        if (p(*first))
	    *result++ = *first;
	first++;
    }
    return result;
}

template <class Iterator>
Iterator removeDuplicates(Iterator first, Iterator last)
{
    Iterator current = first;

    while (current != last && find(first, current, *current) == current)
	current++; 

    if (current == last) return current;

    Iterator next = current;

    while (++next != last)
        if (find(first, current, *next) == current)
	    *current++ = *next;

    return current;
}

template <class Iterator, class Equality>
Iterator removeDuplicates(Iterator first, Iterator last, Equality eq)
{
    Iterator current = first;

    while (current != last && find(first, current, *current, eq) == current)
	current++; 

    if (current == last) return current;

    Iterator next = current;

    while (++next != last)
        if (find(first, current, *next, eq) == current)
	    *current++ = *next;

    return current;
}

template <class Iterator1, class Iterator2>
Iterator2 removeDuplicatesCopy(Iterator1 first, Iterator1 last, 
			       Iterator2 result)
{
    Iterator2 current = result;
    
    while (first != last) {
	if (find(result, current, *first) == current)
	    *current++ = *first;
	first++;
    }
    return current;
}

template <class Iterator1, class Iterator2, class Equality>
Iterator2 removeDuplicatesCopy(Iterator1 first, Iterator1 last, 
			       Iterator2 result, Equality eq)
{
    Iterator2 current = result;
    
    while (first != last) {
	if (find(result, current, *first, eq) == current)
	    *current++ = *first;
	first++;
    }
    return current;
}

template <class Iterator>
Iterator unique(Iterator first, Iterator last)
{
    if (first == last) return last;

    Iterator current = first;

    while (++first != last && *current != *first)
	current++;

    if (first == last) return last;

    while (++first != last)
	if (*current != *first) *++current = *first;

    return ++current;
}

template <class Iterator, class Equality>
Iterator unique(Iterator first, Iterator last, Equality eq)
{
    if (first == last) return last;

    Iterator current = first;

    while (++first != last && !eq(*current, *first))
	current++;

    if (first == last) return last;

    while (++first != last) 
	if (!eq(*current, *first)) *++current = *first;

    return ++current;
}

template <class Iterator1, class Iterator2>
Iterator2 uniqueCopy(Iterator1 first, Iterator1 last, Iterator2 result)
{
    if (first == last) return result;

    *result = *first;
    
    while (++first != last)
	if (*result != *first) *++result = *first;

    return ++result;
}

template <class Iterator1, class Iterator2, class Equality>
Iterator2 uniqueCopy(Iterator1 first, Iterator1 last, Iterator2 result,
		     Equality eq)
{
    if (first == last) return result;

    *result = *first;
    
    while (++first != last)
	if (!eq(*result, *first)) *++result = *first;

    return ++result;
}

template <class Iterator, class Transformation>
void transform(Iterator first, Iterator last, Transformation trans)
{
    while (first != last) {
	*first = trans(*first);
	first++;
    }
}

template <class Iterator1, class Iterator2, class Transformation>
void transform(Iterator1 first, Iterator1 last, Iterator2 otherFirst,
	       Transformation trans)
{
    while (first != last) {
	*first = trans(*first, *otherFirst);
	first++;
	otherFirst++;
    }
}

template <class Iterator1, class Iterator2, class Transformation>
Iterator2 transformCopy(Iterator1 first, Iterator1 last, Iterator2 result,
			Transformation trans)
{
    while (first != last)
	*result++ = trans(*first++);

    return result;
}

template <class Iterator1, class Iterator2, 
          class Iterator3, class Transformation>
Iterator2 transformCopy(Iterator1 first, Iterator1 last, Iterator2 otherFirst,
			Iterator3 result, Transformation trans)
{
    while (first != last)
	*result++ = trans(*first++, *otherFirst++);

    return result;
}

template <class Iterator, class T>
void fill(Iterator first, Iterator last, T value)
{
    while (first != last)
        *first++ = value;
}

template <class Iterator, class T, class Function>
void generate(Iterator first, Iterator last, T value, Function f)
{
    while (first != last)
	*first++ = f(value++);
}

template <class Iterator, class T>
void iota(Iterator first, Iterator last, T value)
{
    while (first != last)
	*first++ = value++;
}

template <class Iterator, class T>
T accumulate(Iterator first, Iterator last, T a)
{
    while (first != last)
	a += *first++;

    return a;
}

template <class Iterator, class T, class Function>
T accumulate(Iterator first, Iterator last, T a, Function f)
{
    while (first != last)
	a = f(a, *first++);

    return a;
}

template <class Iterator1, class Iterator2, class T, class Function>
T accumulate(Iterator1 first, Iterator1 last, Iterator2 otherFirst, 
	     T a, Function f)
{
    while (first != last)
	a = f(a, *first++, *otherFirst++);

    return a;
}

template <class Iterator, class T, class Predicate>
T accumulateIf(Iterator first, Iterator last, T value, Predicate p)
{
    for (; first != last; first++)
	if (p(*first)) value += *first++;
    return value;
}

template <class Iterator, class T, class Predicate, class Function>
T accumulateIf(Iterator first, Iterator last, T value, Predicate p,
	       Function f)
{
    for (; first != last; first++)
	if (p(*first)) value = f(value, *first++);
    return value;
}

template <class Iterator, class Function>
void scan(Iterator first, Iterator last, Function f)
{
    if (first == last) return;
    Iterator prev = first;
    while (++first != last) {
	*first = f(*prev, *first);
	prev = first;
    }
}

template <class Iterator1, class Iterator2, class Function>
Iterator2 scanCopy(Iterator1 first, Iterator1 last, Iterator2 result, 
		   Function f)
{
    if (first == last) return result;
    *result = *first;
    Iterator2 prev = result++;
    while (++first != last) {
        *result = f(*prev, *first);
        prev = result++;
    }
    return result;
}

template <class Iterator1, class Iterator2>
Iterator2 swapRanges(Iterator1 first, Iterator1 last, Iterator2 otherFirst)
{
    while (first != last)
	swap(*first++, *otherFirst++);

    return otherFirst;
}

template <class Iterator1, class Iterator2>
Iterator2 swapRanges(Iterator1 first, size_t n, Iterator2 otherFirst)
{
    while (n--)
	swap(*first++, *otherFirst++);

    return otherFirst;
}

template <class Iterator>
Iterator maxElement(Iterator first, Iterator last)
{
    if (first == last) return first;
    Iterator result = first;
    while (++first != last) 
	if (*first - *result > 0) result = first;
    return result;
}

template <class Iterator, class Compare>
Iterator maxElement(Iterator first, Iterator last, Compare comp)
{
    if (first == last) return first;
    Iterator result = first;
    while (++first != last) 
	if (comp(*first, *result) > 0) result = first;
    return result;
}

template <class Iterator>
Iterator minElement(Iterator first, Iterator last)
{
    if (first == last) return first;
    Iterator result = first;
    while (++first != last) 
	if (*first - *result < 0) result = first;
    return result;
}

template <class Iterator, class Compare>
Iterator minElement(Iterator first, Iterator last, Compare comp)
{
    if (first == last) return first;
    Iterator result = first;
    while (++first != last) 
	if (comp(*first, *result) < 0) result = first;
    return result;
}

template <class Iterator>
void rotate(Iterator first, Iterator middle, Iterator last)
{
    if (first == middle || middle == last) return;

    for(Iterator i = middle;;) {
        swap(*first++, *i++);
        if (first == middle) {
            if (i == last) return;
            middle = i;
        } else if (i == last)
            i = middle;
    }
}

template <class Iterator1, class Iterator2>
int isPermutation(Iterator1 first, Iterator1 last, 
		  Iterator2 otherFirst, Iterator2 otherLast)
{
    Iterator1 x = first;
    Iterator2 y = otherFirst;
    while (x != last && y != otherLast &&
	   count(first, last, *x) == count(otherFirst, otherLast, *x))
	x++, y++;

    return x == last && y == otherLast;
}

template <class Iterator1, class Iterator2>
int isSubset(Iterator1 first, Iterator1 last, 
	     Iterator2 otherFirst, Iterator2 otherLast)
{
    Iterator1 x = first;

    while (x != last &&
	   count(first, last, *x) <= count(otherFirst, otherLast, *x))
	x++;

    return x == last;
}

template <class Iterator, class Compare>
Iterator adjacentCompare(Iterator first, Iterator last, Compare comp)
{
    if (first == last) return last;

    Iterator next = first;

    while(++next != last)
        if (!comp(*first++, *next)) return first;

    return last;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 concatenateCopy(Iterator1 first1, Iterator1 last1, 
		          Iterator2 first2, Iterator2 last2, 
			  Iterator3 result)
{
    while (first1 != last1)
	*result++ = *first1++;
    while (first2 != last2)
	*result++ = *first2++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 unionCopy(Iterator1 first1, Iterator1 last1, 
		    Iterator2 first2, Iterator2 last2, 
		    Iterator3 result)
{
    while (first1 != last1 && first2 != last2) {
	int c = int(*first1 - *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    *result++ = *first2++;
	else {
	    *result++ = *first1++;
	    first2++;
	}
    }
    if (first1 == last1)
	while (first2 != last2)
	    *result++ = *first2++;
    if (first2 == last2)
	while (first1 != last1)
	    *result++ = *first1++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3, class Compare>
Iterator3 unionCopy(Iterator1 first1, Iterator1 last1, 
		    Iterator2 first2, Iterator2 last2, 
		    Iterator3 result, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
	int c = comp(*first1, *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    *result++ = *first2++;
	else {
	    *result++ = *first1++;
	    first2++;
	}
    }
    if (first1 == last1)
	while (first2 != last2)
	    *result++ = *first2++;
    if (first2 == last2)
	while (first1 != last1)
	    *result++ = *first1++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 intersectionCopy(Iterator1 first1, Iterator1 last1, 
		           Iterator2 first2, Iterator2 last2, 
		           Iterator3 result)
{
    while (first1 != last1 && first2 != last2) {
	int c = int(*first1 - *first2);
	if (c < 0)
	    first1++;
	else if (c > 0)
	    first2++;
	else {
	    *result++ = *first1++;
	    first2++;
	}
    }
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3, class Compare>
Iterator3 intersectionCopy(Iterator1 first1, Iterator1 last1, 
		           Iterator2 first2, Iterator2 last2, 
		           Iterator3 result, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
	int c = Comp(*first1, *first2);
	if (c < 0)
	    first1++;
	else if (c > 0)
	    first2++;
	else {
	    *result++ = *first1++;
	    first2++;
	}
    }
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 differenceCopy(Iterator1 first1, Iterator1 last1, 
		         Iterator2 first2, Iterator2 last2, 
			 Iterator3 result)
{
    while (first1 != last1 && first2 != last2) {
	int c = int(*first1 - *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    first2++;
	else {
	    first1++;
	    first2++;
	}
    }
    while (first1 != last1)
	*result++ = *first1++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3, class Compare>
Iterator3 differenceCopy(Iterator1 first1, Iterator1 last1, 
		         Iterator2 first2, Iterator2 last2, 
			 Iterator3 result, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
	int c = comp(*first1, *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    first2++;
	else {
	    first1++;
	    first2++;
	}
    }
    while (first1 != last1)
	*result++ = *first1++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3>
Iterator3 symmetricDifferenceCopy(Iterator1 first1, Iterator1 last1, 
			          Iterator2 first2, Iterator2 last2, 
			          Iterator3 result)
{
    while (first1 != last1 && first2 != last2) {
	int c = int(*first1 - *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    *result++ = *first2++;
	else {
	    first1++;
	    first2++;
	}
    }
    while (first1 != last1)
	*result++ = *first1++;
    while (first2 != last2)
	*result++ = *first2++;
    return result;
}

template <class Iterator1, class Iterator2, class Iterator3, class Compare>
Iterator3 symmetricDifferenceCopy(Iterator1 first1, Iterator1 last1, 
			          Iterator2 first2, Iterator2 last2, 
			          Iterator3 result, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
	int c = comp(*first1, *first2);
	if (c < 0)
	    *result++ = *first1++;
	else if (c > 0)
	    *result++ = *first2++;
	else {
	    first1++;
	    first2++;
	}
    }
    while (first1 != last1)
	*result++ = *first1++;
    while (first2 != last2)
	*result++ = *first2++;
    return result;
}

#endif