Re: Iterator Related Design Problem
From: H. S. Lahman (h.lahman_at_verizon.net)
Date: 06/19/04
- Next message: Topmind: "Re: Dealing with the partial paradigm shift problem...."
- Previous message: H. S. Lahman: "Re: Factories and lazy objects"
- In reply to: Ken: "Iterator Related Design Problem"
- Next in thread: Robert C. Martin: "Re: Iterator Related Design Problem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 19 Jun 2004 16:05:23 GMT
Responding to Ken...
> 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.
1 provides X for <<ordered>> *
[Client] -------------------------------------- [Item]
+ priority
This seems to be a simple collection class problem. Choose an
appropriate collection class (ItemList) to implement the relationship
that maintains the priority order as Items are added.
However, because "priority" is mentioned, I'll bet there is a
requirement that you forgot to mention. B-) Item priority can change
over time while it is related to a Client.
Assuming your collection is efficient at handling additions and
deletions, then the simplest way around that problem is to delete/add
the item. That can be done by the priority setter in Item.
As far as criteria X is concerned, don't add any items to the collection
that don't match the X criteria.
But I'll bet there is yet another requirement you forgot to mention.
B-) X has a range of values from which Client may want to select. For
example, X is color and the client may wish to select the blue Item or
the green Item with the highest priority.
This is a much more interesting problem. However, it is an optimization
problem and without more information it is impossible to pick the best
algorithm. What one can say, though, is that it is an optimization
problem for the collection class implementation. That is, Client asks
for the highest priority green Item and the collection class lives to
find that Item as efficiently as possible.
For something like X being a color, an obvious solution is for ItemList
to maintain the order based upon a compound key of {color, priority}
with a lookaside list of the first occurrence of each color. (The
lookaside list would actually provide the Item with a single table
lookup.) One would still deal with changing priority (or color) as
described above.
If the number of colors are limited, the collection might maintain a
separate ordered list of priority for each color internally. The point
here is that the search optimization will always be part of the
collection class implementation.
[BTW, the golden rule of ordered relationships in OO development is that
one provides order as the elements are added to the collection rather
than through sorting. There are some exceptions, but they tend to be
quite rare. This is because at the OOA level one tends to think in
terms of set operations and sets are inherently ordered or inherently
not ordered so one doesn't impose order on a set after it is created.
(Some of the abstract action languages that support OOA do not even have
syntax for item-by-item iteration over members of a set.)]
>
> 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.
Sort by priority every time an Item is accessed?!? Then a linear
search?!? Yech. Whoever suggested this has clearly never worked in
R-T/E. B-))
>
> 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.
The problem here is that the optimization algorithm is actually being
implemented in the Client asking for an Item. That is, to ask for an
Item it has to understand a particular access mechanism for the
collection (i.e., Client is doing all the work in these steps). The
interface Client sees should just be something like:
ItemList.getHIghestPriorityItem (X)
(Assuming there are choices for X.)
*************
There is nothing wrong with me that could
not be cured by a capful of Drano.
H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions -- Put MDA to Work
http://www.pathfindermda.com
(888)-OOA-PATH
- Next message: Topmind: "Re: Dealing with the partial paradigm shift problem...."
- Previous message: H. S. Lahman: "Re: Factories and lazy objects"
- In reply to: Ken: "Iterator Related Design Problem"
- Next in thread: Robert C. Martin: "Re: Iterator Related Design Problem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
