1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
//
// clr_std/algorithm
//
// Copy of some key Standard Template Library functionality
#ifdef _MSC_VER
#pragma once
#endif
#ifdef USE_STL
#include <algorithm>
#else
#ifndef __clr_std_algorithm_h__
#define __clr_std_algorithm_h__
namespace std
{
template<class iter, class CompareFunc>
iter find_if ( iter first, iter last, CompareFunc comp )
{
for ( ; first!=last ; first++ )
if ( comp(*first) )
break;
return first;
}
template<class iter, class T>
iter find(iter first, iter last, const T& val)
{
for (;first != last; first++)
{
if (*first == val)
break;
}
return first;
}
template <class iter, class comp>
iter qsort_partition( iter first, iter last, iter pivot, comp compare )
{
iter lastMinusOne = last - 1;
swap(pivot, lastMinusOne);
// Pivot is at end
pivot = last - 1;
iter partitionLoc = first;
for (iter partitionWalk = first; partitionWalk != pivot; ++partitionWalk)
{
if (compare(*partitionWalk, *pivot))
{
swap(*partitionWalk, *partitionLoc);
partitionLoc++;
}
}
swap(*pivot, *partitionLoc);
return partitionLoc;
}
template <class iter, class comp>
void sort_worker ( iter first, iter last, comp compare )
{
typename iter::difference_type RangeSize = last - first;
// When down to a list of size 1, be done
if (RangeSize < 2)
return;
// Pick pivot
// Use simple pick middle algorithm
iter pivotLoc = first + (RangeSize / 2);
// Partition
pivotLoc = qsort_partition(first, last, pivotLoc, compare);
// Sort first array
sort_worker(first, pivotLoc, compare);
// Sort second array
sort_worker(pivotLoc + 1, last, compare);
}
template <class iter, class comp>
void sort ( iter first, iter last, comp compare )
{
sort_worker(first, last, compare);
if (first != last)
{
for (iter i = first; i < (last - 1); i++)
{
// Assert that the sort function works.
assert(!compare(*(i+1), *i));
}
}
}
template<class InIter, class OutIter, class Fn1>
OutIter transform( InIter first, InIter last, OutIter dest, Fn1 func )
{
for ( ; first!=last ; ++first, ++dest )
*dest = func(*first);
return dest;
}
} // namespace std
#endif /* __clr_std_algorithm_h__ */
#endif // !USE_STL
// Help the VIM editor figure out what kind of file this no-extension file is.
// vim: filetype=cpp
|
