InheritanceTree


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  package org.openide.util.lookup;
20  
21  import org.openide.util.Enumerations;
22  import org.openide.util.Lookup;
23  import org.openide.util.lookup.AbstractLookup.Pair;
24  import org.openide.util.lookup.AbstractLookup.ReferenceIterator;
25  import org.openide.util.lookup.AbstractLookup.ReferenceToResult;
26  
27  import java.io.*;
28  
29  import java.lang.ref.WeakReference  ;
30  
31  import java.util.*;
32  
33  
34  /** A tree to represent classes with inheritance. Description of the
35   * data structure by Petr Nejedly:
36   * <P>
37   * So pretend I'm Lookup implementation. I've got a bunch of Items (e.g.
38   * setPairs() method),
39   * didn't do anything on them yet (no startup penalty) so I know nothing
40   * about them.
41   * Then I'll be asked for all instances implementing given interface or a
42   * class. I surely need
43   * to check all the Items now, as I don't know anything abou them. I surely
44   * don't want to call
45   * Item.getClass() as it will dismiss the whole effort. So all I have is
46   * Item.instanceOf()
47   * and I'll call it on every Item. I'll cache results, so the next time
48   * you'll ask me for
49   * the same interface/class, I'll answer immediatelly. But what if you ask
50   * me for another
51   * interface/class? I'll have to scan all Items for it again, unless I can
52   * be sure some
53   * of them can't implement it. The only source of this knowledge are the
54   * previous questions
55   * and my rulings on them. Here the algorithm have to be split into two
56   * paths. If you
57   * previously asked me for interfaces only, I'll have no hint for
58   * subsequent queries,
59   * but if you asked me for a class in history, and then for another class
60   * and these classes
61   * are not in inheritance relation (I can check hierarchy of lookup
62   * arguments, because
63   * they are already resolved/loaded) I can tell that those returned in
64   * previous query can't
65   * implement the newly asked class (they are in different hierarchy branch)
66   * and I need to
67   * ask less Items.
68   * <P>
69   * So if we use mostly classes for asking for services (and it is a trend
70   * to use
71   * abstract classes for this purpose in IDE anyway), this could be usable.
72   * <P>
73   * The data structure for separating the Items based on previous queries is
74   * simple
75   * tree, with every node tagged with one class. The tree's root is,
76   * naturally,
77   * java.lang.Object, is marked invited and initially contains all the
78   * Items.
79   * For every class query, the missing part of class hierarchy tree is
80   * created,
81   * the node of the class looked up is marked as invited and all Items from
82   * nearest
83   * invited parent (sperclass) are dragged to this node. The result are then
84   * all
85   * Items from this node and all the nodes deeper in hierarchy. Because it
86   * may
87   * be too complicated to walk through the children nodes, the results could
88   * be
89   * cached in the map.
90   * For interface lookup, there is a little hint in reality (interfaces
91   * and superinterfaces), but it would be harder to exploit it, so we could
92   * fall-back
93   * to walking through all the Items and cache results.
94   *
95   *
96   * @author  Jaroslav Tulach
97   */
98  final class InheritanceTree extends Object  
99  implements Serializable, AbstractLookup.Storage<ArrayList<Class  >> {
100     private static final long serialVersionUID = 1L;
101 
102     /** the root item (represents Object) */
103     private transient Node object;
104 
105     /** Map of queried interfaces.
106      * <p>Type: <code>Map&lt;Class, (Collection&lt;AbstractLookup.Pair&gt; | AbstractLookup.Pair)&gt;</code>
107      */
108     private transient Map<Class  ,Object  > interfaces;
109 
110     /** Map (Class, ReferenceToResult) of all listeners that are waiting in
111      * changes in class Class
112      */
113     private transient Map<Class  ,ReferenceToResult> reg;
114 
115     /** Constructor
116      */
117     public InheritanceTree() {
118         object = new Node(java.lang.Object  .class);
119     }
120 
121     private void writeObject(ObjectOutputStream oos) throws IOException {
122         oos.writeObject(object);
123 
124         if (interfaces != null) {
125             Iterator it = interfaces.entrySet().iterator();
126 
127             while (it.hasNext()) {
128                 Map.Entry e = (Map.Entry) it.next();
129                 Class   c = (Class  ) e.getKey();
130                 oos.writeObject(c.getName());
131 
132                 Object   o = e.getValue();
133 
134                 if (!(o instanceof Collection) && !(o instanceof AbstractLookup.Pair)) {
135                     throw new ClassCastException  (String.valueOf(o));
136                 }
137 
138                 oos.writeObject(o);
139             }
140         }
141 
142         oos.writeObject(null);
143     }
144 
145     private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException   {
146         object = (Node) ois.readObject();
147         interfaces = new WeakHashMap<Class  ,Object  >();
148 
149         String   clazz;
150         ClassLoader   l = Lookup.getDefault().lookup(ClassLoader  .class);
151 
152         while ((clazz = (String  ) ois.readObject()) != null) {
153             Object   o = ois.readObject();
154 
155             if (!(o instanceof Collection) && !(o instanceof AbstractLookup.Pair)) {
156                 throw new ClassCastException  (String.valueOf(o));
157             }
158 
159             Class   c = Class.forName(clazz, false, l);
160             interfaces.put(c, o);
161         }
162     }
163 
164     /** Adds an item into the tree.
165     * @param item to add
166     * @return true if the Item has been added for the first time or false if some other
167     *    item equal to this one already existed in the lookup
168     */
169     public boolean add(AbstractLookup.Pair<?> item, ArrayList<Class  > affected) {
170         Node node = registerClass(object, item);
171 
172         affected.add(node.getType());
173 
174         if (node.assignItem(this, item)) {
175             // this is the first item added to n.items
176             // ok, we have to test interfaces too
177         } else {
178             // equal item is already there => stop processing
179             return false;
180         }
181 
182         boolean registeredAsInterface = registerInterface(item, affected);
183 
184         return registeredAsInterface;
185     }
186 
187     /** Removes an item.
188     */
189     public void remove(AbstractLookup.Pair item, ArrayList<Class  > affected) {
190         Node n = removeClass(object, item);
191 
192         if (n != null) {
193             affected.add(n.getType());
194         }
195 
196         removeInterface(item, affected);
197     }
198 
199     /** Removes all items that are not present in the provided collection.
200     * @param retain collection of Pairs to keep them in
201     * @param notify set of Classes that has possibly changed
202     */
203     public void retainAll(Map retain, ArrayList<Class  > notify) {
204         retainAllInterface(retain, notify);
205         retainAllClasses(object, retain, notify);
206     }
207 
208     /** Queries for instances of given class.
209     * @param clazz the class to check
210     * @return enumeration of Item
211     * @see #unsorted
212     */
213     @SuppressWarnings  ("unchecked")
214     public <T> Enumeration<Pair<T>> lookup(Class  <T> clazz) {
215         if ((clazz != null) && clazz.isInterface()) {
216             return (Enumeration)searchInterface(clazz);
217         } else {
218             return (Enumeration)searchClass(object, clazz);
219         }
220     }
221 
222     /** A method to check whether the enumeration returned from
223      * lookup method is sorted or is not
224      * @param en enumeration to check
225      * @return true if it is unsorted and needs to be sorted to find
226      *   pair with smallest index
227      */
228     public static boolean unsorted(Enumeration en) {
229         return en instanceof NeedsSortEnum;
230     }
231 
232     /** Prints debug messages.
233      * @param out stream to output to
234      * @param instances print also instances of the
235      */
236     public void print(java.io.PrintStream   out, boolean instances) {
237         printNode(object, "", out, instances); // NOI18N
238     }
239 
240     //
241     // methods to work on classes which are not interfaces
242     //
243 
244     /** Searches the subtree and register the item where necessary.
245     * @return the node that should contain the item
246     */
247     private static Node registerClass(Node n, AbstractLookup.Pair item) {
248         if (!n.accepts(item)) {
249             return null;
250         }
251 
252         if (n.children != null) {
253             Iterator it = n.children.iterator();
254 
255             for (;;) {
256                 Node ch = extractNode(it);
257 
258                 if (ch == null) {
259                     break;
260                 }
261 
262                 Node result = registerClass(ch, item);
263 
264                 if (result != null) {
265                     // it is in subclass, in case of classes, it cannot
266                     // be any other class
267                     return result;
268                 }
269             }
270         }
271 
272         // ok, nobody of our subclasses wants the class, I'll take it
273         return n;
274     }
275 
276     /** Removes the item from the tree of objects.
277     * @return most narrow class that this item was removed from
278     */
279     private static Node removeClass(Node n, AbstractLookup.Pair item) {
280         if (!n.accepts(item)) {
281             return null;
282         }
283 
284         if ((n.items != null) && n.items.remove(item)) {
285             // this node really contains the item
286             return n;
287         }
288 
289         if (n.children != null) {
290             Iterator it = n.children.iterator();
291 
292             for (;;) {
293                 Node ch = extractNode(it);
294 
295                 if (ch == null) {
296                     break;
297                 }
298 
299                 Node result = removeClass(ch, item);
300 
301                 // If the children node was emptied, remove it if possible.
302                 if (((ch.items == null) || ch.items.isEmpty()) && ((ch.children == null) || ch.children.isEmpty())) {
303                     it.remove();
304                 }
305 
306                 if (result != null) {
307                     // it is in subclass, in case of classes, it cannot
308                     // be any other class
309                     return result;
310                 }
311             }
312         }
313 
314         // nobody found
315         return null;
316     }
317 
318     /** Finds a node that represents a class.
319     * @param n node to search from
320     * @param clazz the clazz to find
321     * @return node that represents clazz in the tree or null if the clazz is not
322     *    represented under the node n
323     */
324     private Node classToNode(final Node n, final Class  <?> clazz) {
325         if (!n.accepts(clazz)) {
326             // nothing from us
327             return null;
328         }
329 
330         if (n.getType() == clazz) {
331             // we have found what we need
332             return n;
333         }
334 
335         if (n.children != null) {
336             // have to proceed to children
337             Iterator it = n.children.iterator();
338 
339             for (;;) {
340                 final Node ch = extractNode(it);
341 
342                 if (ch == null) {
343                     break;
344                 }
345 
346                 Node found = classToNode(ch, clazz);
347 
348                 if ((found != null) && ch.deserialized()) {
349                     class VerifyJob implements AbstractLookup.ISE.Job {
350                         private AbstractLookup.Pair<?>[] pairs;
351                         private boolean[] answers;
352 
353                         public VerifyJob(Collection<Pair> items) {
354                             if (items != null) {
355                                 pairs = items.toArray(new AbstractLookup.Pair[0]);
356                             }
357                         }
358 
359                         public void before() {
360                             // make sure the node is converted into deserialized state
361                             ch.deserialized();
362 
363                             if (pairs != null) {
364                                 answers = new boolean[pairs.length];
365 
366                                 for (int i = 0; i < pairs.length; i++) {
367                                     answers[i] = pairs[i].instanceOf(clazz);
368                                 }
369                             }
370                         }
371 
372                         public void inside() {
373                             if (pairs != null) {
374                                 for (int i = 0; i < pairs.length; i++) {
375                                     if (answers[i]) {
376                                         ch.assignItem(InheritanceTree.this, pairs[i]);
377                                         n.items.remove(pairs[i]);
378                                     }
379                                 }
380                             }
381 
382                             if (n.children != null) {
383                                 // consolidate all nodes that represent the same class
384                                 HashMap<Class  ,Node> nodes = new HashMap<Class  ,Node>(n.children.size() * 3);
385 
386                                 Iterator child = n.children.iterator();
387 
388                                 while (child.hasNext()) {
389                                     Node node = extractNode(child);
390                                     Node prev = nodes.put(node.getType(), node);
391 
392                                     if (prev != null) {
393                                         child.remove();
394                                         nodes.put(node.getType(), prev);
395 
396                                         // mark as being deserialized
397                                         prev.markDeserialized();
398 
399                                         if (prev.children == null) {
400                                             prev.children = node.children;
401                                         } else {
402                                             if (node.children != null) {
403                                                 prev.children.addAll(node.children);
404                                             }
405                                         }
406 
407                                         if (node.items != null) {
408                                             Iterator items = node.items.iterator();
409 
410                                             while (items.hasNext()) {
411                                                 AbstractLookup.Pair item = (AbstractLookup.Pair) items.next();
412                                                 prev.assignItem(InheritanceTree.this, item);
413                                             }
414                                         }
415                                     }
416                                 }
417                             }
418                         }
419                     }
420 
421                     VerifyJob verify = new VerifyJob(n.items);
422 
423                     try {
424                         verify.before();
425                     } catch (AbstractLookup.ISE ex) {
426                         // mark deserialized again
427                         ch.markDeserialized();
428                         ex.registerJob(verify);
429                         throw ex;
430                     }
431 
432                     verify.inside();
433 
434                     found = classToNode(ch, clazz);
435                 }
436 
437                 if (found != null) {
438                     // class found in one of subnodes
439                     return found;
440                 }
441             }
442         }
443 
444         class TwoJobs implements AbstractLookup.ISE.Job {
445             private AbstractLookup.Pair[] pairs;
446             private boolean[] answers;
447             private Node newNode;
448 
449             public void before() {
450                 // have to create new subnode and possibly reparent one of my own
451                 // but all changes can be done only if we will not be interrupted from
452                 // outside - e.g. instanceOf methods will not throw exception
453                 // first of all let's compute the answers to method instanceOf
454                 AbstractLookup.Pair[] arr = null;
455                 boolean[] boolArr = null;
456 
457                 if (n.items != null) {
458                     arr = new AbstractLookup.Pair[n.items.size()];
459                     boolArr = new boolean[n.items.size()];
460 
461                     int i = 0;
462                     Iterator<Pair> it = n.items.iterator();
463 
464                     while (it.hasNext()) {
465                         AbstractLookup.Pair<?> item = it.next();
466                         arr[i] = item;
467                         boolArr[i] = item.instanceOf(clazz);
468                         i++;
469                     }
470                 }
471 
472                 pairs = arr;
473                 answers = boolArr;
474             }
475 
476             public void inside() {
477                 // test if the query has not chagned since
478                 if (pairs != null) {
479                     if (!Arrays.equals(n.items.toArray(), pairs)) {
480                         // ok, let try once more
481                         return;
482                     }
483                 }
484 
485                 internal();
486             }
487 
488             public void internal() {
489                 ArrayList<Node> reparent = null;
490 
491                 if (n.children == null) {
492                     n.children = new ArrayList<Node>();
493                 } else {
494                     // scan thru all my nodes if some of them are not a subclass
495                     // of clazz => then they would need to become child of newNode
496                     Iterator it = n.children.iterator();
497 
498                     for (;;) {
499                         Node r = extractNode(it);
500 
501                         if (r == null) {
502                             break;
503                         }
504 
505                         if (clazz.isAssignableFrom(r.getType())) {
506                             if (reparent == null) {
507                                 reparent = new ArrayList<Node>();
508                             }
509 
510                             reparent.add(r);
511                             it.remove();
512                         }
513                     }
514                 }
515 
516                 newNode = new Node(clazz);
517                 n.children.add(newNode);
518 
519                 if (reparent != null) {
520                     // reassing reparent node as a child of newNode
521                     newNode.children = reparent;
522                 }
523 
524                 // now take all my items that are instances of that class and
525                 // reasign them
526                 if (n.items != null) {
527                     Iterator it = n.items.iterator();
528                     int i = 0;
529 
530                     while (it.hasNext()) {
531                         AbstractLookup.Pair item = (AbstractLookup.Pair) it.next();
532 
533                         if (answers[i]) { // answers[i] is precomputed value of item.instanceOf (clazz))
534                             it.remove();
535                             newNode.assignItem(InheritanceTree.this, pairs[i]);
536                         }
537 
538                         i++;
539                     }
540                 }
541             }
542         }
543 
544         TwoJobs j = new TwoJobs();
545 
546         try {
547             j.before();
548         } catch (AbstractLookup.ISE ex) {
549             // ok, it is not possible to call instanceOf now, let's 
550             // schedule it for later
551             // so register recovery job 
552             ex.registerJob(j);
553             throw ex;
554         }
555 
556         j.internal();
557 
558         // newNode represents my clazz
559         return j.newNode;
560     }
561 
562     /** Search for a requested class.
563     * @return enumeration of Pair
564     */
565     private Enumeration<Pair> searchClass(Node n, Class  <?> clazz) {
566         if (clazz != null) {
567             n = classToNode(n, clazz);
568         }
569 
570         if (n == null) {
571             // not for us
572             return org.openide.util.Enumerations.empty();
573         } else {
574             return nodeToEnum(n);
575         }
576     }
577 
578     /** Retains all classes. Removes nodes which items and children are emptied, works
579      * recursivelly from specified root node.
580      * @param node root node from which to start to process the tree
581      * @param retain a map from (Item, AbstractLookup.Info) that describes which items to retain
582      *    and witch integer to assign them
583      * @param notify collection of classes will be changed
584      * @return <code>true<code> if some items were changed and node items and children are emptied,
585      * those nodes, excluding root, will be removed from tree */
586     private boolean retainAllClasses(Node node, Map retain, Collection<Class  > notify) {
587         boolean retained = false;
588 
589         if ((node.items != null) && (retain != null)) {
590             Iterator<Pair> it = node.items.iterator();
591 
592             while (it.hasNext()) {
593                 AbstractLookup.Pair<?> item = it.next();
594                 AbstractLookup.Info n = (AbstractLookup.Info) retain.remove(item);
595 
596                 if (n == null) {
597                     // remove this item, it should not be there
598                     it.remove();
599                     retained = true;
600                 } else {
601                     // change the index
602                     if (item.getIndex() != n.index) {
603                         item.setIndex(null, n.index);
604 
605                         //                        notify.addAll ((ArrayList)n.transaction);
606                     }
607                 }
608             }
609 
610             if (retained && (notify != null)) {
611                 // type of this node has been changed
612                 notify.add(node.getType());
613             }
614         }
615 
616         if (node.children != null) {
617             for (Iterator it = node.children.iterator();;) {
618                 Node ch = extractNode(it);
619 
620                 if (ch == null) {
621                     break;
622                 }
623 
624                 boolean result = retainAllClasses(ch, retain, notify);
625 
626                 if (result) {
627                     // The children node was emptied and has no children -> remove it.
628                     it.remove();
629                 }
630             }
631         }
632 
633         return retained && node.items.isEmpty() && ((node.children == null) || node.children.isEmpty());
634     }
635 
636     /** A method that creates enumeration of all items under given node.
637      *
638      * @param n node to create enumeration for
639      * @return enumeration of Pairs
640      */
641     private static Enumeration<Pair> nodeToEnum(Node n) {
642         if (n.children == null) {
643             // create a simple enumeration because we do not have children
644             Enumeration<Pair> e;
645             if (n.items == null) {
646                 e = Enumerations.empty();
647             } else {
648                 e = Collections.enumeration(n.items);
649             }
650             return e;
651         }
652 
653         // we have found what we need
654         // now we have to just build the enumeration
655         class DeepAndItems implements Enumerations.Processor<Node,Enumeration<Pair>> {
656             public Enumeration<Pair> process(Node n2, Collection<Node> toAdd) {
657                 if (n2.children != null) {
658                     toAdd.addAll(n2.children);
659                 }
660 
661                 if ((n2.items == null) || n2.items.isEmpty()) {
662                     return Enumerations.empty();
663                 } else {
664                     return Collections.enumeration(n2.items);
665                 }
666             }
667         }
668 
669         Enumeration<Enumeration<Pair>> en = Enumerations.queue(
670             // initial node is our current one
671             Enumerations.singleton(n), new DeepAndItems()
672         );
673         Enumeration<Pair> all = Enumerations.concat(en);
674         // create enumeration of Items
675         return new NeedsSortEnum<Pair>(all);
676     }
677 
678     //
679     // Methods to work on interfaces
680     // 
681 
682     /** Registers an item with interfaces.
683     * @param item item to register
684     * @param affected list of classes that were affected
685     * @return false if similar item has already been registered
686     */
687     @SuppressWarnings  ("unchecked")
688     private boolean registerInterface(AbstractLookup.Pair<?> item, Collection<Class  > affected) {
689         if (interfaces == null) {
690             return true;
691         }
692 
693         Iterator<Map.Entry<Class  ,Object  >> it = interfaces.entrySet().iterator();
694 
695         while (it.hasNext()) {
696             Map.Entry<Class  ,Object  > entry = it.next();
697             Class  <?> iface = entry.getKey();
698 
699             if (item.instanceOf(iface)) {
700                 Object   value = entry.getValue();
701 
702                 if (value instanceof Collection) {
703                     Collection<Object  > set = (Collection<Object  >) value;
704 
705                     if (!set.add(item)) {
706                         // item is already there, probably (if everything is correct) is registered in 
707                         // all other ifaces too, so stop additional testing
708                         return false;
709                     }
710                 } else {
711                     // there is just one pair right now
712                     if (value.equals(item)) {
713                         // item is there => stop processing (same as above)
714                         return false;
715                     }
716 
717                     // otherwise replace the single item with ArrayList
718                     ArrayList<Object  > ll = new ArrayList<Object  >(3);
719                     ll.add(value);
720                     ll.add(item);
721                     entry.setValue(ll);
722                 }
723 
724                 affected.add(iface);
725             }
726         }
727 
728         return true;
729     }
730 
731     /** Removes interface.
732     * @param item item to register
733     * @param affected list of classes that were affected
734     */
735     @SuppressWarnings  ("unchecked")
736     private void removeInterface(AbstractLookup.Pair item, Collection affected) {
737         if (interfaces == null) {
738             return;
739         }
740 
741         Iterator it = interfaces.entrySet().iterator();
742 
743         while (it.hasNext()) {
744             Map.Entry entry = (Map.Entry) it.next();
745             Object   value = entry.getValue();
746 
747             if (value instanceof Collection) {
748                 Collection set = (Collection) value;
749 
750                 if (set.remove(item)) {
751                     if (set.size() == 1) {
752                         // if there is just one item remaining change to single item mode
753                         entry.setValue(set.iterator().next());
754                     }
755 
756                     // adds the Class the item was register to into affected
757                     affected.add(entry.getKey());
758                 }
759             } else {
760                 // single item value
761                 if (value.equals(item)) {
762                     // Emptied -> remove.
763                     it.remove();
764 
765                     affected.add(entry.getKey());
766                 }
767             }
768         }
769     }
770 
771     /** Retains some items.
772     * @param retainItems items to retain and their mapping to index numbers
773     *    (AbstractLookup.Pair -> AbstractLookup.Info)
774     * @param affected list of classes that were affected
775     */
776     @SuppressWarnings  ("unchecked")
777     private void retainAllInterface(Map retainItems, Collection affected) {
778         if (interfaces == null) {
779             return;
780         }
781 
782         Iterator it = interfaces.entrySet().iterator();
783 
784         while (it.hasNext()) {
785             Map.Entry entry = (Map.Entry) it.next();
786             Object   value = entry.getValue();
787 
788             HashMap<?,?> retain = new HashMap(retainItems);
789 
790             Iterator elems;
791             boolean multi = value instanceof Collection;
792 
793             if (multi) {
794                 // collection mode
795                 elems = ((Collection) value).iterator();
796             } else {
797                 // single item mode
798                 elems = Collections.singleton(value).iterator();
799             }
800 
801             boolean changed = false;
802             boolean reordered = false;
803 
804             while (elems.hasNext()) {
805                 AbstractLookup.Pair p = (AbstractLookup.Pair) elems.next();
806 
807                 AbstractLookup.Info n = (AbstractLookup.Info) retain.remove(p);
808 
809                 if (n == null) {
810                     if (multi) {
811                         // remove it
812                         elems.remove();
813                     }
814 
815                     changed = true;
816                 } else {
817                     if (p.getIndex() != n.index) {
818                         // improve the index
819                         p.setIndex(null, n.index);
820 
821                         //                    affected.addAll ((ArrayList)n.transaction);
822                         reordered = true;
823                     }
824                 }
825             }
826 
827             if (reordered && value instanceof List) {
828                 // if reordered, than update the order in the collection
829                 List l = (List) value;
830                 Collections.sort(l, ALPairComparator.DEFAULT);
831             }
832 
833             if (changed) {
834                 if (multi) {
835                     Collection c = (Collection) value;
836 
837                     if (c.size() == 1) {
838                         // back to single item mode
839                         entry.setValue(c.iterator().next());
840                     }
841                 } else {
842                     // remove in single mode => remove completely
843                     it.remove();
844                 }
845 
846                 // adds the Class the item was register to into affected
847                 affected.add(entry.getKey());
848             }
849         }
850     }
851 
852     /** Searches for a clazz between interfaces.
853     * @param clazz class to search for
854     * @return enumeration of Items
855     */
856     @SuppressWarnings  ("unchecked")
857     private Enumeration<Pair> searchInterface(final Class  <?> clazz) {
858         if (interfaces == null) {
859             // first call for interface, only initialize
860             interfaces = new WeakHashMap();
861         }
862 
863         Object   obj = interfaces.get(clazz);
864 
865         if (obj == null) {
866             // set of items
867             AbstractLookup.Pair one = null;
868             ArrayList items = null;
869 
870             Enumeration en = lookup(Object  .class);
871 
872             while (en.hasMoreElements()) {
873                 AbstractLookup.Pair it = (AbstractLookup.Pair) en.nextElement();
874 
875                 if (it.instanceOf(clazz)) {
876                     // ok, this item implements given clazz
877                     if (one == null) {
878                         one = it;
879                     } else {
880                         if (items == null) {
881                             items = new ArrayList(3);
882                             items.add(one);
883                         }
884 
885                         items.add(it);
886                     }
887                 }
888             }
889 
890             if ((items == null) && (one != null)) {
891                 // single item mode
892                 interfaces.put(clazz, one);
893 
894                 return org.openide.util.Enumerations.singleton(one);
895             } else {
896                 if (items == null) {
897                     items = new ArrayList(2);
898                 }
899 
900                 interfaces.put(clazz, items);
901 
902                 return Collections.enumeration(items);
903             }
904         } else {
905             if (obj instanceof Collection) {
906                 return Collections.enumeration((Collection) obj);
907             } else {
908                 // single item mode
909                 return org.openide.util.Enumerations.singleton((Pair)obj);
910             }
911         }
912     }
913 
914     /** Extracts a node from an iterator, returning null if no next element found
915      */
916     private static Node extractNode(Iterator it) {
917         while (it.hasNext()) {
918             Node n = (Node) it.next();
919 
920             if (n.get() == null) {
921                 it.remove();
922             } else {
923                 return n;
924             }
925         }
926 
927         return null;
928     }
929 
930     /** Prints debug info about the node.
931      * @param n node to print
932      * @param sp spaces to add
933      * @param out where
934      * @param instances print also instances
935      */
936     private static void printNode(Node n, String   sp, java.io.PrintStream   out, boolean instances) {
937         int i;
938         Iterator it;
939 
940         Class   type = n.getType();
941 
942         out.print(sp);
943         out.println("Node for: " + type + "\t" + ((type == null) ? null : type.getClassLoader())); // NOI18N
944 
945         if (n.items != null) {
946             i = 0;
947             it = new ArrayList<Pair>(n.items).iterator();
948 
949             while (it.hasNext()) {
950                 AbstractLookup.Pair p = (AbstractLookup.Pair) it.next();
951                 out.print(sp);
952                 out.print("  item (" + i++ + "): ");
953                 out.print(p); // NOI18N
954                 out.print(" id: " + Integer.toHexString(System.identityHashCode(p))); // NOI18N
955                 out.print(" index: "); // NOI18N
956                 out.print(p.getIndex());
957 
958                 if (instances) {
959                     out.print(" I: " + p.getInstance());
960                 }
961 
962                 out.println();
963             }
964         }
965 
966         if (n.children != null) {
967             i = 0;
968             it = n.children.iterator();
969 
970             while (it.hasNext()) {
971                 Node ch = (Node) it.next();
972                 printNode(ch, sp + "  ", out, instances); // NOI18N
973             }
974         }
975     }
976 
977     public ReferenceToResult registerReferenceToResult(ReferenceToResult<?> newRef) {
978         if (reg == null) {
979             reg = new HashMap<Class  ,ReferenceToResult>();
980         }
981 
982         Class  <? extends Object  > clazz = newRef.template.getType();
983 
984         // initialize the data structures if not yet
985         lookup(clazz);
986 
987         // newRef will be the new head of the list
988         return reg.put(clazz, newRef);
989     }
990 
991     public ReferenceToResult cleanUpResult(Lookup.Template templ) {
992         collectListeners(null, templ.getType());
993 
994         return (reg == null) ? null : reg.get(templ.getType());
995     }
996 
997     public ArrayList<Class  > beginTransaction(int ensure) {
998         return new ArrayList<Class  >();
999     }
1000
1001    public void endTransaction(ArrayList<Class  > list, Set<AbstractLookup.R> allAffectedResults) {
1002        if (list.size() == 1) {
1003            // probably the most common case
1004            collectListeners(allAffectedResults, list.get(0));
1005        } else {
1006            Iterator it = list.iterator();
1007
1008            while (it.hasNext()) {
1009                collectListeners(allAffectedResults, (Class  ) it.next());
1010            }
1011        }
1012    }
1013
1014    /** Notifies all listeners that are interested in changes in this class.
1015     * Should be called from synchronized places.
1016     * @param allAffectedResults adds Results into this set
1017     * @param c the class that has changed
1018     */
1019    private void collectListeners(Set<AbstractLookup.R> allAffectedResults, Class   c) {
1020        if (reg == null) {
1021            return;
1022        }
1023
1024        while (c != null) {
1025            ReferenceToResult first = reg.get(c);
1026            ReferenceIterator it = new ReferenceIterator(first);
1027
1028            while (it.next()) {
1029                AbstractLookup.R result = it.current().getResult();
1030
1031                if (allAffectedResults != null) {
1032                    // add result
1033                    allAffectedResults.add(result);
1034                }
1035            }
1036
1037            if (first != it.first()) {
1038                if (it.first() == null) {
1039                    // we do not need have more results on this object
1040                    reg.remove(c);
1041                } else {
1042                    // move the head of the list
1043                    reg.put(c, it.first());
1044                }
1045            }
1046
1047            c = c.getSuperclass();
1048        }
1049
1050        if (reg.isEmpty()) {
1051            // clean up the list of all results if we do not need them anymore
1052            reg = null;
1053        }
1054    }
1055
1056    /** Node in the tree.
1057    */
1058    static final class Node extends WeakReference  <Class  > implements Serializable {
1059        static final long serialVersionUID = 3L;
1060
1061        /** children nodes */
1062        public ArrayList<Node> children;
1063
1064        /** list of items assigned to this node (suspect to be subclasses) */
1065        public List<Pair> items;
1066
1067        /** Constructor.
1068        */
1069        public Node(Class   clazz) {
1070            super(clazz);
1071        }
1072
1073        /** Returns true if the object was deserialized also clears the serialized flag.
1074         * @return true if so.
1075         */
1076        public boolean deserialized() {
1077            if ((items == null) || items instanceof ArrayList) {
1078                return false;
1079            }
1080
1081            if (items.isEmpty()) {
1082                items = null;
1083            } else {
1084                items = new ArrayList<Pair>(items);
1085            }
1086
1087            return true;
1088        }
1089
1090        /** Marks this item as being deserialized.
1091         */
1092        public void markDeserialized() {
1093            if (items == null || items == Collections.EMPTY_LIST) {
1094                items = Collections.emptyList();
1095            } else {
1096                items = Collections.synchronizedList(items);
1097            }
1098        }
1099
1100        /** Getter for the type associated with this node.
1101         */
1102        public Class  <?> getType() {
1103            Class  <?> c = get();
1104
1105            // if  garbage collected, then return a garbage
1106            return (c == null) ? Void.TYPE : c;
1107        }
1108
1109        /** Checks whether a node can represent an class.
1110        */
1111        public boolean accepts(Class  <?> clazz) {
1112            if (getType() == Object  .class) {
1113                return true;
1114            }
1115
1116            return getType().isAssignableFrom(clazz);
1117        }
1118
1119        /** Checks whether item is instance of this node.
1120        */
1121        public boolean accepts(AbstractLookup.Pair<?> item) {
1122            if (getType() == Object  .class) {
1123                // Object.class
1124                return true;
1125            }
1126
1127            return item.instanceOf(getType());
1128        }
1129
1130        /** Assings an item to this node.
1131        * @param item the item
1132        * @return true if item has been added as new
1133        */
1134        public boolean assignItem(InheritanceTree tree, AbstractLookup.Pair<?> item) {
1135            if ((items == null) || (items == Collections.EMPTY_LIST)) {
1136                items = new ArrayList<Pair>();
1137                items.add(item);
1138
1139                return true;
1140            }
1141
1142            if (items.contains(item)) {
1143                int i = items.indexOf(item);
1144                AbstractLookup.Pair old = items.get(i);
1145
1146                if (old != item) {
1147                    // replace the items there
1148                    item.setIndex(tree, old.getIndex());
1149                }
1150
1151                items.remove(old);
1152                items.add(item);
1153
1154                return false;
1155            }
1156
1157            items.add(item);
1158
1159            return true;
1160        }
1161
1162        private Object   writeReplace() {
1163            return new R(this);
1164        }
1165
1166        public String   toString() {
1167            return "Node for " + get();
1168        }
1169    }
1170     // End of class Node.
1171
1172    private static final class R implements Serializable {
1173        static final long serialVersionUID = 1L;
1174        private static ClassLoader   l;
1175        private String   clazzName;
1176        private transient Class  <?> clazz;
1177        private ArrayList<Node> children;
1178        private ArrayList<Pair> items;
1179
1180        public R(Node n) {
1181            this.clazzName = n.getType().getName();
1182            this.children = n.children;
1183
1184            if (n.items instanceof ArrayList || (n.items == null)) {
1185                this.items = (ArrayList<Pair>) n.items;
1186            } else {
1187                this.items = new ArrayList<Pair>(n.items);
1188            }
1189        }
1190
1191        private void readObject(ObjectInputStream ois)
1192        throws IOException, ClassNotFoundException   {
1193            ois.defaultReadObject();
1194
1195            if (l == null) {
1196                l = Lookup.getDefault().lookup(ClassLoader  .class);
1197            }
1198
1199            clazz = Class.forName(clazzName, false, l);
1200        }
1201
1202        private Object   readResolve() throws ObjectStreamException {
1203            Node n = new Node(clazz);
1204            n.children = children;
1205            n.items = items;
1206            n.markDeserialized();
1207
1208            return n;
1209        }
1210    }
1211     // end of R
1212
1213    /** Just a marker class to be able to do instanceof and find out
1214     * that this enumeration is not sorted
1215     */
1216    private static final class NeedsSortEnum<T> implements Enumeration<T> {
1217        private Enumeration<T> en;
1218
1219        public NeedsSortEnum(Enumeration<T> en) {
1220            this.en = en;
1221        }
1222
1223        public boolean hasMoreElements() {
1224            return en.hasMoreElements();
1225        }
1226
1227        public T nextElement() {
1228            return en.nextElement();
1229        }
1230    }
1231     // end of NeedsSortEnum
1232}
1233
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags