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