org.hd.d.pg2k.webSvr.exhibit
Class TreeFilterBean

java.lang.Object
  org.hd.d.pg2k.webSvr.exhibit.AbstractFilterBean
      org.hd.d.pg2k.webSvr.exhibit.TreeFilterBean

All Implemented Interfaces:

java.io.Serializable

public final class TreeFilterBean
extends AbstractFilterBean

This bean is designed to be used to support browsable sets of exhibits (ordered by name) as trees. Only the main portion of the name (not the category, nor attributes, etc) is relevant to the construction of the tree.

In general this allows a specified set of exhibits to be anchored at some partial URL in a WAR and the tail URL be used to select some sub-tree or a leaf of exhibits to display in a page.

This, like its base class, silently forces internal data structures to be recomputed if either the underlying data changes or the List input changes.

This logically maintains a tree organised by monocased prefix word sequences from the main stem (ie excluding attribute words, number-in-series, author and exhibit suffix) of the exhibits in the selected set.

This is thread-safe.

(This class contains a static convenience method for converting a partial trailing URL to a monocased (lowercased) prefix word sequence sequence.)

See Also:

Serialized Form

NO_ANSWER

private static final boolean[] NO_ANSWER

Fixed response for getUninterestingNodesFromMap() when the prefix is too short to answer.

JUST_ONE

private static final java.lang.Integer JUST_ONE

Used to indicate a single exhibit at or below the given node.

MIN_SIZE_FOR_CONCURRENCY

private static final int MIN_SIZE_FOR_CONCURRENCY

Minimum number of values worth attempting to filter in parallel; strictly positive. This plays off parallelism overhead vs available concurrency but should not be especially critical an order of magnitude either way.

See Also:

Constant Field Values

OPTNAMECS_CASE_INSENSITIVE_ORDER

private static final java.util.Comparator<java.lang.CharSequence> OPTNAMECS_CASE_INSENSITIVE_ORDER

Case-insensitive Comparator used for CharSequence where we know both args to actually be Name or ExhibitShort; not null. In particular we assume that is worth converting to the 'fast' forms for comparison.

ALLOW_NODE_SS_CONC

private static final boolean ALLOW_NODE_SS_CONC

Allow SorteSet concurrency (not just thread-safety) if true.

See Also:

Constant Field Values

CACHE_PREFIX_TO_COUNT

private static final boolean CACHE_PREFIX_TO_COUNT

If true then cache _prefixToCount for getExhibitCount().

See Also:

Constant Field Values

_prefixToCount

private transient java.lang.ref.SoftReference<java.util.Map<Name,java.util.Map<java.lang.CharSequence,java.lang.Integer>>> _prefixToCount

Cached Map from Name prefix word list to Integer count of exhibits with that prefix. Built on the fly as required.

Accessed under the instance lock.

Always held via a SoftReference regardless of general memory sensitivity of this bean since this is fairly quick to recompute on demand.

Not stored when the bean is serialized.

CACHE_PREFIX_MAP

private static final boolean CACHE_PREFIX_MAP

If true then cache the prefix map. Performance on large trees (exhibit sets) will be lousy if this is false.

See Also:

Constant Field Values

_cachedMap

private transient java.lang.Object _cachedMap

Cached map in format returned by computePrefixMap with List nodes. Map from each possible (lower-cased) legal input prefix (as a base Name instance) to a SortedSet or immutable List of any sub-nodes (as prefix word sequences ending with "-" (Name) and starting with the key) and the short names of any exhibits at that level (Name.ExhibitShort). The sort of the SortedSet or List is case-insensitive.

If this bean is memory-sensitive then the Map will be cached via a SoftReference, else the map itself (or null) is stored here.

Not stored when the bean is serialized.

serialVersionUID

private static final long serialVersionUID

Unique Serialisation class ID generated by http://random.hd.org/.

See Also:

Constant Field Values

ALLOW_PARALLEL

private static final boolean ALLOW_PARALLEL

If true allow parallelisation. May wish to turn off for profiling for example.

See Also:

Constant Field Values

TreeFilterBean

public TreeFilterBean()

selectPrefixesAndShortNames

public java.util.List<java.lang.CharSequence> selectPrefixesAndShortNames(javax.servlet.ServletContext ctxt,
                                                                          java.lang.CharSequence prefixWordList,
                                                                          java.util.List<Name.ExhibitFull> inputSet)
                                                                   throws java.io.IOException,
                                                                          java.lang.IllegalStateException

Gets List of exhibits from filtered set with given lowercased prefix (from the main-word stem); null if prefix is invalid. Returns a sorted (case-insensitive) unmodifiable List of:

• lowercase prefixes (as Name, ending in "-"; links to nodes further from the root and starting with this prefix),
• short exhibit names (as Name.ExhibitShort).

The data source is found automagically.

The data source must already have been initialised for this to work.

The result is a List of (short) exhibit names at this level (ie that contain no more main words) interleaved with the main-word prefixes of any longer exhibit names (that can be used as the basis of a hyperlink for example) as an immutable RandomAccess List of String values.

If the inputSet argument is null the whole set of exhibits is used, else the supplied set is used.

This will only (re)compute its result if:

• there are no cached results, or,
• the exhibit hash has changed, or,
• the argument List is not the same one presented before (its hash has changed), or,
• this is a memory-sensitive cache that has been automatically cleared.

This returns null if the prefix is invalid syntactically or if no item with that prefix exists. This result may lead the Web server to return a 404 error code.

A prefix of "" returns the root node of the tree.

Null names and names that do not represent items currently in the exhibit set are silently dropped.

Throws:

java.lang.IllegalStateException - if the filter has not been set

java.io.IOException

getPrefixMap

private java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> getPrefixMap(javax.servlet.ServletContext ctxt,
                                                                                      java.util.List<Name.ExhibitFull> inputSet,
                                                                                      boolean force)
                                                                               throws java.io.IOException,
                                                                                      java.lang.IllegalStateException

Internal routine to get the immutable prefix map (in List form); never null unless !force and out of date. May retrieve the data from cache and/or cache the data once computed.

Note that the key type is Name (and not any sub-class).

Parameters:

force - if true then force full computation if needed, else if false and out of date then return null

Throws:

java.io.IOException

java.lang.IllegalStateException

getUninterestingNodes

public boolean[] getUninterestingNodes(javax.servlet.ServletContext ctxt,
                                       java.lang.CharSequence prefixWordList,
                                       java.util.List<Name.ExhibitFull> inputSet)
                                throws java.io.IOException,
                                       java.lang.IllegalStateException

Given arguments as for selectPrefixesAndShortNames(), returns set of uninteresting parent nodes. See getUninterestingNodesFromMap() for the definition of the returned value.

Always forces recomputation (which may be very slow).

Throws:

java.lang.IllegalArgumentException - if prefix does not end with "-" or is otherwise ill-formed, or if prefix or any of its parents are not present in the map

java.lang.IllegalStateException - if the filter has not been set

java.io.IOException

See Also:

TreeFilterBean#getUninterestingNodesFromMap(Map, String)

getUninterestingNodes

public boolean[] getUninterestingNodes(javax.servlet.ServletContext ctxt,
                                       java.lang.CharSequence prefixWordList,
                                       java.util.List<Name.ExhibitFull> inputSet,
                                       boolean force)
                                throws java.io.IOException,
                                       java.lang.IllegalStateException

Given arguments as for selectPrefixesAndShortNames(), returns set of uninteresting parent nodes. See getUninterestingNodesFromMap() for the definition of the returned value.

Parameters:

force - if true then force recomputation if necessary, else return empty array if result not currently ready

Throws:

java.lang.IllegalArgumentException - if prefix does not end with "-" or is otherwise ill-formed, or if prefix or any of its parents are not present in the map

java.lang.IllegalStateException - if the filter has not been set

java.io.IOException

See Also:

TreeFilterBean#getUninterestingNodesFromMap(Map, String)

_nodesSameContent

private static boolean _nodesSameContent(java.util.Collection<java.lang.CharSequence> c1,
                                         java.util.Collection<java.lang.CharSequence> c2)

Tests two (non-null, sorted) nodes for equal content. Relies on the nodes having the same (sorted) iteration order, and compares the collections by iterating over them checking all elements pairwise for identical content.

getUninterestingNodesFromMap

public static boolean[] getUninterestingNodesFromMap(java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> m,
                                                     java.lang.CharSequence prefixWordList)

Given a Map as computed by computePrefixMap() and a prefix as passed to selectPrefixesAndFullNames(), returns set of uninteresting parent nodes. Given an prefix with n words, this returns a length n-1 boolean array for each parent node/word between (but excluding) the root and the specified node (where this is passed the root prefix, in which case a zero-length array), with a true element corresponding to each parent node/word in left to right (0 to high index) set for each "uninteresting" node. Other nodes are considered interesting.

The node immediately below the root is represented at element 0.

The returned array is private to the caller, ie the caller may alter it at will without causing any problems.

A node is considered "uninteresting" if it has exactly one child element which is either a prefix (so presumably the prefix of a node below it and thus a wasted click for the user), or a copy of the node below it (and thus not worth visiting in its own right).

A node is also considered uninteresting if it contains exactly the same information as its parent node.

If the input is not a well-formed word-prefix string the result is undefined.

Thus this should work with optimised and non-optimised maps.

This version of the method is public primarily to allow testing of the algorithm in jUnit, but is used internally. It does not alter any of its inputs and relies on them remaining unchanged during its use of them.

Throws:

java.lang.IllegalArgumentException - if prefix does not end with "-" or is otherwise ill-formed, or if prefix or any of its parents are not present in the map

getExhibitCount

public java.util.Map<java.lang.CharSequence,java.lang.Integer> getExhibitCount(javax.servlet.ServletContext ctxt,
                                                                               java.lang.CharSequence prefixWordList,
                                                                               java.util.List<Name.ExhibitFull> inputSet)
                                                                        throws java.io.IOException,
                                                                               java.lang.IllegalStateException

Given arguments as for selectPrefixesAndShortNames(), returns Map from name to count for all nodes at the given level; null if no nodes with given prefix. Returns an immutable Map from the given name to the count (Integer) of exhibits at or below that subnode (or just 1 for an exhibit rather than subnode).

Caches its results for speed.

The return value is intended to work with any (immutable) CharSequence key, eg String.

Returns:

Map from String (name) to Integer count; null if no such prefix

Throws:

java.lang.IllegalArgumentException - if prefix does not end with "-" or is otherwise ill-formed, or if prefix or any of its parents are not present in the map

java.lang.IllegalStateException - if the filter has not been set

java.io.IOException

See Also:

TreeFilterBean#getUninterestingNodesFromMap(Map, String)

getExhibitCountFromMap

private java.util.Map<java.lang.CharSequence,java.lang.Integer> getExhibitCountFromMap(java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> m,
                                                                                       Name prefixWordList)
                                                                                throws java.io.IOException,
                                                                                       java.lang.IllegalStateException

Given arguments as for selectPrefixesAndShortNames(), returns Map from name to count for all nodes at the given level; null if no nodes with given prefix. Returns an immutable Map from the given name (CharSequence) to the count (Integer) of exhibits at or below that subnode (or just 1 for an exhibit rather than subnode).

This computes the value recursively from the source Map, so may be slow on large exhibit sets, especially near the base.

The Map implementation allows lookup with any CharSequence (eg String).

Returns:

Map from String (name) to Integer count; null if no such prefix

Throws:

java.lang.IllegalArgumentException - if prefix does not end with "-" or is otherwise ill-formed, or if prefix or any of its parents are not present in the map

java.lang.IllegalStateException - if the filter has not been set

java.io.IOException

computePrefixMap

public static java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> computePrefixMap(java.util.List<Name.ExhibitFull> inputExhibitList,
                                                                                                boolean nodeAsSet,
                                                                                                boolean optimise)

Compute immutable Map from prefix word sequence (as Name) to SortedSet or sorted List of exhibits at this node and any sub-nodes; never null. This computes an immutable Map from each possible (lower-cased) legal input prefix to a mutable SortedSet or immutable List of any sub-nodes (as prefix word sequences ending with "-" (Name) and starting with the key) and the short names of any exhibits at that level (Name.ExhibitShort). The sort of the SortedSet or List is case-insensitive.

The argument nodeAsSet determines whether nodes are SortedSet or List objects; they provide the same iteration order and both support operations such as contains(). A SortedSet will be faster for lookups (and is faster for this routine to construct), whereas the (immutable) List form is more memory efficient and can be handed out directly by selectPrefixesAndShortNames() for example.

(As an optimisation sub-nodes that contain only links may be omitted.)

The Map returned is mutable as are its keys and values. To make access by multiple threads safe it must not be changed and/or other activity must be otherwise serialised.

This computes the Map based on the exhibit list supplied rather than the current AllExhibitProperties, though the results are undefined unless all the exhibits in the input list are part of the AllExhibitProperties.

This uses the attribute word set to help decide how to parse the exhibit names.

This routine is uncached and stateless. (It is exposed mainly to make testing easy.)

Note that the keys of the returned Map are of the base class Name for space efficiency.

We may attempt to generate this concurrently on multi-CPU hosts, especially for those such as Niagara where individual threads/CPUs may be very slow but there may be many of them available.

Parameters:

inputExhibitList - null for all exhibits else a an immutable thread-safe List of exhibits (as full exhibit names) for this tree; non-null, String, non-duplicated, valid full exhibit names (that should be a subset of those in AEP)

nodeAsSet - if true, the values in the Map are of type SortedSet else they of type List and are sorted and unmodifiable; in both cases the values are the same type (immutable CharSequence) and the iterator order is the same (case-insensitive) so for many uses they are algorithmically interchangeable though with different performance considerations for different use patterns

optimise - if true, the routine will remove links down the tree into nodes that contain exactly one sub-node link and no exhibits (and thus save a user some redundant clicking); and such link will instead point to the the first multi-entry node en route to the leaf exhibits or become a direct reference to the leaf exhibit if there is only one below this point or the link will be replaced with the expanded set of exhibits at its destination if small enough to display on one page

Returns:

Map from each possible (lower-cased) legal input prefix to a SortedSet or immutable List of any sub-nodes; never null

Throws:

java.lang.IllegalArgumentException - if any input is invalid and in particular if any name in the input exhibit list is not a valid exhibit name

_processOneExhibitName

private static void _processOneExhibitName(java.util.concurrent.ConcurrentMap<Name,java.util.Collection<java.lang.CharSequence>> workingMap,
                                           java.util.SortedSet<java.lang.String> attrWords,
                                           Name.ExhibitFull name)

Handle the insertion of the leaf node and parent nodes for one exhibit. This is intended to work safely and efficiently in the presence of concurrent operations to deal with other names.

convertNodesToList

private static void convertNodesToList(java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> workingMap)

Convert the supplied mutable Map's values to unmodifiable sorted List objects. These can be directly handed out by select(), for example.

We may also take this opportunity to fold duplicates together to trim memory use.

optimiseMap

private static void optimiseMap(java.util.Map<Name,java.util.Collection<java.lang.CharSequence>> workingMap)

Optimise the supplied mutable Map to eliminate redundant internal link traversals towards the leaves. We do this so that a user can make fewer clicks to reach exhibits or a point where they have to chose between two or more items.

This optimises the Map in situ.

This does not delete any nodes; arriving at an intermediate node will still work fine, linking downwards to the final target node (but also skipping any redundant intermediaries).

This routine is idempotent.

This routine must be run when the Map is complete and while the nodes are still of SortedSet type.

Parameters:

workingMap -

_insertRefToSubNode

private static void _insertRefToSubNode(java.util.concurrent.ConcurrentMap<Name,java.util.Collection<java.lang.CharSequence>> work,
                                        Name parentNode,
                                        Name subNode)

Helper method: inserts link from parent node to current node, creating parent node if need be. This may correspond to a hyperlink down the tree in a realised HTML page for example, allowing a user to browse sub-nodes with longer exhibit name stems.

Note the following conditions:

• The arguments must not be null.
• The Map and its values must be modifiable.
• The sub-node must be a valid exhibit stem word-prefix string ending in a dash, and the parent must be a prefix of it.
• The parent must be a valid exhibit stem word-prefix string ending in a dash, or "" if the root node.
• The map must not be in use by another thread while this routine is running.
  A subset of these conditions may be (explicitly) checked at run-time.

  Any new (thread-safe) set created is sorted keyed by parent case-insensitively.

_insertExhibit

private static void _insertExhibit(java.util.concurrent.ConcurrentMap<Name,java.util.Collection<java.lang.CharSequence>> work,
                                   Name stem,
                                   Name.ExhibitShort exhibitShortName)

Helper routine to insert exhibit (as Name.ExhibitShort) at its final node. Note that the stem must be lower-cased and (ignoring case) a prefix of the exhibit name, which in turn must be valid.

This will create the child node if need be.

The map must not be in use by another thread while this routine is running.

Any new set created is sorted case-insensitively.

Any subset of the conditions may be checked at runtime.

The exhibit name argument must be a short name.

makeCaseInsensitiveCSSortedMap

private static java.util.SortedSet<java.lang.CharSequence> makeCaseInsensitiveCSSortedMap()

Created thread-safe case-insensitive sorted Set of CharSequence instances for the tree nodes; never null. The implementation may be tuned for the run-time environment.

clearCache

public void clearCache()

Clear cached state. We have to chain to the super method first.

This method is available to a caller to help free memory, eg if data is known to have changed and so any cache would be invalid anyway, or if the user of this object has no further use for it.

Overrides:

clearCache in class AbstractFilterBean

convertTrailingURIToWordSequence

public static Name convertTrailingURIToWordSequence(java.lang.String trailingURI)
                                             throws java.lang.IllegalArgumentException

Convert trailing URL to monocased word sequence; never null. Converts a partial trailing URI of the form:

     [/]word1/word2/.../wordn/final.component
     

(containing no dashes or dots in the word components, and ignoring any leading slash and final (dot-but-not-slash-containing) component) into a monocased (lowercased) prefix word sequence sequence of the form:

     word1-word2-...wordn-
     

(note the trailing dash) which would be the prefix of any valid exhibit (and exhibit main stem) in the requested subtree, ignoring case.

Note in particular that these three are all parsed the same, ie give the same result:

     word1/word2/index.html
     word1/word2/
     word1/word2
 

If trailing words are attributes or number-in-series then the resulting sequence will not match any exhibits.

(This treats any runs of slashes as a single slash.)

The return value is in a compact (memory-efficient) form.

Throws:

java.lang.IllegalArgumentException - if a dash or non-word character is found in any but the final component of the URI, or the components are in any other way not legal words, or the result prefix would be too long to form part of a valid exhibit name