I'm going batty trying to figure out why this is not working.
I'm trying to find all objects within a class derived from CollectionBase
which meet a certain criteria, but the search seems to be skipping some
objects. The following code is supposed to start searching the InnerList
from the beginning, and continue searching while there are still objects
that my comparer class says matches. In the code, comp is my comparer
object, and source is the object I'm looking for.
int from = 0;
int pos = 0;
while(pos >= 0)
{
pos = InnerList.BinarySearch(from, InnerList.Count - from, source,
comp);
if(pos > -1)
{
//.....Do some stuff with the object at index pos....
from = pos + 1;
}
}
Now with my test, if there is one object in the collection, it works. I get
that object. But if there is more than one, I don't get all. With the test
case of five objects, I get three, the first two are skipped over. I checked
and found that my comparer is not being called five times. The documentation
states that if BinarySearch finds more than one match, it only returns the
first one. This is not what I am seeing. It seems to be skipping over the
first two objects in my collection, based on the fact that my comparer is
only being called three times, while searching through 5 objects, all of
which should be hits. If I iterate through the collection, calling my
comparer myself, all five return tests return 0 as expected.
I'm not particularyly averse to writing my own search but I'd like to
understand why I don't see the documented behavior. Any ideas?
Eric 6 3886
<"Eric Eggermann" <<none>>> wrote:
<snip> Now with my test, if there is one object in the collection, it works. I get that object. But if there is more than one, I don't get all. With the test case of five objects, I get three, the first two are skipped over. I checked and found that my comparer is not being called five times. The documentation states that if BinarySearch finds more than one match, it only returns the first one. This is not what I am seeing. It seems to be skipping over the first two objects in my collection, based on the fact that my comparer is only being called three times, while searching through 5 objects, all of which should be hits. If I iterate through the collection, calling my comparer myself, all five return tests return 0 as expected.
It sounds like your comparer isn't being terribly useful. Note that:
<quote>
If the ArrayList contains more than one element with the same value,
the method returns only one of the occurrences, and it might return any
one of the occurrences, not necessarily the first one.
</quote>
So there's nothing to stop it from returning the last element, and
that's all.
If your comparer is just returning 0 for everything, I'd just iterate
over the whole collection if I were you. BinarySearch is for *sorted*
lists where there's a meaningful comparison to make.
--
Jon Skeet - <sk***@pobox.com> http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Where did you find that quote about it returns any one of the ocurrences? My
help file states "If the ArrayList contains more than one element with the
same value, the method returns only the index of the first occurrence."
Of course, your quote explains what I'm seeing perfectly. My doc should
probably read 'returns the index of the first occurrence found'. And
actually, my collection is sorted, and the comparer is doing exactly what I
need it to do. The objects all contain different values, but within this
program, many will be considered the same.
Anyway, thanks for that quote Jon, I'll have to write my own search. I'd
have liked to have avoided that, but there's nothing else for it.
Cheers,
Eric
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:MP************************@msnews.microsoft.c om... <"Eric Eggermann" <<none>>> wrote:
It sounds like your comparer isn't being terribly useful. Note that:
<quote> If the ArrayList contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one. </quote>
So there's nothing to stop it from returning the last element, and that's all.
If your comparer is just returning 0 for everything, I'd just iterate over the whole collection if I were you. BinarySearch is for *sorted* lists where there's a meaningful comparison to make.
-- Jon Skeet - <sk***@pobox.com> http://www.pobox.com/~skeet If replying to the group, please do not mail me too
<"Eric Eggermann" <<none>>> wrote: Where did you find that quote about it returns any one of the ocurrences?
The docs for ArrayList.BinarySearch Method (Int32, Int32, Object,
IComparer) in the remarks. The other overloads have the same bit in.
My help file states "If the ArrayList contains more than one element with the same value, the method returns only the index of the first occurrence."
Hmm... odd.
Of course, your quote explains what I'm seeing perfectly. My doc should probably read 'returns the index of the first occurrence found'. And actually, my collection is sorted, and the comparer is doing exactly what I need it to do. The objects all contain different values, but within this program, many will be considered the same.
Anyway, thanks for that quote Jon, I'll have to write my own search. I'd have liked to have avoided that, but there's nothing else for it.
Well, if your list is sorted, then you just need to find *a* match, and
then go each way (forwards and backwards) until it doesn't match. As
it's already sorted, all the matches should be in one "lump" as it
were.
--
Jon Skeet - <sk***@pobox.com> http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
do you know what the binary search algorithm does? the behavior you are experiencing is exactly what one would expect from a binary search. binary search always start at the middle of the list, keeps on cutting list in half until a match is found. so stepping through your code, the very first match is found at pos 2 since that's the middle of the list. first 2 elements are skipped by your own code because from = pos + 1
----- Eric Eggermann > wrote: ----
I'm going batty trying to figure out why this is not working
I'm trying to find all objects within a class derived from CollectionBas
which meet a certain criteria, but the search seems to be skipping som
objects. The following code is supposed to start searching the InnerLis
from the beginning, and continue searching while there are still object
that my comparer class says matches. In the code, comp is my compare
object, and source is the object I'm looking for
int from = 0
int pos = 0
while(pos >= 0
pos = InnerList.BinarySearch(from, InnerList.Count - from, source
comp)
if(pos > -1
//.....Do some stuff with the object at index pos...
from = pos + 1
Now with my test, if there is one object in the collection, it works. I ge
that object. But if there is more than one, I don't get all. With the tes
case of five objects, I get three, the first two are skipped over. I checke
and found that my comparer is not being called five times. The documentatio
states that if BinarySearch finds more than one match, it only returns th
first one. This is not what I am seeing. It seems to be skipping over th
first two objects in my collection, based on the fact that my comparer i
only being called three times, while searching through 5 objects, all o
which should be hits. If I iterate through the collection, calling m
comparer myself, all five return tests return 0 as expected
I'm not particularyly averse to writing my own search but I'd like t
understand why I don't see the documented behavior. Any ideas
Eri
Jon Skeet [C# MVP] wrote: <"Eric Eggermann" <<none>>> wrote:
Where did you find that quote about it returns any one of the ocurrences?
The docs for ArrayList.BinarySearch Method (Int32, Int32, Object, IComparer) in the remarks. The other overloads have the same bit in.
My help file states "If the ArrayList contains more than one element with the same value, the method returns only the index of the first occurrence."
Hmm... odd.
The docs for Framework 1.0 state that the index of the first occurrence
will be returned.
This was changed in the 1.1 docs to say that the index returned would
not necessarily be the first if there were more than one element with
the same value.
It appears that the 1.0 docs are in error.
--
mikeb
Yeah, sure, I knew how it works, just my docs said they returned the first,
so silly me, I thought that's what it did. My docs are old I guess. I just
figured it did the backup down the list to find the first for me. My mistake
was assuming my code was wrong, instead of the docs.
Thanks for the help, all. I got it now.
Eric
"Daniel Jin" <an*******@discussions.microsoft.com> wrote in message
news:63**********************************@microsof t.com... do you know what the binary search algorithm does? the behavior you
are experiencing is exactly what one would expect from a binary search.
binary search always start at the middle of the list, keeps on cutting list
in half until a match is found. so stepping through your code, the very
first match is found at pos 2 since that's the middle of the list. first 2
elements are skipped by your own code because from = pos + 1. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Homa |
last post by:
I can' believe my own eye, but it happens...there is a bug in
ArrayList.BinarySearch!! It should be such a simple function......
Here is the detail. (I'm using C#, don't know if this is C#'s...
|
by: Pete Z |
last post by:
Does anyone know why this snippet of code continues to return x with a value
of -1?
Is there an issue with ArrayList.BinarySearch?
ArrayList myAL = new ArrayList();
myAL .Add(1);
myAL...
|
by: Sek |
last post by:
Folks,
I have an ArrayList of integers.
I have sorted the list already.
Now, i want to find the index of the first element that is greater than
a given number.
How to accomplish this in C#?
|
by: Bernie Yaeger |
last post by:
I'm having difficulty searching an arraylist for certain values that are in
another arraylist. Essentially, I want to load the second arraylist with
only one of each of the possible elements in...
|
by: Mike Dole |
last post by:
I have an arraylist like the one with the Guitar Class sample in
Q316302.
Dim MycolliCol as arraylist
Private Sub FillArray()
MyColliCol.Add(New Colli(1, "STUK", 0))
MyColliCol.Add(New...
|
by: Paul Nations |
last post by:
I've got arraylists of simple classes bound to controls. I need to search
through those arraylists to set the correct SelectedItem in the control.
The code looks like:
Public Class...
|
by: JohnR |
last post by:
I have an arraylist of string values. I would like to search the arraylist
to find the index of a particular string and I would like the search to be
case insensitive.
dim al as new arraylist...
|
by: John Veldthuis |
last post by:
I have an ArrayList set up with a set of class objects.
The class has 3 strings in it and are as follows
ProdID
GSP
Description
Okay now problem with getting all these into the list and...
|
by: Justin |
last post by:
Here's a quick rundown of what I'm doing.
I'm filling an arraylist with data. Then I loop through a dataset and grab
a field to perform a search on the arraylist. Every time I find a match I...
|
by: Guy |
last post by:
Is there a better way to search identical elements in a sorted array
list than the following:
iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count,
aSearchedObject );
aFoundObject= m_Array;...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |