vcl_algorithm.h

DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.

#ifndef vcl_emulation_algorithm_h_
#define vcl_emulation_algorithm_h_
/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 * Exception Handling:
 * Copyright (c) 1997
 * Mark of the Unicorn, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Mark of the Unicorn makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 * Adaptation:
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Moscow Center for SPARC Technology makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

//#include <vcl_cstdlib.h>
//#include <vcl_climits.h>
#include "vcl_algobase.h"
#include "vcl_heap.h"
#include "vcl_tempbuf.h"
#define vcl_remove vcl_remove

template <class T>
inline const T& __median(const T& a, const T& b, const T& c) {
    if (a < b)
        if (b < c)
            return b;
        else if (a < c)
            return c;
        else
            return a;
    else if (a < c)
        return a;
    else if (b < c)
        return c;
    else
        return b;
}

template <class T, class Compare>
inline const T& __median(const T& a, const T& b, const T& c, Compare comp) {
    if (comp(a, b))
        if (comp(b, c))
            return b;
        else if (comp(a, c))
            return c;
        else
            return a;
    else if (comp(a, c))
        return a;
    else if (comp(b, c))
        return c;
    else
        return b;
}

template <class InputIterator, class Function>
inline
Function vcl_for_each(InputIterator first, InputIterator last, Function f) {
    __stl_debug_check(__check_range(first, last));
    for (;first != last;++first) f(*first);
    return f;
}

template <class InputIterator, class T>
inline
InputIterator vcl_find(InputIterator first, InputIterator last, const T& value) {
    __stl_debug_check(__check_range(first, last));
    while (first != last && *first != value) ++first;
    return first;
}

template <class InputIterator, class Predicate>
inline
InputIterator vcl_find_if(InputIterator first, InputIterator last,
                          Predicate pred) {
    __stl_debug_check(__check_range(first, last));
    while (first != last && !pred(*first)) ++first;
    return first;
}

template <class ForwardIterator>
inline
ForwardIterator vcl_adjacent_find(ForwardIterator first, ForwardIterator last) {
    __stl_debug_check(__check_range(first, last));
    if (first == last) return last;
    ForwardIterator next = first;
    while (++next != last) {
        if (*first == *next) return first;
        first = next;
    }
    return last;
}

template <class ForwardIterator, class BinaryPredicate>
inline
ForwardIterator vcl_adjacent_find(ForwardIterator first, ForwardIterator last,
                                  BinaryPredicate binary_pred) {
    __stl_debug_check(__check_range(first, last));
    if (first == last) return last;
    ForwardIterator next = first;
    while (++next != last) {
        if (binary_pred(*first, *next)) return first;
        first = next;
    }
    return last;
}

template <class InputIterator, class T, class Size>
inline
void vcl_count(InputIterator first, InputIterator last, const T& value,
               Size& n) {
    __stl_debug_check(__check_range(first, last));
    for (; first != last; ++first)
        if (*first == value) ++n;
}

template <class InputIterator, class Predicate, class Size>
inline
void vcl_count_if(InputIterator first, InputIterator last, Predicate pred,
                  Size& n) {
    __stl_debug_check(__check_range(first, last));
    for (;first != last;++first)
        if (pred(*first)) ++n;
}

template <class ForwardIterator1, class ForwardIterator2, class Distance1, class Distance2>
inline
ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2,
                          Distance1*, Distance2*) {
    Distance1 d1 = 0;
    vcl_distance(first1, last1, d1);
    Distance2 d2 = 0;
    vcl_distance(first2, last2, d2);

    if (d1 < d2) return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    while (current2 != last2)
        if (*current1++ != *current2++)
            if (d1-- == d2)
                return last1;
            else {
                current1 = ++first1;
                current2 = first2;
            }
    return (current2 == last2) ? first1 : last1;
}

template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1 vcl_search(ForwardIterator1 first1, ForwardIterator1 last1,
                                   ForwardIterator2 first2, ForwardIterator2 last2)
{
    __stl_debug_check(__check_range(first1, last1));
    __stl_debug_check(__check_range(first2, last2));
    return __search(first1, last1, first2, last2, distance_type(first1),
                    distance_type(first2));
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate, class Distance1, class Distance2>
inline
ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2,
                          BinaryPredicate binary_pred, Distance1*, Distance2*) {
    Distance1 d1 = 0;
    vcl_distance(first1, last1, d1);
    Distance2 d2 = 0;
    vcl_distance(first2, last2, d2);

    if (d1 < d2) return last1;

    ForwardIterator1 current1 = first1;
    ForwardIterator2 current2 = first2;

    while (current2 != last2)
        if (!binary_pred(*current1++, *current2++))
            if (d1-- == d2)
                return last1;
            else {
                current1 = ++first1;
                current2 = first2;
            }
    return (current2 == last2) ? first1 : last1;
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
inline ForwardIterator1 vcl_search(ForwardIterator1 first1, ForwardIterator1 last1,
                                   ForwardIterator2 first2, ForwardIterator2 last2,
                                   BinaryPredicate binary_pred) {
    __stl_debug_check(__check_range(first1, last1));
    __stl_debug_check(__check_range(first2, last2));
    return __search(first1, last1, first2, last2, binary_pred,
                    distance_type(first1), distance_type(first2));
}

template <class ForwardIterator1, class ForwardIterator2>
inline
ForwardIterator2 vcl_swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                                 ForwardIterator2 first2) {
    __stl_debug_check(__check_range(first1, last1));
    for (;first1 != last1;++first1,++first2) iter_swap(first1, first2);
    return first2;
}

template <class InputIterator, class OutputIterator, class UnaryOperation>
inline
OutputIterator vcl_transform(InputIterator first, InputIterator last,
                             OutputIterator result, UnaryOperation op) {
    __stl_debug_check(__check_range(first, last));
    for (;first != last;++first,++result) *result = op(*first);
    return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
inline
OutputIterator vcl_transform(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, OutputIterator result,
                             BinaryOperation binary_op) {
    __stl_debug_check(__check_range(first1, last1));
    for (;first1 != last1;++first1,++first2,++result) *result = binary_op(*first1, *first2);
    return result;
}

template <class ForwardIterator, class T>
inline
void vcl_replace(ForwardIterator first, ForwardIterator last, const T& old_value,
                 const T& new_value) {
    __stl_debug_check(__check_range(first, last));
    while (first != last) {
        if (*first == old_value) *first = new_value;
        ++first;
    }
}

template <class ForwardIterator, class Predicate, class T>
inline
void vcl_replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
                    const T& new_value) {
    __stl_debug_check(__check_range(first, last));
    while (first != last) {
        if (pred(*first)) *first = new_value;
        ++first;
    }
}

template <class InputIterator, class OutputIterator, class T>
inline
OutputIterator vcl_replace_copy(InputIterator first, InputIterator last,
                                OutputIterator result, const T& old_value,
                                const T& new_value) {
    __stl_debug_check(__check_range(first, last));
    for (;first != last;++first,++result) {
        *result = *first == old_value ? new_value : *first;
    }
    return result;
}

template <class Iterator, class OutputIterator, class Predicate, class T>
inline
OutputIterator vcl_replace_copy_if(Iterator first, Iterator last,
                                   OutputIterator result, Predicate pred,
                                   const T& new_value) {
    __stl_debug_check(__check_range(first, last));
    for (; first != last; ++first,++result) {
        *result = pred(*first) ? new_value : *first;
    }
    return result;
}

template <class ForwardIterator, class Generator>
inline
void vcl_generate(ForwardIterator first, ForwardIterator last, Generator gen) {
    __stl_debug_check(__check_range(first, last));
    for (; first != last; ++first) *first = gen();
}

template <class OutputIterator, class Size, class Generator>
inline
OutputIterator vcl_generate_n(OutputIterator first, Size n, Generator gen) {
    for (; n > 0; --n, ++first) *first = gen();
    return first;
}

template <class InputIterator, class OutputIterator, class T>
inline
OutputIterator vcl_remove_copy(InputIterator first, InputIterator last,
                               OutputIterator result, const T& value) {
    __stl_debug_check(__check_range(first, last));
    for (; first != last; ++first) {
        if (*first != value)  {
            *result = *first;
            ++result;
        }
    }
    return result;
}

template <class InputIterator, class OutputIterator, class Predicate>
inline
OutputIterator vcl_remove_copy_if(InputIterator first, InputIterator last,
                                  OutputIterator result, Predicate pred) {
    __stl_debug_check(__check_range(first, last));
    for (; first != last; ++first) {
        if (!pred(*first)) {
            *result = *first;
            ++result;
        }
    }
    return result;
}

template <class ForwardIterator, class T>
inline
ForwardIterator vcl_remove(ForwardIterator first, ForwardIterator last, const T& value) {