offline314159
asked on
Searching a list using a generic instance of a class
I'm trying to implement a list where I'll be storing specific instances of objects, but where I need to be able to find elements in the list based on traits they share in common with generic objects.
Basically, my stored classes have the attibutes "name" and "number". I can have more than one of a given pairing of those, I just need the basic ability to find the *first* match in the list based on either those two pieces of data, ideally by passing a similar object to a search routine and having it find the first match.
Although it is possible to impose an ordering on the items, it's not really natural to do so, and there's a fair number of ways to cause it to mess up, since the items are grouped, but the groups don't have a natural ordering.
Basically, my stored classes have the attibutes "name" and "number". I can have more than one of a given pairing of those, I just need the basic ability to find the *first* match in the list based on either those two pieces of data, ideally by passing a similar object to a search routine and having it find the first match.
Although it is possible to impose an ordering on the items, it's not really natural to do so, and there's a fair number of ways to cause it to mess up, since the items are grouped, but the groups don't have a natural ordering.
ASKER
I was hoping for something a bit less in the O(n) range for searching. I was thinking of using a binary search, but I think that rests on the equals() method as well, and I don't want to override that for other reasons of my own. Not to mention the fact that any ordering I impose on these items will be a bit of a kludge.
If all else fails, I guess I'll go linear on it, but that's just excessively inefficient from where I sit.
If all else fails, I guess I'll go linear on it, but that's just excessively inefficient from where I sit.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Typo there:
>>Collections.binarySearcc
should obviously be
Collections.binarySearch
>>Collections.binarySearcc
should obviously be
Collections.binarySearch
Oh - and you'll need to use the return value from that method too ;-)
> I was thinking of using a binary search
Binary search will work on sorted items. I seem to remember you said that groups do not have a natural ordering. Do they have any ordering at all?
Binary search will work on sorted items. I seem to remember you said that groups do not have a natural ordering. Do they have any ordering at all?
It's the Comparator that does the ordering. Brackets required here:
return (info1.getName().hashCode(
(Not quite awake yet ;-))
return (info1.getName().hashCode(
(Not quite awake yet ;-))
ASKER
Hrm. So, if I force an ordering on them -- whether via implementing the Comparable interface or writing a quick and dirty comparator -- I'll be able to do that? I can kludge an ordering that just arbitrarily ranks the name field and then use that. Collections.binarySearch never uses the equals() method at all, then?
>>I can kludge an ordering that just arbitrarily ranks the name field and then use that
Yes
>>Collections.binarySearch
Not with the method that passes a Comparator
Yes
>>Collections.binarySearch
Not with the method that passes a Comparator
Another option is to use the TreeMap class. Your key can be the "name" and "number". To find the closest match you can use the headMap(key) and tailMap(key) methods. To iterate through your list you can either use map.Values(), or Arrays.asList(map.values()
8-)
Info info toBeSearchedFor = new Info("girionis", 10);
for (int i=0; i<myList.size(); i++)
{
Info info = (Info) myList.get(i);
if (info.getName().equals(toB
{
// do whatever you want with the object.
// you might as well return it, in this cae you do not need th ebreak statement below
break;
}
}