commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Eric Trepanier <eric_trepan...@mac.com>
Subject Re: [COLLECTIONS] Some more lobbying for the OrderedSet class
Date Wed, 30 Apr 2003 15:43:42 GMT
On 03-04-29 23:11, "Christopher (siege)  OBrien" <siege@preoccupied.net>
wrote:

> 
> Having the methods from the List interface added to a Set to make
> ListSet actually sounds pretty useful. How are you determining the
> success of a call to add(int,Object)? The List interface makes that
> method void rather than boolean, which seems like a problem when there's
> a possibility that by some criteria the Object may not have been
> actually inserted.

Well, having to support List means having to make some concessions:

- List typically accepts duplicate elements
- List accepts calls (add, contains, remove, ...) with a single parameter
  (these are really methods from the more generic Collection interface)

A List implementation can choose to not allow inserting nulls, in which case
it can throw an NPE. It could also throw another type of RuntimeException
(e.g. IllegalArgumentException) if the object to be added fails to meet some
specific criteria. Thus, no exception means insertion was successful.

Let's say I want to be able to code something like this:

/**
 * Takes a list of named objects, and reorders it according to the
 * specified list of object names.
 * 
 * @param catalog the list of named objects to be reordered
 * @param names the collection of object names that indicates the new order
 *        in which the named objects should be iterated
 */
void reorder(Catalog catalog, Collection names) {
    int size = catalog.size();
    if (size > 0) {
        int last = size - 1;
        int position = 0;
        for (Iterator i = names.iterator(); i.hasNext(); ) {
            Object name = i.next();
            int j = position;
            while ((j < last) &&
                   ((j = catalog.indexOfByName(name, j))) >= 0) {
                catalog.add(position++, catalog.remove(j++));
            }
        }
    }
}

A Catalog (in the code above) is a sub interface of List, which adds methods
like:
  - containsName(Object)
  - containsAllNames(Collection)
  - indexOfByName(Object)
  - indexOfByName(Object, int)  (used in the example above)
  - getByName(Object)
  - removeByName(Object)
  - ...

The catch is that in order to be compatible with the List interface and
hence support methods like add(Object) and addAll(Collection), it is
necessary for a Catalog implementation to know what the 'name' of an object
is. This can be done by introspection, assuming that the objects
being stored in the Catalog have a specific property that acts as the 'name'
property (example: Object getName()). Of course, the specific property name
could be specified in a Catalog-implementing class' constructor.

> How are you determining the existence of a duplicate? Is there an
> internal hash-table, or is it iterative?

Since a Catalog is really a List (not a Set), then I don't think it should
prevent duplicates (although a user could add some business logic to prevent
them).

> How are you determining and
> maintaining the internal order? With a linked-list, or with an array?

Two arrays, one of objects and one of object name. There is a problem with
this though: if the name property is mutable, then the Catalog has to be
notified of name changes to maintain the two arrays in sync. This could be
done via a listener mechanism at the cost of additional complexity and a
possible performance hit. It is of course preferable if the name property is
immutable, but this cannot be guaranteed.

> Combining this with the name lookup portion seems like it belongs to its
> own class though.

Well this really sounds like a 'Collection' to me (unlike a Map which is not
a Collection). That is why I would like to extend (and reuse) from Java's
Collection framework as much as possible.

> - Chris

Thanks for the comments though, they have allowed me to improve on my
current implementation.

Eric


---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message