BindingManager


1   /*******************************************************************************
2    * Copyright (c) 2004, 2007 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  package org.eclipse.jface.bindings;
12  
13  import java.io.BufferedWriter  ;
14  import java.io.IOException  ;
15  import java.io.StringWriter  ;
16  import java.util.ArrayList  ;
17  import java.util.Arrays  ;
18  import java.util.Collection  ;
19  import java.util.Collections  ;
20  import java.util.HashMap  ;
21  import java.util.HashSet  ;
22  import java.util.Iterator  ;
23  import java.util.List  ;
24  import java.util.Locale  ;
25  import java.util.Map  ;
26  import java.util.Set  ;
27  import java.util.StringTokenizer  ;
28  
29  import org.eclipse.core.commands.CommandManager;
30  import org.eclipse.core.commands.ParameterizedCommand;
31  import org.eclipse.core.commands.common.HandleObjectManager;
32  import org.eclipse.core.commands.common.NotDefinedException;
33  import org.eclipse.core.commands.contexts.Context;
34  import org.eclipse.core.commands.contexts.ContextManager;
35  import org.eclipse.core.commands.contexts.ContextManagerEvent;
36  import org.eclipse.core.commands.contexts.IContextManagerListener;
37  import org.eclipse.core.commands.util.Tracing;
38  import org.eclipse.core.runtime.IStatus;
39  import org.eclipse.core.runtime.MultiStatus;
40  import org.eclipse.core.runtime.Status;
41  import org.eclipse.jface.bindings.keys.IKeyLookup;
42  import org.eclipse.jface.bindings.keys.KeyLookupFactory;
43  import org.eclipse.jface.bindings.keys.KeyStroke;
44  import org.eclipse.jface.contexts.IContextIds;
45  import org.eclipse.jface.internal.InternalPolicy;
46  import org.eclipse.jface.util.Policy;
47  import org.eclipse.jface.util.Util;
48  import org.eclipse.swt.SWT;
49  
50  /**
51   * <p>
52   * A central repository for bindings -- both in the defined and undefined
53   * states. Schemes and bindings can be created and retrieved using this manager.
54   * It is possible to listen to changes in the collection of schemes and bindings
55   * by adding a listener to the manager.
56   * </p>
57   * <p>
58   * The binding manager is very sensitive to performance. Misusing the manager
59   * can render an application unenjoyable to use. As such, each of the public
60   * methods states the current run-time performance. In future releases, it is
61   * guaranteed that the method will run in at least the stated time constraint --
62   * though it might get faster. Where possible, we have also tried to be memory
63   * efficient.
64   * </p>
65   * 
66   * @since 3.1
67   */
68  public final class BindingManager extends HandleObjectManager implements
69          IContextManagerListener, ISchemeListener {
70  
71      /**
72       * This flag can be set to <code>true</code> if the binding manager should
73       * print information to <code>System.out</code> when certain boundary
74       * conditions occur.
75       */
76      public static boolean DEBUG = false;
77  
78      /**
79       * Returned for optimized lookup.
80       */
81      private static final TriggerSequence[] EMPTY_TRIGGER_SEQUENCE = new TriggerSequence[0];
82  
83      /**
84       * The separator character used in locales.
85       */
86      private static final String   LOCALE_SEPARATOR = "_"; //$NON-NLS-1$
87  
88      /**
89       * </p>
90       * A utility method for adding entries to a map. The map is checked for
91       * entries at the key. If such an entry exists, it is expected to be a
92       * <code>Collection</code>. The value is then appended to the collection.
93       * If no such entry exists, then a collection is created, and the value
94       * added to the collection.
95       * </p>
96       * 
97       * @param map
98       *            The map to modify; if this value is <code>null</code>, then
99       *            this method simply returns.
100      * @param key
101      *            The key to look up in the map; may be <code>null</code>.
102      * @param value
103      *            The value to look up in the map; may be <code>null</code>.
104      */
105     private static final void addReverseLookup(final Map   map, final Object   key,
106             final Object   value) {
107         if (map == null) {
108             return;
109         }
110 
111         final Object   currentValue = map.get(key);
112         if (currentValue != null) {
113             final Collection   values = (Collection  ) currentValue;
114             values.add(value);
115         } else { // currentValue == null
116             final Collection   values = new ArrayList  (1);
117             values.add(value);
118             map.put(key, values);
119         }
120     }
121 
122     /**
123      * <p>
124      * Takes a fully-specified string, and converts it into an array of
125      * increasingly less-specific strings. So, for example, "en_GB" would become
126      * ["en_GB", "en", "", null].
127      * </p>
128      * <p>
129      * This method runs in linear time (O(n)) over the length of the string.
130      * </p>
131      * 
132      * @param string
133      *            The string to break apart into its less specific components;
134      *            should not be <code>null</code>.
135      * @param separator
136      *            The separator that indicates a separation between a degrees of
137      *            specificity; should not be <code>null</code>.
138      * @return An array of strings from the most specific (i.e.,
139      *         <code>string</code>) to the least specific (i.e.,
140      *         <code>null</code>).
141      */
142     private static final String  [] expand(String   string, final String   separator) {
143         // Test for boundary conditions.
144         if (string == null || separator == null) {
145             return new String  [0];
146         }
147 
148         final List   strings = new ArrayList  ();
149         final StringBuffer   stringBuffer = new StringBuffer  ();
150         string = string.trim(); // remove whitespace
151         if (string.length() > 0) {
152             final StringTokenizer   stringTokenizer = new StringTokenizer  (string,
153                     separator);
154             while (stringTokenizer.hasMoreElements()) {
155                 if (stringBuffer.length() > 0) {
156                     stringBuffer.append(separator);
157                 }
158                 stringBuffer.append(((String  ) stringTokenizer.nextElement())
159                         .trim());
160                 strings.add(stringBuffer.toString());
161             }
162         }
163         Collections.reverse(strings);
164         strings.add(Util.ZERO_LENGTH_STRING);
165         strings.add(null);
166         return (String  []) strings.toArray(new String  [strings.size()]);
167     }
168 
169     /**
170      * The active bindings. This is a map of triggers (
171      * <code>TriggerSequence</code>) to bindings (<code>Binding</code>).
172      * This value will only be <code>null</code> if the active bindings have
173      * not yet been computed. Otherwise, this value may be empty.
174      */
175     private Map   activeBindings = null;
176 
177     /**
178      * The active bindings indexed by fully-parameterized commands. This is a
179      * map of fully-parameterized commands (<code>ParameterizedCommand</code>)
180      * to triggers ( <code>TriggerSequence</code>). This value will only be
181      * <code>null</code> if the active bindings have not yet been computed.
182      * Otherwise, this value may be empty.
183      */
184     private Map   activeBindingsByParameterizedCommand = null;
185     
186     private Set   triggerConflicts = new HashSet  ();
187 
188     /**
189      * The scheme that is currently active. An active scheme is the one that is
190      * currently dictating which bindings will actually work. This value may be
191      * <code>null</code> if there is no active scheme. If the active scheme
192      * becomes undefined, then this should automatically revert to
193      * <code>null</code>.
194      */
195     private Scheme activeScheme = null;
196 
197     /**
198      * The array of scheme identifiers, starting with the active scheme and
199      * moving up through its parents. This value may be <code>null</code> if
200      * there is no active scheme.
201      */
202     private String  [] activeSchemeIds = null;
203 
204     /**
205      * The number of bindings in the <code>bindings</code> array.
206      */
207     private int bindingCount = 0;
208 
209     /**
210      * A cache of context IDs that weren't defined.
211      */
212     private Set   bindingErrors = new HashSet  ();
213 
214     /**
215      * The array of all bindings currently handled by this manager. This array
216      * is the raw list of bindings, as provided to this manager. This value may
217      * be <code>null</code> if there are no bindings. The size of this array
218      * is not necessarily the number of bindings.
219      */
220     private Binding[] bindings = null;
221 
222     /**
223      * A cache of the bindings previously computed by this manager. This value
224      * may be empty, but it is never <code>null</code>. This is a map of
225      * <code>CachedBindingSet</code> to <code>CachedBindingSet</code>.
226      */
227     private Map   cachedBindings = new HashMap  ();
228 
229     /**
230      * The command manager for this binding manager. This manager is only needed
231      * for the <code>getActiveBindingsFor(String)</code> method. This value is
232      * guaranteed to never be <code>null</code>.
233      */
234     private final CommandManager commandManager;
235 
236     /**
237      * The context manager for this binding manager. For a binding manager to
238      * function, it needs to listen for changes to the contexts. This value is
239      * guaranteed to never be <code>null</code>.
240      */
241     private final ContextManager contextManager;
242 
243     /**
244      * The locale for this manager. This defaults to the current locale. The
245      * value will never be <code>null</code>.
246      */
247     private String   locale = Locale.getDefault().toString();
248 
249     /**
250      * The array of locales, starting with the active locale and moving up
251      * through less specific representations of the locale. For example,
252      * ["en_US", "en", "", null]. This value will never be <code>null</code>.
253      */
254     private String  [] locales = expand(locale, LOCALE_SEPARATOR);
255 
256     /**
257      * The platform for this manager. This defaults to the current platform. The
258      * value will never be <code>null</code>.
259      */
260     private String   platform = SWT.getPlatform();
261 
262     /**
263      * The array of platforms, starting with the active platform and moving up
264      * through less specific representations of the platform. For example,
265      * ["gtk", "", null]. This value will never be <code>null,/code>.
266      */
267     private String  [] platforms = expand(platform, Util.ZERO_LENGTH_STRING);
268 
269     /**
270      * A map of prefixes (<code>TriggerSequence</code>) to a map of
271      * available completions (possibly <code>null</code>, which means there
272      * is an exact match). The available completions is a map of trigger (<code>TriggerSequence</code>)
273      * to bindings (<code>Binding</code>). This value may be
274      * <code>null</code> if there is no existing solution.
275      */
276     private Map   prefixTable = null;
277 
278     /**
279      * <p>
280      * Constructs a new instance of <code>BindingManager</code>.
281      * </p>
282      * <p>
283      * This method completes in amortized constant time (O(1)).
284      * </p>
285      * 
286      * @param contextManager
287      *            The context manager that will support this binding manager.
288      *            This value must not be <code>null</code>.
289      * @param commandManager
290      *            The command manager that will support this binding manager.
291      *            This value must not be <code>null</code>.
292      */
293     public BindingManager(final ContextManager contextManager,
294             final CommandManager commandManager) {
295         if (contextManager == null) {
296             throw new NullPointerException  (
297                     "A binding manager requires a context manager"); //$NON-NLS-1$
298         }
299 
300         if (commandManager == null) {
301             throw new NullPointerException  (
302                     "A binding manager requires a command manager"); //$NON-NLS-1$
303         }
304 
305         this.contextManager = contextManager;
306         contextManager.addContextManagerListener(this);
307         this.commandManager = commandManager;
308     }
309 
310     /**
311      * <p>
312      * Adds a single new binding to the existing array of bindings. If the array
313      * is currently <code>null</code>, then a new array is created and this
314      * binding is added to it. This method does not detect duplicates.
315      * </p>
316      * <p>
317      * This method completes in amortized <code>O(1)</code>.
318      * </p>
319      * 
320      * @param binding
321      *            The binding to be added; must not be <code>null</code>.
322      */
323     public final void addBinding(final Binding binding) {
324         if (binding == null) {
325             throw new NullPointerException  ("Cannot add a null binding"); //$NON-NLS-1$
326         }
327 
328         if (bindings == null) {
329             bindings = new Binding[1];
330         } else if (bindingCount >= bindings.length) {
331             final Binding[] oldBindings = bindings;
332             bindings = new Binding[oldBindings.length * 2];
333             System.arraycopy(oldBindings, 0, bindings, 0, oldBindings.length);
334         }
335         bindings[bindingCount++] = binding;
336         clearCache();
337     }
338 
339     /**
340      * <p>
341      * Adds a listener to this binding manager. The listener will be notified
342      * when the set of defined schemes or bindings changes. This can be used to
343      * track the global appearance and disappearance of bindings.
344      * </p>
345      * <p>
346      * This method completes in amortized constant time (<code>O(1)</code>).
347      * </p>
348      * 
349      * @param listener
350      *            The listener to attach; must not be <code>null</code>.
351      */
352     public final void addBindingManagerListener(
353             final IBindingManagerListener listener) {
354         addListenerObject(listener);
355     }
356 
357     /**
358      * <p>
359      * Builds a prefix table look-up for a map of active bindings.
360      * </p>
361      * <p>
362      * This method takes <code>O(mn)</code>, where <code>m</code> is the
363      * length of the trigger sequences and <code>n</code> is the number of
364      * bindings.
365      * </p>
366      * 
367      * @param activeBindings
368      *            The map of triggers (<code>TriggerSequence</code>) to
369      *            command ids (<code>String</code>) which are currently
370      *            active. This value may be <code>null</code> if there are no
371      *            active bindings, and it may be empty. It must not be
372      *            <code>null</code>.
373      * @return A map of prefixes (<code>TriggerSequence</code>) to a map of
374      *         available completions (possibly <code>null</code>, which means
375      *         there is an exact match). The available completions is a map of
376      *         trigger (<code>TriggerSequence</code>) to command identifier (<code>String</code>).
377      *         This value will never be <code>null</code>, but may be empty.
378      */
379     private final Map   buildPrefixTable(final Map   activeBindings) {
380         final Map   prefixTable = new HashMap  ();
381 
382         final Iterator   bindingItr = activeBindings.entrySet().iterator();
383         while (bindingItr.hasNext()) {
384             final Map.Entry   entry = (Map.Entry  ) bindingItr.next();
385             final TriggerSequence triggerSequence = (TriggerSequence) entry
386                     .getKey();
387 
388             // Add the perfect match.
389             if (!prefixTable.containsKey(triggerSequence)) {
390                 prefixTable.put(triggerSequence, null);
391             }
392 
393             final TriggerSequence[] prefixes = triggerSequence.getPrefixes();
394             final int prefixesLength = prefixes.length;
395             if (prefixesLength == 0) {
396                 continue;
397             }
398 
399             // Break apart the trigger sequence.
400             final Binding binding = (Binding) entry.getValue();
401             for (int i = 0; i < prefixesLength; i++) {
402                 final TriggerSequence prefix = prefixes[i];
403                 final Object   value = prefixTable.get(prefix);
404                 if ((prefixTable.containsKey(prefix)) && (value instanceof Map  )) {
405                     ((Map  ) value).put(triggerSequence, binding);
406                 } else {
407                     final Map   map = new HashMap  ();
408                     prefixTable.put(prefix, map);
409                     map.put(triggerSequence, binding);
410                 }
411             }
412         }
413 
414         return prefixTable;
415     }
416 
417     /**
418      * <p>
419      * Clears the cache, and the existing solution. If debugging is turned on,
420      * then this will also print a message to standard out.
421      * </p>
422      * <p>
423      * This method completes in <code>O(1)</code>.
424      * </p>
425      */
426     private final void clearCache() {
427         if (DEBUG) {
428             Tracing.printTrace("BINDINGS", "Clearing cache"); //$NON-NLS-1$ //$NON-NLS-2$
429         }
430         cachedBindings.clear();
431         clearSolution();
432     }
433 
434     /**
435      * <p>
436      * Clears the existing solution.
437      * </p>
438      * <p>
439      * This method completes in <code>O(1)</code>.
440      */
441     private final void clearSolution() {
442         setActiveBindings(null, null, null, null);
443     }
444 
445     /**
446      * Compares the identifier of two schemes, and decides which scheme is the
447      * youngest (i.e., the child) of the two. Both schemes should be active
448      * schemes.
449      * 
450      * @param schemeId1
451      *            The identifier of the first scheme; must not be
452      *            <code>null</code>.
453      * @param schemeId2
454      *            The identifier of the second scheme; must not be
455      *            <code>null</code>.
456      * @return <code>0</code> if the two schemes are equal of if neither
457      *         scheme is active; <code>1</code> if the second scheme is the
458      *         youngest; and <code>-1</code> if the first scheme is the
459      *         youngest.
460      * @since 3.2
461      */
462     private final int compareSchemes(final String   schemeId1,
463             final String   schemeId2) {
464         if (!schemeId2.equals(schemeId1)) {
465             for (int i = 0; i < activeSchemeIds.length; i++) {
466                 final String   schemePointer = activeSchemeIds[i];
467                 if (schemeId2.equals(schemePointer)) {
468                     return 1;
469 
470                 } else if (schemeId1.equals(schemePointer)) {
471                     return -1;
472 
473                 }
474 
475             }
476         }
477 
478         return 0;
479     }
480 
481     /**
482      * <p>
483      * Computes the bindings given the context tree, and inserts them into the
484      * <code>commandIdsByTrigger</code>. It is assumed that
485      * <code>locales</code>,<code>platforsm</code> and
486      * <code>schemeIds</code> correctly reflect the state of the application.
487      * This method does not deal with caching.
488      * </p>
489      * <p>
490      * This method completes in <code>O(n)</code>, where <code>n</code> is
491      * the number of bindings.
492      * </p>
493      * 
494      * @param activeContextTree
495      *            The map representing the tree of active contexts. The map is
496      *            one of child to parent, each being a context id (
497      *            <code>String</code>). The keys are never <code>null</code>,
498      *            but the values may be (i.e., no parent). This map may be
499      *            empty. It may be <code>null</code> if we shouldn't consider
500      *            contexts.
501      * @param bindingsByTrigger
502      *            The empty of map that is intended to be filled with triggers (
503      *            <code>TriggerSequence</code>) to bindings (
504      *            <code>Binding</code>). This value must not be
505      *            <code>null</code> and must be empty.
506      * @param triggersByCommandId
507      *            The empty of map that is intended to be filled with command
508      *            identifiers (<code>String</code>) to triggers (
509      *            <code>TriggerSequence</code>). This value must either be
510      *            <code>null</code> (indicating that these values are not
511      *            needed), or empty (indicating that this map should be
512      *            computed).
513      */
514     private final void computeBindings(final Map   activeContextTree,
515             final Map   bindingsByTrigger, final Map   triggersByCommandId, 
516             final Map   conflictsByTrigger) {
517         /*
518          * FIRST PASS: Remove all of the bindings that are marking deletions.
519          */
520         final Binding[] trimmedBindings = removeDeletions(bindings);
521 
522         /*
523          * SECOND PASS: Just throw in bindings that match the current state. If
524          * there is more than one match for a binding, then create a list.
525          */
526         final Map   possibleBindings = new HashMap  ();
527         final int length = trimmedBindings.length;
528         for (int i = 0; i < length; i++) {
529             final Binding binding = trimmedBindings[i];
530             boolean found;
531 
532             // Check the context.
533             final String   contextId = binding.getContextId();
534             if ((activeContextTree != null)
535                     && (!activeContextTree.containsKey(contextId))) {
536                 continue;
537             }
538 
539             // Check the locale.
540             if (!localeMatches(binding)) {
541                 continue;
542             }
543 
544             // Check the platform.
545             if (!platformMatches(binding)) {
546                 continue;
547             }
548 
549             // Check the scheme ids.
550             final String   schemeId = binding.getSchemeId();
551             found = false;
552             if (activeSchemeIds != null) {
553                 for (int j = 0; j < activeSchemeIds.length; j++) {
554                     if (Util.equals(schemeId, activeSchemeIds[j])) {
555                         found = true;
556                         break;
557                     }
558                 }
559             }
560             if (!found) {
561                 continue;
562             }
563 
564             // Insert the match into the list of possible matches.
565             final TriggerSequence trigger = binding.getTriggerSequence();
566             final Object   existingMatch = possibleBindings.get(trigger);
567             if (existingMatch instanceof Binding) {
568                 possibleBindings.remove(trigger);
569                 final Collection   matches = new ArrayList  ();
570                 matches.add(existingMatch);
571                 matches.add(binding);
572                 possibleBindings.put(trigger, matches);
573 
574             } else if (existingMatch instanceof Collection  ) {
575                 final Collection   matches = (Collection  ) existingMatch;
576                 matches.add(binding);
577 
578             } else {
579                 possibleBindings.put(trigger, binding);
580             }
581         }
582 
583         MultiStatus conflicts = new MultiStatus("org.eclipse.jface", 0, //$NON-NLS-1$
584                 "Keybinding conflicts occurred.  They may interfere with normal accelerator operation.", //$NON-NLS-1$
585                 null);
586         /*
587          * THIRD PASS: In this pass, we move any non-conflicting bindings
588          * directly into the map. In the case of conflicts, we apply some
589          * further logic to try to resolve them. If the conflict can't be
590          * resolved, then we log the problem.
591          */
592         final Iterator   possibleBindingItr = possibleBindings.entrySet()
593                 .iterator();
594         while (possibleBindingItr.hasNext()) {
595             final Map.Entry   entry = (Map.Entry  ) possibleBindingItr.next();
596             final TriggerSequence trigger = (TriggerSequence) entry.getKey();
597             final Object   match = entry.getValue();
598             /*
599              * What we do depends slightly on whether we are trying to build a
600              * list of all possible bindings (disregarding context), or a flat
601              * map given the currently active contexts.
602              */
603             if (activeContextTree == null) {
604                 // We are building the list of all possible bindings.
605                 final Collection   bindings = new ArrayList  ();
606                 if (match instanceof Binding) {
607                     bindings.add(match);
608                     bindingsByTrigger.put(trigger, bindings);
609                     addReverseLookup(triggersByCommandId, ((Binding) match)
610                             .getParameterizedCommand(), trigger);
611 
612                 } else if (match instanceof Collection  ) {
613                     bindings.addAll((Collection  ) match);
614                     bindingsByTrigger.put(trigger, bindings);
615 
616                     final Iterator   matchItr = bindings.iterator();
617                     while (matchItr.hasNext()) {
618                         addReverseLookup(triggersByCommandId,
619                                 ((Binding) matchItr.next())
620                                         .getParameterizedCommand(), trigger);
621                     }
622                 }
623 
624             } else {
625                 // We are building the flat map of trigger to commands.
626                 if (match instanceof Binding) {
627                     final Binding binding = (Binding) match;
628                     bindingsByTrigger.put(trigger, binding);
629                     addReverseLookup(triggersByCommandId, binding
630                             .getParameterizedCommand(), trigger);
631 
632                 } else if (match instanceof Collection  ) {
633                     final Binding winner = resolveConflicts((Collection  ) match,
634                             activeContextTree);
635                     if (winner == null) {
636                         // warn once ... so as not to flood the logs
637                         conflictsByTrigger.put(trigger, match);
638                         if (triggerConflicts.add(trigger)) {
639                             final StringWriter   sw = new StringWriter  ();
640                             final BufferedWriter   buffer = new BufferedWriter  (sw);
641                             try {
642                                 buffer.write("A conflict occurred for "); //$NON-NLS-1$
643                                 buffer.write(trigger.toString());
644                                 buffer.write(':');
645                                 Iterator   i = ((Collection  ) match).iterator();
646                                 while (i.hasNext()) {
647                                     buffer.newLine();
648                                     buffer.write(i.next().toString());
649                                 }
650                                 buffer.flush();
651                             } catch (IOException   e) {
652                                 // we should not get this
653                             }
654                             conflicts.add(new Status(IStatus.WARNING,
655                                     "org.eclipse.jface", //$NON-NLS-1$
656                                     sw.toString()));
657                         }
658                         if (DEBUG) {
659                             Tracing.printTrace("BINDINGS", //$NON-NLS-1$
660                                     "A conflict occurred for " + trigger); //$NON-NLS-1$
661                             Tracing.printTrace("BINDINGS", "    " + match); //$NON-NLS-1$ //$NON-NLS-2$
662                         }
663                     } else {
664                         bindingsByTrigger.put(trigger, winner);
665                         addReverseLookup(triggersByCommandId, winner
666                                 .getParameterizedCommand(), trigger);
667                     }
668                 }
669             }
670         }
671         if (conflicts.getSeverity() != IStatus.OK) {
672             Policy.getLog().log(conflicts);
673         }
674     }
675 
676     /**
677      * <p>
678      * Notifies this manager that the context manager has changed. This method
679      * is intended for internal use only.
680      * </p>
681      * <p>
682      * This method completes in <code>O(1)</code>.
683      * </p>
684      */
685     public final void contextManagerChanged(
686             final ContextManagerEvent contextManagerEvent) {
687         if (contextManagerEvent.isActiveContextsChanged()) {
688 // clearSolution();
689             recomputeBindings();
690         }
691     }
692 
693     /**
694      * Returns the number of strokes in an array of triggers. It is assumed that
695      * there is one natural key per trigger. The strokes are counted based on
696      * the type of key. Natural keys are worth one; ctrl is worth two; shift is
697      * worth four; and alt is worth eight.
698      * 
699      * @param triggers
700      *            The triggers on which to count strokes; must not be
701      *            <code>null</code>.
702      * @return The value of the strokes in the triggers.
703      * @since 3.2
704      */
705     private final int countStrokes(final Trigger[] triggers) {
706         int strokeCount = triggers.length;
707         for (int i = 0; i < triggers.length; i++) {
708             final Trigger trigger = triggers[i];
709             if (trigger instanceof KeyStroke) {
710                 final KeyStroke keyStroke = (KeyStroke) trigger;
711                 final int modifierKeys = keyStroke.getModifierKeys();
712                 final IKeyLookup lookup = KeyLookupFactory.getDefault();
713                 if ((modifierKeys & lookup.getAlt()) != 0) {
714                     strokeCount += 8;
715                 }
716                 if ((modifierKeys & lookup.getCtrl()) != 0) {
717                     strokeCount += 2;
718                 }
719                 if ((modifierKeys & lookup.getShift()) != 0) {
720                     strokeCount += 4;
721                 }
722                 if ((modifierKeys & lookup.getCommand()) != 0) {
723                     strokeCount += 2;
724                 }
725             } else {
726                 strokeCount += 99;
727             }
728         }
729 
730         return strokeCount;
731     }
732 
733     /**
734      * <p>
735      * Creates a tree of context identifiers, representing the hierarchical
736      * structure of the given contexts. The tree is structured as a mapping from
737      * child to parent.
738      * </p>
739      * <p>
740      * This method completes in <code>O(n)</code>, where <code>n</code> is
741      * the height of the context tree.
742      * </p>
743      * 
744      * @param contextIds
745      *            The set of context identifiers to be converted into a tree;
746      *            must not be <code>null</code>.
747      * @return The tree of contexts to use; may be empty, but never
748      *         <code>null</code>. The keys and values are both strings.
749      */
750     private final Map   createContextTreeFor(final Set   contextIds) {
751         final Map   contextTree = new HashMap  ();
752 
753         final Iterator   contextIdItr = contextIds.iterator();
754         while (contextIdItr.hasNext()) {
755             String   childContextId = (String  ) contextIdItr.next();
756             while (childContextId != null) {
757                 // Check if we've already got the part of the tree from here up.
758                 if (contextTree.containsKey(childContextId)) {
759                     break;
760                 }
761 
762                 // Retrieve the context.
763                 final Context childContext = contextManager
764                         .getContext(childContextId);
765 
766                 // Add the child-parent pair to the tree.
767                 try {
768                     final String   parentContextId = childContext.getParentId();
769                     contextTree.put(childContextId, parentContextId);
770                     childContextId = parentContextId;
771                 } catch (final NotDefinedException e) {
772                     break; // stop ascending
773                 }
774             }
775         }
776 
777         return contextTree;
778     }
779 
780     /**
781      * <p>
782      * Creates a tree of context identifiers, representing the hierarchical
783      * structure of the given contexts. The tree is structured as a mapping from
784      * child to parent. In this tree, the key binding specific filtering of
785      * contexts will have taken place.
786      * </p>
787      * <p>
788      * This method completes in <code>O(n^2)</code>, where <code>n</code>
789      * is the height of the context tree.
790      * </p>
791      * 
792      * @param contextIds
793      *            The set of context identifiers to be converted into a tree;
794      *            must not be <code>null</code>.
795      * @return The tree of contexts to use; may be empty, but never
796      *         <code>null</code>. The keys and values are both strings.
797      */
798     private final Map   createFilteredContextTreeFor(final Set   contextIds) {
799         // Check to see whether a dialog or window is active.
800         boolean dialog = false;
801         boolean window = false;
802         Iterator   contextIdItr = contextIds.iterator();
803         while (contextIdItr.hasNext()) {
804             final String   contextId = (String  ) contextIdItr.next();
805             if (IContextIds.CONTEXT_ID_DIALOG.equals(contextId)) {
806                 dialog = true;
807                 continue;
808             }
809             if (IContextIds.CONTEXT_ID_WINDOW.equals(contextId)) {
810                 window = true;
811                 continue;
812             }
813         }
814 
815         /*
816          * Remove all context identifiers for contexts whose parents are dialog
817          * or window, and the corresponding dialog or window context is not
818          * active.
819          */
820         contextIdItr = contextIds.iterator();
821         while (contextIdItr.hasNext()) {
822             String   contextId = (String  ) contextIdItr.next();
823             Context context = contextManager.getContext(contextId);
824             try {
825                 String   parentId = context.getParentId();
826                 while (parentId != null) {
827                     if (IContextIds.CONTEXT_ID_DIALOG.equals(parentId)) {
828                         if (!dialog) {
829                             contextIdItr.remove();
830                         }
831                         break;
832                     }
833                     if (IContextIds.CONTEXT_ID_WINDOW.equals(parentId)) {
834                         if (!window) {
835                             contextIdItr.remove();
836                         }
837                         break;
838                     }
839                     if (IContextIds.CONTEXT_ID_DIALOG_AND_WINDOW
840                             .equals(parentId)) {
841                         if ((!window) && (!dialog)) {
842                             contextIdItr.remove();
843                         }
844                         break;
845                     }
846 
847                     context = contextManager.getContext(parentId);
848                     parentId = context.getParentId();
849                 }
850             } catch (NotDefinedException e) {
851                 // since this context was part of an undefined hierarchy,
852                 // I'm going to yank it out as a bad bet
853                 contextIdItr.remove();
854 
855                 // This is a logging optimization, only log the error once.
856                 if (context == null || !bindingErrors.contains(context.getId())) {
857                     if (context != null) {
858                         bindingErrors.add(context.getId());
859                     }
860 
861                     // now log like you've never logged before!
862                     Policy
863                             .getLog()
864                             .log(
865                                     new Status(
866                                             IStatus.ERROR,
867                                             Policy.JFACE,
868                                             IStatus.OK,
869                                             "Undefined context while filtering dialog/window contexts", //$NON-NLS-1$
870                                             e));
871                 }
872             }
873         }
874 
875         return createContextTreeFor(contextIds);
876     }
877 
878     /**
879      * <p>
880      * Notifies all of the listeners to this manager that the defined or active
881      * schemes of bindings have changed.
882      * </p>
883      * <p>
884      * The time this method takes to complete is dependent on external
885      * listeners.
886      * </p>
887      * 
888      * @param event
889      *            The event to send to all of the listeners; must not be
890      *            <code>null</code>.
891      */
892     private final void fireBindingManagerChanged(final BindingManagerEvent event) {
893         if (event == null) {
894             throw new NullPointerException  ();
895         }
896 
897         final Object  [] listeners = getListeners();
898         for (int i = 0; i < listeners.length; i++) {
899             final IBindingManagerListener listener = (IBindingManagerListener) listeners[i];
900             listener.bindingManagerChanged(event);
901         }
902     }
903 
904     /**
905      * <p>
906      * Returns the active bindings. The caller must not modify the returned map.
907      * </p>
908      * <p>
909      * This method completes in <code>O(1)</code>. If the active bindings are
910      * not yet computed, then this completes in <code>O(nn)</code>, where
911      * <code>n</code> is the number of bindings.
912      * </p>
913      * 
914      * @return The map of triggers (<code>TriggerSequence</code>) to
915      *         bindings (<code>Binding</code>) which are currently active.
916      *         This value may be <code>null</code> if there are no active
917      *         bindings, and it may be empty.
918      */
919     private final Map   getActiveBindings() {
920         if (activeBindings == null) {
921             recomputeBindings();
922         }
923 
924         return activeBindings;
925     }
926 
927     /**
928      * <p>
929      * Returns the active bindings indexed by command identifier. The caller
930      * must not modify the returned map.
931      * </p>
932      * <p>
933      * This method completes in <code>O(1)</code>. If the active bindings are
934      * not yet computed, then this completes in <code>O(nn)</code>, where
935      * <code>n</code> is the number of bindings.
936      * </p>
937      * 
938      * @return The map of fully-parameterized commands (<code>ParameterizedCommand</code>)
939      *         to triggers (<code>TriggerSequence</code>) which are
940      *         currently active. This value may be <code>null</code> if there
941      *         are no active bindings, and it may be empty.
942      */
943     private final Map   getActiveBindingsByParameterizedCommand() {
944         if (activeBindingsByParameterizedCommand == null) {
945             recomputeBindings();
946         }
947 
948         return activeBindingsByParameterizedCommand;
949     }
950 
951     /**
952      * <p>
953      * Computes the bindings for the current state of the application, but
954      * disregarding the current contexts. This can be useful when trying to
955      * display all the possible bindings.
956      * </p>
957      * <p>
958      * This method completes in <code>O(n)</code>, where <code>n</code> is
959      * the number of bindings.
960      * </p>
961      * 
962      * @return A map of trigger (<code>TriggerSequence</code>) to bindings (
963      *         <code>Collection</code> containing <code>Binding</code>).
964      *         This map may be empty, but it is never <code>null</code>.
965      */
966     public final Map   getActiveBindingsDisregardingContext() {
967         if (bindings == null) {
968             // Not yet initialized. This is happening too early. Do nothing.
969             return Collections.EMPTY_MAP;
970         }
971 
972         // Build a cached binding set for that state.
973         final CachedBindingSet bindingCache = new CachedBindingSet(null,
974                 locales, platforms, activeSchemeIds);
975 
976         /*
977          * Check if the cached binding set already exists. If so, simply set the
978          * active bindings and return.
979          */
980         CachedBindingSet existingCache = (CachedBindingSet) cachedBindings
981                 .get(bindingCache);
982         if (existingCache == null) {
983             existingCache = bindingCache;
984             cachedBindings.put(existingCache, existingCache);
985         }
986         Map   commandIdsByTrigger = existingCache.getBindingsByTrigger();
987         if (commandIdsByTrigger != null) {
988             if (DEBUG) {
989                 Tracing.printTrace("BINDINGS", "Cache hit"); //$NON-NLS-1$ //$NON-NLS-2$
990             }
991 
992             return Collections.unmodifiableMap(commandIdsByTrigger);
993         }
994 
995         // There is no cached entry for this.
996         if (DEBUG) {
997             Tracing.printTrace("BINDINGS", "Cache miss"); //$NON-NLS-1$ //$NON-NLS-2$
998         }
999 
1000        // Compute the active bindings.
1001        commandIdsByTrigger = new HashMap  ();
1002        final Map   triggersByParameterizedCommand = new HashMap  ();
1003        final Map   conflictsByTrigger = new HashMap  ();
1004        computeBindings(null, commandIdsByTrigger,
1005                triggersByParameterizedCommand, conflictsByTrigger);
1006        existingCache.setBindingsByTrigger(commandIdsByTrigger);
1007        existingCache.setTriggersByCommandId(triggersByParameterizedCommand);
1008        existingCache.setConflictsByTrigger(conflictsByTrigger);
1009        return Collections.unmodifiableMap(commandIdsByTrigger);
1010    }
1011
1012    /**
1013     * <p>
1014     * Computes the bindings for the current state of the application, but
1015     * disregarding the current contexts. This can be useful when trying to
1016     * display all the possible bindings.
1017     * </p>
1018     * <p>
1019     * This method completes in <code>O(n)</code>, where <code>n</code> is
1020     * the number of bindings.
1021     * </p>
1022     * 
1023     * @return A map of trigger (<code>TriggerSequence</code>) to bindings (
1024     *         <code>Collection</code> containing <code>Binding</code>).
1025     *         This map may be empty, but it is never <code>null</code>.
1026     * @since 3.2
1027     */
1028    private final Map   getActiveBindingsDisregardingContextByParameterizedCommand() {
1029        if (bindings == null) {
1030            // Not yet initialized. This is happening too early. Do nothing.
1031            return Collections.EMPTY_MAP;
1032        }
1033
1034        // Build a cached binding set for that state.
1035        final CachedBindingSet bindingCache = new CachedBindingSet(null,
1036                locales, platforms, activeSchemeIds);
1037
1038        /*
1039         * Check if the cached binding set already exists. If so, simply set the
1040         * active bindings and return.
1041         */
1042        CachedBindingSet existingCache = (CachedBindingSet) cachedBindings
1043                .get(bindingCache);
1044        if (existingCache == null) {
1045            existingCache = bindingCache;
1046            cachedBindings.put(existingCache, existingCache);
1047        }
1048        Map   triggersByParameterizedCommand = existingCache
1049                .getTriggersByCommandId();
1050        if (triggersByParameterizedCommand != null) {
1051            if (DEBUG) {
1052                Tracing.printTrace("BINDINGS", "Cache hit"); //$NON-NLS-1$ //$NON-NLS-2$
1053            }
1054
1055            return Collections.unmodifiableMap(triggersByParameterizedCommand);
1056        }
1057
1058        // There is no cached entry for this.
1059        if (DEBUG) {
1060            Tracing.printTrace("BINDINGS", "Cache miss"); //$NON-NLS-1$ //$NON-NLS-2$
1061        }
1062
1063        // Compute the active bindings.
1064        final Map   commandIdsByTrigger = new HashMap  ();
1065        final Map   conflictsByTrigger = new HashMap  ();
1066        triggersByParameterizedCommand = new HashMap  ();
1067        computeBindings(null, commandIdsByTrigger,
1068                triggersByParameterizedCommand, conflictsByTrigger);
1069        existingCache.setBindingsByTrigger(commandIdsByTrigger);
1070        existingCache.setTriggersByCommandId(triggersByParameterizedCommand);
1071        existingCache.setConflictsByTrigger(conflictsByTrigger);
1072
1073        return Collections.unmodifiableMap(triggersByParameterizedCommand);
1074    }
1075
1076    /**
1077     * <p>
1078     * Computes the bindings for the current state of the application, but
1079     * disregarding the current contexts. This can be useful when trying to
1080     * display all the possible bindings.
1081     * </p>
1082     * <p>
1083     * This method completes in <code>O(n)</code>, where <code>n</code> is
1084     * the number of bindings.
1085     * </p>
1086     * 
1087     * @return All of the active bindings (<code>Binding</code>), not sorted
1088     *         in any fashion. This collection may be empty, but it is never
1089     *         <code>null</code>.
1090     */
1091    public final Collection   getActiveBindingsDisregardingContextFlat() {
1092        final Collection   bindingCollections = getActiveBindingsDisregardingContext()
1093                .values();
1094        final Collection   mergedBindings = new ArrayList  ();
1095        final Iterator   bindingCollectionItr = bindingCollections.iterator();
1096        while (bindingCollectionItr.hasNext()) {
1097            final Collection   bindingCollection = (Collection  ) bindingCollectionItr
1098                    .next();
1099            if ((bindingCollection != null) && (!bindingCollection.isEmpty())) {
1100                mergedBindings.addAll(bindingCollection);
1101            }
1102        }
1103
1104        return mergedBindings;
1105    }
1106
1107    /**
1108     * <p>
1109     * Returns the active bindings for a particular command identifier, but
1110     * discounting the current contexts. This method operates in O(n) time over
1111     * the number of bindings.
1112     * </p>
1113     * <p>
1114     * This method completes in <code>O(1)</code>. If the active bindings are
1115     * not yet computed, then this completes in <code>O(nn)</code>, where
1116     * <code>n</code> is the number of bindings.
1117     * </p>
1118     * 
1119     * @param parameterizedCommand
1120     *            The fully-parameterized command whose bindings are requested.
1121     *            This argument may be <code>null</code>.
1122     * @return The array of active triggers (<code>TriggerSequence</code>)
1123     *         for a particular command identifier. This value is guaranteed to
1124     *         never be <code>null</code>, but it may be empty.
1125     * @since 3.2
1126     */
1127    public final TriggerSequence[] getActiveBindingsDisregardingContextFor(
1128            final ParameterizedCommand parameterizedCommand) {
1129        final Object   object = getActiveBindingsDisregardingContextByParameterizedCommand()
1130                .get(parameterizedCommand);
1131        if (object instanceof Collection  ) {
1132            final Collection   collection = (Collection  ) object;
1133            return (TriggerSequence[]) collection
1134                    .toArray(new TriggerSequence[collection.size()]);
1135        }
1136
1137        return EMPTY_TRIGGER_SEQUENCE;
1138    }
1139
1140    /**
1141     * <p>
1142     * Returns the active bindings for a particular command identifier. This
1143     * method operates in O(n) time over the number of bindings.
1144     * </p>
1145     * <p>
1146     * This method completes in <code>O(1)</code>. If the active bindings are
1147     * not yet computed, then this completes in <code>O(nn)</code>, where
1148     * <code>n</code> is the number of bindings.
1149     * </p>
1150     * 
1151     * @param parameterizedCommand
1152     *            The fully-parameterized command whose bindings are requested.
1153     *            This argument may be <code>null</code>.
1154     * @return The array of active triggers (<code>TriggerSequence</code>)
1155     *         for a particular command identifier. This value is guaranteed to
1156     *         never be <code>null</code>, but it may be empty.
1157     */
1158    public final TriggerSequence[] getActiveBindingsFor(
1159            final ParameterizedCommand parameterizedCommand) {
1160        final Object   object = getActiveBindingsByParameterizedCommand().get(
1161                parameterizedCommand);
1162        if (object instanceof Collection  ) {
1163            final Collection   collection = (Collection  ) object;
1164            return (TriggerSequence[]) collection
1165                    .toArray(new TriggerSequence[collection.size()]);
1166        }
1167
1168        return EMPTY_TRIGGER_SEQUENCE;
1169    }
1170
1171    /**
1172     * <p>
1173     * Returns the active bindings for a particular command identifier. This
1174     * method operates in O(n) time over the number of bindings.
1175     * </p>
1176     * <p>
1177     * This method completes in <code>O(1)</code>. If the active bindings are
1178     * not yet computed, then this completes in <code>O(nn)</code>, where
1179     * <code>n</code> is the number of bindings.
1180     * </p>
1181     * 
1182     * @param commandId
1183     *            The identifier of the command whose bindings are requested.
1184     *            This argument may be <code>null</code>. It is assumed that
1185     *            the command has no parameters.
1186     * @return The array of active triggers (<code>TriggerSequence</code>)
1187     *         for a particular command identifier. This value is guaranteed not
1188     *         to be <code>null</code>, but it may be empty.
1189     */
1190    public final TriggerSequence[] getActiveBindingsFor(final String   commandId) {
1191        final ParameterizedCommand parameterizedCommand = new ParameterizedCommand(
1192                commandManager.getCommand(commandId), null);
1193        final Object   object = getActiveBindingsByParameterizedCommand().get(
1194                parameterizedCommand);
1195        if (object instanceof Collection  ) {
1196            final Collection   collection = (Collection  ) object;
1197            return (TriggerSequence[]) collection
1198                    .toArray(new TriggerSequence[collection.size()]);
1199        }
1200
1201        return EMPTY_TRIGGER_SEQUENCE;
1202    }
1203
1204    /**
1205     * A variation on {@link BindingManager#getActiveBindingsFor(String)} that
1206     * returns an array of bindings, rather than trigger sequences. This method
1207     * is needed for doing "best" calculations on the active bindings.
1208     * 
1209     * @param commandId
1210     *            The identifier of the command for which the active bindings
1211     *            should be retrieved; must not be <code>null</code>.
1212     * @return The active bindings for the given command; this value may be
1213     *         <code>null</code> if there are no active bindings.
1214     * @since 3.2
1215     */
1216    private final Binding[] getActiveBindingsFor1(final String   commandId) {
1217        final TriggerSequence[] triggers = getActiveBindingsFor(commandId);
1218        if (triggers.length == 0) {
1219            return null;
1220        }
1221
1222        final Map   activeBindings = getActiveBindings();
1223        if (activeBindings != null) {
1224            final Binding[] bindings = new Binding[triggers.length];
1225            for (int i = 0; i < triggers.length; i++) {
1226                final TriggerSequence triggerSequence = triggers[i];
1227                final Object   object = activeBindings.get(triggerSequence);
1228                final Binding binding = (Binding) object;
1229                bindings[i] = binding;
1230            }
1231            return bindings;
1232        }
1233
1234        return null;
1235    }
1236
1237    /**
1238     * <p>
1239     * Gets the currently active scheme.
1240     * </p>
1241     * <p>
1242     * This method completes in <code>O(1)</code>.
1243     * </p>
1244     * 
1245     * @return The active scheme; may be <code>null</code> if there is no
1246     *         active scheme. If a scheme is returned, it is guaranteed to be
1247     *         defined.
1248     */
1249    public final Scheme getActiveScheme() {
1250        return activeScheme;
1251    }
1252
1253    /**
1254     * Gets the best active binding for a command. The best binding is the one
1255     * that would be most appropriate to show in a menu. Bindings which belong
1256     * to a child scheme are given preference over those in a parent scheme.
1257     * Bindings which belong to a particular locale or platform are given
1258     * preference over those that do not. The rest of the calculaton is based
1259     * most on various concepts of "length", as well as giving some modifier
1260     * keys preference (e.g., <code>Alt</code> is less likely to appear than
1261     * <code>Ctrl</code>).
1262     * 
1263     * @param commandId
1264     *            The identifier of the command for which the best active
1265     *            binding should be retrieved; must not be <code>null</code>.
1266     * @return The trigger sequence for the best binding; may be
1267     *         <code>null</code> if no bindings are active for the given
1268     *         command.
1269     * @since 3.2
1270     */
1271    public final TriggerSequence getBestActiveBindingFor(final String   commandId) {
1272        final Binding[] bindings = getActiveBindingsFor1(commandId);
1273        if ((bindings == null) || (bindings.length == 0)) {
1274            return null;
1275        }
1276
1277        Binding bestBinding = bindings[0];
1278        int compareTo;
1279        for (int i = 1; i < bindings.length; i++) {
1280            final Binding currentBinding = bindings[i];
1281
1282            // Bindings in a child scheme are always given preference.
1283            final String   bestSchemeId = bestBinding.getSchemeId();
1284            final String   currentSchemeId = currentBinding.getSchemeId();
1285            compareTo = compareSchemes(bestSchemeId, currentSchemeId);
1286            if (compareTo > 0) {
1287                bestBinding = currentBinding;
1288            }
1289            if (compareTo != 0) {
1290                continue;
1291            }
1292
1293            /*
1294             * Bindings with a locale are given preference over those that do
1295             * not.
1296             */
1297            final String   bestLocale = bestBinding.getLocale();
1298            final String   currentLocale = currentBinding.getLocale();
1299            if ((bestLocale == null) && (currentLocale != null)) {
1300                bestBinding = currentBinding;
1301            }
1302            if (!(Util.equals(bestLocale, currentLocale))) {
1303                continue;
1304            }
1305
1306            /*
1307             * Bindings with a platform are given preference over those that do
1308             * not.
1309             */
1310            final String   bestPlatform = bestBinding.getPlatform();
1311            final String   currentPlatform = currentBinding.getPlatform();
1312            if ((bestPlatform == null) && (currentPlatform != null)) {
1313                bestBinding = currentBinding;
1314            }
1315            if (!(Util.equals(bestPlatform, currentPlatform))) {
1316                continue;
1317            }
1318
1319            /*
1320             * Check to see which has the least number of triggers in the
1321             * trigger sequence.
1322             */
1323            final TriggerSequence bestTriggerSequence = bestBinding
1324                    .getTriggerSequence();
1325            final TriggerSequence currentTriggerSequence = currentBinding
1326                    .getTriggerSequence();
1327            final Trigger[] bestTriggers = bestTriggerSequence.getTriggers();
1328            final Trigger[] currentTriggers = currentTriggerSequence
1329                    .getTriggers();
1330            compareTo = bestTriggers.length - currentTriggers.length;
1331            if (compareTo > 0) {
1332                bestBinding = currentBinding;
1333            }
1334            if (compareTo != 0) {
1335                continue;
1336            }
1337
1338            /*
1339             * Compare the number of keys pressed in each trigger sequence. Some
1340             * types of keys count less than others (i.e., some types of
1341             * modifiers keys are less likely to be chosen).
1342             */
1343            compareTo = countStrokes(bestTriggers)
1344                    - countStrokes(currentTriggers);
1345            if (compareTo > 0) {
1346                bestBinding = currentBinding;
1347            }
1348            if (compareTo != 0) {
1349                continue;
1350            }
1351
1352            // If this is still a tie, then just chose the shortest text.
1353            compareTo = bestTriggerSequence.format().length()
1354                    - currentTriggerSequence.format().length();
1355            if (compareTo > 0) {
1356                bestBinding = currentBinding;
1357            }
1358        }
1359
1360        return bestBinding.getTriggerSequence();
1361    }
1362
1363    /**
1364     * Gets the formatted string representing the best active binding for a
1365     * command. The best binding is the one that would be most appropriate to
1366     * show in a menu. Bindings which belong to a child scheme are given
1367     * preference over those in a parent scheme. The rest of the calculaton is
1368     * based most on various concepts of "length", as well as giving some
1369     * modifier keys preference (e.g., <code>Alt</code> is less likely to
1370     * appear than <code>Ctrl</code>).
1371     * 
1372     * @param commandId
1373     *            The identifier of the command for which the best active
1374     *            binding should be retrieved; must not be <code>null</code>.
1375     * @return The formatted string for the best binding; may be
1376     *         <code>null</code> if no bindings are active for the given
1377     *         command.
1378     * @since 3.2
1379     */
1380    public final String   getBestActiveBindingFormattedFor(final String   commandId) {
1381        final TriggerSequence binding = getBestActiveBindingFor(commandId);
1382        if (binding != null) {
1383            return binding.format();
1384        }
1385
1386        return null;
1387    }
1388
1389    /**
1390     * <p>
1391     * Returns the set of all bindings managed by this class.
1392     * </p>
1393     * <p>
1394     * This method completes in <code>O(1)</code>.
1395     * </p>
1396     * 
1397     * @return The array of all bindings. This value may be <code>null</code>
1398     *         and it may be empty.
1399     */
1400    public final Binding[] getBindings() {
1401        if (bindings == null) {
1402            return null;
1403        }
1404
1405        final Binding[] returnValue = new Binding[bindingCount];
1406        System.arraycopy(bindings, 0, returnValue, 0, bindingCount);
1407        return returnValue;
1408    }
1409
1410    /**
1411     * <p>
1412     * Returns the array of schemes that are defined.
1413     * </p>
1414     * <p>
1415     * This method completes in <code>O(1)</code>.
1416     * </p>
1417     * 
1418     * @return The array of defined schemes; this value may be empty or
1419     *         <code>null</code>.
1420     */
1421    public final Scheme[] getDefinedSchemes() {
1422        return (Scheme[]) definedHandleObjects
1423                .toArray(new Scheme[definedHandleObjects.size()]);
1424    }
1425
1426    /**
1427     * <p>
1428     * Returns the active locale for this binding manager. The locale is in the
1429     * same format as <code>Locale.getDefault().toString()</code>.
1430     * </p>
1431     * <p>
1432     * This method completes in <code>O(1)</code>.
1433     * </p>
1434     * 
1435     * @return The active locale; never <code>null</code>.
1436     */
1437    public final String   getLocale() {
1438        return locale;
1439    }
1440
1441    /**
1442     * <p>
1443     * Returns all of the possible bindings that start with the given trigger
1444     * (but are not equal to the given trigger).
1445     * </p>
1446     * <p>
1447     * This method completes in <code>O(1)</code>. If the bindings aren't
1448     * currently computed, then this completes in <code>O(n)</code>, where
1449     * <code>n</code> is the number of bindings.
1450     * </p>
1451     * 
1452     * @param trigger
1453     *            The prefix to look for; must not be <code>null</code>.
1454     * @return A map of triggers (<code>TriggerSequence</code>) to bindings (<code>Binding</code>).
1455     *         This map may be empty, but it is never <code>null</code>.
1456     */
1457    public final Map   getPartialMatches(final TriggerSequence trigger) {
1458        final Map   partialMatches = (Map  ) getPrefixTable().get(trigger);
1459        if (partialMatches == null) {
1460            return Collections.EMPTY_MAP;
1461        }
1462
1463        return partialMatches;
1464    }
1465
1466    /**
1467     * <p>
1468     * Returns the command identifier for the active binding matching this
1469     * trigger, if any.
1470     * </p>
1471     * <p>
1472     * This method completes in <code>O(1)</code>. If the bindings aren't
1473     * currently computed, then this completes in <code>O(n)</code>, where
1474     * <code>n</code> is the number of bindings.
1475     * </p>
1476     * 
1477     * @param trigger
1478     *            The trigger to match; may be <code>null</code>.
1479     * @return The binding that matches, if any; <code>null</code> otherwise.
1480     */
1481    public final Binding getPerfectMatch(final TriggerSequence trigger) {
1482        return (Binding) getActiveBindings().get(trigger);
1483    }
1484
1485    /**
1486     * <p>
1487     * Returns the active platform for this binding manager. The platform is in
1488     * the same format as <code>SWT.getPlatform()</code>.
1489     * </p>
1490     * <p>
1491     * This method completes in <code>O(1)</code>.
1492     * </p>
1493     * 
1494     * @return The active platform; never <code>null</code>.
1495     */
1496    public final String   getPlatform() {
1497        return platform;
1498    }
1499
1500    /**
1501     * <p>
1502     * Returns the prefix table. The caller must not modify the returned map.
1503     * </p>
1504     * <p>
1505     * This method completes in <code>O(1)</code>. If the active bindings are
1506     * not yet computed, then this completes in <code>O(n)</code>, where
1507     * <code>n</code> is the number of bindings.
1508     * </p>
1509     * 
1510     * @return A map of prefixes (<code>TriggerSequence</code>) to a map of
1511     *         available completions (possibly <code>null</code>, which means
1512     *         there is an exact match). The available completions is a map of
1513     *         trigger (<code>TriggerSequence</code>) to binding (<code>Binding</code>).
1514     *         This value will never be <code>null</code> but may be empty.
1515     */
1516    private final Map   getPrefixTable() {
1517        if (prefixTable == null) {
1518            recomputeBindings();
1519        }
1520
1521        return prefixTable;
1522    }
1523
1524    /**
1525     * <p>
1526     * Gets the scheme with the given identifier. If the scheme does not already
1527     * exist, then a new (undefined) scheme is created with that identifier.
1528     * This guarantees that schemes will remain unique.
1529     * </p>
1530     * <p>
1531     * This method completes in amortized <code>O(1)</code>.
1532     * </p>
1533     * 
1534     * @param schemeId
1535     *            The identifier for the scheme to retrieve; must not be
1536     *            <code>null</code>.
1537     * @return A scheme with the given identifier.
1538     */
1539    public final Scheme getScheme(final String   schemeId) {
1540        checkId(schemeId);
1541
1542        Scheme scheme = (Scheme) handleObjectsById.get(schemeId);
1543        if (scheme == null) {
1544            scheme = new Scheme(schemeId);
1545            handleObjectsById.put(schemeId, scheme);
1546            scheme.addSchemeListener(this);
1547        }
1548
1549        return scheme;
1550    }
1551
1552    /**
1553     * <p>
1554     * Ascends all of the parents of the scheme until no more parents are found.
1555     * </p>
1556     * <p>
1557     * This method completes in <code>O(n)</code>, where <code>n</code> is
1558     * the height of the context tree.
1559     * </p>
1560     * 
1561     * @param schemeId
1562     *            The id of the scheme for which the parents should be found;
1563     *            may be <code>null</code>.
1564     * @return The array of scheme ids (<code>String</code>) starting with
1565     *         <code>schemeId</code> and then ascending through its ancestors.
1566     */
1567    private final String  [] getSchemeIds(String   schemeId) {
1568        final List   strings = new ArrayList  ();
1569        while (schemeId != null) {
1570            strings.add(schemeId);
1571            try {
1572                schemeId = getScheme(schemeId).getParentId();
1573            } catch (final NotDefinedException e) {
1574                Policy.getLog().log(
1575                        new Status(IStatus.ERROR, Policy.JFACE, IStatus.OK,
1576                                "Failed ascending scheme parents", //$NON-NLS-1$
1577                                e));
1578                return new String  [0];
1579            }
1580        }
1581
1582        return (String  []) strings.toArray(new String  [strings.size()]);
1583    }
1584
1585    /**
1586     * <p>
1587     * Returns whether the given trigger sequence is a partial match for the
1588     * given sequence.
1589     * </p>
1590     * <p>
1591     * This method completes in <code>O(1)</code>. If the bindings aren't
1592     * currently computed, then this completes in <code>O(n)</code>, where
1593     * <code>n</code> is the number of bindings.
1594     * </p>
1595     * 
1596     * @param trigger
1597     *            The sequence which should be the prefix for some binding;
1598     *            should not be <code>null</code>.
1599     * @return <code>true</code> if the trigger can be found in the active
1600     *         bindings; <code>false</code> otherwise.
1601     */
1602    public final boolean isPartialMatch(final TriggerSequence trigger) {
1603        return (getPrefixTable().get(trigger) != null);
1604    }
1605
1606    /**
1607     * <p>
1608     * Returns whether the given trigger sequence is a perfect match for the
1609     * given sequence.
1610     * </p>
1611     * <p>
1612     * This method completes in <code>O(1)</code>. If the bindings aren't
1613     * currently computed, then this completes in <code>O(n)</code>, where
1614     * <code>n</code> is the number of bindings.
1615     * </p>
1616     * 
1617     * @param trigger
1618     *            The sequence which should match exactly; should not be
1619     *            <code>null</code>.
1620     * @return <code>true</code> if the trigger can be found in the active
1621     *         bindings; <code>false</code> otherwise.
1622     */
1623    public final boolean isPerfectMatch(final TriggerSequence trigger) {
1624        return getActiveBindings().containsKey(trigger);
1625    }
1626
1627    /**
1628     * <p>
1629     * Tests whether the locale for the binding matches one of the active
1630     * locales.
1631     * </p>
1632     * <p>
1633     * This method completes in <code>O(n)</code>, where <code>n</code> is
1634     * the number of active locales.
1635     * </p>
1636     * 
1637     * @param binding
1638     *            The binding with which to test; must not be <code>null</code>.
1639     * @return <code>true</code> if the binding's locale matches;
1640     *         <code>false</code> otherwise.
1641     */
1642    private final boolean localeMatches(final Binding binding) {
1643        boolean matches = false;
1644
1645        final String   locale = binding.getLocale();
1646        if (locale == null) {
1647            return true; // shortcut a common case
1648        }
1649
1650        for (int i = 0; i < locales.length; i++) {
1651            if (Util.equals(locales[i], locale)) {
1652                matches = true;
1653                break;
1654            }
1655        }
1656
1657        return matches;
1658    }
1659
1660    /**
1661     * <p>
1662     * Tests whether the platform for the binding matches one of the active
1663     * platforms.
1664     * </p>
1665     * <p>
1666     * This method completes in <code>O(n)</code>, where <code>n</code> is
1667     * the number of active platforms.
1668     * </p>
1669     * 
1670     * @param binding
1671     *            The binding with which to test; must not be <code>null</code>.
1672     * @return <code>true</code> if the binding's platform matches;
1673     *         <code>false</code> otherwise.
1674     */
1675    private final boolean platformMatches(final Binding binding) {
1676        boolean matches = false;
1677
1678        final String   platform = binding.getPlatform();
1679        if (platform == null) {
1680            return true; // shortcut a common case
1681        }
1682
1683        for (int i = 0; i < platforms.length; i++) {
1684            if (Util.equals(platforms[i], platform)) {
1685                matches = true;
1686                break;
1687            }
1688        }
1689
1690        return matches;
1691    }
1692
1693    /**
1694     * <p>
1695     * This recomputes the bindings based on changes to the state of the world.
1696     * This computation can be triggered by changes to contexts, the active
1697     * scheme, the locale, or the platform. This method tries to use the cache
1698     * of pre-computed bindings, if possible. When this method completes,
1699     * <code>activeBindings</code> will be set to the current set of bindings
1700     * and <code>cachedBindings</code> will contain an instance of
1701     * <code>CachedBindingSet</code> representing these bindings.
1702     * </p>
1703     * <p>
1704     * This method completes in <code>O(n+pn)</code>, where <code>n</code>
1705     * is the number of bindings, and <code>p</code> is the average number of
1706     * triggers in a trigger sequence.
1707     * </p>
1708     */
1709    private final void recomputeBindings() {
1710        if (bindings == null) {
1711            // Not yet initialized. This is happening too early. Do nothing.
1712            setActiveBindings(Collections.EMPTY_MAP, Collections.EMPTY_MAP,
1713                    Collections.EMPTY_MAP, Collections.EMPTY_MAP);
1714            return;
1715        }
1716
1717        // Figure out the current state.
1718        final Set   activeContextIds = new HashSet  (contextManager
1719                .getActiveContextIds());
1720        final Map   activeContextTree = createFilteredContextTreeFor(activeContextIds);
1721
1722        // Build a cached binding set for that state.
1723        final CachedBindingSet bindingCache = new CachedBindingSet(
1724                activeContextTree, locales, platforms, activeSchemeIds);
1725
1726        /*
1727         * Check if the cached binding set already exists. If so, simply set the
1728         * active bindings and return.
1729         */
1730        CachedBindingSet existingCache = (CachedBindingSet) cachedBindings
1731                .get(bindingCache);
1732        if (existingCache == null) {
1733            existingCache = bindingCache;
1734            cachedBindings.put(existingCache, existingCache);
1735        }
1736        Map   commandIdsByTrigger = existingCache.getBindingsByTrigger();
1737        if (commandIdsByTrigger != null) {
1738            if (DEBUG) {
1739                Tracing.printTrace("BINDINGS", "Cache hit"); //$NON-NLS-1$ //$NON-NLS-2$
1740            }
1741            setActiveBindings(commandIdsByTrigger, existingCache
1742                    .getTriggersByCommandId(), existingCache.getPrefixTable(),
1743                    existingCache.getConflictsByTrigger());
1744            return;
1745        }
1746
1747        // There is no cached entry for this.
1748        if (DEBUG) {
1749            Tracing.printTrace("BINDINGS", "Cache miss"); //$NON-NLS-1$ //$NON-NLS-2$
1750        }
1751
1752        // Compute the active bindings.
1753        commandIdsByTrigger = new HashMap  ();
1754        final Map   triggersByParameterizedCommand = new HashMap  ();
1755        final Map   conflictsByTrigger = new HashMap  ();
1756        computeBindings(activeContextTree, commandIdsByTrigger,
1757                triggersByParameterizedCommand, conflictsByTrigger);
1758        existingCache.setBindingsByTrigger(commandIdsByTrigger);
1759        existingCache.setTriggersByCommandId(triggersByParameterizedCommand);
1760        existingCache.setConflictsByTrigger(conflictsByTrigger);
1761        setActiveBindings(commandIdsByTrigger, triggersByParameterizedCommand,
1762                buildPrefixTable(commandIdsByTrigger),
1763                conflictsByTrigger);
1764        existingCache.setPrefixTable(prefixTable);
1765    }
1766
1767    /**
1768     * <p>
1769     * Remove the specific binding by identity. Does nothing if the binding is
1770     * not in the manager.
1771     * </p>
1772     * <p>
1773     * This method completes in <code>O(n)</code>, where <code>n</code> is
1774     * the number of bindings.
1775     * </p>
1776     * 
1777     * @param binding
1778     *            The binding to be removed; must not be <code>null</code>.
1779     * @since 3.2
1780     */
1781    public final void removeBinding(final Binding binding) {
1782        if (bindings == null || bindings.length < 1) {
1783            return;
1784        }
1785
1786        final Binding[] newBindings = new Binding[bindings.length];
1787        boolean bindingsChanged = false;
1788        int index = 0;
1789        for (int i = 0; i < bindingCount; i++) {
1790            final Binding b = bindings[i];
1791            if (b == binding) {
1792                bindingsChanged = true;
1793            } else {
1794                newBindings[index++] = b;
1795            }
1796        }
1797
1798        if (bindingsChanged) {
1799            this.bindings = newBindings;
1800            bindingCount = index;
1801            clearCache();
1802        }
1803    }
1804
1805    /**
1806     * <p>
1807     * Removes a listener from this binding manager.
1808     * </p>
1809     * <p>
1810     * This method completes in amortized <code>O(1)</code>.
1811     * </p>
1812     * 
1813     * @param listener
1814     *            The listener to be removed; must not be <code>null</code>.
1815     */
1816    public final void removeBindingManagerListener(
1817            final IBindingManagerListener listener) {
1818        removeListenerObject(listener);
1819    }
1820
1821    /**
1822     * <p>
1823     * Removes any binding that matches the given values -- regardless of
1824     * command identifier.
1825     * </p>
1826     * <p>
1827     * This method completes in <code>O(n)</code>, where <code>n</code> is
1828     * the number of bindings.
1829     * </p>
1830     * 
1831     * @param sequence
1832     *            The sequence to match; may be <code>null</code>.
1833     * @param schemeId
1834     *            The scheme id to match; may be <code>null</code>.
1835     * @param contextId
1836     *            The context id to match; may be <code>null</code>.
1837     * @param locale
1838     *            The locale to match; may be <code>null</code>.
1839     * @param platform
1840     *            The platform to match; may be <code>null</code>.
1841     * @param windowManager
1842     *            The window manager to match; may be <code>null</code>. TODO
1843     *            Currently ignored.
1844     * @param type
1845     *            The type to look for.
1846     * 
1847     */
1848    public final void removeBindings(final TriggerSequence sequence,
1849            final String   schemeId, final String   contextId, final String   locale,
1850            final String   platform, final String   windowManager, final int type) {
1851        if ((bindings == null) || (bindingCount < 1)) {
1852            return;
1853        }
1854
1855        final Binding[] newBindings = new Binding[bindings.length];
1856        boolean bindingsChanged = false;
1857        int index = 0;
1858        for (int i = 0; i < bindingCount; i++) {
1859            final Binding binding = bindings[i];
1860            boolean equals = true;
1861            equals &= Util.equals(sequence, binding.getTriggerSequence());
1862            equals &= Util.equals(schemeId, binding.getSchemeId());
1863            equals &= Util.equals(contextId, binding.getContextId());
1864            equals &= Util.equals(locale, binding.getLocale());
1865            equals &= Util.equals(platform, binding.getPlatform());
1866            equals &= (type == binding.getType());
1867            if (equals) {
1868                bindingsChanged = true;
1869            } else {
1870                newBindings[index++] = binding;
1871            }
1872        }
1873
1874        if (bindingsChanged) {
1875            this.bindings = newBindings;
1876            bindingCount = index;
1877            clearCache();
1878        }
1879    }
1880
1881    /**
1882     * <p>
1883     * Attempts to remove deletion markers from the collection of bindings.
1884     * </p>
1885     * <p>
1886     * This method completes in <code>O(n)</code>, where <code>n</code> is
1887     * the number of bindings.
1888     * </p>
1889     * 
1890     * @param bindings
1891     *            The bindings from which the deleted items should be removed.
1892     *            This array should not be <code>null</code>, but may be
1893     *            empty.
1894     * @return The array of bindings with the deletions removed; never
1895     *         <code>null</code>, but may be empty. Contains only instances
1896     *         of <code>Binding</code>.
1897     */
1898    private final Binding[] removeDeletions(final Binding[] bindings) {
1899        final Map   deletions = new HashMap  ();
1900        final Binding[] bindingsCopy = new Binding[bindingCount];
1901        System.arraycopy(bindings, 0, bindingsCopy, 0, bindingCount);
1902        int deletedCount = 0;
1903
1904        // Extract the deletions.
1905        for (int i = 0; i < bindingCount; i++) {
1906            final Binding binding = bindingsCopy[i];
1907            if ((binding.getParameterizedCommand() == null)
1908                    && (localeMatches(binding)) && (platformMatches(binding))) {
1909                final TriggerSequence sequence = binding.getTriggerSequence();
1910                final Object   currentValue = deletions.get(sequence);
1911                if (currentValue instanceof Binding) {
1912                    final Collection   collection = new ArrayList  (2);
1913                    collection.add(currentValue);
1914                    collection.add(binding);
1915                    deletions.put(sequence, collection);
1916                } else if (currentValue instanceof Collection  ) {
1917                    final Collection   collection = (Collection  ) currentValue;
1918                    collection.add(binding);
1919                } else {
1920                    deletions.put(sequence, binding);
1921                }
1922                bindingsCopy[i] = null;
1923                deletedCount++;
1924            }
1925        }
1926
1927        if (DEBUG) {
1928            Tracing.printTrace("BINDINGS", "There are " + deletions.size() //$NON-NLS-1$ //$NON-NLS-2$
1929                    + " deletion markers"); //$NON-NLS-1$
1930        }
1931
1932        // Remove the deleted items.
1933        for (int i = 0; i < bindingCount; i++) {
1934            final Binding binding = bindingsCopy[i];
1935            if (binding != null) {
1936                final Object   deletion = deletions.get(binding
1937                        .getTriggerSequence());
1938                if (deletion instanceof Binding) {
1939                    if (((Binding) deletion).deletes(binding)) {
1940                        bindingsCopy[i] = null;
1941                        deletedCount++;
1942                    }
1943
1944                } else if (deletion instanceof Collection  ) {
1945                    final Collection   collection = (Collection  ) deletion;
1946                    final Iterator   iterator = collection.iterator();
1947                    while (iterator.hasNext()) {
1948                        final Object   deletionBinding = iterator.next();
1949                        if (deletionBinding instanceof Binding) {
1950                            if (((Binding) deletionBinding).deletes(binding)) {
1951                                bindingsCopy[i] = null;
1952                                deletedCount++;
1953                                break;
1954                            }
1955                        }
1956                    }
1957
1958                }
1959            }
1960        }
1961
1962        // Compact the array.
1963        final Binding[] returnValue = new Binding[bindingCount - deletedCount];
1964        int index = 0;
1965        for (int i = 0; i < bindingCount; i++) {
1966            final Binding binding = bindingsCopy[i];
1967            if (binding != null) {
1968                returnValue[index++] = binding;
1969            }
1970        }
1971
1972        return returnValue;
1973    }
1974
1975    /**
1976     * <p>
1977     * Attempts to resolve the conflicts for the given bindings.
1978     * </p>
1979     * <p>
1980     * This method completes in <code>O(n)</code>, where <code>n</code> is
1981     * the number of bindings.
1982     * </p>
1983     * 
1984     * @param bindings
1985     *            The bindings which all match the same trigger sequence; must
1986     *            not be <code>null</code>, and should contain at least two
1987     *            items. This collection should only contain instances of
1988     *            <code>Binding</code> (i.e., no <code>null</code> values).
1989     * @param activeContextTree
1990     *            The tree of contexts to be used for all of the comparison. All
1991     *            of the keys should be active context identifiers (i.e., never
1992     *            <code>null</code>). The values will be their parents (i.e.,
1993     *            possibly <code>null</code>). Both keys and values are
1994     *            context identifiers (<code>String</code>). This map should
1995     *            never be empty, and must never be <code>null</code>.
1996     * @return The binding which best matches the current state. If there is a
1997     *         tie, then return <code>null</code>.
1998     */
1999    private final Binding resolveConflicts(final Collection   bindings,
2000            final Map   activeContextTree) {
2001        /*
2002         * This flag is used to indicate when the bestMatch binding conflicts
2003         * with another binding. We keep the best match binding so that we know
2004         * if we find a better binding. However, if we don't find a better
2005         * binding, then we known to return null.
2006         */
2007        boolean conflict = false;
2008
2009        final Iterator   bindingItr = bindings.iterator();
2010        Binding bestMatch = (Binding) bindingItr.next();
2011
2012        /*
2013         * Iterate over each binding and compare it with the best match. If a
2014         * better match is found, then replace the best match and set the
2015         * conflict flag to false. If a conflict is found, then leave the best
2016         * match and set the conflict flag. Otherwise, just continue.
2017         */
2018        while (bindingItr.hasNext()) {
2019            final Binding current = (Binding) bindingItr.next();
2020
2021            /*
2022             * SCHEME: Test whether the current is in a child scheme. Bindings
2023             * defined in a child scheme will always take priority over bindings
2024             * defined in a parent scheme.
2025             */
2026            final String   currentSchemeId = current.getSchemeId();
2027            final String   bestSchemeId = bestMatch.getSchemeId();
2028            final int compareTo = compareSchemes(bestSchemeId, currentSchemeId);
2029            if (compareTo > 0) {
2030                bestMatch = current;
2031                conflict = false;
2032            }
2033            if (compareTo != 0) {
2034                continue;
2035            }
2036
2037            /*
2038             * CONTEXTS: Check for context superiority. Bindings defined in a
2039             * child context will take priority over bindings defined in a
2040             * parent context -- assuming that the schemes lead to a conflict.
2041             */
2042            final String   currentContext = current.getContextId();
2043            final String   bestContext = bestMatch.getContextId();
2044            if (!currentContext.equals(bestContext)) {
2045                boolean goToNextBinding = false;
2046
2047                // Ascend the current's context tree.
2048                String   contextPointer = currentContext;
2049                while (contextPointer != null) {
2050                    if (contextPointer.equals(bestContext)) {
2051                        // the current wins
2052                        bestMatch = current;
2053                        conflict = false;
2054                        goToNextBinding = true;
2055                        break;
2056                    }
2057                    contextPointer = (String  ) activeContextTree
2058                            .get(contextPointer);
2059                }
2060
2061                // Ascend the best match's context tree.
2062                contextPointer = bestContext;
2063                while (contextPointer != null) {
2064                    if (contextPointer.equals(currentContext)) {
2065                        // the best wins
2066                        goToNextBinding = true;
2067                        break;
2068                    }
2069                    contextPointer = (String  ) activeContextTree
2070                            .get(contextPointer);
2071                }
2072
2073                if (goToNextBinding) {
2074                    continue;
2075                }
2076            }
2077
2078            /*
2079             * TYPE: Test for type superiority.
2080             */
2081            if (current.getType() > bestMatch.getType()) {
2082                bestMatch = current;
2083                conflict = false;
2084                continue;
2085            } else if (bestMatch.getType() > current.getType()) {
2086                continue;
2087            }
2088
2089            // We could not resolve the conflict between these two.
2090            conflict = true;
2091        }
2092
2093        // If the best match represents a conflict, then return null.
2094        if (conflict) {
2095            return null;
2096        }
2097
2098        // Otherwise, we have a winner....
2099        return bestMatch;
2100    }
2101
2102    /**
2103     * <p>
2104     * Notifies this manager that a scheme has changed. This method is intended
2105     * for internal use only.
2106     * </p>
2107     * <p>
2108     * This method calls out to listeners, and so the time it takes to complete
2109     * is dependent on third-party code.
2110     * </p>
2111     * 
2112     * @param schemeEvent
2113     *            An event describing the change in the scheme.
2114     */
2115    public final void schemeChanged(final SchemeEvent schemeEvent) {
2116        if (schemeEvent.isDefinedChanged()) {
2117            final Scheme scheme = schemeEvent.getScheme();
2118            final boolean schemeIdAdded = scheme.isDefined();
2119            boolean activeSchemeChanged = false;
2120            if (schemeIdAdded) {
2121                definedHandleObjects.add(scheme);
2122            } else {
2123                definedHandleObjects.remove(scheme);
2124
2125                if (activeScheme == scheme) {
2126                    activeScheme = null;
2127                    activeSchemeIds = null;
2128                    activeSchemeChanged = true;
2129
2130                    // Clear the binding solution.
2131                    clearSolution();
2132                }
2133            }
2134
2135            if (isListenerAttached()) {
2136                fireBindingManagerChanged(new BindingManagerEvent(this, false,
2137                        null, activeSchemeChanged, scheme, schemeIdAdded,
2138                        false, false));
2139            }
2140        }
2141    }
2142
2143    /**
2144     * Sets the active bindings and the prefix table. This ensures that the two
2145     * values change at the same time, and that any listeners are notified
2146     * appropriately.
2147     * 
2148     * @param activeBindings
2149     *            This is a map of triggers ( <code>TriggerSequence</code>)
2150     *            to bindings (<code>Binding</code>). This value will only
2151     *            be <code>null</code> if the active bindings have not yet
2152     *            been computed. Otherwise, this value may be empty.
2153     * @param activeBindingsByCommandId
2154     *            This is a map of fully-parameterized commands (<code>ParameterizedCommand</code>)
2155     *            to triggers ( <code>TriggerSequence</code>). This value
2156     *            will only be <code>null</code> if the active bindings have
2157     *            not yet been computed. Otherwise, this value may be empty.
2158     * @param prefixTable
2159     *            A map of prefixes (<code>TriggerSequence</code>) to a map
2160     *            of available completions (possibly <code>null</code>, which
2161     *            means there is an exact match). The available completions is a
2162     *            map of trigger (<code>TriggerSequence</code>) to binding (<code>Binding</code>).
2163     *            This value may be <code>null</code> if there is no existing
2164     *            solution.
2165     */
2166    private final void setActiveBindings(final Map   activeBindings,
2167            final Map   activeBindingsByCommandId, final Map   prefixTable,
2168            final Map   conflicts) {
2169        this.activeBindings = activeBindings;
2170        final Map   previousBindingsByParameterizedCommand = this.activeBindingsByParameterizedCommand;
2171        this.activeBindingsByParameterizedCommand = activeBindingsByCommandId;
2172        this.prefixTable = prefixTable;
2173        InternalPolicy.currentConflicts = conflicts;
2174
2175        fireBindingManagerChanged(new BindingManagerEvent(this, true,
2176                previousBindingsByParameterizedCommand, false, null, false,
2177                false, false));
2178    }
2179
2180    /**
2181     * <p>
2182     * Selects one of the schemes as the active scheme. This scheme must be
2183     * defined.
2184     * </p>
2185     * <p>
2186     * This method completes in <code>O(n)</code>, where <code>n</code> is
2187     * the height of the context tree.
2188     * </p>
2189     * 
2190     * @param scheme
2191     *            The scheme to become active; must not be <code>null</code>.
2192     * @throws NotDefinedException
2193     *             If the given scheme is currently undefined.
2194     */
2195    public final void setActiveScheme(final Scheme scheme)
2196            throws NotDefinedException {
2197        if (scheme == null) {
2198            throw new NullPointerException  ("Cannot activate a null scheme"); //$NON-NLS-1$
2199        }
2200
2201        if ((scheme == null) || (!scheme.isDefined())) {
2202            throw new NotDefinedException(
2203                    "Cannot activate an undefined scheme. " //$NON-NLS-1$
2204                            + scheme.getId());
2205        }
2206
2207        if (Util.equals(activeScheme, scheme)) {
2208            return;
2209        }
2210
2211        activeScheme = scheme;
2212        activeSchemeIds = getSchemeIds(activeScheme.getId());
2213        clearSolution();
2214        fireBindingManagerChanged(new BindingManagerEvent(this, false, null,
2215                true, null, false, false, false));
2216    }
2217
2218    /**
2219     * <p>
2220     * Changes the set of bindings for this binding manager. Changing the set of
2221     * bindings all at once ensures that: (1) duplicates are removed; and (2)
2222     * avoids unnecessary intermediate computations. This method clears the
2223     * existing bindings, but does not trigger a recomputation (other method
2224     * calls are required to do that).
2225     * </p>
2226     * <p>
2227     * This method completes in <code>O(n)</code>, where <code>n</code> is
2228     * the number of bindings.
2229     * </p>
2230     * 
2231     * @param bindings
2232     *            The new array of bindings; may be <code>null</code>. This
2233     *            set is copied into a local data structure.
2234     */
2235    public final void setBindings(final Binding[] bindings) {
2236        if (Arrays.equals(this.bindings, bindings)) {
2237            return; // nothing has changed
2238        }
2239
2240        if ((bindings == null) || (bindings.length == 0)) {
2241            this.bindings = null;
2242            bindingCount = 0;
2243        } else {
2244            final int bindingsLength = bindings.length;
2245            this.bindings = new Binding[bindingsLength];
2246            System.arraycopy(bindings, 0, this.bindings, 0, bindingsLength);
2247            bindingCount = bindingsLength;
2248        }
2249        clearCache();
2250    }
2251
2252    /**
2253     * <p>
2254     * Changes the locale for this binding manager. The locale can be used to
2255     * provide locale-specific bindings. If the locale is different than the
2256     * current locale, this will force a recomputation of the bindings. The
2257     * locale is in the same format as
2258     * <code>Locale.getDefault().toString()</code>.
2259     * </p>
2260     * <p>
2261     * This method completes in <code>O(1)</code>.
2262     * </p>
2263     * 
2264     * @param locale
2265     *            The new locale; must not be <code>null</code>.
2266     * @see Locale#getDefault()
2267     */
2268    public final void setLocale(final String   locale) {
2269        if (locale == null) {
2270            throw new NullPointerException  ("The locale cannot be null"); //$NON-NLS-1$
2271        }
2272
2273        if (!Util.equals(this.locale, locale)) {
2274            this.locale = locale;
2275            this.locales = expand(locale, LOCALE_SEPARATOR);
2276            clearSolution();
2277            fireBindingManagerChanged(new BindingManagerEvent(this, false,
2278                    null, false, null, false, true, false));
2279        }
2280    }
2281
2282    /**
2283     * <p>
2284     * Changes the platform for this binding manager. The platform can be used
2285     * to provide platform-specific bindings. If the platform is different than
2286     * the current platform, then this will force a recomputation of the
2287     * bindings. The locale is in the same format as
2288     * <code>SWT.getPlatform()</code>.
2289     * </p>
2290     * <p>
2291     * This method completes in <code>O(1)</code>.
2292     * </p>
2293     * 
2294     * @param platform
2295     *            The new platform; must not be <code>null</code>.
2296     * @see org.eclipse.swt.SWT#getPlatform()
2297     */
2298    public final void setPlatform(final String   platform) {
2299        if (platform == null) {
2300            throw new NullPointerException  ("The platform cannot be null"); //$NON-NLS-1$
2301        }
2302
2303        if (!Util.equals(this.platform, platform)) {
2304            this.platform = platform;
2305            this.platforms = expand(platform, Util.ZERO_LENGTH_STRING);
2306            clearSolution();
2307            fireBindingManagerChanged(new BindingManagerEvent(this, false,
2308                    null, false, null, false, false, true));
2309        }
2310    }
2311}
2312
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags