5 // Joe Shaw (joe@ximian.com)
6 // Martin Baulig (martin@gnome.org)
7 // Dietmar Maurer (dietmar@ximian.com)
8 // Gonzalo Paniagua Javier (gonzalo@ximian.com)
10 // (C) 2001-2003 Ximian, Inc. http://www.ximian.com
11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 using System
.Collections
;
34 using System
.Runtime
.CompilerServices
;
35 using System
.Runtime
.InteropServices
;
37 using System
.Collections
.Generic
;
38 using System
.Collections
.ObjectModel
;
39 using System
.Runtime
.ConstrainedExecution
;
40 using System
.Reflection
.Emit
;
46 // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
47 public abstract class Array
: ICloneable
, ICollection
, IList
, IEnumerable
49 , IStructuralComparable
, IStructuralEquatable
58 * These methods are used to implement the implicit generic interfaces
59 * implemented by arrays in NET 2.0.
60 * Only make those methods generic which really need it, to avoid
61 * creating useless instantiations.
63 internal int InternalArray__ICollection_get_Count ()
68 internal bool InternalArray__ICollection_get_IsReadOnly ()
73 internal IEnumerator
<T
> InternalArray__IEnumerable_GetEnumerator
<T
> ()
75 return new InternalEnumerator
<T
> (this);
78 internal void InternalArray__ICollection_Clear ()
80 throw new NotSupportedException ("Collection is read-only");
83 internal void InternalArray__ICollection_Add
<T
> (T item
)
85 throw new NotSupportedException ("Collection is read-only");
88 internal bool InternalArray__ICollection_Remove
<T
> (T item
)
90 throw new NotSupportedException ("Collection is read-only");
93 internal bool InternalArray__ICollection_Contains
<T
> (T item
)
96 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
98 int length
= this.Length
;
99 for (int i
= 0; i
< length
; i
++) {
101 GetGenericValueImpl (i
, out value);
109 if (item
.Equals (value))
116 internal void InternalArray__ICollection_CopyTo
<T
> (T
[] array
, int index
)
119 throw new ArgumentNullException ("array");
121 // The order of these exception checks may look strange,
122 // but that's how the microsoft runtime does it.
124 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
125 if (index
+ this.GetLength (0) > array
.GetLowerBound (0) + array
.GetLength (0))
126 throw new ArgumentException ("Destination array was not long " +
127 "enough. Check destIndex and length, and the array's " +
130 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
132 throw new ArgumentOutOfRangeException (
133 "index", Locale
.GetText ("Value has to be >= 0."));
135 Copy (this, this.GetLowerBound (0), array
, index
, this.GetLength (0));
138 internal void InternalArray__Insert
<T
> (int index
, T item
)
140 throw new NotSupportedException ("Collection is read-only");
143 internal void InternalArray__RemoveAt (int index
)
145 throw new NotSupportedException ("Collection is read-only");
148 internal int InternalArray__IndexOf
<T
> (T item
)
151 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
153 int length
= this.Length
;
154 for (int i
= 0; i
< length
; i
++) {
156 GetGenericValueImpl (i
, out value);
159 return i
+ this.GetLowerBound (0);
162 return this.GetLowerBound (0) - 1;
166 if (value.Equals (item
))
167 // array index may not be zero-based.
169 return i
+ this.GetLowerBound (0);
173 // lower bound may be MinValue
174 return this.GetLowerBound (0) - 1;
178 internal T InternalArray__get_Item
<T
> (int index
)
180 if (unchecked ((uint) index
) >= unchecked ((uint) Length
))
181 throw new ArgumentOutOfRangeException ("index");
184 GetGenericValueImpl (index
, out value);
188 internal void InternalArray__set_Item
<T
> (int index
, T item
)
190 if (unchecked ((uint) index
) >= unchecked ((uint) Length
))
191 throw new ArgumentOutOfRangeException ("index");
193 object[] oarray
= this as object [];
194 if (oarray
!= null) {
195 oarray
[index
] = (object)item
;
198 SetGenericValueImpl (index
, ref item
);
201 // CAUTION! No bounds checking!
202 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
203 internal extern void GetGenericValueImpl
<T
> (int pos
, out T
value);
205 // CAUTION! No bounds checking!
206 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
207 internal extern void SetGenericValueImpl
<T
> (int pos
, ref T
value);
209 internal struct InternalEnumerator
<T
> : IEnumerator
<T
>
211 const int NOT_STARTED
= -2;
213 // this MUST be -1, because we depend on it in move next.
214 // we just decr the size, so, 0 - 1 == FINISHED
215 const int FINISHED
= -1;
220 internal InternalEnumerator (Array array
)
226 public void Dispose ()
231 public bool MoveNext ()
233 if (idx
== NOT_STARTED
)
236 return idx
!= FINISHED
&& -- idx
!= FINISHED
;
241 if (idx
== NOT_STARTED
)
242 throw new InvalidOperationException ("Enumeration has not started. Call MoveNext");
244 throw new InvalidOperationException ("Enumeration already finished");
246 return array
.InternalArray__get_Item
<T
> (array
.Length
- 1 - idx
);
250 void IEnumerator
.Reset ()
255 object IEnumerator
.Current
{
264 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
266 int length
= this.GetLength (0);
268 for (int i
= 1; i
< this.Rank
; i
++) {
269 length
*= this.GetLength (i
);
276 public long LongLength
{
277 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
278 get { return Length; }
282 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
284 return this.GetRank ();
289 object IList
.this [int index
] {
291 if (unchecked ((uint) index
) >= unchecked ((uint) Length
))
292 throw new IndexOutOfRangeException ("index");
294 throw new ArgumentException (Locale
.GetText ("Only single dimension arrays are supported."));
295 return GetValueImpl (index
);
298 if (unchecked ((uint) index
) >= unchecked ((uint) Length
))
299 throw new IndexOutOfRangeException ("index");
301 throw new ArgumentException (Locale
.GetText ("Only single dimension arrays are supported."));
302 SetValueImpl (value, index
);
306 int IList
.Add (object value)
308 throw new NotSupportedException ();
313 Array
.Clear (this, this.GetLowerBound (0), this.Length
);
316 bool IList
.Contains (object value)
319 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
321 int length
= this.Length
;
322 for (int i
= 0; i
< length
; i
++) {
323 if (Object
.Equals (this.GetValueImpl (i
), value))
329 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
330 int IList
.IndexOf (object value)
333 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
335 int length
= this.Length
;
336 for (int i
= 0; i
< length
; i
++) {
337 if (Object
.Equals (this.GetValueImpl (i
), value))
338 // array index may not be zero-based.
340 return i
+ this.GetLowerBound (0);
344 // lower bound may be MinValue
345 return this.GetLowerBound (0) - 1;
349 void IList
.Insert (int index
, object value)
351 throw new NotSupportedException ();
354 void IList
.Remove (object value)
356 throw new NotSupportedException ();
359 void IList
.RemoveAt (int index
)
361 throw new NotSupportedException ();
364 // InternalCall Methods
365 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
366 extern int GetRank ();
368 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
369 public extern int GetLength (int dimension
);
372 public long GetLongLength (int dimension
)
374 return GetLength (dimension
);
377 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
378 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
379 public extern int GetLowerBound (int dimension
);
381 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
382 public extern object GetValue (params int[] indices
);
384 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
385 public extern void SetValue (object value, params int[] indices
);
387 // CAUTION! No bounds checking!
388 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
389 internal extern object GetValueImpl (int pos
);
391 // CAUTION! No bounds checking!
392 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
393 internal extern void SetValueImpl (object value, int pos
);
395 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
396 internal extern static bool FastCopy (Array source
, int source_idx
, Array dest
, int dest_idx
, int length
);
398 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
399 internal extern static Array
CreateInstanceImpl (Type elementType
, int[] lengths
, int[] bounds
);
402 int ICollection
.Count
{
408 public bool IsSynchronized
{
414 public object SyncRoot
{
420 public bool IsFixedSize
{
426 public bool IsReadOnly
{
432 public IEnumerator
GetEnumerator ()
434 return new SimpleEnumerator (this);
438 int IStructuralComparable
.CompareTo (object other
, IComparer comparer
)
443 Array arr
= other
as Array
;
445 throw new ArgumentException ("Not an array", "other");
447 int len
= GetLength (0);
448 if (len
!= arr
.GetLength (0))
449 throw new ArgumentException ("Not of the same length", "other");
452 throw new ArgumentException ("Array must be single dimensional");
455 throw new ArgumentException ("Array must be single dimensional", "other");
457 for (int i
= 0; i
< len
; ++i
) {
458 object a
= GetValue (i
);
459 object b
= arr
.GetValue (i
);
460 int r
= comparer
.Compare (a
, b
);
467 bool IStructuralEquatable
.Equals (object other
, IEqualityComparer comparer
)
469 Array o
= other
as Array
;
470 if (o
== null || o
.Length
!= Length
)
473 if (Object
.ReferenceEquals (other
, this))
476 for (int i
= 0; i
< Length
; i
++) {
477 object this_item
= this.GetValue (i
);
478 object other_item
= o
.GetValue (i
);
479 if (!comparer
.Equals (this_item
, other_item
))
486 int IStructuralEquatable
.GetHashCode (IEqualityComparer comparer
)
488 if (comparer
== null)
489 throw new ArgumentNullException ("comparer");
492 for (int i
= 0; i
< Length
; i
++)
493 hash
= ((hash
<< 7) + hash
) ^
GetValue (i
).GetHashCode ();
498 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
499 public int GetUpperBound (int dimension
)
501 return GetLowerBound (dimension
) + GetLength (dimension
) - 1;
504 public object GetValue (int index
)
507 throw new ArgumentException (Locale
.GetText ("Array was not a one-dimensional array."));
508 if (index
< GetLowerBound (0) || index
> GetUpperBound (0))
509 throw new IndexOutOfRangeException (Locale
.GetText (
510 "Index has to be between upper and lower bound of the array."));
512 return GetValueImpl (index
- GetLowerBound (0));
515 public object GetValue (int index1
, int index2
)
517 int[] ind
= {index1, index2}
;
518 return GetValue (ind
);
521 public object GetValue (int index1
, int index2
, int index3
)
523 int[] ind
= {index1, index2, index3}
;
524 return GetValue (ind
);
528 public object GetValue (long index
)
530 if (index
< 0 || index
> Int32
.MaxValue
)
531 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
532 "Value must be >= 0 and <= Int32.MaxValue."));
534 return GetValue ((int) index
);
538 public object GetValue (long index1
, long index2
)
540 if (index1
< 0 || index1
> Int32
.MaxValue
)
541 throw new ArgumentOutOfRangeException ("index1", Locale
.GetText (
542 "Value must be >= 0 and <= Int32.MaxValue."));
544 if (index2
< 0 || index2
> Int32
.MaxValue
)
545 throw new ArgumentOutOfRangeException ("index2", Locale
.GetText (
546 "Value must be >= 0 and <= Int32.MaxValue."));
548 return GetValue ((int) index1
, (int) index2
);
552 public object GetValue (long index1
, long index2
, long index3
)
554 if (index1
< 0 || index1
> Int32
.MaxValue
)
555 throw new ArgumentOutOfRangeException ("index1", Locale
.GetText (
556 "Value must be >= 0 and <= Int32.MaxValue."));
558 if (index2
< 0 || index2
> Int32
.MaxValue
)
559 throw new ArgumentOutOfRangeException ("index2", Locale
.GetText (
560 "Value must be >= 0 and <= Int32.MaxValue."));
562 if (index3
< 0 || index3
> Int32
.MaxValue
)
563 throw new ArgumentOutOfRangeException ("index3", Locale
.GetText (
564 "Value must be >= 0 and <= Int32.MaxValue."));
566 return GetValue ((int) index1
, (int) index2
, (int) index3
);
570 public void SetValue (object value, long index
)
572 if (index
< 0 || index
> Int32
.MaxValue
)
573 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
574 "Value must be >= 0 and <= Int32.MaxValue."));
576 SetValue (value, (int) index
);
580 public void SetValue (object value, long index1
, long index2
)
582 if (index1
< 0 || index1
> Int32
.MaxValue
)
583 throw new ArgumentOutOfRangeException ("index1", Locale
.GetText (
584 "Value must be >= 0 and <= Int32.MaxValue."));
586 if (index2
< 0 || index2
> Int32
.MaxValue
)
587 throw new ArgumentOutOfRangeException ("index2", Locale
.GetText (
588 "Value must be >= 0 and <= Int32.MaxValue."));
590 int[] ind
= {(int) index1, (int) index2}
;
591 SetValue (value, ind
);
595 public void SetValue (object value, long index1
, long index2
, long index3
)
597 if (index1
< 0 || index1
> Int32
.MaxValue
)
598 throw new ArgumentOutOfRangeException ("index1", Locale
.GetText (
599 "Value must be >= 0 and <= Int32.MaxValue."));
601 if (index2
< 0 || index2
> Int32
.MaxValue
)
602 throw new ArgumentOutOfRangeException ("index2", Locale
.GetText (
603 "Value must be >= 0 and <= Int32.MaxValue."));
605 if (index3
< 0 || index3
> Int32
.MaxValue
)
606 throw new ArgumentOutOfRangeException ("index3", Locale
.GetText (
607 "Value must be >= 0 and <= Int32.MaxValue."));
609 int[] ind
= {(int) index1, (int) index2, (int) index3}
;
610 SetValue (value, ind
);
613 public void SetValue (object value, int index
)
616 throw new ArgumentException (Locale
.GetText ("Array was not a one-dimensional array."));
617 if (index
< GetLowerBound (0) || index
> GetUpperBound (0))
618 throw new IndexOutOfRangeException (Locale
.GetText (
619 "Index has to be >= lower bound and <= upper bound of the array."));
621 SetValueImpl (value, index
- GetLowerBound (0));
624 public void SetValue (object value, int index1
, int index2
)
626 int[] ind
= {index1, index2}
;
627 SetValue (value, ind
);
630 public void SetValue (object value, int index1
, int index2
, int index3
)
632 int[] ind
= {index1, index2, index3}
;
633 SetValue (value, ind
);
636 public static Array
CreateInstance (Type elementType
, int length
)
638 int[] lengths
= {length}
;
640 return CreateInstance (elementType
, lengths
);
643 public static Array
CreateInstance (Type elementType
, int length1
, int length2
)
645 int[] lengths
= {length1, length2}
;
647 return CreateInstance (elementType
, lengths
);
650 public static Array
CreateInstance (Type elementType
, int length1
, int length2
, int length3
)
652 int[] lengths
= {length1, length2, length3}
;
654 return CreateInstance (elementType
, lengths
);
657 public static Array
CreateInstance (Type elementType
, params int[] lengths
)
659 if (elementType
== null)
660 throw new ArgumentNullException ("elementType");
662 throw new ArgumentNullException ("lengths");
664 if (lengths
.Length
> 255)
665 throw new TypeLoadException ();
669 elementType
= elementType
.UnderlyingSystemType
;
670 if (!elementType
.IsSystemType
)
671 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
672 if (elementType
.Equals (typeof (void)))
673 throw new NotSupportedException ("Array type can not be void");
674 if (elementType
.ContainsGenericParameters
)
675 throw new NotSupportedException ("Array type can not be an open generic type");
676 if ((elementType
is TypeBuilder
) && !(elementType
as TypeBuilder
).IsCreated ())
677 throw new NotSupportedException ("Can't create an array of the unfinished type '" + elementType
+ "'.");
679 return CreateInstanceImpl (elementType
, lengths
, bounds
);
682 public static Array
CreateInstance (Type elementType
, int[] lengths
, int [] lowerBounds
)
684 if (elementType
== null)
685 throw new ArgumentNullException ("elementType");
687 throw new ArgumentNullException ("lengths");
688 if (lowerBounds
== null)
689 throw new ArgumentNullException ("lowerBounds");
691 elementType
= elementType
.UnderlyingSystemType
;
692 if (!elementType
.IsSystemType
)
693 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
694 if (elementType
.Equals (typeof (void)))
695 throw new NotSupportedException ("Array type can not be void");
696 if (elementType
.ContainsGenericParameters
)
697 throw new NotSupportedException ("Array type can not be an open generic type");
699 if (lengths
.Length
< 1)
700 throw new ArgumentException (Locale
.GetText ("Arrays must contain >= 1 elements."));
702 if (lengths
.Length
!= lowerBounds
.Length
)
703 throw new ArgumentException (Locale
.GetText ("Arrays must be of same size."));
705 for (int j
= 0; j
< lowerBounds
.Length
; j
++) {
707 throw new ArgumentOutOfRangeException ("lengths", Locale
.GetText (
708 "Each value has to be >= 0."));
709 if ((long)lowerBounds
[j
] + (long)lengths
[j
] > (long)Int32
.MaxValue
)
710 throw new ArgumentOutOfRangeException ("lengths", Locale
.GetText (
711 "Length + bound must not exceed Int32.MaxValue."));
714 if (lengths
.Length
> 255)
715 throw new TypeLoadException ();
717 return CreateInstanceImpl (elementType
, lengths
, lowerBounds
);
720 static int [] GetIntArray (long [] values
)
722 int len
= values
.Length
;
723 int [] ints
= new int [len
];
724 for (int i
= 0; i
< len
; i
++) {
725 long current
= values
[i
];
726 if (current
< 0 || current
> (long) Int32
.MaxValue
)
727 throw new ArgumentOutOfRangeException ("values", Locale
.GetText (
728 "Each value has to be >= 0 and <= Int32.MaxValue."));
730 ints
[i
] = (int) current
;
735 public static Array
CreateInstance (Type elementType
, params long [] lengths
)
738 throw new ArgumentNullException ("lengths");
739 return CreateInstance (elementType
, GetIntArray (lengths
));
743 public object GetValue (params long [] indices
)
746 throw new ArgumentNullException ("indices");
747 return GetValue (GetIntArray (indices
));
751 public void SetValue (object value, params long [] indices
)
754 throw new ArgumentNullException ("indices");
755 SetValue (value, GetIntArray (indices
));
758 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
759 public static int BinarySearch (Array array
, object value)
762 throw new ArgumentNullException ("array");
768 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
770 if (array
.Length
== 0)
773 if (!(value is IComparable
))
774 throw new ArgumentException (Locale
.GetText ("value does not support IComparable."));
776 return DoBinarySearch (array
, array
.GetLowerBound (0), array
.GetLength (0), value, null);
779 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
780 public static int BinarySearch (Array array
, object value, IComparer comparer
)
783 throw new ArgumentNullException ("array");
786 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
788 if (array
.Length
== 0)
791 if ((comparer
== null) && (value != null) && !(value is IComparable
))
792 throw new ArgumentException (Locale
.GetText (
793 "comparer is null and value does not support IComparable."));
795 return DoBinarySearch (array
, array
.GetLowerBound (0), array
.GetLength (0), value, comparer
);
798 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
799 public static int BinarySearch (Array array
, int index
, int length
, object value)
802 throw new ArgumentNullException ("array");
805 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
807 if (index
< array
.GetLowerBound (0))
808 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
809 "index is less than the lower bound of array."));
811 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
812 "Value has to be >= 0."));
813 // re-ordered to avoid possible integer overflow
814 if (index
> array
.GetLowerBound (0) + array
.GetLength (0) - length
)
815 throw new ArgumentException (Locale
.GetText (
816 "index and length do not specify a valid range in array."));
818 if (array
.Length
== 0)
821 if ((value != null) && (!(value is IComparable
)))
822 throw new ArgumentException (Locale
.GetText (
823 "value does not support IComparable"));
825 return DoBinarySearch (array
, index
, length
, value, null);
828 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
829 public static int BinarySearch (Array array
, int index
, int length
, object value, IComparer comparer
)
832 throw new ArgumentNullException ("array");
835 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
837 if (index
< array
.GetLowerBound (0))
838 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
839 "index is less than the lower bound of array."));
841 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
842 "Value has to be >= 0."));
843 // re-ordered to avoid possible integer overflow
844 if (index
> array
.GetLowerBound (0) + array
.GetLength (0) - length
)
845 throw new ArgumentException (Locale
.GetText (
846 "index and length do not specify a valid range in array."));
848 if (array
.Length
== 0)
851 if ((comparer
== null) && (value != null) && !(value is IComparable
))
852 throw new ArgumentException (Locale
.GetText (
853 "comparer is null and value does not support IComparable."));
855 return DoBinarySearch (array
, index
, length
, value, comparer
);
858 static int DoBinarySearch (Array array
, int index
, int length
, object value, IComparer comparer
)
860 // cache this in case we need it
861 if (comparer
== null)
862 comparer
= Comparer
.Default
;
865 // Comment from Tum (tum@veridicus.com):
866 // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
867 int iMax
= index
+ length
- 1;
870 while (iMin
<= iMax
) {
871 // Be careful with overflow
872 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
873 int iMid
= iMin
+ ((iMax
- iMin
) / 2);
874 object elt
= array
.GetValueImpl (iMid
);
876 iCmp
= comparer
.Compare (elt
, value);
883 iMin
= iMid
+ 1; // compensate for the rounding down
886 catch (Exception e
) {
887 throw new InvalidOperationException (Locale
.GetText ("Comparer threw an exception."), e
);
893 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
894 public static void Clear (Array array
, int index
, int length
)
897 throw new ArgumentNullException ("array");
899 throw new IndexOutOfRangeException ("length < 0");
901 int low
= array
.GetLowerBound (0);
903 throw new IndexOutOfRangeException ("index < lower bound");
906 // re-ordered to avoid possible integer overflow
907 if (index
> array
.Length
- length
)
908 throw new IndexOutOfRangeException ("index + length > size");
910 ClearInternal (array
, index
, length
);
913 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
914 static extern void ClearInternal (Array a
, int index
, int count
);
916 [MethodImplAttribute (MethodImplOptions
.InternalCall
)]
917 public extern object Clone ();
919 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
920 public static void Copy (Array sourceArray
, Array destinationArray
, int length
)
922 // need these checks here because we are going to use
923 // GetLowerBound() on source and dest.
924 if (sourceArray
== null)
925 throw new ArgumentNullException ("sourceArray");
927 if (destinationArray
== null)
928 throw new ArgumentNullException ("destinationArray");
930 Copy (sourceArray
, sourceArray
.GetLowerBound (0), destinationArray
,
931 destinationArray
.GetLowerBound (0), length
);
934 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
935 public static void Copy (Array sourceArray
, int sourceIndex
, Array destinationArray
, int destinationIndex
, int length
)
937 if (sourceArray
== null)
938 throw new ArgumentNullException ("sourceArray");
940 if (destinationArray
== null)
941 throw new ArgumentNullException ("destinationArray");
944 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
945 "Value has to be >= 0."));;
948 throw new ArgumentOutOfRangeException ("sourceIndex", Locale
.GetText (
949 "Value has to be >= 0."));;
951 if (destinationIndex
< 0)
952 throw new ArgumentOutOfRangeException ("destinationIndex", Locale
.GetText (
953 "Value has to be >= 0."));;
955 if (FastCopy (sourceArray
, sourceIndex
, destinationArray
, destinationIndex
, length
))
958 int source_pos
= sourceIndex
- sourceArray
.GetLowerBound (0);
959 int dest_pos
= destinationIndex
- destinationArray
.GetLowerBound (0);
961 // re-ordered to avoid possible integer overflow
962 if (source_pos
> sourceArray
.Length
- length
)
963 throw new ArgumentException ("length");
965 if (dest_pos
> destinationArray
.Length
- length
) {
966 string msg
= "Destination array was not long enough. Check " +
967 "destIndex and length, and the array's lower bounds";
968 throw new ArgumentException (msg
, string.Empty
);
971 if (sourceArray
.Rank
!= destinationArray
.Rank
)
972 throw new RankException (Locale
.GetText ("Arrays must be of same size."));
974 Type src_type
= sourceArray
.GetType ().GetElementType ();
975 Type dst_type
= destinationArray
.GetType ().GetElementType ();
977 if (!Object
.ReferenceEquals (sourceArray
, destinationArray
) || source_pos
> dest_pos
) {
978 for (int i
= 0; i
< length
; i
++) {
979 Object srcval
= sourceArray
.GetValueImpl (source_pos
+ i
);
982 destinationArray
.SetValueImpl (srcval
, dest_pos
+ i
);
984 if (src_type
.Equals (typeof (Object
)))
985 throw new InvalidCastException ();
987 throw new ArrayTypeMismatchException (String
.Format (Locale
.GetText (
988 "(Types: source={0}; target={1})"), src_type
.FullName
, dst_type
.FullName
));
993 for (int i
= length
- 1; i
>= 0; i
--) {
994 Object srcval
= sourceArray
.GetValueImpl (source_pos
+ i
);
997 destinationArray
.SetValueImpl (srcval
, dest_pos
+ i
);
999 if (src_type
.Equals (typeof (Object
)))
1000 throw new InvalidCastException ();
1002 throw new ArrayTypeMismatchException (String
.Format (Locale
.GetText (
1003 "(Types: source={0}; target={1})"), src_type
.FullName
, dst_type
.FullName
));
1009 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1010 public static void Copy (Array sourceArray
, long sourceIndex
, Array destinationArray
,
1011 long destinationIndex
, long length
)
1013 if (sourceArray
== null)
1014 throw new ArgumentNullException ("sourceArray");
1016 if (destinationArray
== null)
1017 throw new ArgumentNullException ("destinationArray");
1019 if (sourceIndex
< Int32
.MinValue
|| sourceIndex
> Int32
.MaxValue
)
1020 throw new ArgumentOutOfRangeException ("sourceIndex",
1021 Locale
.GetText ("Must be in the Int32 range."));
1023 if (destinationIndex
< Int32
.MinValue
|| destinationIndex
> Int32
.MaxValue
)
1024 throw new ArgumentOutOfRangeException ("destinationIndex",
1025 Locale
.GetText ("Must be in the Int32 range."));
1027 if (length
< 0 || length
> Int32
.MaxValue
)
1028 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
1029 "Value must be >= 0 and <= Int32.MaxValue."));
1031 Copy (sourceArray
, (int) sourceIndex
, destinationArray
, (int) destinationIndex
, (int) length
);
1034 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1035 public static void Copy (Array sourceArray
, Array destinationArray
, long length
)
1037 if (length
< 0 || length
> Int32
.MaxValue
)
1038 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
1039 "Value must be >= 0 and <= Int32.MaxValue."));
1041 Copy (sourceArray
, destinationArray
, (int) length
);
1044 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1045 public static int IndexOf (Array array
, object value)
1048 throw new ArgumentNullException ("array");
1050 return IndexOf (array
, value, 0, array
.Length
);
1053 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1054 public static int IndexOf (Array array
, object value, int startIndex
)
1057 throw new ArgumentNullException ("array");
1059 return IndexOf (array
, value, startIndex
, array
.Length
- startIndex
);
1062 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1063 public static int IndexOf (Array array
, object value, int startIndex
, int count
)
1066 throw new ArgumentNullException ("array");
1069 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1071 // re-ordered to avoid possible integer overflow
1072 if (count
< 0 || startIndex
< array
.GetLowerBound (0) || startIndex
- 1 > array
.GetUpperBound (0) - count
)
1073 throw new ArgumentOutOfRangeException ();
1075 int max
= startIndex
+ count
;
1076 for (int i
= startIndex
; i
< max
; i
++) {
1077 if (Object
.Equals (array
.GetValueImpl (i
), value))
1081 return array
.GetLowerBound (0) - 1;
1084 public void Initialize()
1086 //FIXME: We would like to find a compiler that uses
1087 // this method. It looks like this method do nothing
1088 // in C# so no exception is trown by the moment.
1091 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1092 public static int LastIndexOf (Array array
, object value)
1095 throw new ArgumentNullException ("array");
1097 if (array
.Length
== 0)
1098 return array
.GetLowerBound (0) - 1;
1099 return LastIndexOf (array
, value, array
.Length
- 1);
1102 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1103 public static int LastIndexOf (Array array
, object value, int startIndex
)
1106 throw new ArgumentNullException ("array");
1108 return LastIndexOf (array
, value, startIndex
, startIndex
- array
.GetLowerBound (0) + 1);
1111 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1112 public static int LastIndexOf (Array array
, object value, int startIndex
, int count
)
1115 throw new ArgumentNullException ("array");
1118 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1120 int lb
= array
.GetLowerBound (0);
1121 // Empty arrays do not throw ArgumentOutOfRangeException
1122 if (array
.Length
== 0)
1125 if (count
< 0 || startIndex
< lb
||
1126 startIndex
> array
.GetUpperBound (0) || startIndex
- count
+ 1 < lb
)
1127 throw new ArgumentOutOfRangeException ();
1129 for (int i
= startIndex
; i
>= startIndex
- count
+ 1; i
--) {
1130 if (Object
.Equals (array
.GetValueImpl (i
), value))
1137 /* delegate used to swap array elements */
1138 delegate void Swapper (int i
, int j
);
1140 static Swapper
get_swapper (Array array
)
1143 return new Swapper (array
.int_swapper
);
1144 if (array
is double[])
1145 return new Swapper (array
.double_swapper
);
1146 if (array
is object[]) {
1147 return new Swapper (array
.obj_swapper
);
1149 return new Swapper (array
.slow_swapper
);
1152 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1153 public static void Reverse (Array array
)
1156 throw new ArgumentNullException ("array");
1158 Reverse (array
, array
.GetLowerBound (0), array
.GetLength (0));
1161 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1162 public static void Reverse (Array array
, int index
, int length
)
1165 throw new ArgumentNullException ("array");
1168 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1170 if (index
< array
.GetLowerBound (0) || length
< 0)
1171 throw new ArgumentOutOfRangeException ();
1173 // re-ordered to avoid possible integer overflow
1174 if (index
> array
.GetUpperBound (0) + 1 - length
)
1175 throw new ArgumentException ();
1177 int end
= index
+ length
- 1;
1178 object[] oarray
= array
as object[];
1179 if (oarray
!= null) {
1180 while (index
< end
) {
1181 object tmp
= oarray
[index
];
1182 oarray
[index
] = oarray
[end
];
1189 int[] iarray
= array
as int[];
1190 if (iarray
!= null) {
1191 while (index
< end
) {
1192 int tmp
= iarray
[index
];
1193 iarray
[index
] = iarray
[end
];
1200 double[] darray
= array
as double[];
1201 if (darray
!= null) {
1202 while (index
< end
) {
1203 double tmp
= darray
[index
];
1204 darray
[index
] = darray
[end
];
1212 Swapper swapper
= get_swapper (array
);
1213 while (index
< end
) {
1214 swapper (index
, end
);
1220 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1221 public static void Sort (Array array
)
1223 Sort (array
, (IComparer
)null);
1226 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1227 public static void Sort (Array keys
, Array items
)
1229 Sort (keys
, items
, (IComparer
)null);
1232 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1233 public static void Sort (Array array
, IComparer comparer
)
1236 throw new ArgumentNullException ("array");
1239 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1241 SortImpl (array
, null, array
.GetLowerBound (0), array
.GetLength (0), comparer
);
1244 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1245 public static void Sort (Array array
, int index
, int length
)
1247 Sort (array
, index
, length
, (IComparer
)null);
1250 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1251 public static void Sort (Array keys
, Array items
, IComparer comparer
)
1253 if (items
== null) {
1254 Sort (keys
, comparer
);
1259 throw new ArgumentNullException ("keys");
1261 if (keys
.Rank
> 1 || items
.Rank
> 1)
1262 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1264 SortImpl (keys
, items
, keys
.GetLowerBound (0), keys
.GetLength (0), comparer
);
1267 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1268 public static void Sort (Array keys
, Array items
, int index
, int length
)
1270 Sort (keys
, items
, index
, length
, (IComparer
)null);
1273 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1274 public static void Sort (Array array
, int index
, int length
, IComparer comparer
)
1277 throw new ArgumentNullException ("array");
1280 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1282 if (index
< array
.GetLowerBound (0))
1283 throw new ArgumentOutOfRangeException ("index");
1286 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
1287 "Value has to be >= 0."));
1289 if (array
.Length
- (array
.GetLowerBound (0) + index
) < length
)
1290 throw new ArgumentException ();
1292 SortImpl (array
, null, index
, length
, comparer
);
1295 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1296 public static void Sort (Array keys
, Array items
, int index
, int length
, IComparer comparer
)
1298 if (items
== null) {
1299 Sort (keys
, index
, length
, comparer
);
1304 throw new ArgumentNullException ("keys");
1306 if (keys
.Rank
> 1 || items
.Rank
> 1)
1307 throw new RankException ();
1309 if (keys
.GetLowerBound (0) != items
.GetLowerBound (0))
1310 throw new ArgumentException ();
1312 if (index
< keys
.GetLowerBound (0))
1313 throw new ArgumentOutOfRangeException ("index");
1316 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
1317 "Value has to be >= 0."));
1319 if (keys
.Length
!= items
.Length
|| keys
.Length
- (index
+ keys
.GetLowerBound (0)) < length
)
1320 throw new ArgumentException ();
1322 SortImpl (keys
, items
, index
, length
, comparer
);
1325 private static void SortImpl (Array keys
, Array items
, int index
, int length
, IComparer comparer
)
1331 int high
= index
+ length
- 1;
1333 #if !BOOTSTRAP_BASIC
1334 if (comparer
== null) {
1335 if (keys
is int[]) {
1336 qsort (keys
as int[], items
as object[], low
, high
);
1339 if (keys
is long[]) {
1340 qsort (keys
as long[], items
as object[], low
, high
);
1343 if (keys
is char[]) {
1344 qsort (keys
as char[], items
as object[], low
, high
);
1347 if (keys
is double[]) {
1348 qsort (keys
as double[], items
as object[], low
, high
);
1351 if (keys
is uint[]) {
1352 qsort (keys
as uint[], items
as object[], low
, high
);
1355 if (keys
is ulong[]) {
1356 qsort (keys
as ulong[], items
as object[], low
, high
);
1359 if (keys
is byte[]) {
1360 qsort (keys
as byte[], items
as object[], low
, high
);
1363 if (keys
is ushort[]) {
1364 qsort (keys
as ushort[], items
as object[], low
, high
);
1370 low
= MoveNullKeysToFront (keys
, items
, low
, high
, comparer
== null);
1375 qsort (keys
, items
, low
, high
, comparer
);
1376 } catch (Exception e
) {
1377 throw new InvalidOperationException (Locale
.GetText ("The comparer threw an exception."), e
);
1381 /* note, these are instance methods */
1382 void int_swapper (int i
, int j
) {
1383 int[] array
= this as int[];
1384 int val
= array
[i
];
1385 array
[i
] = array
[j
];
1389 void obj_swapper (int i
, int j
) {
1390 object[] array
= this as object[];
1391 object val
= array
[i
];
1392 array
[i
] = array
[j
];
1396 void slow_swapper (int i
, int j
) {
1397 object val
= GetValueImpl (i
);
1398 SetValueImpl (GetValue (j
), i
);
1399 SetValueImpl (val
, j
);
1402 void double_swapper (int i
, int j
) {
1403 double[] array
= this as double[];
1404 double val
= array
[i
];
1405 array
[i
] = array
[j
];
1409 private static void qsort (Array keys
, Array items
, int low0
, int high0
, IComparer comparer
)
1414 // Be careful with overflows
1415 int mid
= low
+ ((high
- low
) / 2);
1416 object keyPivot
= keys
.GetValueImpl (mid
);
1417 IComparable cmpPivot
= keyPivot
as IComparable
;
1420 // Move the walls in
1421 if (comparer
!= null) {
1422 while (low
< high0
&& comparer
.Compare (keyPivot
, keys
.GetValueImpl (low
)) > 0)
1424 while (high
> low0
&& comparer
.Compare (keyPivot
, keys
.GetValueImpl (high
)) < 0)
1427 while (low
< high0
&& cmpPivot
.CompareTo (keys
.GetValueImpl (low
)) > 0)
1429 while (high
> low0
&& cmpPivot
.CompareTo (keys
.GetValueImpl (high
)) < 0)
1434 swap (keys
, items
, low
, high
);
1442 qsort (keys
, items
, low0
, high
, comparer
);
1444 qsort (keys
, items
, low
, high0
, comparer
);
1447 private static int MoveNullKeysToFront (Array keys
, Array items
, int low
, int high
, bool ensureComparable
)
1449 // find first nun-null key
1450 while (low
< high
&& keys
.GetValueImpl (low
) == null)
1453 // move null keys to beginning of array,
1454 // ensure that non-null keys implement IComparable
1455 for (int i
= low
+ 1; i
<= high
; i
++) {
1456 object obj
= keys
.GetValueImpl (i
);
1458 swap (keys
, items
, low
, i
);
1461 if (ensureComparable
&& !(obj
is IComparable
)) {
1462 string msg
= Locale
.GetText ("No IComparable interface found for type '{0}'.");
1463 throw new InvalidOperationException (String
.Format (msg
, obj
.GetType ()));
1470 private static void swap (Array keys
, Array items
, int i
, int j
)
1472 object tmp
= keys
.GetValueImpl (i
);
1473 keys
.SetValueImpl (keys
.GetValueImpl (j
), i
);
1474 keys
.SetValueImpl (tmp
, j
);
1476 if (items
!= null) {
1477 tmp
= items
.GetValueImpl (i
);
1478 items
.SetValueImpl (items
.GetValueImpl (j
), i
);
1479 items
.SetValueImpl (tmp
, j
);
1483 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1484 public static void Sort
<T
> (T
[] array
)
1486 Sort
<T
> (array
, (IComparer
<T
>)null);
1489 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1490 public static void Sort
<TKey
, TValue
> (TKey
[] keys
, TValue
[] items
)
1492 Sort
<TKey
, TValue
> (keys
, items
, (IComparer
<TKey
>)null);
1495 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1496 public static void Sort
<T
> (T
[] array
, IComparer
<T
> comparer
)
1499 throw new ArgumentNullException ("array");
1501 SortImpl
<T
, T
> (array
, null, 0, array
.Length
, comparer
);
1504 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1505 public static void Sort
<TKey
, TValue
> (TKey
[] keys
, TValue
[] items
, IComparer
<TKey
> comparer
)
1507 if (items
== null) {
1508 Sort
<TKey
> (keys
, comparer
);
1513 throw new ArgumentNullException ("keys");
1515 if (keys
.Length
!= items
.Length
)
1516 throw new ArgumentException ("Length of keys and items does not match.");
1518 SortImpl
<TKey
, TValue
> (keys
, items
, 0, keys
.Length
, comparer
);
1521 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1522 public static void Sort
<T
> (T
[] array
, int index
, int length
)
1524 Sort
<T
> (array
, index
, length
, (IComparer
<T
>)null);
1527 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1528 public static void Sort
<TKey
, TValue
> (TKey
[] keys
, TValue
[] items
, int index
, int length
)
1530 Sort
<TKey
, TValue
> (keys
, items
, index
, length
, (IComparer
<TKey
>)null);
1533 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1534 public static void Sort
<T
> (T
[] array
, int index
, int length
, IComparer
<T
> comparer
)
1537 throw new ArgumentNullException ("array");
1540 throw new ArgumentOutOfRangeException ("index");
1543 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
1544 "Value has to be >= 0."));
1546 if (index
+ length
> array
.Length
)
1547 throw new ArgumentException ();
1549 SortImpl
<T
, T
> (array
, null, index
, length
, comparer
);
1552 [ReliabilityContractAttribute (Consistency
.MayCorruptInstance
, Cer
.MayFail
)]
1553 public static void Sort
<TKey
, TValue
> (TKey
[] keys
, TValue
[] items
, int index
, int length
, IComparer
<TKey
> comparer
)
1555 if (items
== null) {
1556 Sort
<TKey
> (keys
, index
, length
, comparer
);
1561 throw new ArgumentNullException ("keys");
1564 throw new ArgumentOutOfRangeException ("index");
1567 throw new ArgumentOutOfRangeException ("length");
1569 if (keys
.Length
!= items
.Length
|| keys
.Length
- index
< length
)
1570 throw new ArgumentException ();
1572 SortImpl
<TKey
, TValue
> (keys
, items
, index
, length
, comparer
);
1575 private static void SortImpl
<TKey
, TValue
> (TKey
[] keys
, TValue
[] items
, int index
, int length
, IComparer
<TKey
> comparer
)
1577 if (keys
.Length
<= 1)
1581 int high
= index
+ length
- 1;
1584 // Check for value types which can be sorted without Compare () method
1586 if (comparer
== null) {
1587 #if !BOOTSTRAP_BASIC
1588 switch (Type
.GetTypeCode (typeof (TKey
))) {
1589 case TypeCode
.Int32
:
1590 qsort (keys
as Int32
[], items
, low
, high
);
1592 case TypeCode
.Int64
:
1593 qsort (keys
as Int64
[], items
, low
, high
);
1596 qsort (keys
as byte[], items
, low
, high
);
1599 qsort (keys
as char[], items
, low
, high
);
1601 case TypeCode
.DateTime
:
1602 qsort (keys
as DateTime
[], items
, low
, high
);
1604 case TypeCode
.Decimal
:
1605 qsort (keys
as decimal[], items
, low
, high
);
1607 case TypeCode
.Double
:
1608 qsort (keys
as double[], items
, low
, high
);
1610 case TypeCode
.Int16
:
1611 qsort (keys
as Int16
[], items
, low
, high
);
1613 case TypeCode
.SByte
:
1614 qsort (keys
as SByte
[], items
, low
, high
);
1616 case TypeCode
.Single
:
1617 qsort (keys
as Single
[], items
, low
, high
);
1619 case TypeCode
.UInt16
:
1620 qsort (keys
as UInt16
[], items
, low
, high
);
1622 case TypeCode
.UInt32
:
1623 qsort (keys
as UInt32
[], items
, low
, high
);
1625 case TypeCode
.UInt64
:
1626 qsort (keys
as UInt64
[], items
, low
, high
);
1630 // Using Comparer<TKey> adds a small overload, but with value types it
1631 // helps us to not box them.
1632 if (typeof (IComparable
<TKey
>).IsAssignableFrom (typeof (TKey
)) &&
1633 typeof (TKey
).IsValueType
)
1634 comparer
= Comparer
<TKey
>.Default
;
1637 low
= MoveNullKeysToFront
<TKey
, TValue
> (keys
, items
, low
, high
, comparer
== null);
1643 qsort (keys
, items
, low
, high
, comparer
);
1644 } catch (Exception e
) {
1645 throw new InvalidOperationException (Locale
.GetText ("The comparer threw an exception."), e
);
1649 public static void Sort
<T
> (T
[] array
, Comparison
<T
> comparison
)
1652 throw new ArgumentNullException ("array");
1654 if (comparison
== null)
1655 throw new ArgumentNullException ("comparison");
1657 SortImpl
<T
> (array
, array
.Length
, comparison
);
1660 // used by List<T>.Sort (Comparison <T>)
1661 internal static void SortImpl
<T
> (T
[] array
, int length
, Comparison
<T
> comparison
)
1668 int high0
= length
- 1;
1669 qsort
<T
> (array
, low0
, high0
, comparison
);
1670 } catch (InvalidOperationException
) {
1672 } catch (Exception e
) {
1673 throw new InvalidOperationException (Locale
.GetText ("Comparison threw an exception."), e
);
1677 private static void qsort
<T
, U
> (T
[] array
, U
[] items
, int low0
, int high0
) where T
: IComparable
<T
>
1682 // Be careful with overflows
1683 int mid
= low
+ ((high
- low
) / 2);
1684 var keyPivot
= array
[mid
];
1687 // Move the walls in
1688 while (low
< high0
&& keyPivot
.CompareTo (array
[low
]) > 0)
1690 while (high
> low0
&& keyPivot
.CompareTo (array
[high
]) < 0)
1694 swap (array
, items
, low
, high
);
1702 qsort (array
, items
, low0
, high
);
1704 qsort (array
, items
, low
, high0
);
1707 private static void qsort
<K
, V
> (K
[] keys
, V
[] items
, int low0
, int high0
, IComparer
<K
> comparer
)
1712 // Be careful with overflows
1713 int mid
= low
+ ((high
- low
) / 2);
1714 K keyPivot
= keys
[mid
];
1715 IComparable
<K
> genCmpPivot
= keyPivot
as IComparable
<K
>;
1716 IComparable cmpPivot
= keyPivot
as IComparable
;
1719 // Move the walls in
1720 if (comparer
!= null) {
1721 while (low
< high0
&& comparer
.Compare (keyPivot
, keys
[low
]) > 0)
1723 while (high
> low0
&& comparer
.Compare (keyPivot
, keys
[high
]) < 0)
1726 if (genCmpPivot
!= null) {
1727 while (low
< high0
&& genCmpPivot
.CompareTo (keys
[low
]) > 0)
1729 while (high
> low0
&& genCmpPivot
.CompareTo (keys
[high
]) < 0)
1732 while (low
< high0
&& cmpPivot
.CompareTo (keys
[low
]) > 0)
1734 while (high
> low0
&& cmpPivot
.CompareTo (keys
[high
]) < 0)
1740 swap
<K
, V
> (keys
, items
, low
, high
);
1748 qsort
<K
, V
> (keys
, items
, low0
, high
, comparer
);
1750 qsort
<K
, V
> (keys
, items
, low
, high0
, comparer
);
1753 private static void qsort
<T
> (T
[] array
, int low0
, int high0
, Comparison
<T
> comparison
)
1758 // Be careful with overflows
1759 int mid
= low
+ ((high
- low
) / 2);
1760 T keyPivot
= array
[mid
];
1763 // Move the walls in
1764 while (low
< high0
&& comparison (array
[low
], keyPivot
) < 0)
1766 while (high
> low0
&& comparison (keyPivot
, array
[high
]) < 0)
1770 swap
<T
> (array
, low
, high
);
1778 qsort
<T
> (array
, low0
, high
, comparison
);
1780 qsort
<T
> (array
, low
, high0
, comparison
);
1783 private static int MoveNullKeysToFront
<K
, V
> (K
[] keys
, V
[] items
, int low
, int high
, bool ensureComparable
)
1785 // find first nun-null key
1786 while (low
< high
&& keys
[low
] == null)
1789 // move null keys to beginning of array,
1790 // ensure that non-null keys implement IComparable
1791 for (int i
= low
+ 1; i
<= high
; i
++) {
1794 swap
<K
, V
> (keys
, items
, low
, i
);
1797 if (ensureComparable
&& !(key
is IComparable
<K
>) && !(key
is IComparable
)) {
1798 string msg
= Locale
.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
1799 throw new InvalidOperationException (String
.Format (msg
, key
.GetType ()));
1806 private static void swap
<K
, V
> (K
[] keys
, V
[] items
, int i
, int j
)
1811 keys
[i
] = keys
[j
];
1814 if (items
!= null) {
1817 items
[i
] = items
[j
];
1822 private static void swap
<T
> (T
[] array
, int i
, int j
)
1825 array
[i
] = array
[j
];
1829 public void CopyTo (Array array
, int index
)
1832 throw new ArgumentNullException ("array");
1834 // The order of these exception checks may look strange,
1835 // but that's how the microsoft runtime does it.
1837 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1838 if (index
+ this.GetLength (0) > array
.GetLowerBound (0) + array
.GetLength (0))
1839 throw new ArgumentException ("Destination array was not long " +
1840 "enough. Check destIndex and length, and the array's " +
1843 throw new RankException (Locale
.GetText ("Only single dimension arrays are supported."));
1845 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
1846 "Value has to be >= 0."));
1848 Copy (this, this.GetLowerBound (0), array
, index
, this.GetLength (0));
1851 [ComVisible (false)]
1852 public void CopyTo (Array array
, long index
)
1854 if (index
< 0 || index
> Int32
.MaxValue
)
1855 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
1856 "Value must be >= 0 and <= Int32.MaxValue."));
1858 CopyTo (array
, (int) index
);
1861 internal class SimpleEnumerator
: IEnumerator
, ICloneable
1867 public SimpleEnumerator (Array arrayToEnumerate
)
1869 this.enumeratee
= arrayToEnumerate
;
1870 this.currentpos
= -1;
1871 this.length
= arrayToEnumerate
.Length
;
1874 public object Current
{
1876 // Exception messages based on MS implementation
1877 if (currentpos
< 0 )
1878 throw new InvalidOperationException (Locale
.GetText (
1879 "Enumeration has not started."));
1880 if (currentpos
>= length
)
1881 throw new InvalidOperationException (Locale
.GetText (
1882 "Enumeration has already ended"));
1883 // Current should not increase the position. So no ++ over here.
1884 return enumeratee
.GetValueImpl (currentpos
);
1888 public bool MoveNext()
1890 //The docs say Current should throw an exception if last
1891 //call to MoveNext returned false. This means currentpos
1892 //should be set to length when returning false.
1893 if (currentpos
< length
)
1895 if(currentpos
< length
)
1906 public object Clone ()
1908 return MemberwiseClone ();
1912 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
1913 public static void Resize
<T
> (ref T
[] array
, int newSize
)
1915 Resize
<T
> (ref array
, array
== null ? 0 : array
.Length
, newSize
);
1918 internal static void Resize
<T
> (ref T
[] array
, int length
, int newSize
)
1921 throw new ArgumentOutOfRangeException ();
1923 if (array
== null) {
1924 array
= new T
[newSize
];
1928 if (array
.Length
== newSize
)
1931 T
[] a
= new T
[newSize
];
1932 Array
.Copy (array
, a
, Math
.Min (newSize
, length
));
1936 public static bool TrueForAll
<T
> (T
[] array
, Predicate
<T
> match
)
1939 throw new ArgumentNullException ("array");
1941 throw new ArgumentNullException ("match");
1943 foreach (T t
in array
)
1950 public static void ForEach
<T
> (T
[] array
, Action
<T
> action
)
1953 throw new ArgumentNullException ("array");
1955 throw new ArgumentNullException ("action");
1957 foreach (T t
in array
)
1961 public static TOutput
[] ConvertAll
<TInput
, TOutput
> (TInput
[] array
, Converter
<TInput
, TOutput
> converter
)
1964 throw new ArgumentNullException ("array");
1965 if (converter
== null)
1966 throw new ArgumentNullException ("converter");
1968 TOutput
[] output
= new TOutput
[array
.Length
];
1969 for (int i
= 0; i
< array
.Length
; i
++)
1970 output
[i
] = converter (array
[i
]);
1975 public static int FindLastIndex
<T
> (T
[] array
, Predicate
<T
> match
)
1978 throw new ArgumentNullException ("array");
1980 return FindLastIndex
<T
> (array
, 0, array
.Length
, match
);
1983 public static int FindLastIndex
<T
> (T
[] array
, int startIndex
, Predicate
<T
> match
)
1986 throw new ArgumentNullException ();
1988 return FindLastIndex
<T
> (array
, startIndex
, array
.Length
- startIndex
, match
);
1991 public static int FindLastIndex
<T
> (T
[] array
, int startIndex
, int count
, Predicate
<T
> match
)
1994 throw new ArgumentNullException ("array");
1996 throw new ArgumentNullException ("match");
1998 if (startIndex
> array
.Length
|| startIndex
+ count
> array
.Length
)
1999 throw new ArgumentOutOfRangeException ();
2001 for (int i
= startIndex
+ count
- 1; i
>= startIndex
; i
--)
2002 if (match (array
[i
]))
2008 public static int FindIndex
<T
> (T
[] array
, Predicate
<T
> match
)
2011 throw new ArgumentNullException ("array");
2013 return FindIndex
<T
> (array
, 0, array
.Length
, match
);
2016 public static int FindIndex
<T
> (T
[] array
, int startIndex
, Predicate
<T
> match
)
2019 throw new ArgumentNullException ("array");
2021 return FindIndex
<T
> (array
, startIndex
, array
.Length
- startIndex
, match
);
2024 public static int FindIndex
<T
> (T
[] array
, int startIndex
, int count
, Predicate
<T
> match
)
2027 throw new ArgumentNullException ("array");
2030 throw new ArgumentNullException ("match");
2032 if (startIndex
> array
.Length
|| startIndex
+ count
> array
.Length
)
2033 throw new ArgumentOutOfRangeException ();
2035 for (int i
= startIndex
; i
< startIndex
+ count
; i
++)
2036 if (match (array
[i
]))
2042 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
2043 public static int BinarySearch
<T
> (T
[] array
, T
value)
2046 throw new ArgumentNullException ("array");
2048 return BinarySearch
<T
> (array
, 0, array
.Length
, value, null);
2051 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
2052 public static int BinarySearch
<T
> (T
[] array
, T
value, IComparer
<T
> comparer
)
2055 throw new ArgumentNullException ("array");
2057 return BinarySearch
<T
> (array
, 0, array
.Length
, value, comparer
);
2060 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
2061 public static int BinarySearch
<T
> (T
[] array
, int index
, int length
, T
value)
2063 return BinarySearch
<T
> (array
, index
, length
, value, null);
2066 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.MayFail
)]
2067 public static int BinarySearch
<T
> (T
[] array
, int index
, int length
, T
value, IComparer
<T
> comparer
)
2070 throw new ArgumentNullException ("array");
2072 throw new ArgumentOutOfRangeException ("index", Locale
.GetText (
2073 "index is less than the lower bound of array."));
2075 throw new ArgumentOutOfRangeException ("length", Locale
.GetText (
2076 "Value has to be >= 0."));
2077 // re-ordered to avoid possible integer overflow
2078 if (index
> array
.Length
- length
)
2079 throw new ArgumentException (Locale
.GetText (
2080 "index and length do not specify a valid range in array."));
2081 if (comparer
== null)
2082 comparer
= Comparer
<T
>.Default
;
2085 int iMax
= index
+ length
- 1;
2088 while (iMin
<= iMax
) {
2089 // Be careful with overflows
2090 int iMid
= iMin
+ ((iMax
- iMin
) / 2);
2091 iCmp
= comparer
.Compare (value, array
[iMid
]);
2098 iMin
= iMid
+ 1; // compensate for the rounding down
2100 } catch (Exception e
) {
2101 throw new InvalidOperationException (Locale
.GetText ("Comparer threw an exception."), e
);
2107 public static int IndexOf
<T
> (T
[] array
, T
value)
2110 throw new ArgumentNullException ("array");
2112 return IndexOf
<T
> (array
, value, 0, array
.Length
);
2115 public static int IndexOf
<T
> (T
[] array
, T
value, int startIndex
)
2118 throw new ArgumentNullException ("array");
2120 return IndexOf
<T
> (array
, value, startIndex
, array
.Length
- startIndex
);
2123 public static int IndexOf
<T
> (T
[] array
, T
value, int startIndex
, int count
)
2126 throw new ArgumentNullException ("array");
2128 // re-ordered to avoid possible integer overflow
2129 if (count
< 0 || startIndex
< array
.GetLowerBound (0) || startIndex
- 1 > array
.GetUpperBound (0) - count
)
2130 throw new ArgumentOutOfRangeException ();
2132 int max
= startIndex
+ count
;
2133 EqualityComparer
<T
> equalityComparer
= EqualityComparer
<T
>.Default
;
2134 for (int i
= startIndex
; i
< max
; i
++) {
2135 if (equalityComparer
.Equals (array
[i
], value))
2142 public static int LastIndexOf
<T
> (T
[] array
, T
value)
2145 throw new ArgumentNullException ("array");
2147 if (array
.Length
== 0)
2149 return LastIndexOf
<T
> (array
, value, array
.Length
- 1);
2152 public static int LastIndexOf
<T
> (T
[] array
, T
value, int startIndex
)
2155 throw new ArgumentNullException ("array");
2157 return LastIndexOf
<T
> (array
, value, startIndex
, startIndex
+ 1);
2160 public static int LastIndexOf
<T
> (T
[] array
, T
value, int startIndex
, int count
)
2163 throw new ArgumentNullException ("array");
2165 if (count
< 0 || startIndex
< array
.GetLowerBound (0) ||
2166 startIndex
> array
.GetUpperBound (0) || startIndex
- count
+ 1 < array
.GetLowerBound (0))
2167 throw new ArgumentOutOfRangeException ();
2169 EqualityComparer
<T
> equalityComparer
= EqualityComparer
<T
>.Default
;
2170 for (int i
= startIndex
; i
>= startIndex
- count
+ 1; i
--) {
2171 if (equalityComparer
.Equals (array
[i
], value))
2178 public static T
[] FindAll
<T
> (T
[] array
, Predicate
<T
> match
)
2181 throw new ArgumentNullException ("array");
2184 throw new ArgumentNullException ("match");
2187 T
[] d
= new T
[array
.Length
];
2188 foreach (T t
in array
)
2192 Resize
<T
> (ref d
, pos
);
2196 public static bool Exists
<T
> (T
[] array
, Predicate
<T
> match
)
2199 throw new ArgumentNullException ("array");
2202 throw new ArgumentNullException ("match");
2204 foreach (T t
in array
)
2210 public static ReadOnlyCollection
<T
> AsReadOnly
<T
> (T
[] array
)
2213 throw new ArgumentNullException ("array");
2215 return new ReadOnlyCollection
<T
> (array
);
2218 public static T Find
<T
> (T
[] array
, Predicate
<T
> match
)
2221 throw new ArgumentNullException ("array");
2224 throw new ArgumentNullException ("match");
2226 foreach (T t
in array
)
2233 public static T FindLast
<T
> (T
[] array
, Predicate
<T
> match
)
2236 throw new ArgumentNullException ("array");
2239 throw new ArgumentNullException ("match");
2241 for (int i
= array
.Length
- 1; i
>= 0; i
--)
2242 if (match (array
[i
]))
2248 [ReliabilityContractAttribute (Consistency
.WillNotCorruptState
, Cer
.Success
)]
2250 // The constrained copy should guarantee that if there is an exception thrown
2251 // during the copy, the destination array remains unchanged.
2252 // This is related to System.Runtime.Reliability.CER
2253 public static void ConstrainedCopy (Array sourceArray
, int sourceIndex
, Array destinationArray
, int destinationIndex
, int length
)
2255 Copy (sourceArray
, sourceIndex
, destinationArray
, destinationIndex
, length
);