Hi all,
It's my turn to have an DSL outage today, so I don't know when you will
actually read this mail. Upside: due to the lack of internet I finally had
some time to think really hard about some ordered relationship issues,
especially the collection side of things.
Dirk Olmes wrote:
> Andrus Adamchik wrote:
> > Hi Martin,
> > this feature is not there yet. In fact one of our contributors, Holger,
> > is currently working on it.
*cough*
> Well, I'm obviously not Holger but we've discussed the issue we sat
> together last time. Since Holger remains silent I thought I'd just let
> you know of the current thoughts we had.
Yes, and thanks for that. You summarized it well.
[List problems]
Dirk mentioned only the most obvious, user-visible problems with the
concept of an OrderedList. The issues are even more depressing in reality
when you actually try to implement it. Bottom line: it's _impossible_ to
implement a correct List that keeps itself ordered _all_ the time; you
_must_ choose between not-always-sorted and a broken List interface
contract. No alternatives.
Some highlights are:
- the externalization of operations via Collections (no categories,
remember?) yields untrackable, externally controlled modification of the
instance's elements. Goodbye state management.
- Collections.sort() uses a temporary Object[] for sorting and then just
walks the original list instance (which is a highly questionable approach
in itself), using set(int, Object) to plaster the sorted array over the
list indices. Too bad for you if your List has dared to override this
method; here's your ConcurrentModificationException - would you like a
StackOverflow due to endless recursion with that?
- removeRange(int, int) uses a ListIterator, which uses add(int, Object) -
which is an optional operation! So JavaSoft even violate their own API
contracts. You really don't want to override add(int, Object) either - at
least not really carefully.
As Dirk said, the biggest problem is the completely insufficient
separation of concerns in the interfaces - like List having set(int,
Object) and add(int, Object) methods is so bad and so apparently wrong
that my brain starts to hurt. Things like the Collection hierarchy in
Smalltalk or the NSArray/NSMutableArray separation in Foundation have
existed for years and these ignorant dolts just go ahead and ignore all
that, for absolutely no good reason except their lack of farsight...grrr.
*phew* sorry. I'll get back on track now.
However, there is hope. Thin, but there. After experimenting a lot with
different approaches like subclassing, having my own List instance and
delegating to that, experimenting which methods to override, which to
delegate and which to ignore, I now have a small, fast, flexible and
as-correct-as-possible-according-to-List OrderedList class:
- subclass of ArrayList
- implements an OrderedList subinterface of List
- with or without per-instance element Comparator
- as compatible with Collections.sort as posible: won't die, won't break
and stays compatible with List (in fact OrderedList now uses Collctions
internally)
- yes, it can get 'dirty'/out of sync (e.g. by Collections.sort) and/or
become unordered; this is caused mainly by set/add(int, Object). You can
give it a nudge and it will help itself.
- can be used as a plain List without unexpected side effects, except for
add(Object) which will not add to the end of the list but sort instead.
- uses fast binary search where possible, but the built-in ArrayList
linear search where binary search might stumble over duplicates, which are
allowed in Lists.
Overall I think this could well be used as a basis for further work with
ordered relationships. Source with JUnit test is available, just drop me a
line.
> Theoretically, if I add an object to a List I'd expect it to be
> accessible under the index I used to put the object into the List
> (list.add(1, theObject) == list.get(1) == theObject). Now, if the list
> will be automatically sorted I cannot be sure of that any more.
Yes. Additionally, many other things will NOT work because of
Iterator/ListIterator.
[snip]
> How could this be solved? One solution would be to use the Set interface
> rather than the List interface for relationships. I would think however
Yes. Set would really solve a number of API problems with List.
Unfortunately it would also be slow(er) and more cumbersome to use.
HashSets are implemented as HashMaps internally (how's that for dumb?) and
consequently use relatively large amounts of memory. I also thought about
using a SkipList which implements Set but is kick-ass fast and of course
directly ordered by an per-element int, which can also be e.g. the hash of
the inserted object or some other property. Might make for an interesting
alternative Set implementation.
> that List was chosen carefully. Set's objects cannot be accessed by
> their index, you'd always have to convert the set toArray() or something
> like that. I doubt if that would be practical.
Agreed, toArray or always recreating a List would be really terrible. One
good reason for index-based access is e.g. repetitions/loops in WO or
Tapestry. While the overall performance hit would perhaps not be
immediately noticeable in a test case, I'm not so sure about large-scale
operations. Not to mention API mismatches - many Java APIs simply can't
deal properly with Iterator chains or Sets.
Of course _my_ CoolSet class could have a cached, fast
zero-allocation/zero-copy listRepresentation(). Too bad I cannot fix the
Set interface itself.
So I guess it must be List after all.
-h
This archive was generated by hypermail 2.0.0 : Tue Dec 03 2002 - 22:20:43 EST