[Mono-bugs] [Bug 77504][Maj] New - System.Array:BinarySearch does not return the correct value

[bugzilla-daemon at bugzilla.ximian.com]

Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.

Changed by julien.degroote at tremplin-utc.net.

http://bugzilla.ximian.com/show_bug.cgi?id=77504

--- shadow/77504	2006-02-08 11:57:34.000000000 -0500
+++ shadow/77504.tmp.14477	2006-02-08 11:57:34.000000000 -0500
@@ -0,0 +1,107 @@
+Bug#: 77504
+Product: Mono: Class Libraries
+Version: 1.1
+OS: GNU/Linux [Other]
+OS Details: Linux mordor 2.6.8.1-epia1 #2 Tue Mar 29 23:40:09 CEST 2005 i686 VIA Nehemiah CentaurHauls GNU/Linux
+Status: NEW   
+Resolution: 
+Severity: Unknown
+Priority: Major
+Component: CORLIB
+AssignedTo: mono-bugs at ximian.com                            
+ReportedBy: julien.degroote at tremplin-utc.net               
+QAContact: mono-bugs at ximian.com
+TargetMilestone: ---
+URL: 
+Cc: 
+Summary: System.Array:BinarySearch does not return the correct value
+
+Please fill in this template when reporting a bug, unless you know what you
+are doing.
+Description of Problem:
+
+I noticed that the return value of
+System.Collections.Generic.List:BinarySearch(T item, IComparer<T> comparer)
+ is invalid when item is not in the List.
+
+
+Steps to reproduce the problem:
+1.  Use the given file compile and run : 
+==========================================================
+using System;
+using System.Collections.Generic;
+
+namespace Test {
+    class Node {
+        public Node(int x) {
+            cx = x;
+        }
+        public int cx;
+    }
+
+    class MyComparer : IComparer<Node> {
+        public int Compare(Node a, Node b) {
+            string sa = (a == null ? "null" : "cx:"+a.cx.ToString());
+            string sb = (b == null ? "null" : "cx:"+b.cx.ToString());
+            Console.WriteLine("Comparing {0} and {1}",sa,sb);
+            if (a == null) {
+                if (b == null) {
+                    return 0;
+                } else {
+                    return -1;
+                }
+            }
+            if (b == null) {
+                return 1;
+            }
+            if (a.cx < b.cx) {
+                return -1;
+            } else if (a.cx > b.cx) {
+                return 1;
+            } else {
+                return 0;
+            }
+        }
+    }
+
+    class Start {
+        public static void Main() {
+            IComparer<Node> comp = new MyComparer();
+            List<Node> ss = new List<Node>();
+            Node n = new Node(50);
+            int ind1 = ss.BinarySearch(n,comp);
+            ss.Insert(~ind1,n);
+
+            n = new Node(51);
+            ind1 = ss.BinarySearch(n,comp);
+            ss.Insert(~ind1,n);
+        }
+    }
+}
+
+==========================================================
+
+
+Actual Results:
+You will notice that the second Insert produces an exception here it looks
+like this : 
+==========================================================
+Unhandled Exception: System.ArgumentOutOfRangeException: Argument is out of
+range.
+Parameter name: index
+in <0x00088> System.Collections.Generic.List`1[Test.Node]:Insert (Int32 ,
+Test.Node )
+
+Expected Results:
+Program runs and returns with no problem. Both Node objects added to the
+List ss.
+
+How often does this happen? 
+Always
+
+Additional Information:
+The cause of the exception is that BinarySearch returns -5 (the binary
+complement of 4) but it should return -2 (binary complement of 1).
+I tracked down the bug to System.Array:BinarySearch that apparently uses
+the capacity of the internal array instead of the actual number of items to
+do its search.