vcl_algorithm.h

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

        Distance M = __rand() % t;
        if (M < n)
            out[M] = *first;
        ++first;
    }

    return out + m;
}

template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator, class Distance>
inline
RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
                                     RandomAccessIterator out,
                                     RandomNumberGenerator& rand,
                                     const Distance n)
{
    Distance m = 0;
    Distance t = n;
    for (; first != last && m < n; ++m,++first)
        out[m] = *first;

    while (first != last) {
        ++t;
        Distance M = rand(t);
        if (M < n)
            out[M] = *first;
        ++first;
    }

    return out + m;
}

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
vcl_random_sample(InputIterator first, InputIterator last,
                  RandomAccessIterator out_first, RandomAccessIterator out_last)
{
    __stl_debug_check(__check_range(first, last));
    return __random_sample(first, last, out_first, out_last - out_first);
}

template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator>
inline RandomAccessIterator
vcl_random_sample(InputIterator first, InputIterator last,
                  RandomAccessIterator out_first, RandomAccessIterator out_last,
                  RandomNumberGenerator& rand)
{
    __stl_debug_check(__check_range(first, last));
    return __random_sample(first, last, out_first, rand, out_last - out_first);
}

template <class BidirectionalIterator, class Predicate>
inline
BidirectionalIterator vcl_partition(BidirectionalIterator first,
                                    BidirectionalIterator last, Predicate pred) {
    __stl_debug_check(__check_range(first, last));
    while (true) {
        while (true)
            if (first == last)
                return first;
            else if (pred(*first))
                ++first;
            else
                break;
        --last;
        while (true)
            if (first == last)
                return first;
            else if (!pred(*last))
                --last;
            else
                break;
        iter_swap(first, last);
        ++first;
    }
}

template <class ForwardIterator, class Predicate, class Distance>
inline
ForwardIterator __inplace_stable_partition(ForwardIterator first,
                                           ForwardIterator last,
                                           Predicate pred, Distance len) {
    if (len == 1) return pred(*first) ? last : first;
    ForwardIterator middle = first;
    vcl_advance(middle, len / 2);
    ForwardIterator
        first_cut = __inplace_stable_partition(first, middle, pred, len / 2);
    ForwardIterator
        second_cut = __inplace_stable_partition(middle, last, pred,
                                                len - len / 2);
    rotate(first_cut, middle, second_cut);
    len = 0;
    vcl_distance(middle, second_cut, len);
    vcl_advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Predicate, class Distance, class T>
inline
ForwardIterator __stable_partition_adaptive(ForwardIterator first,
                                            ForwardIterator last,
                                            Predicate pred, Distance len,
                                            __stl_tempbuf<T,Distance>& buffer) {
    typedef typename  __stl_tempbuf<T,Distance>::pointer Pointer;
    Distance fill_pointer = buffer.size();
    if (len <= buffer.capacity()) {
        len = 0;
        ForwardIterator result1 = first;
        Pointer result2 = buffer.begin();
        for (; first != last && len < fill_pointer; ++first)
            if (pred(*first)) {
                *result1 = *first;
                ++result1;
            }
            else {
                *result2++ = *first;
                ++len;
            }
        if (first != last) {
            raw_storage_iterator<Pointer, T> result3(result2);
            IUEg__TRY {
                for (; first != last; ++first)
                    if (pred(*first)) {
                        *result1 = *first;
                        ++result1;
                    }
                    else {
                        *result3 = *first;
                        ++len;
                        ++result3;
                    }
            }
#  if defined ( __STL_USE_EXCEPTIONS )
            catch(...) {
                buffer.adjust_size(len);
                throw;
            }
#  endif
            buffer.adjust_size(len);
        }
        vcl_copy(buffer.begin(), buffer.begin() + len, result1);
        return result1;
    }
    ForwardIterator middle = first;
    vcl_advance(middle, len / 2);
    ForwardIterator first_cut = __stable_partition_adaptive
        (first, middle, pred, len / 2, buffer);
    ForwardIterator second_cut = __stable_partition_adaptive
        (middle, last, pred, len - len / 2, buffer);
    vcl_rotate(first_cut, middle, second_cut);
    len = 0;
    vcl_distance(middle, second_cut, len);
    vcl_advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Predicate, class T, class Distance>
inline
ForwardIterator __stable_partition(ForwardIterator first, ForwardIterator last,
                                   Predicate pred, Distance len,
                                   __stl_tempbuf<T, Distance>& buffer) {
    if ( buffer.capacity() >0 )
       return __stable_partition_adaptive(first, last, pred, len, buffer);
    else
       return __inplace_stable_partition(first, last, pred, len);
}

template <class ForwardIterator, class Predicate, class Distance, class T>
inline ForwardIterator __stable_partition_aux(ForwardIterator first,
                                              ForwardIterator last,
                                              Predicate pred, Distance*, T*) {
    Distance len = 0;
    vcl_distance(first, last, len);
    __stl_tempbuf<T,Distance> buf(len);
    return __stable_partition(first, last, pred, len, buf);
}

template <class ForwardIterator, class Predicate>
inline ForwardIterator stable_partition(ForwardIterator first,
                                        ForwardIterator last,
                                        Predicate pred) {
    __stl_debug_check(__check_range(first, last));
    return __stable_partition_aux(first, last, pred, distance_type(first),value_type(first));
}

template <class RandomAccessIterator, class T>
inline
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
                                           RandomAccessIterator last,
                                           T pivot) {
    while (1) {
        while (*first < pivot) {
            ++first;
        }
        --last;
        while (pivot < *last) --last;
        if (!(first < last)) {
            return first;
        }
        iter_swap(first, last);
        ++first;
    }
}

template <class RandomAccessIterator, class T, class Compare>
inline
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
                                           RandomAccessIterator last,
                                           T pivot, Compare comp) {
    while (1) {
        while (comp(*first, pivot)) ++first;
        --last;
        while (comp(pivot, *last)) --last;
        if (!(first < last)) return first;
        iter_swap(first, last);
        ++first;
    }
}

# define  __stl_threshold  16

template <class RandomAccessIterator, class T>
inline
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}

template <class RandomAccessIterator, class T, class Compare>
inline
void __unguarded_linear_insert(RandomAccessIterator last, T value,
                               Compare comp) {
    RandomAccessIterator next = last;
    --next;
    while (comp(value , *next)) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
                            RandomAccessIterator last, T*) {
    T value = *last;
    if (value < *first) {
        vcl_copy_backward(first, last, last + 1);
        *first = value;
    } else
        __unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator, class T, class Compare>
inline void __linear_insert(RandomAccessIterator first,
                            RandomAccessIterator last, T*, Compare comp) {
    T value = *last;
    if (comp(value, *first)) {
        vcl_copy_backward(first, last, last + 1);
        *first = value;
    } else
        __unguarded_linear_insert(last, value, comp);
}

template <class RandomAccessIterator>
inline
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first));
}

template <class RandomAccessIterator, class Compare>
inline
void __insertion_sort(RandomAccessIterator first,
                      RandomAccessIterator last, Compare comp) {
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first), comp);
}

template <class RandomAccessIterator, class T>
inline
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
                                    RandomAccessIterator last, T*) {
    for (RandomAccessIterator i = first; i != last; ++i)
        __unguarded_linear_insert(i, T(*i));
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
                                       RandomAccessIterator last) {
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
inline
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
                                    RandomAccessIterator last,
                                    T*, Compare comp) {
    for (RandomAccessIterator i = first; i != last; ++i)
        __unguarded_linear_insert(i, T(*i), comp);
}

template <class RandomAccessIterator, class Compare>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
                                       RandomAccessIterator last,
                                       Compare comp) {
    __unguarded_insertion_sort_aux(first, last, value_type(first), comp);
}

template <class RandomAccessIterator>
inline
void __final_insertion_sort(RandomAccessIterator first,
                            RandomAccessIterator last) {
    if (last - first > __stl_threshold) {
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    } else
        __insertion_sort(first, last);
}

template <class RandomAccessIterator, class Compare>
inline
void __final_insertion_sort(RandomAccessIterator first,
                            RandomAccessIterator last, Compare comp) {
    if (last - first > __stl_threshold) {
        __insertion_sort(first, first + __stl_threshold, comp);
        __unguarded_insertion_sort(first + __stl_threshold, last, comp);
    } else
        __insertion_sort(first, last, comp);
}

template <class Size>
inline
Size __lg(Size n) {
    Size k;
    for (k = 0; n != 1; n = n / 2) ++k;
    return k;
}

template <class RandomAccessIterator, class T, class Size>
inline
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
    while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            vcl_partial_sort(first, last, last);