Re: Merging Linked Lists

Patricia Shanahan wrote:


Can any of these support inserting a new element into the middle of the
ordering? Well, the first can't, and the third and fourth can if you do
the "BASIC line numbering trick" and give every item a position number,
where you leave gaps so you can fill in missing positions later. That's
a bit of a hack (but it can be done, e.g. using doubles and suggesting
the client code insert baz between foo and bar by setting
(foo.getPosition() + bar.getPosition())/2 as the position for baz.

Of course, once you are comparing stuff using a position number field
you set to suit, you're looking at a comparator that isn't consistent
with equals, which is going to bomb your TreeSet anyway. Now you need
the objects to use their position number to decide equality (and hash
code) too. You probably actually want to wrap them with a

public class PositionalHolder<T>
        implements Comparable<PositionalHolder<T>> {
    public double position;
    public T object;
    public PositionalHolder (T object, double position) {
        this.object = object;
        this.position = position;
    }
    @SuppressWarnings("unchecked")
    public void equals (Object x) {
        return (x == this)
            ||(x instanceof PositionalHolder
             && ((PositionalHolder)x).position
            == position);
    }
    public int hashCode () {
        return Double.valueOf(position).hashCode();
    }
    public int compareTo (PositionalHolder<T> other) {
        return (position < other.position)
            ?-1:((position > other.position)?1:0);
    }
    public void putBetween (PositionalHolder<T> x,
            PositionalHolder<T> y) {
        // Convenience method.
        position = (x.position + y.position)/2;
    }
}

Of course, Bad Things will likely happen if you a) use infs or nans as
positions, b) use the same position for multiple objects in the same
ordered collection, or c) change something's position while it's in one
rather than remove it, change its position, and then reinsert it. You
might want to prevent the last by making the PositionalHolder immutable
with a (x, object, y) "between" constructor, a just-an-object
constructor (position gets zero), a "before" constructor (object, y)
that uses y.position - 1, and an "after" constructor (x, object) that
uses x.position + 1. (This overload is clearly ambiguous if you try to
put a PositionalHolder inside another PositionalHolder but why the hell
would you?)