+1 On Wed, Jan 19, 2011 at 10:24 PM, Blake Sullivan <blake.sulli...@oracle.com> wrote: > The JIRA has the complete story, but the basic issue is that operations that > create keys representing the ancestors of TreeModel keys can currently only > get those keys by essentially recursively calling > TreeModel.getContainerRowKey(). For list-based keys, this creates deeply > nested subLists. When these keys are used as keys into a HashMap, the > resulting behavior is n^3. For example, adding each of the keys in a 374 > element-deep path to a HashSet resulted in over 800 million calls to > ListIterator.next(). > > The two api parts to the solution are to add another method to TreeModel > that subclasses can override for greater efficiency: > > And also allow immutable lists to cache their hash codes with: > > /** > * Returns the nth ancestor rowKey or <code>null</code> if no such > ancestor exists. > * This is more efficient than calling > <code>getContainerRowKey(Object)</code> > * on each rowKey in turn. > * <p> > * If generationFromChild is 0, the childRowKey will be returned. > * <p> > * While for backwards compatibility, <code>getAncestorRowKey</code> is > implemented in terms > * of <code>getContainerRowKey</code>, Path-based subclasses should > implement > * <code>getContainerRowKey</code> in terms of > <code>getAncestorRowKey</code> to avoid > * creating deeply nested sublists of keys. > * @param childRowKey > * @param generationFromChild > * @return the nth ancestor rowKey or <code>null</code> if no such > ancestor exists > * @throws NullPointerException if childRowKey is <code>null</code> > * @throws IllegalArgumentException if generationFromChild is less than 0 > * @see #getContainerRowKey > */ > public Object getAncestorRowKey(Object childRowKey, int > generationFromChild) > > in TreeModel > > > /** > * Returns a new immutable wrapper list based on an existing list > <code>l</code>. > * <p> > * Once an immutable wrapper has been created on <code>l</code>, neither > * <code>l</code> nor the contents of List <code>l</code> may be changed. > * <p> > * In return for this restriction, the immutable List offers much faster > * implementations of operations such as <code>hashCode</code> and > * <code>subList</code>. This makes the instances returned for use as > keys into > * Sets or Maps, especially since the immutability restrictions are > identical. > * @param l The List to create an immutable wrapper on > * @return A new immutable list on <code>l</code> > * @throws NullPointerException if <code>l</code> is null. > */ > public static <T> List<? extends T> newImmutableList(List<? extends T> l) > > in org.apache.myfaces.trinidad.util.CollectionUtils > > -- Blake Sullivan > >
-- Matthias Wessendorf blog: http://matthiaswessendorf.wordpress.com/ sessions: http://www.slideshare.net/mwessendorf twitter: http://twitter.com/mwessendorf