1 // 2 // Copyright (c) ZeroC, Inc. All rights reserved. 3 // 4 5 using System.Collections; 6 using System.Collections.Generic; 7 using System.Diagnostics; 8 9 namespace IceUtilInternal 10 { 11 public sealed class Collections 12 { SequenceEquals(ICollection seq1, ICollection seq2)13 public static bool SequenceEquals(ICollection seq1, ICollection seq2) 14 { 15 if(ReferenceEquals(seq1, seq2)) 16 { 17 return true; 18 } 19 20 if((seq1 == null && seq2 != null) || (seq1 != null && seq2 == null)) 21 { 22 return false; 23 } 24 25 if(seq1.Count == seq2.Count) 26 { 27 IEnumerator e1 = seq1.GetEnumerator(); 28 IEnumerator e2 = seq2.GetEnumerator(); 29 while(e1.MoveNext()) 30 { 31 e2.MoveNext(); 32 if(e1.Current == null) 33 { 34 if(e2.Current != null) 35 { 36 return false; 37 } 38 } 39 else if(!e1.Current.Equals(e2.Current)) 40 { 41 return false; 42 } 43 } 44 45 return true; 46 } 47 48 return false; 49 } 50 SequenceEquals(IEnumerable seq1, IEnumerable seq2)51 public static bool SequenceEquals(IEnumerable seq1, IEnumerable seq2) 52 { 53 if(ReferenceEquals(seq1, seq2)) 54 { 55 return true; 56 } 57 58 if((seq1 == null && seq2 != null) || (seq1 != null && seq2 == null)) 59 { 60 return false; 61 } 62 63 IEnumerator e1 = seq1.GetEnumerator(); 64 IEnumerator e2 = seq2.GetEnumerator(); 65 while(e1.MoveNext()) 66 { 67 if(!e2.MoveNext()) 68 { 69 return false; 70 } 71 if(e1.Current == null) 72 { 73 if(e2.Current != null) 74 { 75 return false; 76 } 77 } 78 else if(!e1.Current.Equals(e2.Current)) 79 { 80 return false; 81 } 82 } 83 84 if(e2.MoveNext()) 85 { 86 return false; 87 } 88 89 return true; 90 } 91 SequenceGetHashCode(IEnumerable seq)92 public static int SequenceGetHashCode(IEnumerable seq) 93 { 94 int h = 5381; 95 IEnumerator e = seq.GetEnumerator(); 96 while(e.MoveNext()) 97 { 98 IceInternal.HashUtil.hashAdd(ref h, e.Current); 99 } 100 return h; 101 } 102 DictionaryEquals(IDictionary d1, IDictionary d2)103 public static bool DictionaryEquals(IDictionary d1, IDictionary d2) 104 { 105 if(ReferenceEquals(d1, d2)) 106 { 107 return true; 108 } 109 110 if((d1 == null && d2 != null) || (d1 != null && d2 == null)) 111 { 112 return false; 113 } 114 115 if(d1.Count == d2.Count) 116 { 117 IDictionaryEnumerator e1 = d1.GetEnumerator(); 118 IDictionaryEnumerator e2 = d2.GetEnumerator(); 119 while(e1.MoveNext()) 120 { 121 e2.MoveNext(); 122 if(!e1.Key.Equals(e2.Key)) 123 { 124 return false; 125 } 126 if(e1.Value == null) 127 { 128 if(e2.Value != null) 129 { 130 return false; 131 } 132 } 133 else if(!e1.Value.Equals(e2.Value)) 134 { 135 return false; 136 } 137 } 138 139 return true; 140 } 141 142 return false; 143 } 144 DictionaryGetHashCode(IDictionary d)145 public static int DictionaryGetHashCode(IDictionary d) 146 { 147 int h = 5381; 148 IDictionaryEnumerator e = d.GetEnumerator(); 149 while(e.MoveNext()) 150 { 151 IceInternal.HashUtil.hashAdd(ref h, e.Key); 152 IceInternal.HashUtil.hashAdd(ref h, e.Value); 153 } 154 return h; 155 } 156 Shuffle(ref List<T> l)157 public static void Shuffle<T>(ref List<T> l) 158 { 159 lock(_rand) 160 { 161 for(int j = 0; j < l.Count - 1; ++j) 162 { 163 int r = _rand.Next(l.Count - j) + j; 164 Debug.Assert(r >= j && r < l.Count); 165 if(r != j) 166 { 167 T tmp = l[j]; 168 l[j] = l[r]; 169 l[r] = tmp; 170 } 171 } 172 } 173 } 174 Sort(ref List<T> array, IComparer<T> comparator)175 public static void Sort<T>(ref List<T> array, IComparer<T> comparator) 176 { 177 // 178 // This Sort method implements the merge sort algorithm 179 // which is a stable sort (unlike the Sort method of the 180 // System.Collections.ArrayList which is unstable). 181 // 182 Sort1(ref array, 0, array.Count, comparator); 183 } 184 Sort1(ref List<T> array, int begin, int end, IComparer<T> comparator)185 private static void Sort1<T>(ref List<T> array, int begin, int end, IComparer<T> comparator) 186 { 187 int mid; 188 if(end - begin <= 1) 189 { 190 return; 191 } 192 193 mid = (begin + end) / 2; 194 Sort1(ref array, begin, mid, comparator); 195 Sort1(ref array, mid, end, comparator); 196 Merge(ref array, begin, mid, end, comparator); 197 } 198 Merge(ref List<T> array, int begin, int mid, int end, IComparer<T> comparator)199 private static void Merge<T>(ref List<T> array, int begin, int mid, int end, IComparer<T> comparator) 200 { 201 int i = begin; 202 int j = mid; 203 int k = 0; 204 205 T[] tmp = new T[end - begin]; 206 while(i < mid && j < end) 207 { 208 if(comparator.Compare(array[i], array[j]) <= 0) 209 { 210 tmp[k++] = array[i++]; 211 } 212 else 213 { 214 tmp[k++] = array[j++]; 215 } 216 } 217 218 while(i < mid) 219 { 220 tmp[k++] = array[i++]; 221 } 222 while(j < end) 223 { 224 tmp[k++] = array[j++]; 225 } 226 for(i = 0; i < (end - begin); ++i) 227 { 228 array[begin + i] = tmp[i]; 229 } 230 } 231 232 private static System.Random _rand = new System.Random(unchecked((int)System.DateTime.Now.Ticks)); 233 } 234 } 235