LayoutNode


1   /*******************************************************************************
2    * Copyright (c) 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   ******************************************************************************/
11  
12  package org.eclipse.ui.internal.menus;
13  
14  import java.util.ArrayList  ;
15  import java.util.Collection  ;
16  import java.util.Collections  ;
17  import java.util.HashMap  ;
18  import java.util.Iterator  ;
19  import java.util.List  ;
20  import java.util.Map  ;
21  
22  import org.eclipse.core.commands.common.IIdentifiable;
23  import org.eclipse.core.commands.common.NotDefinedException;
24  import org.eclipse.jface.util.IPropertyChangeListener;
25  import org.eclipse.jface.util.PropertyChangeEvent;
26  import org.eclipse.jface.util.Util;
27  import org.eclipse.ui.internal.misc.Policy;
28  
29  /**
30   * <p>
31   * A node within a menu layout. A node has contains a menu element and some
32   * child nodes.
33   * </p>
34   * <p>
35   * This class is only intended to be used from within the
36   * <code>org.eclipse.jface</code> plug-in.
37   * </p>
38   * <p>
39   * <strong>PROVISIONAL</strong>. This class or interface has been added as
40   * part of a work in progress. There is a guarantee neither that this API will
41   * work nor that it will remain the same. Please do not use this API without
42   * consulting with the Platform/UI team.
43   * </p>
44   * <p>
45   * This class will eventually exist in <code>org.eclipse.jface.menus</code>.
46   * </p>
47   * 
48   * @since 3.2
49   */
50  final class LayoutNode implements ILayoutNode, IMenuCollection,
51          IPropertyChangeListener {
52  
53      /**
54       * The number of items that need to be contained within a block before we
55       * switch to binary insertion sort.
56       */
57      private static final int BINARY_CUT_OFF = 5;
58  
59      /**
60       * The index of the block containing order nodes that need to appear at the
61       * end.
62       */
63      private static final int END = 2;
64  
65      /**
66       * The index of the block containing order nodes that specify no ordering
67       * constraints.
68       */
69      private static final int MIDDLE = 1;
70  
71      /**
72       * The number of blocks, used for initializing an array.
73       */
74      private static final int NUMBER_OF_BLOCKS = 3;
75  
76      /**
77       * The index of the block containing order nodes that need to appear at the
78       * start.
79       */
80      private static final int START = 0;
81  
82      /**
83       * Returns the location to use from the menu element, if the menu element
84       * was provided to the {@link #add(MenuElement)} method.
85       * 
86       * @param element
87       *            The element from which the location should be retrieved; must
88       *            not be <code>null</code>
89       * @return The preferred location for this menu element; may be
90       *         <code>null</code> if none.
91       * @throws NotDefinedException
92       *             If the provided menu element is <code>null</code>.
93       */
94      private static final SLocation getLocation(final MenuElement element)
95              throws NotDefinedException {
96          final SLocation[] locations = element.getLocations();
97          if (locations.length > 0) {
98              return locations[0];
99          }
100 
101         return null;
102     }
103 
104     /**
105      * Inserts a node into a list, sorted based on the identifier of the
106      * element. If there is no element, then the item appears first.
107      * 
108      * @param list
109      *            The list into which the element should be inserted; must not
110      *            be <code>null</code>.
111      * @param node
112      *            The node to inserted; must not be <code>null</code>.
113      */
114     static final void sortedInsert(final List   list, final IIdentifiable node) {
115         if (list.size() < BINARY_CUT_OFF) {
116             // Linear insert.
117             sortedInsertLinear(list, node);
118         } else {
119             // Binary insert.
120             sortedInsertBinary(list, node);
121         }
122     }
123 
124     /**
125      * Inserts a node into a list using a binary search, sorted based on the
126      * identifier of the element. If there is no element, then the item appears
127      * first.
128      * 
129      * @param list
130      *            The list into which the element should be inserted; must not
131      *            be <code>null</code>.
132      * @param node
133      *            The node to inserted; must not be <code>null</code>.
134      */
135     private static final void sortedInsertBinary(final List   list,
136             final IIdentifiable node) {
137         final String   nodeId = node.getId();
138         int topIndex = list.size() - 1;
139         int bottomIndex = 0;
140         int middleIndex = 0;
141         while (true) {
142             middleIndex = (topIndex + bottomIndex) / 2;
143             final IIdentifiable current = (IIdentifiable) list.get(middleIndex);
144             final String   currentId = current.getId();
145             final int comparison = Util.compare(nodeId, currentId);
146             if (comparison < 0) {
147                 if (bottomIndex == middleIndex) {
148                     list.add(bottomIndex, node);
149                     break;
150                 }
151                 topIndex = middleIndex;
152 
153             } else if (comparison > 0) {
154                 if (bottomIndex == middleIndex) {
155                     list.add(topIndex, node);
156                     break;
157                 }
158                 bottomIndex = middleIndex;
159 
160             } else {
161                 list.add(middleIndex, node);
162                 break;
163 
164             }
165         }
166     }
167 
168     /**
169      * Inserts a node into an array using a linear search, sorted based on the
170      * identifier of the element. If there is no element, then the item appears
171      * first.
172      * 
173      * @param list
174      *            The list into which the element should be inserted; must not
175      *            be <code>null</code>.
176      * @param node
177      *            The node to inserted; must not be <code>null</code>.
178      */
179     private static final void sortedInsertLinear(final List   list,
180             final IIdentifiable node) {
181         final String   nodeId = node.getId();
182         final int length = list.size();
183         for (int i = 0; i < length; i++) {
184             final IIdentifiable current = (IIdentifiable) list.get(i);
185             final String   currentId = current.getId();
186             final int comparison = Util.compare(nodeId, currentId);
187             if (comparison < 0) {
188                 list.add(i, node);
189                 return;
190             }
191         }
192 
193         list.add(node);
194     }
195 
196     /**
197      * The children of this node indexed by their identifiers. This map is
198      * lazily initialized, and will be <code>null</code> until someone adds a
199      * child node.
200      */
201     private Map   childrenById;
202 
203     /**
204      * The element this node represents. This value may be <code>null</code>
205      * if this is a top-level node in some menu layout structure, or if the
206      * element is implied.
207      */
208     private MenuElement element;
209 
210     /**
211      * The specific location this node is referring to. This value may be
212      * <code>null</code> if this is a top-level node in some menu layout
213      * structure, or if the element is implied.
214      */
215     private SLocation location;
216 
217     /**
218      * The identifiers of the children, but in the order indicating by their
219      * ordering constraints. This list is lazily generated.
220      */
221     private List   orderedChildren;
222 
223     /**
224      * Constructs a new <code>SMenuLayout</code>.
225      */
226     LayoutNode() {
227         // Do nothing
228     }
229 
230     public final void add(final MenuElement element) throws NotDefinedException {
231         createChildNode(element, null);
232         orderedChildren = null;
233     }
234 
235     public final void clear() {
236         childrenById = null;
237         orderedChildren = null;
238     }
239 
240     /**
241      * Retrieves the child node based on the given menu element.
242      * 
243      * @param element
244      *            The element on which the child node should be based; must not
245      *            be <code>null</code>.
246      * @param location
247      *            The location in which this particular node exists. If
248      *            <code>null</code>, then the first location in the element
249      *            is used as the location.
250      * @throws NotDefinedException
251      *             If the given menu element is not defined.
252      */
253     final void createChildNode(final MenuElement element,
254             final SLocation location) throws NotDefinedException {
255         if (element == null) {
256             throw new NullPointerException  (
257                     "A child node cannot be created from a null element"); //$NON-NLS-1$
258         }
259 
260         final String   id = element.getId();
261         if (Policy.EXPERIMENTAL_MENU 
262                 && id.equals(LeafLocationElement.BREAKPOINT_PATH)) {
263             System.err.println("createChildNode: " + location); //$NON-NLS-1$
264         }
265         LayoutNode childNode = null;
266         if (childrenById == null) {
267             childrenById = new HashMap  (4);
268         } else {
269             childNode = (LayoutNode) childrenById.get(id);
270         }
271         if (childNode == null) {
272             childNode = new LayoutNode();
273             childrenById.put(id, childNode);
274             orderedChildren = null;
275         }
276         if (element!=null) {
277             childNode.setElement(element);
278         }
279         childNode.setLocation((location == null) ? getLocation(element)
280                 : location);
281     }
282 
283     /**
284      * Retrieves the child node with the given identifier. If no such node
285      * exists yet, it is created.
286      * 
287      * @param token
288      *            The token representing the child node to retrieve; must not be
289      *            <code>null</code>.
290      * @return The child node; never <code>null</code>.
291      */
292     final LayoutNode getChildNode(final LocationElementToken token) {
293         if (token == null) {
294             throw new NullPointerException  (
295                     "A child node cannot be created from a null token"); //$NON-NLS-1$
296         }
297 
298         final String   id = token.getId();
299         LayoutNode childNode = null;
300         if (childrenById == null) {
301             childrenById = new HashMap  (4);
302         } else {
303             childNode = (LayoutNode) childrenById.get(id);
304         }
305         if (childNode == null) {
306             childNode = new LayoutNode();
307             childrenById.put(id, childNode);
308             childNode.setLocation(token.getLocation());
309             orderedChildren = null;
310         }
311         return childNode;
312     }
313 
314     public final List   getChildrenSorted() {
315         final Collection   unsortedChildren = getChildrenUnsorted();
316         final int numberOfChildren = unsortedChildren.size();
317         final ArrayList   sortedChildren = new ArrayList  (numberOfChildren);
318 
319         /*
320          * Step 1. Sort into four groups and one map. One group is the middle
321          * block, which is all children with no ordering constraint. Two other
322          * groups are the start and end blocks, which contain children that only
323          * specify start or end constraints. The last group are those children
324          * that specify a relative constraints. Finally, a map is maintained for
325          * the first three groups (i.e., start, middle and end blocks). This
326          * allows easy look-up of those nodes when the relatively positioned
327          * nodes are eventually merged. Note: each block is sorted
328          * alphabetically. This algorithm takes O(NlogN) time over the number of
329          * children.
330          */
331         final Map   orderNodeById = new HashMap  ();
332         final List  [] blocks = new List  [NUMBER_OF_BLOCKS];
333         blocks[START] = new ArrayList  (numberOfChildren);
334         blocks[MIDDLE] = new ArrayList  (numberOfChildren);
335         blocks[END] = new ArrayList  (numberOfChildren);
336         final List   relativeOrderedChildren = new ArrayList  (numberOfChildren);
337         final Iterator   childItr = unsortedChildren.iterator();
338         while (childItr.hasNext()) {
339             final LayoutNode child = (LayoutNode) childItr.next();
340             final OrderNode orderNode = new OrderNode(child);
341             orderNodeById.put(orderNode.getId(), orderNode);
342             final SLocation location = child.getLocation();
343 
344             /*
345              * Check to see if there is an ordering constraints. If there isn't,
346              * then the item can be added to the fixed block.
347              */
348             if (location == null) {
349                 sortedInsert(blocks[MIDDLE], orderNode);
350                 continue;
351             }
352             final SOrder orderingConstraint = location.getOrdering();
353             if (orderingConstraint == null) {
354                 sortedInsert(blocks[MIDDLE], orderNode);
355                 continue;
356             }
357 
358             /*
359              * Check to see if there is a relative ordering constraint. If there
360              * is, add it to the relative block.
361              */
362             final int position = orderingConstraint.getPosition();
363             switch (position) {
364             case SOrder.POSITION_AFTER:
365             case SOrder.POSITION_BEFORE:
366                 sortedInsert(relativeOrderedChildren, child);
367                 break;
368             case SOrder.POSITION_START:
369                 sortedInsert(blocks[START], orderNode);
370                 break;
371             case SOrder.POSITION_END:
372                 sortedInsert(blocks[END], orderNode);
373                 break;
374             case SOrder.NO_POSITION:
375             default:
376                 sortedInsert(blocks[MIDDLE], orderNode);
377             }
378         }
379 
380         /*
381          * Step 2. Now we have four alphabetically sorted blocks: start, middle,
382          * end and relative. We now need to merge the relatively ordered block
383          * into the other three blocks. This can be done by using the order node
384          * map we built up in step 1.
385          */
386         for (int i = 0; i < relativeOrderedChildren.size(); i++) {
387             final LayoutNode node = (LayoutNode) relativeOrderedChildren.get(i);
388             final String   id = node.getId();
389             final SLocation location = node.getLocation();
390             final SOrder order = location.getOrdering();
391             final String   relativeTo = order.getRelativeTo();
392             final boolean before = order.getPosition() == SOrder.POSITION_BEFORE;
393 
394             final OrderNode orderNode = (OrderNode) orderNodeById.get(id);
395             final OrderNode relativeNode = (OrderNode) orderNodeById
396                     .get(relativeTo);
397             if (relativeNode == null) {
398                 // TODO Print error message?
399                 continue;
400             }
401 
402             if (before) {
403                 relativeNode.addBeforeNode(orderNode);
404             } else {
405                 relativeNode.addAfterNode(orderNode);
406             }
407         }
408 
409         /*
410          * Step 3. Copy the order nodes from the start, middle and end blocks
411          * into the final result.
412          */
413         for (int i = 0; i < blocks.length; i++) {
414             final Iterator   itr = blocks[i].iterator();
415             while (itr.hasNext()) {
416                 final OrderNode node = (OrderNode) itr.next();
417                 node.addTo(sortedChildren);
418             }
419         }
420 
421         return sortedChildren;
422     }
423 
424     /**
425      * Returns the children of this node, if any. This collection is unsorted.
426      * 
427      * @return The children ({@link LayoutNode}); never <code>null</code>,
428      *         but may be empty.
429      */
430     final Collection   getChildrenUnsorted() {
431         if (childrenById == null) {
432             return Collections.EMPTY_LIST;
433         }
434 
435         return childrenById.values();
436     }
437 
438     public final String   getId() {
439         if (element != null) {
440             return element.getId();
441         }
442 
443         return null;
444     }
445 
446     public final SLocation getLocation() {
447         return location;
448     }
449 
450     public final MenuElement getMenuElement() {
451         return element;
452     }
453 
454     public final boolean isEmpty() {
455         return (childrenById == null) || (childrenById.isEmpty());
456     }
457 
458     public final void propertyChange(final PropertyChangeEvent event) {
459         // TODO Respond to dynamic changes.
460     }
461 
462     public final boolean remove(final MenuElement element) {
463         if (orderedChildren != null) {
464             orderedChildren.remove(element);
465         }
466         if (childrenById != null) {
467             final String   id = element.getId();
468             final Object   removedObject = childrenById.remove(id);
469             return (removedObject != null);
470         }
471 
472         return false;
473     }
474 
475     /**
476      * Sets the menu element for this node.
477      * 
478      * @param element
479      *            The element to set; must not be <code>null</code>.
480      */
481     final void setElement(final MenuElement element) {
482         if (element == null) {
483             throw new NullPointerException  (
484                     "A node cannot be given a null element"); //$NON-NLS-1$
485         }
486 
487         if (this.element != null) {
488             this.element.removeListener(this);
489         }
490         this.element = element;
491         if (element != null) {
492             element.addListener(this);
493         }
494     }
495 
496     /**
497      * Sets the location for this node.
498      * 
499      * @param location
500      *            The location to set; must not be <code>null</code>.
501      */
502     final void setLocation(final SLocation location) {
503         if (location == null) {
504             throw new NullPointerException  (
505                     "A node cannot be given a null location"); //$NON-NLS-1$
506         }
507 
508         this.location = location;
509     }
510 
511     public final String   toString() {
512         final StringBuffer   buffer = new StringBuffer  ("LayoutNode("); //$NON-NLS-1$
513         buffer.append(element);
514         buffer.append(',');
515         buffer.append(location);
516         buffer.append(')');
517         return buffer.toString();
518     }
519 }
520
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags