| | | 1 | | // Copyright (c) ZeroC, Inc. |
| | | 2 | | |
| | | 3 | | using System.Diagnostics; |
| | | 4 | | |
| | | 5 | | namespace Ice.UtilInternal; |
| | | 6 | | |
| | | 7 | | public static class Collections |
| | | 8 | | { |
| | | 9 | | public static void Shuffle<T>(ref List<T> l) |
| | | 10 | | { |
| | 1 | 11 | | lock (_rand) |
| | | 12 | | { |
| | 1 | 13 | | for (int j = 0; j < l.Count - 1; ++j) |
| | | 14 | | { |
| | 0 | 15 | | int r = _rand.Next(l.Count - j) + j; |
| | | 16 | | Debug.Assert(r >= j && r < l.Count); |
| | 0 | 17 | | if (r != j) |
| | | 18 | | { |
| | 0 | 19 | | T tmp = l[j]; |
| | 0 | 20 | | l[j] = l[r]; |
| | 0 | 21 | | l[r] = tmp; |
| | | 22 | | } |
| | | 23 | | } |
| | 1 | 24 | | } |
| | 1 | 25 | | } |
| | | 26 | | |
| | | 27 | | internal static void Sort<T>(ref List<T> array, IComparer<T> comparator) => |
| | | 28 | | // |
| | | 29 | | // This Sort method implements the merge sort algorithm |
| | | 30 | | // which is a stable sort (unlike the Sort method of the |
| | | 31 | | // System.Collections.ArrayList which is unstable). |
| | | 32 | | // |
| | 1 | 33 | | Sort1(ref array, 0, array.Count, comparator); |
| | | 34 | | |
| | | 35 | | private static void Sort1<T>(ref List<T> array, int begin, int end, IComparer<T> comparator) |
| | | 36 | | { |
| | | 37 | | int mid; |
| | 1 | 38 | | if (end - begin <= 1) |
| | | 39 | | { |
| | 1 | 40 | | return; |
| | | 41 | | } |
| | | 42 | | |
| | 1 | 43 | | mid = (begin + end) / 2; |
| | 1 | 44 | | Sort1(ref array, begin, mid, comparator); |
| | 1 | 45 | | Sort1(ref array, mid, end, comparator); |
| | 1 | 46 | | Merge(ref array, begin, mid, end, comparator); |
| | 1 | 47 | | } |
| | | 48 | | |
| | | 49 | | private static void Merge<T>(ref List<T> array, int begin, int mid, int end, IComparer<T> comparator) |
| | | 50 | | { |
| | 1 | 51 | | int i = begin; |
| | 1 | 52 | | int j = mid; |
| | 1 | 53 | | int k = 0; |
| | | 54 | | |
| | 1 | 55 | | var tmp = new T[end - begin]; |
| | 1 | 56 | | while (i < mid && j < end) |
| | | 57 | | { |
| | 1 | 58 | | if (comparator.Compare(array[i], array[j]) <= 0) |
| | | 59 | | { |
| | 1 | 60 | | tmp[k++] = array[i++]; |
| | | 61 | | } |
| | | 62 | | else |
| | | 63 | | { |
| | 1 | 64 | | tmp[k++] = array[j++]; |
| | | 65 | | } |
| | | 66 | | } |
| | | 67 | | |
| | 1 | 68 | | while (i < mid) |
| | | 69 | | { |
| | 1 | 70 | | tmp[k++] = array[i++]; |
| | | 71 | | } |
| | 1 | 72 | | while (j < end) |
| | | 73 | | { |
| | 1 | 74 | | tmp[k++] = array[j++]; |
| | | 75 | | } |
| | 1 | 76 | | for (i = 0; i < (end - begin); ++i) |
| | | 77 | | { |
| | 1 | 78 | | array[begin + i] = tmp[i]; |
| | | 79 | | } |
| | 1 | 80 | | } |
| | | 81 | | |
| | 1 | 82 | | private static readonly Random _rand = new(unchecked((int)DateTime.Now.Ticks)); |
| | | 83 | | } |