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


#ifndef BINARY_H
#define BINARY_H

#include <stddef.h>
#include "pair.H"

template <class Iterator, class T>
Iterator binaryLess(Iterator first, Iterator last, T a)
{
    size_t len = last - first;
    size_t half;
    Iterator middle;

    while (len > 0) {
        half = len/2;
        middle = first + half;

        if (*middle - a < 0) {
            first = middle + 1;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class Iterator, class T, class Compare>
Iterator binaryLess(Iterator first, Iterator last, T a, Compare comp)
{
    size_t len = last - first;
    size_t half;
    Iterator middle;

    while (len > 0) {
        half = len/2;
        middle = first + half;

        if (comp(*middle, a) < 0) {
            first = middle + 1;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class Iterator, class T>
Iterator binaryNotGreater(Iterator first, Iterator last, T a)
{
    size_t len = last - first;
    size_t half;
    Iterator middle;

    while (len > 0) {
        half = len/2;
        middle = first + half;

        if (a - *middle < 0) {
	    len = half;
	} else {
            first = middle + 1;
            len = len - half - 1;
        }
    }
    return first;
}

template <class Iterator, class T, class Compare>
Iterator binaryNotGreater(Iterator first, Iterator last, T a, Compare comp)
{
    size_t len = last - first;
    size_t half;
    Iterator middle;

    while (len > 0) {
        half = len/2;
        middle = first + half;

        if (comp(*middle, a) > 0) {
	    len = half;
	} else {
            first = middle + 1;
            len = len - half - 1;
        }
    }
    return first;
}

template <class Iterator, class T>
Pair<Iterator, Iterator> binaryEqual(Iterator first, Iterator last, T a)
{
    size_t len = last - first;
    size_t half;
    Iterator middle, left, right;

    while (len > 0) {
        half = len/2;
        middle = first + half;
	int c = *middle - a;
        if (c < 0) {
            first = middle + 1;
            len = len - half - 1;
        } else if (c == 0) {
	    left = binaryLess(first, middle, a);
	    right = binaryNotGreater(middle + 1, first + len, a);
	    return Pair<Iterator, Iterator>(left, right);
	} else
            len = half;
    }
    return Pair<Iterator, Iterator>(first, first);
}

template <class Iterator, class T, class Compare>
Pair<Iterator, Iterator> binaryEqual(Iterator first, Iterator last, 
				     T a, Compare comp)
{
    size_t len = last - first;
    size_t half;
    Iterator middle, left, right;

    while (len > 0) {
        half = len/2;
        middle = first + half;
	int c = comp(*middle, a);
        if (c < 0) {
            first = middle + 1;
            len = len - half - 1;
        } else if (c == 0) {
	    left = binaryLess(first, middle, a, comp);
	    right = binaryNotGreater(middle + 1, first + len, a, comp);
	    return Pair<Iterator, Iterator>(left, right);
	} else
            len = half;
    }
    return Pair<Iterator, Iterator>(first, first);
}

#endif