HELP - Fast algorithm for Comparator implementation

[bdinmstig]

[I posted this to comp.programming but realised later that
comp.lang.java is probably more appropriate - apologies if you are
reading this for the 2nd time]

Hi. I need an implementation of java.util.Comparator with the
following features:

1. Given a (mutable) java.util.List instance of unspecified size at
construction time.

2. That List instance ALWAYS contains the objects it will be asked to
compare.

3. The compare(Object,Object) method should return its result based on
the relative positions of the specified objects in that List instance
- e.g. if o1 is at index 5 and o2 is at index 19, then compare(o1,o2)
should return a negative integer.

4. The compare(..) method will be called very often, so I am looking
for the most efficient algorithm possible.

5. It may be possible to be notified by that List instance whenever
its contents change, which would be relatively infrequent compared to
calls to the compare(..) method.

I appeal to all you clever people out there for a fast, elegant
solution to this problem. Let me say in advance I am extremely
grateful for your efforts!

Cheers.