org.openide.util.lookup
Class InheritanceTree

java.lang.Object
  extended by org.openide.util.lookup.InheritanceTree
All Implemented Interfaces:
java.io.Serializable, AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>

final class InheritanceTree
extends java.lang.Object
implements java.io.Serializable, AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>

A tree to represent classes with inheritance. Description of the data structure by Petr Nejedly:

So pretend I'm Lookup implementation. I've got a bunch of Items (e.g. setPairs() method), didn't do anything on them yet (no startup penalty) so I know nothing about them. Then I'll be asked for all instances implementing given interface or a class. I surely need to check all the Items now, as I don't know anything abou them. I surely don't want to call Item.getClass() as it will dismiss the whole effort. So all I have is Item.instanceOf() and I'll call it on every Item. I'll cache results, so the next time you'll ask me for the same interface/class, I'll answer immediatelly. But what if you ask me for another interface/class? I'll have to scan all Items for it again, unless I can be sure some of them can't implement it. The only source of this knowledge are the previous questions and my rulings on them. Here the algorithm have to be split into two paths. If you previously asked me for interfaces only, I'll have no hint for subsequent queries, but if you asked me for a class in history, and then for another class and these classes are not in inheritance relation (I can check hierarchy of lookup arguments, because they are already resolved/loaded) I can tell that those returned in previous query can't implement the newly asked class (they are in different hierarchy branch) and I need to ask less Items.

So if we use mostly classes for asking for services (and it is a trend to use abstract classes for this purpose in IDE anyway), this could be usable.

The data structure for separating the Items based on previous queries is simple tree, with every node tagged with one class. The tree's root is, naturally, java.lang.Object, is marked invited and initially contains all the Items. For every class query, the missing part of class hierarchy tree is created, the node of the class looked up is marked as invited and all Items from nearest invited parent (sperclass) are dragged to this node. The result are then all Items from this node and all the nodes deeper in hierarchy. Because it may be too complicated to walk through the children nodes, the results could be cached in the map. For interface lookup, there is a little hint in reality (interfaces and superinterfaces), but it would be harder to exploit it, so we could fall-back to walking through all the Items and cache results.

Author:
Jaroslav Tulach

Nested Class Summary
(package private) static class InheritanceTree.Node
          Node in the tree.
 
Constructor Summary
InheritanceTree()
          Constructor
 
Method Summary
 boolean add(AbstractLookup.Pair<?> item, java.util.ArrayList<java.lang.Class> affected)
          Adds an item into the tree.
 java.util.ArrayList<java.lang.Class> beginTransaction(int ensure)
          Initializes a modification operation by creating an object that will be passsed to all add, remove, retainAll methods and should collect enough information about the change to notify listeners about the transaction later
 AbstractLookup.ReferenceToResult cleanUpResult(Lookup.Template templ)
          Given the provided template, Do cleanup the results.
 void endTransaction(java.util.ArrayList<java.lang.Class> list, java.util.Set<AbstractLookup.R> allAffectedResults)
          Collects all affected results R that were modified in the given transaction.
<T> java.util.Enumeration<AbstractLookup.Pair<T>>
lookup(java.lang.Class<T> clazz)
          Queries for instances of given class.
 void print(java.io.PrintStream out, boolean instances)
          Prints debug messages.
 AbstractLookup.ReferenceToResult registerReferenceToResult(AbstractLookup.ReferenceToResult<?> newRef)
          Registers another reference to a result with the storage.
 void remove(AbstractLookup.Pair item, java.util.ArrayList<java.lang.Class> affected)
          Removes an item.
 void retainAll(java.util.Map retain, java.util.ArrayList<java.lang.Class> notify)
          Removes all items that are not present in the provided collection.
static boolean unsorted(java.util.Enumeration en)
          A method to check whether the enumeration returned from lookup method is sorted or is not
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

InheritanceTree

public InheritanceTree()
Constructor

Method Detail

add

public boolean add(AbstractLookup.Pair<?> item,
                   java.util.ArrayList<java.lang.Class> affected)
Adds an item into the tree.

Specified by:
add in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
item - to add
affected - transaction token
Returns:
true if the Item has been added for the first time or false if some other item equal to this one already existed in the lookup

remove

public void remove(AbstractLookup.Pair item,
                   java.util.ArrayList<java.lang.Class> affected)
Removes an item.

Specified by:
remove in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>

retainAll

public void retainAll(java.util.Map retain,
                      java.util.ArrayList<java.lang.Class> notify)
Removes all items that are not present in the provided collection.

Specified by:
retainAll in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
retain - collection of Pairs to keep them in
notify - set of Classes that has possibly changed

lookup

public <T> java.util.Enumeration<AbstractLookup.Pair<T>> lookup(java.lang.Class<T> clazz)
Queries for instances of given class.

Specified by:
lookup in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
clazz - the class to check
Returns:
enumeration of Item
See Also:
unsorted(java.util.Enumeration)

unsorted

public static boolean unsorted(java.util.Enumeration en)
A method to check whether the enumeration returned from lookup method is sorted or is not

Parameters:
en - enumeration to check
Returns:
true if it is unsorted and needs to be sorted to find pair with smallest index

print

public void print(java.io.PrintStream out,
                  boolean instances)
Prints debug messages.

Parameters:
out - stream to output to
instances - print also instances of the

registerReferenceToResult

public AbstractLookup.ReferenceToResult registerReferenceToResult(AbstractLookup.ReferenceToResult<?> newRef)
Description copied from interface: AbstractLookup.Storage
Registers another reference to a result with the storage. This method has also a special meaning.

Specified by:
registerReferenceToResult in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
newRef - the new reference to remember
Returns:
the previous reference that was kept (null if newRef is the first one) the applications is expected to link from newRef to this returned value to form a linked list

cleanUpResult

public AbstractLookup.ReferenceToResult cleanUpResult(Lookup.Template templ)
Description copied from interface: AbstractLookup.Storage
Given the provided template, Do cleanup the results.

Specified by:
cleanUpResult in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
templ - template of a result(s) that should be checked
Returns:
null if all references for this template were cleared or one of them

beginTransaction

public java.util.ArrayList<java.lang.Class> beginTransaction(int ensure)
Description copied from interface: AbstractLookup.Storage
Initializes a modification operation by creating an object that will be passsed to all add, remove, retainAll methods and should collect enough information about the change to notify listeners about the transaction later

Specified by:
beginTransaction in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
ensure - the amount of items that will appear in the storage after the modifications (-1 == remove one, -2 == add one, >= 0 the amount of objects at the end
Returns:
a token to identify the transaction

endTransaction

public void endTransaction(java.util.ArrayList<java.lang.Class> list,
                           java.util.Set<AbstractLookup.R> allAffectedResults)
Description copied from interface: AbstractLookup.Storage
Collects all affected results R that were modified in the given transaction.

Specified by:
endTransaction in interface AbstractLookup.Storage<java.util.ArrayList<java.lang.Class>>
Parameters:
list - the transaction indentification