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


#ifndef INSERTION_SORT_H
#define INSERTION_SORT_H

#include "assert.H"
#include "utilities.H"
#include "binary.H"

template <class Iterator, class T>
inline Iterator unguardedLinearInsert(Iterator last, T value)
{
    while (value - *(last - 1) < 0) {
	*last = *(last - 1);
	last--;
    }
    *last = value;
    return last;
}

template <class Iterator, class T, class Compare>
inline Iterator unguardedLinearInsert(Iterator last, T value, Compare comp)
{
    while (comp(value , *(last - 1)) < 0) {
	*last = *(last - 1);
	last--;
    }
    *last = value;
    return last;
}

template <class Iterator, class T>
Iterator linearInsert(Iterator first, Iterator last, T value)
{
    ASSERT(first != last);

    if (value - *first >= 0) 
	return unguardedLinearInsert(last, value);

    moveBackward(first, last, last + 1);
    *first = value;
    return first;
}

template <class Iterator, class T, class Compare>
Iterator linearInsert(Iterator first, Iterator last, T value, Compare comp)
{
    ASSERT(first != last);

    if (comp(value, *first) >= 0) 
	return unguardedLinearInsert(last, value, comp);

    moveBackward(first, last, last + 1);
    *first = value;
    return first;
}

template <class Iterator, class T>
Iterator binaryInsert(Iterator first, Iterator last, T value)
{
    ASSERT(first != last);

    Iterator cut = binaryNotGreater(first, last, value);

    moveBackward(cut, last, last + 1);
    *cut = value;
    return cut;
}

template <class Iterator, class T, class Compare>
Iterator binaryInsert(Iterator first, Iterator last, T value, Compare comp)
{
    ASSERT(first != last);

    Iterator cut = binaryNotGreater(first, last, value, comp);

    moveBackward(cut, last, last + 1);
    *cut = value;
    return cut;
}

template <class Iterator>
void unguardedInsertionSort(Iterator first, Iterator last)
{
    if (first == last) return;
    for (Iterator i = first; i != last; i++)
	(void)unguardedLinearInsert(i, *i);
}

template <class Iterator, class Compare>
void unguardedInsertionSort(Iterator first, Iterator last, Compare comp)
{
    if (first == last) return;
    for (Iterator i = first; i != last; i++)
	(void)unguardedLinearInsert(i, *i, comp);
}

template <class Iterator>
void insertionSort(Iterator first, Iterator last)
{
    if ((first == last) || (first + 1 == last)) return;
    for (Iterator i = first + 1; i != last; i++)
	(void)linearInsert(first, i, *i);
}

template <class Iterator, class Compare>
void insertionSort(Iterator first, Iterator last, Compare comp)
{
    if ((first == last) || (first + 1 == last)) return;
    for (Iterator i = first + 1; i != last; i++)
	(void)linearInsert(first, i, *i, comp);
}

template <class Iterator>
void binaryInsertionSort(Iterator first, Iterator last)
{
    if ((first == last) || (first + 1 == last)) return;
    for (Iterator i = first + 1; i != last; i++)
	(void)binaryInsert(first, i, *i);
}

template <class Iterator, class Compare>
void binaryInsertionSort(Iterator first, Iterator last, Compare comp)
{
    if ((first == last) || (first + 1 == last)) return;
    for (Iterator i = first + 1; i != last; i++)
	(void)binaryInsert(first, i, comp, *i);
}

#endif