Help! BinarySearch on an ArrayList of objects

[Sal Sal]

Hi, I have a sorted (alphanumeric) ArrayList of class objects as follows.

    public class reports
    {
        public System.Collections.ArrayList rptCollection = new System.Collections.ArrayList();
        public reports()
        {
           
        }
    }

    public class values
    {
        private string ID= string.Empty;
        private string Num= string.Empty;
        private string Inp= string.Empty;
  
        public values()
        {
        }

        public string ID
        {
            get { return this.ID; }
            set { this.id= value; }
        }
        public string num
        {
            get { return this.Num; }
            set { this.Num= value; }
        }
        public string inp
        {
            get { return this.Inp; }
            set { this.Inp = value; }
        }
    }

In my main class I add each object to an ArrayList collection.

namespace whatever
{
    class Program
    {
        static void Main(string[] args)
        {
            reports rpt = new reports();

            while(true){ //keep filling the arrayList with objects until break

            values Val = new values();
            Val.id = "something";
            Val.num = "whatever";
            Val.inp = "other";

            
            rpt.rptCollection.Add(Val);

            if(something){
               break;
            }

            }

}
}
}

After the collection is complete I sorted it using an AlphaNumeric sorter that implements IComparer, I have now a new Val object like Val.ID = "hello"; How do I search the sorted collection for this value?

Can I use this --> rpt.rptCollecti on.BinarySearch (object, IComparer);??
I just don't know how to implement the IComparer part for this case
Thanks for any help,

[Oralloy]

Sal,

We are an education forum; we won't write your code for you.

So, the way to go from here is to pencil in your solution, make certain it compiles, test it, and then ask specific questions, if you are still having problems.

Binary searches are really quite easy, assuming that your array is correctly sorted. At least I assume that you're trying to do a binary search, based on your posting title.

As a quick observation, however, I do not see your program imposing any sort of order on rpt.rptCollecti on. If the array is not sorted, then a binary search will do nothing useful outside of causing confusion.

BTW, the ArrayList container class may have a search feature built-in, already. You might want to review your documentation.

Cheers!
Oralloy

[Sal Sal]

I'm not asking for anyone to write my code. I need help because I can't locate the information i need to complete my code.
Sorry for not including more detail in my first post, i was in a rush :)

I already sorted my ArrayList, here is the code that does it

//CLASS
    public class sortAscendingHelper : System.Collections.IComparer
    {
        public int Compare(object x, object y)
        {
            values S1 = (values )x;
            values S2 = (values )y;

            string s1 = S1.orderNum;
            string s2 = S2.orderNum;

            //s1.pathID = x as string;
            //s2.pathID = y as string;

            //string s1 = x as string;
            if (s1 == null)
            {
                return 0;
            }
            //string s2 = y as string;
            if (s2 == null)
            {
                return 0;
            }

            int len1 = s1.Length;
            int len2 = s2.Length;
            int marker1 = 0;
            int marker2 = 0;

            // Walk through two the strings with two markers.
            while (marker1 < len1 && marker2 < len2)
            {
                char ch1 = s1[marker1];
                char ch2 = s2[marker2];

                // Some buffers we can build up characters in for each chunk.
                char[] space1 = new char[len1];
                int loc1 = 0;
                char[] space2 = new char[len2];
                int loc2 = 0;

                // Walk through all following characters that are digits or
                // characters in BOTH strings starting at the appropriate marker.
                // Collect char arrays.
                do
                {
                    space1[loc1++] = ch1;
                    marker1++;

                    if (marker1 < len1)
                    {
                        ch1 = s1[marker1];
                    }
                    else
                    {
                        break;
                    }
                } while (char.IsDigit(ch1) == char.IsDigit(space1[0]));

                do
                {
                    space2[loc2++] = ch2;
                    marker2++;

                    if (marker2 < len2)
                    {
                        ch2 = s2[marker2];
                    }
                    else
                    {
                        break;
                    }
                } while (char.IsDigit(ch2) == char.IsDigit(space2[0]));

                // If we have collected numbers, compare them numerically.
                // Otherwise, if we have strings, compare them alphabetically.
                string str1 = new string(space1);
                string str2 = new string(space2);

                int result;

                if (char.IsDigit(space1[0]) && char.IsDigit(space2[0]))
                {
                    int thisNumericChunk = int.Parse(str1);
                    int thatNumericChunk = int.Parse(str2);
                    result = thisNumericChunk.CompareTo(thatNumericChunk);
                }
                else
                {
                    result = str1.CompareTo(str2);
                }

                if (result != 0)
                {
                    return result;
                }
            }
            return len1 - len2;
        }
    }

And here is how I implement it in my main function

rpt.rptCollection.Sort(new sortAscendingHelper());

Basically I want to do the following

values keyVal = new values();
keyVal.ID = "hello";

int location = rpt.rptCollection.BinarySearch(keyVal);

By modifying my values class to implement IComparible like the following

 public class values : IComparable<values>

    {
         private string ID= string.Empty;
         private string Num= string.Empty;
         private string Inp= string.Empty;
  
         public values()
         {
         }
  
         public string ID
         {
             get { return this.ID; }
             set { this.id= value; }
         }
         public string num
         {
             get { return this.Num; }
             set { this.Num= value; }
         }
         public string inp
         {
             get { return this.Inp; }
             set { this.Inp = value; }
         }
        
        public int CompareTo(values otherValue)
        {
            return this.id.CompareTo(otherValue.id);
        }

     }

However I get the following error when I tried this,

System.InvalidO perationExcepti on was unhandled
Message="Failed to compare two elements in the array."
Source="mscorli b"
StackTrace:
at System.Array.Bi narySearch(Arra y array, Int32 index, Int32 length, Object value, IComparer comparer)
at System.Collecti ons.ArrayList.B inarySearch(Int 32 index, Int32 count, Object value, IComparer comparer)
at System.Collecti ons.ArrayList.B inarySearch(Obj ect value)
at batchCompare_TM 2_getPathIDs.Pr ogram.Main(Stri ng[] args) in y:\Visual Studio 2008\Projects\b atchCompare_TM2 _getPathIDs\bat chCompare_TM2_g etPathIDs\Progr am.cs:line 453
at System.AppDomai n._nExecuteAsse mbly(Assembly assembly, String[] args)
at System.AppDomai n.ExecuteAssemb ly(String assemblyFile, Evidence assemblySecurit y, String[] args)
at Microsoft.Visua lStudio.Hosting Process.HostPro c.RunUsersAssem bly()
at System.Threadin g.ThreadHelper. ThreadStart_Con text(Object state)
at System.Threadin g.ExecutionCont ext.Run(Executi onContext executionContex t, ContextCallback callback, Object state)
at System.Threadin g.ThreadHelper. ThreadStart()
InnerException: System.Argument Exception
Message="At least one object must implement IComparable."
Source="mscorli b"
StackTrace:
at System.Collecti ons.Comparer.Co mpare(Object a, Object b)
at System.Array.Bi narySearch(Arra y array, Int32 index, Int32 length, Object value, IComparer comparer)
InnerException:

[Oralloy]

Sal,

I may be off my rocker, but won't this do what you need?

int location =
   rpt.rptCollection.BinarySearch(keyVal,
                                  new sortAscendingHelper());

[Sal Sal]

Update:

I made some progress, I changed from an ArrayList to a List<> because I wanted access to each object in the list, in case i wanted to change a value, and now it works better.

List<reportValues> test2 = new List<reportValues>();

//code to fill List<> and then sort it goes here

values key = new values();
key.id = "whatever";
int location = test2.BinarySearch(key);

But I'm getting a negative number for location. I'm still trying to figure out what that means...

[Sal Sal]

Oralloy thanks, this gives me the same result as my modification in post #3 with the change I made in post #5. Both results are the same negative number (-738)

From MSDN "the Return Value is: The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count."


Does this mean that a negative number indicates the item was not found in the list (which is all i want to know)
But if I take the positive of the result (738) it gives me the location of the next biggest value in the list?

Also what if the item is found, what do they mean by zero-based index. Is that just a positive number equal to the index location?

[Oralloy]

Well ... methinks that it's time to read the documentation a bit more, right?

I expect that you didn't find the key "whatever", though.

BTW, have you written any unit tests demonstrating to yourself that your comparison function works correctly?

Cheers!

[Oralloy]

Yep. Not found.

The bitwise complement of -738 is 737, by the way.

You really should test on a few three or four item data sets, just to make sure your code works as designed.

Luck!
Oralloy