# Iterator-Related Java Design Problem

Discussion in 'Java' started by Ken, Jun 19, 2004.

1. ### KenGuest

Hi. I'm looking for suggestions to this design problem. My target
language is Java, so I have access to its API. Here's the problem:

I have an unsorted list of Items. Let's say the list is called called
ItemList.

I need to find the item with the highest priority that also meets some
other criteria. Let's say that other criteria is called criteria X.

Someone suggested that we approach this by doing the following:

1- Make a copy of the ItemList (actually a list of references to the
Items on the first list, i.e., a shallow copy).

2- Sort this copy based on Item priority.

3- Sequentially search the prioritized list for the first Item to meet
criteria X.

I'm thinking a better approach would be to:

1- Make an iterator for the original list. This iterator would cycle
through items that meet criteria X.

2- For each Item returned by the iterator, check the priority. If
it's the highest one found so far, keep the Item's reference.

3- When the iterator can't provide any more items, you've got the item
with the highest priority that meets criteria X.

making a sorted copy of the original list. It also encapsulates
criteria X in the iterator.

Any thoughts? Better ideas?

Thanks!

Ken

Ken, Jun 19, 2004

2. ### Oscar kindGuest

Ken <> wrote:
> I have an unsorted list of Items. Let's say the list is called called
> ItemList.
>
> I need to find the item with the highest priority that also meets some
> other criteria. Let's say that other criteria is called criteria X.
>
> Someone suggested that we approach this by doing the following:
>
> 1- Make a copy of the ItemList [...].
> 2- Sort this copy based on Item priority.
> 3- Sequentially search the prioritized list for the first Item to meet
> criteria X.
>
> I'm thinking a better approach would be to:
>
> 1- Make an iterator [that only returns elements that meet criteria X].
> [2&3- Use the Iterator to manually search the Item with the highest
> priority].
>
> making a sorted copy of the original list. It also encapsulates
> criteria X in the iterator.

This last part is true, but you'd have to do the search yourself. Also,
you only have the Item with the highest priority: what if the requirements
change and you have to give the 3 top priority Items?

Using the Collections framework is more flexible:
1. Create a Comparator that sorts the elements by priority
2. Create a TreeSet that uses the Comparator
3. Add all Items that match criteria X to the TreeSet
4. Get the first Item of the TreeSet

Since you probably already have the code that checks criteria X, the only
difficult part could be the Comparator. But it isn't:

Comparator priorityComparator = new Comparator()
{
public int compare(Object o1, Object o2)
{
Item i1 = (Item)o1;
Item i2 = (Item)o2;
return i1.getPriority().compareTo(i2.getPriority());
}
}

kind regards,
Oscar

--
Oscar Kind http://home.hccnet.nl/okind/
Software Developer for contact information, see website

PGP Key fingerprint: 91F3 6C72 F465 5E98 C246 61D9 2C32 8E24 097B B4E2

Oscar kind, Jun 19, 2004

3. ### Chris SmithGuest

Ken wrote:
> I have an unsorted list of Items. Let's say the list is called called
> ItemList.
>
> I need to find the item with the highest priority that also meets some
> other criteria. Let's say that other criteria is called criteria X.

Seems to be that the best way would be to use Collections.max and pass
an appropriate Comparator. The comparator would need to rank any item
that fails X behind items that don't, and then sort secondarily on
priority. This would boil down to your second suggestion internally,
but would be much more readable.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

Chris Smith, Jun 19, 2004
4. ### =?ISO-8859-1?Q?Daniel_Sj=F6blom?=Guest

Ken wrote:
> Hi. I'm looking for suggestions to this design problem. My target
> language is Java, so I have access to its API. Here's the problem:
>
> I have an unsorted list of Items. Let's say the list is called called
> ItemList.
>
> I need to find the item with the highest priority that also meets some
> other criteria. Let's say that other criteria is called criteria X.
>
> Someone suggested that we approach this by doing the following:
>
> 1- Make a copy of the ItemList (actually a list of references to the
> Items on the first list, i.e., a shallow copy).
>
> 2- Sort this copy based on Item priority.
>
> 3- Sequentially search the prioritized list for the first Item to meet
> criteria X.
>
> I'm thinking a better approach would be to:
>
> 1- Make an iterator for the original list. This iterator would cycle
> through items that meet criteria X.
>
> 2- For each Item returned by the iterator, check the priority. If
> it's the highest one found so far, keep the Item's reference.
>
> 3- When the iterator can't provide any more items, you've got the item
> with the highest priority that meets criteria X.
>
> making a sorted copy of the original list. It also encapsulates
> criteria X in the iterator.

suggest you write a separate interface that checks the criteria, say:

interface Predicate
{
/* Returns true if object fills criteria, false otherwise */
boolean test(Object o);
}

Then you can easily write a method that will take an iterator and a
predicate as arguments and return a modified iterator that only returns
objects that fulfill the predicate. This code will work with *any*
--
Daniel Sjöblom
Remove _NOSPAM to reply by mail

=?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Jun 19, 2004
5. ### Eric SosmanGuest

Ken wrote:
> Hi. I'm looking for suggestions to this design problem. My target
> language is Java, so I have access to its API. Here's the problem:
>
> I have an unsorted list of Items. Let's say the list is called called
> ItemList.
>
> I need to find the item with the highest priority that also meets some
> other criteria. Let's say that other criteria is called criteria X.
>
> Someone suggested that we approach this by doing the following:
>
> 1- Make a copy of the ItemList (actually a list of references to the
> Items on the first list, i.e., a shallow copy).
>
> 2- Sort this copy based on Item priority.
>
> 3- Sequentially search the prioritized list for the first Item to meet
> criteria X.
>
> I'm thinking a better approach would be to:
>
> 1- Make an iterator for the original list. This iterator would cycle
> through items that meet criteria X.
>
> 2- For each Item returned by the iterator, check the priority. If
> it's the highest one found so far, keep the Item's reference.
>
> 3- When the iterator can't provide any more items, you've got the item
> with the highest priority that meets criteria X.
>
> making a sorted copy of the original list. It also encapsulates
> criteria X in the iterator.
>
> Any thoughts? Better ideas?

Much depends on whether you need to do this search
once or repeatedly, on how many different priorities exist,
on whether an item's priority can change while it's in
the list, on whether there's just one criterion X or many,
and so on and so on.

For a one-time search there's not much reason to spend
time and effort sorting the items or dreaming up fancy
data structures; just use some kind of sequential search
(Chris Smith's suggestion sounds best).

For repeated searches with a short list, sequential
search may still do better than fancier methods. An O(N)
method with a small coefficient may beat an O(log N) method
with a large coefficient, if N is small enough.

For repeated searches with a fixed X, you might keep
a separate priority list for each X value. If there are
|X| values and the items are fairly evenly distributed
among them, your linear (or fancier) search for the item
of highest priority needs to consider only 1/|X| of the
total items. (Observe the connection with hashing.)

... and so on, and so forth. There's no one way that's
"best" for all variations of the class of problems you
describe. Perhaps you'd offer a little more detail ...?

--

Eric Sosman, Jun 21, 2004