The JIRA <https://issues.apache.org/jira/browse/TRINIDAD-2013> 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
