/*******************************************************************************
 * Copyright (c) 2000, 2003 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-v10.html
 * 
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/

package org.eclipse.ui.internal.commands;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import org.eclipse.ui.internal.WorkbenchPlugin;
import org.eclipse.ui.internal.util.Util;
import org.eclipse.ui.keys.KeySequence;
import org.eclipse.ui.keys.KeyStroke;

final class KeySequenceBindingNode {

	final static class Assignment implements Comparable {
		boolean hasPluginCommandIdInFirstKeyConfiguration;
		boolean hasPluginCommandIdInInheritedKeyConfiguration;

		boolean hasPreferenceCommandIdInFirstKeyConfiguration;
		boolean hasPreferenceCommandIdInInheritedKeyConfiguration;
		String pluginCommandIdInFirstKeyConfiguration;
		String pluginCommandIdInInheritedKeyConfiguration;
		String preferenceCommandIdInFirstKeyConfiguration;
		String preferenceCommandIdInInheritedKeyConfiguration;

		public int compareTo(Object object) {
			Assignment castedObject = (Assignment) object;
			int compareTo =
				hasPreferenceCommandIdInFirstKeyConfiguration == false
					? (castedObject.hasPreferenceCommandIdInFirstKeyConfiguration
						== true
						? -1
						: 0)
					: 1;

			if (compareTo == 0) {
				compareTo =
					hasPreferenceCommandIdInInheritedKeyConfiguration == false
						? (castedObject
							.hasPreferenceCommandIdInInheritedKeyConfiguration
							== true
							? -1
							: 0)
						: 1;

				if (compareTo == 0) {
					compareTo =
						hasPluginCommandIdInFirstKeyConfiguration == false
							? (castedObject
								.hasPluginCommandIdInFirstKeyConfiguration
								== true
								? -1
								: 0)
							: 1;

					if (compareTo == 0) {
						compareTo =
							hasPluginCommandIdInInheritedKeyConfiguration
								== false
								? (castedObject
									.hasPluginCommandIdInInheritedKeyConfiguration
									== true
									? -1
									: 0)
								: 1;

						if (compareTo == 0) {
							compareTo =
								Util.compare(
									preferenceCommandIdInFirstKeyConfiguration,
									castedObject
										.preferenceCommandIdInFirstKeyConfiguration);

							if (compareTo == 0) {
								compareTo =
									Util.compare(
										preferenceCommandIdInInheritedKeyConfiguration,
										castedObject
											.preferenceCommandIdInInheritedKeyConfiguration);

								if (compareTo == 0) {
									compareTo =
										Util.compare(
											pluginCommandIdInFirstKeyConfiguration,
											castedObject
												.pluginCommandIdInFirstKeyConfiguration);

									if (compareTo == 0)
										compareTo =
											Util.compare(
												pluginCommandIdInInheritedKeyConfiguration,
												castedObject
													.pluginCommandIdInInheritedKeyConfiguration);
								}
							}
						}
					}
				}
			}

			return compareTo;
		}

		boolean contains(String commandId) {
			return Util.equals(
				commandId,
				preferenceCommandIdInFirstKeyConfiguration)
				|| Util.equals(
					commandId,
					preferenceCommandIdInInheritedKeyConfiguration)
				|| Util.equals(commandId, pluginCommandIdInFirstKeyConfiguration)
				|| Util.equals(
					commandId,
					pluginCommandIdInInheritedKeyConfiguration);
		}

		public boolean equals(Object object) {
			if (!(object instanceof Assignment))
				return false;

			Assignment castedObject = (Assignment) object;
			boolean equals = true;
			equals &= hasPreferenceCommandIdInFirstKeyConfiguration
				== castedObject.hasPreferenceCommandIdInFirstKeyConfiguration;
			equals &= hasPreferenceCommandIdInInheritedKeyConfiguration
				== castedObject.hasPreferenceCommandIdInInheritedKeyConfiguration;
			equals &= hasPluginCommandIdInFirstKeyConfiguration
				== castedObject.hasPluginCommandIdInFirstKeyConfiguration;
			equals &= hasPluginCommandIdInInheritedKeyConfiguration
				== castedObject.hasPluginCommandIdInInheritedKeyConfiguration;
			equals &= preferenceCommandIdInFirstKeyConfiguration
				== castedObject.preferenceCommandIdInFirstKeyConfiguration;
			equals &= preferenceCommandIdInInheritedKeyConfiguration
				== castedObject.preferenceCommandIdInInheritedKeyConfiguration;
			equals &= pluginCommandIdInFirstKeyConfiguration
				== castedObject.pluginCommandIdInFirstKeyConfiguration;
			equals &= pluginCommandIdInInheritedKeyConfiguration
				== castedObject.pluginCommandIdInInheritedKeyConfiguration;
			return equals;
		}
	}

	static void add(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence keySequence,
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale,
		String commandId) {
		List keyStrokes = keySequence.getKeyStrokes();
		Map root = keyStrokeNodeByKeyStrokeMap;
		KeySequenceBindingNode keySequenceBindingNode = null;

		for (int i = 0; i < keyStrokes.size(); i++) {
			KeyStroke keyStroke = (KeyStroke) keyStrokes.get(i);
			keySequenceBindingNode =
				(KeySequenceBindingNode) root.get(keyStroke);

			if (keySequenceBindingNode == null) {
				keySequenceBindingNode = new KeySequenceBindingNode();
				root.put(keyStroke, keySequenceBindingNode);
			}

			root = keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap;
		}

		if (keySequenceBindingNode != null)
			keySequenceBindingNode.add(
				contextId,
				keyConfigurationId,
				rank,
				platform,
				locale,
				commandId);
	}

	static Map find(Map keyStrokeNodeByKeyStrokeMap, KeySequence keySequence) {
		Iterator iterator = keySequence.getKeyStrokes().iterator();
		KeySequenceBindingNode keySequenceBindingNode = null;

		while (iterator.hasNext()) {
			keySequenceBindingNode =
				(KeySequenceBindingNode) keyStrokeNodeByKeyStrokeMap.get(
					iterator.next());

			if (keySequenceBindingNode == null)
				return null;

			keyStrokeNodeByKeyStrokeMap =
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap;
		}

		return keyStrokeNodeByKeyStrokeMap;
	}

	static Map getAssignmentsByContextIdKeySequence(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence prefix) {
		Map assignmentsByContextIdByKeySequence = new HashMap();
		Iterator iterator = keyStrokeNodeByKeyStrokeMap.entrySet().iterator();

		while (iterator.hasNext()) {
			Map.Entry entry = (Map.Entry) iterator.next();
			KeyStroke keyStroke = (KeyStroke) entry.getKey();
			KeySequenceBindingNode keySequenceBindingNode =
				(KeySequenceBindingNode) entry.getValue();
			List keyStrokes = new ArrayList(prefix.getKeyStrokes());
			keyStrokes.add(keyStroke);
			KeySequence keySequence = KeySequence.getInstance(keyStrokes);
			Map childAssignmentsByContextIdByKeySequence =
				getAssignmentsByContextIdKeySequence(
					keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap,
					keySequence);

			if (childAssignmentsByContextIdByKeySequence.size() >= 1)
				assignmentsByContextIdByKeySequence.putAll(
					childAssignmentsByContextIdByKeySequence);

			assignmentsByContextIdByKeySequence.put(
				keySequence,
				keySequenceBindingNode.assignmentsByContextId);
		}

		return assignmentsByContextIdByKeySequence;
	}

	static void getKeySequenceBindingDefinitions(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence prefix,
		int rank,
		List keySequenceBindingDefinitions) {
		Iterator iterator = keyStrokeNodeByKeyStrokeMap.entrySet().iterator();

		while (iterator.hasNext()) {
			Map.Entry entry = (Map.Entry) iterator.next();
			KeyStroke keyStroke = (KeyStroke) entry.getKey();
			KeySequenceBindingNode keySequenceBindingNode =
				(KeySequenceBindingNode) entry.getValue();
			List keyStrokes = new ArrayList(prefix.getKeyStrokes());
			keyStrokes.add(keyStroke);
			KeySequence keySequence = KeySequence.getInstance(keyStrokes);
			Map contextMap = keySequenceBindingNode.contextMap;
			Iterator iterator2 = contextMap.entrySet().iterator();

			while (iterator2.hasNext()) {
				Map.Entry entry2 = (Map.Entry) iterator2.next();
				String contextId = (String) entry2.getKey();
				Map keyConfigurationMap = (Map) entry2.getValue();
				Iterator iterator3 = keyConfigurationMap.entrySet().iterator();

				while (iterator3.hasNext()) {
					Map.Entry entry3 = (Map.Entry) iterator3.next();
					String keyConfigurationId = (String) entry3.getKey();
					Map rankMap = (Map) entry3.getValue();
					Map platformMap = (Map) rankMap.get(new Integer(rank));

					if (platformMap != null) {
						Iterator iterator4 = platformMap.entrySet().iterator();

						while (iterator4.hasNext()) {
							Map.Entry entry4 = (Map.Entry) iterator4.next();
							String platform = (String) entry4.getKey();
							Map localeMap = (Map) entry4.getValue();
							Iterator iterator5 =
								localeMap.entrySet().iterator();

							while (iterator5.hasNext()) {
								Map.Entry entry5 = (Map.Entry) iterator5.next();
								String locale = (String) entry5.getKey();
								Set commandIds = (Set) entry5.getValue();
								Iterator iterator6 = commandIds.iterator();

								while (iterator6.hasNext()) {
									String commandId =
										(String) iterator6.next();
									keySequenceBindingDefinitions.add(
										new KeySequenceBindingDefinition(
											contextId,
											commandId,
											keyConfigurationId,
											keySequence,
											locale,
											platform,
											null));
								}
							}
						}
					}
				}
			}

			getKeySequenceBindingDefinitions(
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap,
				keySequence,
				rank,
				keySequenceBindingDefinitions);
		}
	}

	static Map getKeySequenceBindingsByCommandId(Map keySequenceMap) {
		Map commandMap = new HashMap();
		Iterator iterator = keySequenceMap.entrySet().iterator();

		while (iterator.hasNext()) {
			Map.Entry entry = (Map.Entry) iterator.next();
			KeySequence keySequence = (KeySequence) entry.getKey();
			Match match = (Match) entry.getValue();
			String commandId = match.getCommandId();
			int value = match.getValue();
			SortedSet keySequenceBindings =
				(SortedSet) commandMap.get(commandId);

			if (keySequenceBindings == null) {
				keySequenceBindings = new TreeSet();
				commandMap.put(commandId, keySequenceBindings);
			}

			keySequenceBindings.add(new KeySequenceBinding(keySequence, value));
		}

		return commandMap;
	}

	static Map getMatchesByKeySequence(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence prefix) {
		Map keySequenceMap = new HashMap();
		Iterator iterator = keyStrokeNodeByKeyStrokeMap.entrySet().iterator();

		while (iterator.hasNext()) {
			Map.Entry entry = (Map.Entry) iterator.next();
			KeyStroke keyStroke = (KeyStroke) entry.getKey();
			KeySequenceBindingNode keySequenceBindingNode =
				(KeySequenceBindingNode) entry.getValue();
			List keyStrokes = new ArrayList(prefix.getKeyStrokes());
			keyStrokes.add(keyStroke);
			KeySequence keySequence = KeySequence.getInstance(keyStrokes);
			Map childMatchesByKeySequence =
				getMatchesByKeySequence(
					keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap,
					keySequence);

			if (childMatchesByKeySequence.size() >= 1)
				keySequenceMap.putAll(childMatchesByKeySequence);
			else if (
				keySequenceBindingNode.match != null
					&& keySequenceBindingNode.match.getCommandId() != null)
				keySequenceMap.put(keySequence, keySequenceBindingNode.match);
		}

		return keySequenceMap;
	}

	static void remove(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence keySequence,
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale) {
		Iterator iterator = keySequence.getKeyStrokes().iterator();
		KeySequenceBindingNode keySequenceBindingNode = null;

		while (iterator.hasNext()) {
			keySequenceBindingNode =
				(KeySequenceBindingNode) keyStrokeNodeByKeyStrokeMap.get(
					iterator.next());

			if (keySequenceBindingNode == null)
				return;

			keyStrokeNodeByKeyStrokeMap =
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap;
		}

		keySequenceBindingNode.remove(
			contextId,
			keyConfigurationId,
			rank,
			platform,
			locale);
	}

	static void remove(
		Map keyStrokeNodeByKeyStrokeMap,
		KeySequence keySequence,
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale,
		String commandId) {
		Iterator iterator = keySequence.getKeyStrokes().iterator();
		KeySequenceBindingNode keySequenceBindingNode = null;

		while (iterator.hasNext()) {
			keySequenceBindingNode =
				(KeySequenceBindingNode) keyStrokeNodeByKeyStrokeMap.get(
					iterator.next());

			if (keySequenceBindingNode == null)
				return;

			keyStrokeNodeByKeyStrokeMap =
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap;
		}

		keySequenceBindingNode.remove(
			contextId,
			keyConfigurationId,
			rank,
			platform,
			locale,
			commandId);
	}

	static void solve(
		Map keyStrokeNodeByKeyStrokeMap,
		String[] keyConfigurationIds,
		String[] platforms,
		String[] locales) {
		for (Iterator iterator =
			keyStrokeNodeByKeyStrokeMap.values().iterator();
			iterator.hasNext();
			) {
			KeySequenceBindingNode keySequenceBindingNode =
				(KeySequenceBindingNode) iterator.next();
			keySequenceBindingNode.solveAssignmentsByContextId(
				keyConfigurationIds,
				platforms,
				locales);
			solve(
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap,
				keyConfigurationIds,
				platforms,
				locales);
		}
	}

	static void solve(
		Map keyStrokeNodeByKeyStrokeMap,
		Map contextIds,
		String[] keyConfigurationIds,
		String[] platforms,
		String[] locales) {
		for (Iterator iterator =
			keyStrokeNodeByKeyStrokeMap.values().iterator();
			iterator.hasNext();
			) {
			KeySequenceBindingNode keySequenceBindingNode =
			    (KeySequenceBindingNode) iterator.next();
			keySequenceBindingNode.solveMatch(
				contextIds,
				keyConfigurationIds,
				platforms,
				locales);
			solve(
				keySequenceBindingNode.childKeyStrokeNodeByKeyStrokeMap,
				contextIds,
				keyConfigurationIds,
				platforms,
				locales);
		}
	}
	private Map contextMap = new HashMap();

	private Map assignmentsByContextId = new HashMap();
	private Map childKeyStrokeNodeByKeyStrokeMap = new HashMap();
	private Match match = null;

	private KeySequenceBindingNode() {
	}

	private void add(
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale,
		String commandId) {
		Map keyConfigurationMap = (Map) contextMap.get(contextId);

		if (keyConfigurationMap == null) {
			keyConfigurationMap = new HashMap();
			contextMap.put(contextId, keyConfigurationMap);
		}

		Map rankMap = (Map) keyConfigurationMap.get(keyConfigurationId);

		if (rankMap == null) {
			rankMap = new HashMap();
			keyConfigurationMap.put(keyConfigurationId, rankMap);
		}

		Map platformMap = (Map) rankMap.get(new Integer(rank));

		if (platformMap == null) {
			platformMap = new HashMap();
			rankMap.put(new Integer(rank), platformMap);
		}

		Map localeMap = (Map) platformMap.get(platform);

		if (localeMap == null) {
			localeMap = new HashMap();
			platformMap.put(platform, localeMap);
		}

		Set commandIds = (Set) localeMap.get(locale);

		if (commandIds == null) {
			commandIds = new HashSet();
			localeMap.put(locale, commandIds);
		}

		commandIds.add(commandId);
	}

	private void remove(
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale) {
		Map keyConfigurationMap = (Map) contextMap.get(contextId);

		if (keyConfigurationMap != null) {
			Map rankMap = (Map) keyConfigurationMap.get(keyConfigurationId);

			if (rankMap != null) {
				Map platformMap = (Map) rankMap.get(new Integer(rank));

				if (platformMap != null) {
					Map localeMap = (Map) platformMap.get(platform);

					if (localeMap != null) {
						localeMap.remove(locale);

						if (localeMap.isEmpty()) {
							platformMap.remove(platform);

							if (platformMap.isEmpty()) {
								rankMap.remove(new Integer(rank));

								if (rankMap.isEmpty()) {
									keyConfigurationMap.remove(
										keyConfigurationId);

									if (keyConfigurationMap.isEmpty())
										contextMap.remove(contextId);
								}
							}
						}
					}
				}
			}
		}
	}

	private void remove(
		String contextId,
		String keyConfigurationId,
		int rank,
		String platform,
		String locale,
		String commandId) {
		Map keyConfigurationMap = (Map) contextMap.get(contextId);

		if (keyConfigurationMap != null) {
			Map rankMap = (Map) keyConfigurationMap.get(keyConfigurationId);

			if (rankMap != null) {
				Map platformMap = (Map) rankMap.get(new Integer(rank));

				if (platformMap != null) {
					Map localeMap = (Map) platformMap.get(platform);

					if (localeMap != null) {
						Set commandIds = (Set) localeMap.get(locale);

						if (commandIds != null) {
							commandIds.remove(commandId);

							if (commandIds.isEmpty()) {
								localeMap.remove(locale);

								if (localeMap.isEmpty()) {
									platformMap.remove(platform);

									if (platformMap.isEmpty()) {
										rankMap.remove(new Integer(rank));

										if (rankMap.isEmpty()) {
											keyConfigurationMap.remove(
												keyConfigurationId);

											if (keyConfigurationMap.isEmpty())
												contextMap.remove(contextId);
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}

	private void solveAssignmentsByContextId(
		String[] keyConfigurationIds,
		String[] platforms,
		String[] locales) {
		assignmentsByContextId.clear();

		for (Iterator iterator = contextMap.entrySet().iterator();
			iterator.hasNext();
			) {
			Map.Entry entry = (Map.Entry) iterator.next();
			String contextId = (String) entry.getKey();
			Map keyConfigurationMap = (Map) entry.getValue();
			KeySequenceBindingNode.Assignment assignment = null;

			if (keyConfigurationMap != null)
				for (int keyConfiguration = 0;
					keyConfiguration < keyConfigurationIds.length
						&& keyConfiguration < 0xFF;
					keyConfiguration++) {
					Map rankMap =
						(Map) keyConfigurationMap.get(
							keyConfigurationIds[keyConfiguration]);

					if (rankMap != null)
						for (int rank = 0; rank <= 1; rank++) {
							Map platformMap =
								(Map) rankMap.get(new Integer(rank));

							if (platformMap != null)
								for (int platform = 0;
									platform < platforms.length
										&& platform < 0xFF;
									platform++) {
									Map localeMap =
										(Map) platformMap.get(
											platforms[platform]);

									if (localeMap != null)
										for (int locale = 0;
											locale < locales.length
												&& locale < 0xFF;
											locale++) {
											Set commandIds =
												(Set) localeMap.get(
													locales[locale]);

											if (commandIds != null) {
												String commandId =
													commandIds.size() == 1
														? (String) commandIds
															.iterator()
															.next()
														: null;

												if (assignment == null)
													assignment =
														new Assignment();

												switch (rank) {
													case 0 :
														if (keyConfiguration
															== 0
															&& !assignment
																.hasPreferenceCommandIdInFirstKeyConfiguration) {
															assignment
																.hasPreferenceCommandIdInFirstKeyConfiguration =
																true;
															assignment
																.preferenceCommandIdInFirstKeyConfiguration =
																commandId;
														} else if (
															!assignment
																.hasPreferenceCommandIdInInheritedKeyConfiguration) {
															assignment
																.hasPreferenceCommandIdInInheritedKeyConfiguration =
																true;
															assignment
																.preferenceCommandIdInInheritedKeyConfiguration =
																commandId;
														}

														break;

													case 1 :
														if (keyConfiguration
															== 0
															&& !assignment
																.hasPluginCommandIdInFirstKeyConfiguration) {
															assignment
																.hasPluginCommandIdInFirstKeyConfiguration =
																true;
															assignment
																.pluginCommandIdInFirstKeyConfiguration =
																commandId;
														} else if (
															!assignment
																.hasPluginCommandIdInInheritedKeyConfiguration) {
															assignment
																.hasPluginCommandIdInInheritedKeyConfiguration =
																true;
															assignment
																.pluginCommandIdInInheritedKeyConfiguration =
																commandId;
														}

														break;
												}
											}
										}
								}

						}

				}

			if (assignment != null)
				assignmentsByContextId.put(contextId, assignment);
		}
	}

	/**
     * <p>
     * Finds a single match for this key binding node, given the state passed in
     * as parameters. The match will contain a single command identifier, and a
     * match value (a rough approximation of how accurate the match may be --
     * lower is better).
     * </p>
     * <p>
     * The matching algorithm checks for a match in each context given -- in the
     * order provided. Similar, it checks the key configuration, the rank (see
     * below), the platform, and the locale -- in the order provided. If a
     * single command identifier (note: this could be <code>null</code>--
     * indicating a removed key binding) matches the given characteristics, then
     * it is added to the list. For each context identifier, there can be at
     * most one match. If there is no match,
     * <em>or the match has a <code>null</code> command identifier</em>,
     * then we will move on to consider the next context.
     * </p>
     * <p>
     * The rank is a special value. It is either <code>0</code> or
     * <code>1</code>. It is used for marking removed key bindings. The
     * removed command identifier is moved to the first rank, and a
     * <code>null</code> command identifier is placed in the zeroth rank. The
     * ranking mechanism is controlled externally, but only the zeroth and first
     * ranks are considered internally.
     * </p>
     * <p>
     * When this method completes, <code>match</code> will contain the best
     * possible match, if any. If no match can be found, then <code>match</code>
     * will be <code>null</code>.
     * </p>
     * <p>
     * TODO Doug's Note (May 29, 2004): This mechanism is insanely complex for
     * what it is doing, and doesn't seem to cover all of the use cases. This
     * would be a good candidate for refactoring in the future. Most of this
     * code was written by Chris McLaren, but I've had to hack in some
     * behavioural changes to accomodate bugs for 3.0. If you're looking for
     * insight as to how it currently works, you might try talking to one of us.
     * Most notably, the fall through mechanism for <code>null</code> command
     * identifiers. My main concerns are: interactions between key
     * configurations, and unbinding a key in a child context so as to bind it
     * in a parent context.
     * </p>
     * 
     * @param contextTree
     *            The tree of contexts to consider. The tree is represented as a
     *            map of child context identifiers to parent context
     *            identifiers. This value must never be <code>null</code>,
     *            though it may contain <code>null</code> parents. It should
     *            never contain <code>null</code> children. It should only
     *            contain strings.
     * @param keyConfigurationIds
     *            The key configuration identifiers in the order they should be
     *            considered. This value must never be <code>null</code>,
     *            though it may contain <code>null</code> values.
     *            <code>null</code> values typically indicate "any".
     * @param platforms
     *            The platform identifiers in the order they should be
     *            considered. This value must never be <code>null</code>,
     *            though it may contain <code>null</code> values.
     *            <code>null</code> values typically indicate "any".
     * @param locales
     *            The locale identifiers in the order they should be considered.
     *            This value must never be <code>null</code>, though it may
     *            contain <code>null</code> values. <code>null</code> values
     *            typically indicate "any".
     */
    private void solveMatch(Map contextTree,
            String[] keyConfigurationIds, String[] platforms, String[] locales) {
        // Clear out the current match.
        match = null;
        
        // Get an array of context identifiers.
        final String[] contextIds = (String[]) contextTree.keySet().toArray(
                new String[contextTree.size()]); 

        // Get the maximum indices to consider.
        final int maxContext = (contextIds.length > 0xFF) ? 0xFF
                : contextIds.length;
        int maxKeyConfiguration = (keyConfigurationIds.length > 0xFF) ? 0xFF
                : keyConfigurationIds.length;
        final int maxPlatform = (platforms.length > 0xFF) ? 0xFF
                : platforms.length;
        final int maxLocale = (locales.length > 0xFF) ? 0xFF : locales.length;

        // Peel apart the nested map looking for matches.
        final Collection contextIdsNotToConsider = new HashSet();
        for (int context = 0; context < maxContext; context++) {
            boolean matchFoundForThisContext = false;

            /*
             * Check to see if the context identifier has been nixed by a child
             * context. That is, has a non-null match been found in a child
             * context?
             */
            final String contextId = contextIds[context];
            if (contextIdsNotToConsider.contains(contextId)) {
                continue;
            }

            final Map keyConfigurationMap = (Map) contextMap.get(contextId);
            if (keyConfigurationMap != null)
                    for (int keyConfiguration = 0; keyConfiguration < maxKeyConfiguration
                            && !matchFoundForThisContext; keyConfiguration++) {
                        final Map rankMap = (Map) keyConfigurationMap
                                .get(keyConfigurationIds[keyConfiguration]);

                        if (rankMap != null) {
                            for (int rank = 0; rank <= 1; rank++) {
                                final Map platformMap = (Map) rankMap
                                        .get(new Integer(rank));

                                if (platformMap != null)
                                        for (int platform = 0; platform < maxPlatform
                                                && !matchFoundForThisContext; platform++) {
                                            final Map localeMap = (Map) platformMap
                                                    .get(platforms[platform]);

                                            if (localeMap != null)
                                                    for (int locale = 0; locale < maxLocale
                                                            && !matchFoundForThisContext; locale++) {
                                                        final Set commandIds = (Set) localeMap
                                                                .get(locales[locale]);

                                                        if (commandIds != null) {
                                                            /*
                                                             * Jump to the next
                                                             * context.
                                                             */
                                                            matchFoundForThisContext = true;

                                                            /*
                                                             * Get the command
                                                             * identifier.
                                                             */
                                                            final String commandId = commandIds
                                                                    .size() == 1 ? (String) commandIds
                                                                    .iterator()
                                                                    .next()
                                                                    : null;

                                                            /*
                                                             * Make sure we
                                                             * don't consider
                                                             * any higher key
                                                             * configurations
                                                             * again.
                                                             */
                                                            maxKeyConfiguration = keyConfiguration + 1;

                                                            /*
                                                             * Make sure we
                                                             * don't consider
                                                             * any parents of
                                                             * this context, if
                                                             * the command
                                                             * identifier is not
                                                             * null.
                                                             */
                                                            if (commandId != null) {
                                                                String parentContext = (String) contextTree
                                                                        .get(contextId);
                                                                while (parentContext != null) {
                                                                    contextIdsNotToConsider
                                                                            .add(parentContext);
                                                                    parentContext = (String) contextTree
                                                                            .get(parentContext);
                                                                }

                                                                /*
                                                                 * Check for a
                                                                 * conflict.
                                                                 */
                                                                if ((match != null)
                                                                        && (!contextIdsNotToConsider
                                                                                .contains(contextIds[match
                                                                                        .getValue() >> 24]))) {
                                                                    WorkbenchPlugin
                                                                            .log("Conflicting key binding for '" //$NON-NLS-1$
                                                                                    + commandId
                                                                                    + "' and '" //$NON-NLS-1$
                                                                                    + match
                                                                                            .getCommandId()
                                                                                    + "'"); //$NON-NLS-1$
                                                                    match = null;

                                                                } else {
                                                                    match = new Match(
                                                                            commandId,
                                                                            (context << 24)
                                                                                    + (keyConfiguration << 16)
                                                                                    + (platform << 8)
                                                                                    + locale);
                                                                }
                                                            }
                                                        }
                                                    }
                                        }
                            }
                        }
                    }
        }
    }
}