Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Jim Janney <jjanney@shell.xmission.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
Date: Thu, 11 Oct 2012 14:17:22 -0600
Organization: Phibes vs. the Phantom
Lines: 62
Message-ID: <ydnvceg69wt.fsf@shell.xmission.com>
References: <k4jua8$77d$1@news.albasani.net> <ydn4nm38kpc.fsf@shell.xmission.com> <ydnzk3u74od.fsf@shell.xmission.com> <k544ha$hj0$1@dont-email.me> <ydnvcei70lu.fsf@shell.xmission.com> <ydnr4p66x16.fsf@shell.xmission.com> <6e7da532-e3bb-4b60-8792-71292dba187c@googlegroups.com> <ydnk3uy6u6r.fsf@shell.xmission.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: mx04.eternal-september.org; posting-host="75975abe3fe3503ca7350803ab98e478"; logging-data="31279"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/tUMxmRCND7eBXxtVWeva6"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
Cancel-Lock: sha1:UQymIVMDPjPcJFLmlU+yENK+rxI= sha1:6hitH4V67nz7uwA+cQEzbbGycPQ=
Xref: csiph.com comp.lang.java.programmer:19257

Jim Janney <jjanney@shell.xmission.com> writes:

> The ordering is defined by nextInsertionRank.  Making that a member of
> the map may not be the best choice.  This is not a finished product,
> only a sketch of an approach to the problem.  Some interesting bugs have
> been left as an exercise for the reader...

Here is a design I like better.  It reduces the coupling between classes
and better reflects the underlying concepts:

/**
 * Define an arbitrary ordering on a finite set of values.
 * The ordering is determined by the order of calls to {@code register}.
 */
public class ArbitraryOrder<T> implements Comparator<T> {
  private long nextInsertionRank = 0;
  private final Map<T, Long> insertionRanks = new HashMap<T, Long>();
  
  @Override
  public int compare(T o1, T o2) {
    Long rank1 = insertionRanks.get(o1);
    if (rank1 == null) {
      throw new IllegalArgumentException(o1 + " is not registered");
    }
    Long rank2 = insertionRanks.get(o2);
    if (rank2 == null) {
      throw new IllegalArgumentException(o2 + " is not registered");
    }
    return rank1.compareTo(rank2);
  }
  
  public void register(T value) {
    insertionRanks.put(value, nextInsertionRank++);
  }
  
  public void remove(Object key) {
    insertionRanks.remove(key);
  }
}

public class InsertionOrderedMap<K,V> extends TreeMap<K,V> {

  public InsertionOrderedMap() {
    super(new ArbitraryOrder<K>());
  }

  @Override
  public V put(K key, V value) {
    ((ArbitraryOrder<K>)comparator()).register(key);
    return super.put(key, value);
  };
  
  @Override
  public V remove(Object key) {
    V result = super.remove(key);
    ((ArbitraryOrder<K>)comparator()).remove(key);
    return result;
  }
}

-- 
Jim Janney