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