Iterator-Related Java Design Problem

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

  1. Ken

    Ken Guest

    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.

    What I like about this latter approach is that it precludes us from
    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
    #1
    1. Advertising

  2. Ken

    Oscar kind Guest

    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].
    >
    > What I like about this latter approach is that it precludes us from
    > 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
    #2
    1. Advertising

  3. Ken

    Chris Smith Guest

    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
    #3
  4. 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.
    >
    > What I like about this latter approach is that it precludes us from
    > making a sorted copy of the original list. It also encapsulates
    > criteria X in the iterator.


    Your approach is better. Maybe you already thought about this, but I
    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*
    collection, not just your ItemList.
    --
    Daniel Sjöblom
    Remove _NOSPAM to reply by mail
     
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Jun 19, 2004
    #4
  5. Ken

    Eric Sosman 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.
    >
    > What I like about this latter approach is that it precludes us from
    > 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
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,469
  2. greg
    Replies:
    6
    Views:
    483
    Dietmar Kuehl
    Jul 17, 2003
  3. Maxwell Hammer
    Replies:
    7
    Views:
    674
    Peter Hansen
    Jun 18, 2005
  4. toton

    Iterator related problem

    toton, Feb 7, 2007, in forum: C++
    Replies:
    0
    Views:
    275
    toton
    Feb 7, 2007
  5. Jim Anderson

    problem with iterator (map iterator)

    Jim Anderson, Jan 10, 2014, in forum: C++
    Replies:
    3
    Views:
    160
    Luca Risolia
    Jan 13, 2014
Loading...

Share This Page