vcl_algorithm.h

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

            return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
            (first, last, T(__median(*first, *(first + (last - first)/2),
                                     *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
    }
}

template <class RandomAccessIterator, class T, class Size, class Compare>
inline
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit, Compare comp) {
    while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            vcl_partial_sort(first, last, last, comp);
            return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
            (first, last, T(__median(*first, *(first + (last - first)/2),
                                     *(last - 1), comp)), comp);
        __introsort_loop(cut, last, value_type(first), depth_limit, comp);
        last = cut;
    }
}

template <class RandomAccessIterator>
inline void vcl_sort(RandomAccessIterator first, RandomAccessIterator last) {
    __stl_debug_check(__check_range(first, last));
    if (first==last) return;
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
    __final_insertion_sort(first, last);
}

template <class RandomAccessIterator, class Compare>
inline void vcl_sort(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __stl_debug_check(__check_range(first, last));
    if (first == last) return;
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2, comp);
    __final_insertion_sort(first, last, comp);
}


template <class RandomAccessIterator>
inline
void __inplace_stable_sort(RandomAccessIterator first,
                           RandomAccessIterator last) {
    if (last - first < 15) {
        __insertion_sort(first, last);
        return;
    }
    RandomAccessIterator middle = first + (last - first) / 2;
    __inplace_stable_sort(first, middle);
    __inplace_stable_sort(middle, last);
    __merge_without_buffer(first, middle, last, middle - first, last - middle);
}

template <class RandomAccessIterator, class Compare>
inline
void __inplace_stable_sort(RandomAccessIterator first,
                           RandomAccessIterator last, Compare comp) {
    if (last - first < 15) {
        __insertion_sort(first, last, comp);
        return;
    }
    RandomAccessIterator middle = first + (last - first) / 2;
    __inplace_stable_sort(first, middle, comp);
    __inplace_stable_sort(middle, last, comp);
    __merge_without_buffer(first, middle, last, middle - first,
                           last - middle, comp);
}

template <class RandomAccessIterator1, class RandomAccessIterator2, class Distance>
inline
void __merge_sort_loop(RandomAccessIterator1 first,
                       RandomAccessIterator1 last,
                       RandomAccessIterator2 result, Distance step_size) {
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = merge(first, first + step_size,
                       first + step_size, first + two_step, result);
        first += two_step;
    }
    Distance len(last-first); // VC++ temporary ref warning
    step_size = vcl_min(len, step_size);
    merge(first, first + step_size, first + step_size, last, result);
}

template <class RandomAccessIterator1, class RandomAccessIterator2, class Distance, class Compare>
inline
void __merge_sort_loop(RandomAccessIterator1 first,
                       RandomAccessIterator1 last,
                       RandomAccessIterator2 result, Distance step_size,
                       Compare comp) {
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
        result = merge(first, first + step_size,
                       first + step_size, first + two_step, result, comp);
        first += two_step;
    }
    Distance len(last-first); // VC++ temporary ref warning
    step_size = vcl_min(len, step_size);

    merge(first, first + step_size, first + step_size, last, result, comp);
}

const int __stl_chunk_size = 7;

template <class RandomAccessIterator, class Distance>
inline
void __chunk_insertion_sort(RandomAccessIterator first,
                            RandomAccessIterator last, Distance chunk_size) {
    while (last - first >= chunk_size) {
        __insertion_sort(first, first + chunk_size);
        first += chunk_size;
    }
    __insertion_sort(first, last);
}

template <class RandomAccessIterator, class Distance, class Compare>
inline
void __chunk_insertion_sort(RandomAccessIterator first,
                            RandomAccessIterator last,
                            Distance chunk_size, Compare comp) {
    while (last - first >= chunk_size) {
        __insertion_sort(first, first + chunk_size, comp);
        first += chunk_size;
    }
    __insertion_sort(first, last, comp);
}

template <class RandomAccessIterator, class Distance, class T>
inline
void __merge_sort_with_buffer(RandomAccessIterator first,
                              RandomAccessIterator last,
                              __stl_tempbuf<T, Distance>& buffer) {
    typedef typename  __stl_tempbuf<T,Distance>::pointer Pointer;
    Distance len = last - first;
    Pointer buffer_last = buffer.begin() + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size);

    while (step_size < len) {
        __merge_sort_loop(first, last, buffer.begin(), step_size);
        step_size *= 2;
        __merge_sort_loop(buffer.begin(), buffer_last, first, step_size);
        step_size *= 2;
    }
}


template <class RandomAccessIterator, class Distance, class T, class Compare>
inline
void __merge_sort_with_buffer(RandomAccessIterator first,
                              RandomAccessIterator last,
                              __stl_tempbuf<T, Distance>& buffer,
                              Compare comp) {
    typedef typename  __stl_tempbuf<T,Distance>::pointer Pointer;
    Distance len = last - first;
    Pointer buffer_last = buffer.begin() + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size, comp);

    while (step_size < len) {
        __merge_sort_loop(first, last, buffer.begin(), step_size, comp);
        step_size *= 2;
        __merge_sort_loop(buffer.begin(), buffer_last, first, step_size, comp);
        step_size *= 2;
    }
}

template <class RandomAccessIterator, class Distance, class T>
inline
void __stable_sort_adaptive(RandomAccessIterator first,
                            RandomAccessIterator last,
                            __stl_tempbuf<T,Distance>& buffer) {
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer.capacity()) {
        __stable_sort_adaptive(first, middle, buffer);
        __stable_sort_adaptive(middle, last, buffer);
    } else {
        __merge_sort_with_buffer(first, middle, buffer);
        __merge_sort_with_buffer(middle, last, buffer);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first),
                     Distance(last - middle), buffer);
}

template <class RandomAccessIterator, class Distance, class T, class Compare>
inline
void __stable_sort_adaptive(RandomAccessIterator first,
                            RandomAccessIterator last,
                            __stl_tempbuf<T,Distance>& buffer,
                            Compare comp) {
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer.capacity()) {
        __stable_sort_adaptive(first, middle, buffer, comp);
        __stable_sort_adaptive(middle, last, buffer, comp);
    } else {
        __merge_sort_with_buffer(first, middle, buffer, comp);
        __merge_sort_with_buffer(middle, last, buffer, comp);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first),
                     Distance(last - middle), buffer, comp);
}

template <class RandomAccessIterator, class Distance, class T>
inline void __stable_sort(RandomAccessIterator first,
                          RandomAccessIterator last,
                          __stl_tempbuf<T,Distance>& buffer) {
    if (buffer.capacity() == 0) {
        __inplace_stable_sort(first, last);
    }
    else {
        Distance len(last-first); // VC++ temporary ref warning
        len = vcl_min(buffer.capacity(), len);
        vcl_uninitialized_copy(first, first + len, buffer.begin());
        buffer.adjust_size(len);
        __stable_sort_adaptive(first, last, buffer);
    }
}

template <class RandomAccessIterator, class Distance, class T, class Compare>
inline void __stable_sort(RandomAccessIterator first,
                          RandomAccessIterator last,
                          __stl_tempbuf<T,Distance>& buffer, Compare comp) {
    if (buffer.capacity() == 0) {
        __inplace_stable_sort(first, last, comp);
    }
    else {
        Distance len(last-first); // VC++ temporary ref warning
        len = vcl_min(buffer.capacity(), len);
        vcl_uninitialized_copy(first, first + len, buffer.begin());
        buffer.adjust_size(len);
        __stable_sort_adaptive(first, last, buffer, comp);
    }
}

template <class RandomAccessIterator, class T, class Distance>
inline void __stable_sort_aux(RandomAccessIterator first,
                              RandomAccessIterator last, T*, Distance*) {
    __stl_tempbuf<T,Distance> buffer(Distance(last - first));
    __stable_sort(first, last, buffer);
}

template <class RandomAccessIterator, class T, class Distance, class Compare>
inline void __stable_sort_aux(RandomAccessIterator first,
                              RandomAccessIterator last, T*, Distance*,
                              Compare comp) {
    __stl_tempbuf<T,Distance> buffer(Distance(last - first));
    __stable_sort(first, last, buffer,comp);
}

template <class RandomAccessIterator>
inline void vcl_stable_sort(RandomAccessIterator first,
                            RandomAccessIterator last) {
    __stl_debug_check(__check_range(first, last));
    __stable_sort_aux(first, last, value_type(first), distance_type(first));
}

template <class RandomAccessIterator, class Compare>
inline void vcl_stable_sort(RandomAccessIterator first,
                            RandomAccessIterator last, Compare comp) {
    __stl_debug_check(__check_range(first, last));
    __stable_sort_aux(first, last, value_type(first), distance_type(first),
                      comp);
}

template <class RandomAccessIterator, class T>
inline
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*) {
    vcl_make_heap(first, middle);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (*i < *first)
            __pop_heap(first, middle, i, T(*i), distance_type(first));
    sort_heap(first, middle);
}

template <class RandomAccessIterator>
inline void vcl_partial_sort(RandomAccessIterator first,
                             RandomAccessIterator middle,
                             RandomAccessIterator last) {
    __stl_debug_check(__check_range(middle,first, last));
    __partial_sort(first, middle, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
inline
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
    vcl_make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void vcl_partial_sort(RandomAccessIterator first,
                             RandomAccessIterator middle,
                             RandomAccessIterator last, Compare comp) {
    __stl_debug_check(__check_range(middle,first, last));
    __partial_sort(first, middle, last, value_type(first), comp);
}

template <class InputIterator, class RandomAccessIterator, class Distance, class T>
inline
RandomAccessIterator __partial_sort_copy(InputIterator first,
                                         InputIterator last,
                                         RandomAccessIterator result_first,
                                         RandomAccessIterator result_last,
                                         Distance*, T*) {
    if (result_first == result_last) return result_last;
    RandomAccessIterator result_real_last = result_first;
    for (; first != last && result_real_last != result_last; ++result_real_last,++first)
        *result_real_last = *first;
    vcl_make_heap(result_first, result_real_last);
    while (first != last) {
        if (*first < *result_first)
            __adjust_heap(result_first, Distance(0),
                          Distance(result_real_last - result_first), T(*first));
        ++first;
    }
    vcl_sort_heap(result_first, result_real_last);
    return result_real_last;
}

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
vcl_partial_sort_copy(InputIterator first, InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last) {
    __stl_debug_check(__check_range(first, last));
    __stl_debug_check(__check_range(result_first, result_last));
    return __partial_sort_copy(first, last, result_first, result_last,
                               distance_type(result_first), value_type(first));
}

template <class InputIterator, class RandomAccessIterator, class Compare, class Distance, class T>
inline
RandomAccessIterator __partial_sort_copy(InputIterator first,
                                         InputIterator last,
                                         RandomAccessIterator result_first,