bundles/org.eclipse.ui.workbench/Eclipse UI/org/eclipse/ui/dialogs/FilteredList.java - platform/eclipse.platform.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2006 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *   IBM Corporation - initial API and implementation
  *   Sebastian Davids <sdavids@gmx.de> - Fix for bug 19346 - Dialog font should be activated and used by other components.
  *******************************************************************************/
 package org.eclipse.ui.dialogs;

 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Set;
 import java.util.Vector;

 import org.eclipse.core.runtime.Assert;
 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.IStatus;
 import org.eclipse.core.runtime.Status;
 import org.eclipse.jface.viewers.ILabelProvider;
 import org.eclipse.swt.SWT;
 import org.eclipse.swt.SWTException;
 import org.eclipse.swt.accessibility.Accessible;
 import org.eclipse.swt.events.DisposeEvent;
 import org.eclipse.swt.events.DisposeListener;
 import org.eclipse.swt.events.SelectionListener;
 import org.eclipse.swt.graphics.Image;
 import org.eclipse.swt.layout.GridData;
 import org.eclipse.swt.layout.GridLayout;
 import org.eclipse.swt.widgets.Composite;
 import org.eclipse.swt.widgets.Event;
 import org.eclipse.swt.widgets.Table;
 import org.eclipse.swt.widgets.TableItem;
 import org.eclipse.ui.internal.WorkbenchMessages;
 import org.eclipse.ui.internal.misc.StringMatcher;
 import org.eclipse.ui.internal.util.Util;
 import org.eclipse.ui.progress.WorkbenchJob;

 /**
  * A composite widget which holds a list of elements for user selection. The
  * elements are sorted alphabetically. Optionally, the elements can be filtered
  * and duplicate entries can be hidden (folding).
  *
  * @since 2.0
  */
 public class FilteredList extends Composite {
 	/**
 	 * The FilterMatcher is the interface used to check filtering criterea.
 	 */
 	public interface FilterMatcher {
 		/**
 		 * Sets the filter.
 		 *
 		 * @param pattern
 		 *            the filter pattern.
 		 * @param ignoreCase
 		 *            a flag indicating whether pattern matching is case
 		 *            insensitive or not.
 		 * @param ignoreWildCards
 		 *            a flag indicating whether wildcard characters are
 		 *            interpreted or not.
 		 */
 		void setFilter(String pattern, boolean ignoreCase,
 				boolean ignoreWildCards);

 		/**
 		 * @param element
 		 *            The element to test against.
 		 * @return <code>true</code> if the object matches the pattern,
 		 *         <code>false</code> otherwise. <code>setFilter()</code>
 		 *         must have been called at least once prior to a call to this
 		 *         method.
 		 */
 		boolean match(Object element);
 	}

 	private class DefaultFilterMatcher implements FilterMatcher {
 		private StringMatcher fMatcher;

 		public void setFilter(String pattern, boolean ignoreCase,
 				boolean ignoreWildCards) {
 			fMatcher = new StringMatcher(pattern + '*', ignoreCase,
 					ignoreWildCards);
 		}

 		public boolean match(Object element) {
 			return fMatcher.match(fLabelProvider.getText(element));
 		}
 	}

 	private Table fList;

 	ILabelProvider fLabelProvider;

 	private boolean fMatchEmptyString = true;

 	private boolean fIgnoreCase;

 	private boolean fAllowDuplicates;

 	private String fFilter = ""; //$NON-NLS-1$

 	private TwoArrayQuickSorter fSorter;

 	Object[] fElements = new Object[0];

 	Label[] fLabels;

 	Vector fImages = new Vector();

 	int[] fFoldedIndices;

 	int fFoldedCount;

 	int[] fFilteredIndices;

 	int fFilteredCount;

 	private FilterMatcher fFilterMatcher = new DefaultFilterMatcher();

 	Comparator fComparator;

 	TableUpdateJob fUpdateJob;

 	/**
 	 * Label is a private class used for comparing list objects
 	 */
 	private static class Label {
 		/**
 		 * The string portion of the label.
 		 */
 		public final String string;

 		/**
 		 * The image portion of the label.
 		 */
 		public final Image image;

 		/**
 		 * Create a new instance of label.
 		 *
 		 * @param newString
 		 * @param image
 		 */
 		public Label(String newString, Image image) {
 			if (newString == null) {
 				this.string = Util.ZERO_LENGTH_STRING;
 			} else {
 				this.string = newString;
 			}
 			this.image = image;
 		}

 		/**
 		 * Return whether or not the receiver is the same as label.
 		 *
 		 * @param label
 		 * @return boolean
 		 */
 		public boolean equals(Label label) {
 			if (label == null) {
 				return false;
 			}
 			// If the string portions match (whether null or not), fall
 			// through and check the image portion.
 			if (string == null && label.string != null) {
 				return false;
 			}
 			if ((string != null) && (!string.equals(label.string))) {
 				return false;
 			}
 			if (image == null) {
 				return label.image == null;
 			}
 			return image.equals(label.image);
 		}
 	}

 	private final class LabelComparator implements Comparator {
 		private boolean labelIgnoreCase;

 		LabelComparator(boolean ignoreCase) {
 			labelIgnoreCase = ignoreCase;
 		}

 		public int compare(Object left, Object right) {
 			Label leftLabel = (Label) left;
 			Label rightLabel = (Label) right;
 			int value;
 			if (fComparator == null) {
 				value = labelIgnoreCase ? leftLabel.string
 						.compareToIgnoreCase(rightLabel.string)
 						: leftLabel.string.compareTo(rightLabel.string);
 			} else {
 				value = fComparator
 						.compare(leftLabel.string, rightLabel.string);
 			}
 			if (value != 0) {
 				return value;
 			}
 			// images are allowed to be null
 			if (leftLabel.image == null) {
 				return (rightLabel.image == null) ? 0 : -1;
 			} else if (rightLabel.image == null) {
 				return +1;
 			} else {
 				return fImages.indexOf(leftLabel.image)
 						- fImages.indexOf(rightLabel.image);
 			}
 		}
 	}

 	/**
 	 * Constructs a new filtered list.
 	 *
 	 * @param parent
 	 *            the parent composite
 	 * @param style
 	 *            the widget style
 	 * @param labelProvider
 	 *            the label renderer
 	 * @param ignoreCase
 	 *            specifies whether sorting and folding is case sensitive
 	 * @param allowDuplicates
 	 *            specifies whether folding of duplicates is desired
 	 * @param matchEmptyString
 	 *            specifies whether empty filter strings should filter
 	 *            everything or nothing
 	 */
 	public FilteredList(Composite parent, int style,
 			ILabelProvider labelProvider, boolean ignoreCase,
 			boolean allowDuplicates, boolean matchEmptyString) {
 		super(parent, SWT.NONE);
 		GridLayout layout = new GridLayout();
 		layout.marginHeight = 0;
 		layout.marginWidth = 0;
 		setLayout(layout);
 		fList = new Table(this, style);
 		fList.setLayoutData(new GridData(GridData.FILL_BOTH));
 		fList.setFont(parent.getFont());
 		fList.addDisposeListener(new DisposeListener() {
 			public void widgetDisposed(DisposeEvent e) {
 				fLabelProvider.dispose();
 				if (fUpdateJob != null) {
 					fUpdateJob.cancel();
 				}
 			}
 		});
 		fLabelProvider = labelProvider;
 		fIgnoreCase = ignoreCase;
 		fSorter = new TwoArrayQuickSorter(new LabelComparator(ignoreCase));
 		fAllowDuplicates = allowDuplicates;
 		fMatchEmptyString = matchEmptyString;
 	}

 	/**
 	 * Sets the list of elements.
 	 *
 	 * @param elements
 	 *            the elements to be shown in the list.
 	 */
 	public void setElements(Object[] elements) {
 		if (elements == null) {
 			fElements = new Object[0];
 		} else {
 			// copy list for sorting
 			fElements = new Object[elements.length];
 			System.arraycopy(elements, 0, fElements, 0, elements.length);
 		}
 		int length = fElements.length;
 		// fill labels
 		fLabels = new Label[length];
 		Set imageSet = new HashSet();
 		for (int i = 0; i != length; i++) {
 			String text = fLabelProvider.getText(fElements[i]);
 			Image image = fLabelProvider.getImage(fElements[i]);
 			fLabels[i] = new Label(text, image);
 			imageSet.add(image);
 		}
 		fImages.clear();
 		fImages.addAll(imageSet);
 		fSorter.sort(fLabels, fElements);
 		fFilteredIndices = new int[length];
 		fFoldedIndices = new int[length];
 		updateList();
 	}

 	/**
 	 * Tests if the list (before folding and filtering) is empty.
 	 *
 	 * @return returns <code>true</code> if the list is empty,
 	 *         <code>false</code> otherwise.
 	 */
 	public boolean isEmpty() {
 		return (fElements == null) || (fElements.length == 0);
 	}

 	/**
 	 * Sets the filter matcher.
 	 *
 	 * @param filterMatcher
 	 */
 	public void setFilterMatcher(FilterMatcher filterMatcher) {
 		Assert.isNotNull(filterMatcher);
 		fFilterMatcher = filterMatcher;
 	}

 	/**
 	 * Sets a custom comparator for sorting the list.
 	 *
 	 * @param comparator
 	 */
 	public void setComparator(Comparator comparator) {
 		Assert.isNotNull(comparator);
 		fComparator = comparator;
 	}

 	/**
 	 * Adds a selection listener to the list.
 	 *
 	 * @param listener
 	 *            the selection listener to be added.
 	 */
 	public void addSelectionListener(SelectionListener listener) {
 		fList.addSelectionListener(listener);
 	}

 	/**
 	 * Removes a selection listener from the list.
 	 *
 	 * @param listener
 	 *            the selection listener to be removed.
 	 */
 	public void removeSelectionListener(SelectionListener listener) {
 		fList.removeSelectionListener(listener);
 	}

 	/**
 	 * Sets the selection of the list. Empty or null array removes selection.
 	 *
 	 * @param selection
 	 *            an array of indices specifying the selection.
 	 */
 	public void setSelection(int[] selection) {
 		if (selection == null || selection.length == 0) {
 			fList.deselectAll();
 		} else {
 			// If there is no working update job, or the update job is ready to
 			// accept selections, set the selection immediately.
 			if (fUpdateJob == null) {
 				fList.setSelection(selection);
 				fList.notifyListeners(SWT.Selection, new Event());
 			} else {
 				// There is an update job doing the population of the list, so
 				// it should update the selection.
 				fUpdateJob.updateSelection(selection);
 			}
 		}
 	}

 	/**
 	 * Returns the selection of the list.
 	 *
 	 * @return returns an array of indices specifying the current selection.
 	 */
 	public int[] getSelectionIndices() {
 		return fList.getSelectionIndices();
 	}

 	/**
 	 * Returns the selection of the list. This is a convenience function for
 	 * <code>getSelectionIndices()</code>.
 	 *
 	 * @return returns the index of the selection, -1 for no selection.
 	 */
 	public int getSelectionIndex() {
 		return fList.getSelectionIndex();
 	}

 	/**
 	 * Sets the selection of the list. Empty or null array removes selection.
 	 *
 	 * @param elements
 	 *            the array of elements to be selected.
 	 */
 	public void setSelection(Object[] elements) {
 		if (elements == null || elements.length == 0) {
 			fList.deselectAll();
 			return;
 		}
 		if (fElements == null) {
 			return;
 		}
 		// fill indices
 		int[] indices = new int[elements.length];
 		for (int i = 0; i != elements.length; i++) {
 			int j;
 			for (j = 0; j != fFoldedCount; j++) {
 				int max = (j == fFoldedCount - 1) ? fFilteredCount
 						: fFoldedIndices[j + 1];
 				int l;
 				for (l = fFoldedIndices[j]; l != max; l++) {
 					// found matching element?
 					if (fElements[fFilteredIndices[l]].equals(elements[i])) {
 						indices[i] = j;
 						break;
 					}
 				}
 				if (l != max) {
 					break;
 				}
 			}
 			// not found
 			if (j == fFoldedCount) {
 				indices[i] = 0;
 			}
 		}
 		setSelection(indices);
 	}

 	/**
 	 * Returns an array of the selected elements. The type of the elements
 	 * returned in the list are the same as the ones passed with
 	 * <code>setElements</code>. The array does not contain the rendered
 	 * strings.
 	 *
 	 * @return returns the array of selected elements.
 	 */
 	public Object[] getSelection() {
 		if (fList.isDisposed() || (fList.getSelectionCount() == 0)) {
 			return new Object[0];
 		}
 		int[] indices = fList.getSelectionIndices();
 		Object[] elements = new Object[indices.length];
 		for (int i = 0; i != indices.length; i++) {
 			elements[i] = fElements[fFilteredIndices[fFoldedIndices[indices[i]]]];
 		}
 		return elements;
 	}

 	/**
 	 * Sets the filter pattern. Current only prefix filter patterns are
 	 * supported.
 	 *
 	 * @param filter
 	 *            the filter pattern.
 	 */
 	public void setFilter(String filter) {
 		fFilter = (filter == null) ? "" : filter; //$NON-NLS-1$
 		updateList();
 	}

 	private void updateList() {
 		fFilteredCount = filter();
 		fFoldedCount = fold();
 		if (fUpdateJob != null) {
 			fUpdateJob.cancel();
 		}
 		fUpdateJob = new TableUpdateJob(fList, fFoldedCount);
 		fUpdateJob.schedule();
 	}

 	/**
 	 * Returns the filter pattern.
 	 *
 	 * @return returns the filter pattern.
 	 */
 	public String getFilter() {
 		return fFilter;
 	}

 	/**
 	 * Returns all elements which are folded together to one entry in the list.
 	 *
 	 * @param index
 	 *            the index selecting the entry in the list.
 	 * @return returns an array of elements folded together, <code>null</code>
 	 *         if index is out of range.
 	 */
 	public Object[] getFoldedElements(int index) {
 		if ((index < 0) || (index >= fFoldedCount)) {
 			return null;
 		}
 		int start = fFoldedIndices[index];
 		int count = (index == fFoldedCount - 1) ? fFilteredCount - start
 				: fFoldedIndices[index + 1] - start;
 		Object[] elements = new Object[count];
 		for (int i = 0; i != count; i++) {
 			elements[i] = fElements[fFilteredIndices[start + i]];
 		}
 		return elements;
 	}

 	/*
 	 * Folds duplicate entries. Two elements are considered as a pair of
 	 * duplicates if they coiincide in the rendered string and image. @return
 	 * returns the number of elements after folding.
 	 */
 	private int fold() {
 		if (fAllowDuplicates) {
 			for (int i = 0; i != fFilteredCount; i++) {
 				fFoldedIndices[i] = i; // identity mapping
 			}
 			return fFilteredCount;
 		}
 		int k = 0;
 		Label last = null;
 		for (int i = 0; i != fFilteredCount; i++) {
 			int j = fFilteredIndices[i];
 			Label current = fLabels[j];
 			if (!current.equals(last)) {
 				fFoldedIndices[k] = i;
 				k++;
 				last = current;
 			}
 		}
 		return k;
 	}

 	/*
 	 * Filters the list with the filter pattern. @return returns the number of
 	 * elements after filtering.
 	 */
 	private int filter() {
 		if (((fFilter == null) || (fFilter.length() == 0))
 				&& !fMatchEmptyString) {
 			return 0;
 		}
 		fFilterMatcher.setFilter(fFilter.trim(), fIgnoreCase, false);
 		int k = 0;
 		for (int i = 0; i != fElements.length; i++) {
 			if (fFilterMatcher.match(fElements[i])) {
 				fFilteredIndices[k++] = i;
 			}
 		}
 		return k;
 	}

 	private class TableUpdateJob extends WorkbenchJob {
 		final Table fTable;

 		final int fCount;

 		private int currentIndex = 0;

 		/*
 		 * Programmatic selections requested while this job was running.
 		 */
 		int[] indicesToSelect;

 		private boolean readyForSelection = false;

 		/**
 		 * Create a new instance of a job used to update the table.
 		 *
 		 * @param table
 		 * @param count
 		 *            The number of items to update per running.
 		 */
 		public TableUpdateJob(Table table, int count) {
 			super(WorkbenchMessages.FilteredList_UpdateJobName);
 			setSystem(true);
 			fTable = table;
 			fCount = count;
 		}

 		/*
 		 * (non-Javadoc)
 		 *
 		 * @see org.eclipse.ui.progress.UIJob#runInUIThread(org.eclipse.core.runtime.IProgressMonitor)
 		 */
 public IStatus runInUIThread(IProgressMonitor monitor) {
             if (fTable.isDisposed()) {
 				return Status.CANCEL_STATUS;
 			}
             int itemCount = fTable.getItemCount();

             // Remove excess items
             if (fCount < itemCount) {
                 fTable.setRedraw(false);
                 fTable.remove(fCount, itemCount - 1);
                 fTable.setRedraw(true);
                 itemCount = fTable.getItemCount();
             }
             // table empty -> no selection
             if (fCount == 0) {
                 fTable.notifyListeners(SWT.Selection, new Event());
                 return Status.OK_STATUS;
             }
             // How many we are going to do this time.
             int iterations = Math.min(10, fCount - currentIndex);
             for (int i = 0; i < iterations; i++) {
                 if (monitor.isCanceled()) {
 					return Status.CANCEL_STATUS;
 				}
                 final TableItem item = (currentIndex < itemCount) ? fTable
                         .getItem(currentIndex)
                         : new TableItem(fTable, SWT.NONE);
                 final Label label = fLabels[fFilteredIndices[fFoldedIndices[currentIndex]]];
                 item.setText(label.string);
                 item.setImage(label.image);
                 currentIndex++;
             }
             if (monitor.isCanceled()) {
 				return Status.CANCEL_STATUS;
 			}
             if (currentIndex < fCount) {
 				schedule(100);
 			} else {
                 if (indicesToSelect == null) {
                  	// Make a default selection in the table if there is none.
                 	// If a selection has already been made, honor it.
                 	// See https://bugs.eclipse.org/bugs/show_bug.cgi?id=112146
                     if (fCount > 0) {
                     	if (fTable.getSelectionIndices().length == 0) {
                     		defaultSelect();
                     	} else {
                     		// There is a selection, but it likely hasn't changed since the
                     		// job started.  Force a selection notification, since the
                     		// items represented by the selection have changed.
 							// See https://bugs.eclipse.org/bugs/show_bug.cgi?id=119456
                     		fTable.notifyListeners(SWT.Selection, new Event());
                     	}
                     }
                 } else {
                 	// Set the selection as indicated.
                     selectAndNotify(indicesToSelect);
                 }
                 // This flag signifies that the selection can now be directly
                 // updated in the widget.
                 readyForSelection = true;
             }
             return Status.OK_STATUS;
         }
 		/**
 		 * Update the selection for the supplied indices.
 		 *
 		 * @param indices
 		 */
 		void updateSelection(final int[] indices) {
 			indicesToSelect = indices;
 			if (readyForSelection) {
 				selectAndNotify(indices);
 			}
 		}

 		/**
 		 * Select the first element if there is no selection
 		 */
 		private void defaultSelect() {
 			/**
 			 * Reset to the first selection if no index has been queued.
 			 */
 			selectAndNotify(new int[] { 0 });
 		}

 		/**
 		 * Select the supplied indices and notify any listeners
 		 *
 		 * @param indices
 		 */
 		private void selectAndNotify(final int[] indices) {
 			// It is possible that the table was disposed
 			// before the update finished. If so then leave
 			if (fTable.isDisposed()) {
 				return;
 			}
 			fTable.setSelection(indices);
 			fTable.notifyListeners(SWT.Selection, new Event());
 		}
 	}

 	/**
 	 * Returns whether or not duplicates are allowed.
 	 *
 	 * @return <code>true</code> indicates duplicates are allowed
 	 */
 	public boolean getAllowDuplicates() {
 		return fAllowDuplicates;
 	}

 	/**
 	 * Sets whether or not duplicates are allowed. If this value is set the
 	 * items should be set again for this value to take effect.
 	 *
 	 * @param allowDuplicates
 	 *            <code>true</code> indicates duplicates are allowed
 	 */
 	public void setAllowDuplicates(boolean allowDuplicates) {
 		this.fAllowDuplicates = allowDuplicates;
 	}

 	/**
 	 * Returns whether or not case should be ignored.
 	 *
 	 * @return <code>true</code> if case should be ignored
 	 */
 	public boolean getIgnoreCase() {
 		return fIgnoreCase;
 	}

 	/**
 	 * Sets whether or not case should be ignored If this value is set the items
 	 * should be set again for this value to take effect.
 	 *
 	 * @param ignoreCase
 	 *            <code>true</code> if case should be ignored
 	 */
 	public void setIgnoreCase(boolean ignoreCase) {
 		this.fIgnoreCase = ignoreCase;
 	}

 	/**
 	 * Returns whether empty filter strings should filter everything or nothing.
 	 *
 	 * @return <code>true</code> for the empty string to match all items,
 	 *         <code>false</code> to match none
 	 */
 	public boolean getMatchEmptyString() {
 		return fMatchEmptyString;
 	}

 	/**
 	 * Sets whether empty filter strings should filter everything or nothing. If
 	 * this value is set the items should be set again for this value to take
 	 * effect.
 	 *
 	 * @param matchEmptyString
 	 *            <code>true</code> for the empty string to match all items,
 	 *            <code>false</code> to match none
 	 */
 	public void setMatchEmptyString(boolean matchEmptyString) {
 		this.fMatchEmptyString = matchEmptyString;
 	}

 	/**
 	 * Returns the label provider for the items.
 	 *
 	 * @return the label provider
 	 */
 	public ILabelProvider getLabelProvider() {
 		return fLabelProvider;
 	}

 	/**
 	 * Sets the label provider. If this value is set the items should be set
 	 * again for this value to take effect.
 	 *
 	 * @param labelProvider
 	 *            the label provider
 	 */
 	public void setLabelProvider(ILabelProvider labelProvider) {
 		this.fLabelProvider = labelProvider;
 	}

 	/**
 	 * Returns the accessible object for the receiver.
 	 * If this is the first time this object is requested,
 	 * then the object is created and returned.
 	 *
 	 * @return the accessible object
 	 *
 	 * @exception SWTException <ul>
 	 *    <li>ERROR_WIDGET_DISPOSED - if the receiver has been disposed</li>
 	 *    <li>ERROR_THREAD_INVALID_ACCESS - if not called from the thread that created the receiver</li>
 	 * </ul>
 	 *
 	 * @see Accessible#addAccessibleListener
 	 * @see Accessible#addAccessibleControlListener
 	 *
 	 * @since 3.3
 	 */
 	public Accessible getAccessible() {
 		return fList.getAccessible();
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2006 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	* Sebastian Davids <sdavids@gmx.de> - Fix for bug 19346 - Dialog font should be activated and used by other components.
	*******************************************************************************/
	package org.eclipse.ui.dialogs;

	import java.util.Comparator;
	import java.util.HashSet;
	import java.util.Set;
	import java.util.Vector;

	import org.eclipse.core.runtime.Assert;
	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.IStatus;
	import org.eclipse.core.runtime.Status;
	import org.eclipse.jface.viewers.ILabelProvider;
	import org.eclipse.swt.SWT;
	import org.eclipse.swt.SWTException;
	import org.eclipse.swt.accessibility.Accessible;
	import org.eclipse.swt.events.DisposeEvent;
	import org.eclipse.swt.events.DisposeListener;
	import org.eclipse.swt.events.SelectionListener;
	import org.eclipse.swt.graphics.Image;
	import org.eclipse.swt.layout.GridData;
	import org.eclipse.swt.layout.GridLayout;
	import org.eclipse.swt.widgets.Composite;
	import org.eclipse.swt.widgets.Event;
	import org.eclipse.swt.widgets.Table;
	import org.eclipse.swt.widgets.TableItem;
	import org.eclipse.ui.internal.WorkbenchMessages;
	import org.eclipse.ui.internal.misc.StringMatcher;
	import org.eclipse.ui.internal.util.Util;
	import org.eclipse.ui.progress.WorkbenchJob;

	/**
	* A composite widget which holds a list of elements for user selection. The
	* elements are sorted alphabetically. Optionally, the elements can be filtered
	* and duplicate entries can be hidden (folding).
	*
	* @since 2.0
	*/
	public class FilteredList extends Composite {
	/**
	* The FilterMatcher is the interface used to check filtering criterea.
	*/
	public interface FilterMatcher {
	/**
	* Sets the filter.
	*
	* @param pattern
	* the filter pattern.
	* @param ignoreCase
	* a flag indicating whether pattern matching is case
	* insensitive or not.
	* @param ignoreWildCards
	* a flag indicating whether wildcard characters are
	* interpreted or not.
	*/
	void setFilter(String pattern, boolean ignoreCase,
	boolean ignoreWildCards);

	/**
	* @param element
	* The element to test against.
	* @return <code>true</code> if the object matches the pattern,
	* <code>false</code> otherwise. <code>setFilter()</code>
	* must have been called at least once prior to a call to this
	* method.
	*/
	boolean match(Object element);
	}

	private class DefaultFilterMatcher implements FilterMatcher {
	private StringMatcher fMatcher;

	public void setFilter(String pattern, boolean ignoreCase,
	boolean ignoreWildCards) {
	fMatcher = new StringMatcher(pattern + '*', ignoreCase,
	ignoreWildCards);
	}

	public boolean match(Object element) {
	return fMatcher.match(fLabelProvider.getText(element));
	}
	}

	private Table fList;

	ILabelProvider fLabelProvider;

	private boolean fMatchEmptyString = true;

	private boolean fIgnoreCase;

	private boolean fAllowDuplicates;

	private String fFilter = ""; //$NON-NLS-1$

	private TwoArrayQuickSorter fSorter;

	Object[] fElements = new Object[0];

	Label[] fLabels;

	Vector fImages = new Vector();

	int[] fFoldedIndices;

	int fFoldedCount;

	int[] fFilteredIndices;

	int fFilteredCount;

	private FilterMatcher fFilterMatcher = new DefaultFilterMatcher();

	Comparator fComparator;

	TableUpdateJob fUpdateJob;

	/**
	* Label is a private class used for comparing list objects
	*/
	private static class Label {
	/**
	* The string portion of the label.
	*/
	public final String string;

	/**
	* The image portion of the label.
	*/
	public final Image image;

	/**
	* Create a new instance of label.
	*
	* @param newString
	* @param image
	*/
	public Label(String newString, Image image) {
	if (newString == null) {
	this.string = Util.ZERO_LENGTH_STRING;
	} else {
	this.string = newString;
	}
	this.image = image;
	}

	/**
	* Return whether or not the receiver is the same as label.
	*
	* @param label
	* @return boolean
	*/
	public boolean equals(Label label) {
	if (label == null) {
	return false;
	}
	// If the string portions match (whether null or not), fall
	// through and check the image portion.
	if (string == null && label.string != null) {
	return false;
	}
	if ((string != null) && (!string.equals(label.string))) {
	return false;
	}
	if (image == null) {
	return label.image == null;
	}
	return image.equals(label.image);
	}
	}

	private final class LabelComparator implements Comparator {
	private boolean labelIgnoreCase;

	LabelComparator(boolean ignoreCase) {
	labelIgnoreCase = ignoreCase;
	}

	public int compare(Object left, Object right) {
	Label leftLabel = (Label) left;
	Label rightLabel = (Label) right;
	int value;
	if (fComparator == null) {
	value = labelIgnoreCase ? leftLabel.string
	.compareToIgnoreCase(rightLabel.string)
	: leftLabel.string.compareTo(rightLabel.string);
	} else {
	value = fComparator
	.compare(leftLabel.string, rightLabel.string);
	}
	if (value != 0) {
	return value;
	}
	// images are allowed to be null
	if (leftLabel.image == null) {
	return (rightLabel.image == null) ? 0 : -1;
	} else if (rightLabel.image == null) {
	return +1;
	} else {
	return fImages.indexOf(leftLabel.image)
	- fImages.indexOf(rightLabel.image);
	}
	}
	}

	/**
	* Constructs a new filtered list.
	*
	* @param parent
	* the parent composite
	* @param style
	* the widget style
	* @param labelProvider
	* the label renderer
	* @param ignoreCase
	* specifies whether sorting and folding is case sensitive
	* @param allowDuplicates
	* specifies whether folding of duplicates is desired
	* @param matchEmptyString
	* specifies whether empty filter strings should filter
	* everything or nothing
	*/
	public FilteredList(Composite parent, int style,
	ILabelProvider labelProvider, boolean ignoreCase,
	boolean allowDuplicates, boolean matchEmptyString) {
	super(parent, SWT.NONE);
	GridLayout layout = new GridLayout();
	layout.marginHeight = 0;
	layout.marginWidth = 0;
	setLayout(layout);
	fList = new Table(this, style);
	fList.setLayoutData(new GridData(GridData.FILL_BOTH));
	fList.setFont(parent.getFont());
	fList.addDisposeListener(new DisposeListener() {
	public void widgetDisposed(DisposeEvent e) {
	fLabelProvider.dispose();
	if (fUpdateJob != null) {
	fUpdateJob.cancel();
	}
	}
	});
	fLabelProvider = labelProvider;
	fIgnoreCase = ignoreCase;
	fSorter = new TwoArrayQuickSorter(new LabelComparator(ignoreCase));
	fAllowDuplicates = allowDuplicates;
	fMatchEmptyString = matchEmptyString;
	}

	/**
	* Sets the list of elements.
	*
	* @param elements
	* the elements to be shown in the list.
	*/
	public void setElements(Object[] elements) {
	if (elements == null) {
	fElements = new Object[0];
	} else {
	// copy list for sorting
	fElements = new Object[elements.length];
	System.arraycopy(elements, 0, fElements, 0, elements.length);
	}
	int length = fElements.length;
	// fill labels
	fLabels = new Label[length];
	Set imageSet = new HashSet();
	for (int i = 0; i != length; i++) {
	String text = fLabelProvider.getText(fElements[i]);
	Image image = fLabelProvider.getImage(fElements[i]);
	fLabels[i] = new Label(text, image);
	imageSet.add(image);
	}
	fImages.clear();
	fImages.addAll(imageSet);
	fSorter.sort(fLabels, fElements);
	fFilteredIndices = new int[length];
	fFoldedIndices = new int[length];
	updateList();
	}

	/**
	* Tests if the list (before folding and filtering) is empty.
	*
	* @return returns <code>true</code> if the list is empty,
	* <code>false</code> otherwise.
	*/
	public boolean isEmpty() {
	return (fElements == null) \|\| (fElements.length == 0);
	}

	/**
	* Sets the filter matcher.
	*
	* @param filterMatcher
	*/
	public void setFilterMatcher(FilterMatcher filterMatcher) {
	Assert.isNotNull(filterMatcher);
	fFilterMatcher = filterMatcher;
	}

	/**
	* Sets a custom comparator for sorting the list.
	*
	* @param comparator
	*/
	public void setComparator(Comparator comparator) {
	Assert.isNotNull(comparator);
	fComparator = comparator;
	}

	/**
	* Adds a selection listener to the list.
	*
	* @param listener
	* the selection listener to be added.
	*/
	public void addSelectionListener(SelectionListener listener) {
	fList.addSelectionListener(listener);
	}

	/**
	* Removes a selection listener from the list.
	*
	* @param listener
	* the selection listener to be removed.
	*/
	public void removeSelectionListener(SelectionListener listener) {
	fList.removeSelectionListener(listener);
	}

	/**
	* Sets the selection of the list. Empty or null array removes selection.
	*
	* @param selection
	* an array of indices specifying the selection.
	*/
	public void setSelection(int[] selection) {
	if (selection == null \|\| selection.length == 0) {
	fList.deselectAll();
	} else {
	// If there is no working update job, or the update job is ready to
	// accept selections, set the selection immediately.
	if (fUpdateJob == null) {
	fList.setSelection(selection);
	fList.notifyListeners(SWT.Selection, new Event());
	} else {
	// There is an update job doing the population of the list, so
	// it should update the selection.
	fUpdateJob.updateSelection(selection);
	}
	}
	}

	/**
	* Returns the selection of the list.
	*
	* @return returns an array of indices specifying the current selection.
	*/
	public int[] getSelectionIndices() {
	return fList.getSelectionIndices();
	}

	/**
	* Returns the selection of the list. This is a convenience function for
	* <code>getSelectionIndices()</code>.
	*
	* @return returns the index of the selection, -1 for no selection.
	*/
	public int getSelectionIndex() {
	return fList.getSelectionIndex();
	}

	/**
	* Sets the selection of the list. Empty or null array removes selection.
	*
	* @param elements
	* the array of elements to be selected.
	*/
	public void setSelection(Object[] elements) {
	if (elements == null \|\| elements.length == 0) {
	fList.deselectAll();
	return;
	}
	if (fElements == null) {
	return;
	}
	// fill indices
	int[] indices = new int[elements.length];
	for (int i = 0; i != elements.length; i++) {
	int j;
	for (j = 0; j != fFoldedCount; j++) {
	int max = (j == fFoldedCount - 1) ? fFilteredCount
	: fFoldedIndices[j + 1];
	int l;
	for (l = fFoldedIndices[j]; l != max; l++) {
	// found matching element?
	if (fElements[fFilteredIndices[l]].equals(elements[i])) {
	indices[i] = j;
	break;
	}
	}
	if (l != max) {
	break;
	}
	}
	// not found
	if (j == fFoldedCount) {
	indices[i] = 0;
	}
	}
	setSelection(indices);
	}

	/**
	* Returns an array of the selected elements. The type of the elements
	* returned in the list are the same as the ones passed with
	* <code>setElements</code>. The array does not contain the rendered
	* strings.
	*
	* @return returns the array of selected elements.
	*/
	public Object[] getSelection() {
	if (fList.isDisposed() \|\| (fList.getSelectionCount() == 0)) {
	return new Object[0];
	}
	int[] indices = fList.getSelectionIndices();
	Object[] elements = new Object[indices.length];
	for (int i = 0; i != indices.length; i++) {
	elements[i] = fElements[fFilteredIndices[fFoldedIndices[indices[i]]]];
	}
	return elements;
	}

	/**
	* Sets the filter pattern. Current only prefix filter patterns are
	* supported.
	*
	* @param filter
	* the filter pattern.
	*/
	public void setFilter(String filter) {
	fFilter = (filter == null) ? "" : filter; //$NON-NLS-1$
	updateList();
	}

	private void updateList() {
	fFilteredCount = filter();
	fFoldedCount = fold();
	if (fUpdateJob != null) {
	fUpdateJob.cancel();
	}
	fUpdateJob = new TableUpdateJob(fList, fFoldedCount);
	fUpdateJob.schedule();
	}

	/**
	* Returns the filter pattern.
	*
	* @return returns the filter pattern.
	*/
	public String getFilter() {
	return fFilter;
	}

	/**
	* Returns all elements which are folded together to one entry in the list.
	*
	* @param index
	* the index selecting the entry in the list.
	* @return returns an array of elements folded together, <code>null</code>
	* if index is out of range.
	*/
	public Object[] getFoldedElements(int index) {
	if ((index < 0) \|\| (index >= fFoldedCount)) {
	return null;
	}
	int start = fFoldedIndices[index];
	int count = (index == fFoldedCount - 1) ? fFilteredCount - start
	: fFoldedIndices[index + 1] - start;
	Object[] elements = new Object[count];
	for (int i = 0; i != count; i++) {
	elements[i] = fElements[fFilteredIndices[start + i]];
	}
	return elements;
	}

	/*
	* Folds duplicate entries. Two elements are considered as a pair of
	* duplicates if they coiincide in the rendered string and image. @return
	* returns the number of elements after folding.
	*/
	private int fold() {
	if (fAllowDuplicates) {
	for (int i = 0; i != fFilteredCount; i++) {
	fFoldedIndices[i] = i; // identity mapping
	}
	return fFilteredCount;
	}
	int k = 0;
	Label last = null;
	for (int i = 0; i != fFilteredCount; i++) {
	int j = fFilteredIndices[i];
	Label current = fLabels[j];
	if (!current.equals(last)) {
	fFoldedIndices[k] = i;
	k++;
	last = current;
	}
	}
	return k;
	}

	/*
	* Filters the list with the filter pattern. @return returns the number of
	* elements after filtering.
	*/
	private int filter() {
	if (((fFilter == null) \|\| (fFilter.length() == 0))
	&& !fMatchEmptyString) {
	return 0;
	}
	fFilterMatcher.setFilter(fFilter.trim(), fIgnoreCase, false);
	int k = 0;
	for (int i = 0; i != fElements.length; i++) {
	if (fFilterMatcher.match(fElements[i])) {
	fFilteredIndices[k++] = i;
	}
	}
	return k;
	}

	private class TableUpdateJob extends WorkbenchJob {
	final Table fTable;

	final int fCount;

	private int currentIndex = 0;

	/*
	* Programmatic selections requested while this job was running.
	*/
	int[] indicesToSelect;

	private boolean readyForSelection = false;

	/**
	* Create a new instance of a job used to update the table.
	*
	* @param table
	* @param count
	* The number of items to update per running.
	*/
	public TableUpdateJob(Table table, int count) {
	super(WorkbenchMessages.FilteredList_UpdateJobName);
	setSystem(true);
	fTable = table;
	fCount = count;
	}

	/*
	* (non-Javadoc)
	*
	* @see org.eclipse.ui.progress.UIJob#runInUIThread(org.eclipse.core.runtime.IProgressMonitor)
	*/
	public IStatus runInUIThread(IProgressMonitor monitor) {
	if (fTable.isDisposed()) {
	return Status.CANCEL_STATUS;
	}
	int itemCount = fTable.getItemCount();

	// Remove excess items
	if (fCount < itemCount) {
	fTable.setRedraw(false);
	fTable.remove(fCount, itemCount - 1);
	fTable.setRedraw(true);
	itemCount = fTable.getItemCount();
	}
	// table empty -> no selection
	if (fCount == 0) {
	fTable.notifyListeners(SWT.Selection, new Event());
	return Status.OK_STATUS;
	}
	// How many we are going to do this time.
	int iterations = Math.min(10, fCount - currentIndex);
	for (int i = 0; i < iterations; i++) {
	if (monitor.isCanceled()) {
	return Status.CANCEL_STATUS;
	}
	final TableItem item = (currentIndex < itemCount) ? fTable
	.getItem(currentIndex)
	: new TableItem(fTable, SWT.NONE);
	final Label label = fLabels[fFilteredIndices[fFoldedIndices[currentIndex]]];
	item.setText(label.string);
	item.setImage(label.image);
	currentIndex++;
	}
	if (monitor.isCanceled()) {
	return Status.CANCEL_STATUS;
	}
	if (currentIndex < fCount) {
	schedule(100);
	} else {
	if (indicesToSelect == null) {
	// Make a default selection in the table if there is none.
	// If a selection has already been made, honor it.
	// See https://bugs.eclipse.org/bugs/show_bug.cgi?id=112146
	if (fCount > 0) {
	if (fTable.getSelectionIndices().length == 0) {
	defaultSelect();
	} else {
	// There is a selection, but it likely hasn't changed since the
	// job started. Force a selection notification, since the
	// items represented by the selection have changed.
	// See https://bugs.eclipse.org/bugs/show_bug.cgi?id=119456
	fTable.notifyListeners(SWT.Selection, new Event());
	}
	}
	} else {
	// Set the selection as indicated.
	selectAndNotify(indicesToSelect);
	}
	// This flag signifies that the selection can now be directly
	// updated in the widget.
	readyForSelection = true;
	}
	return Status.OK_STATUS;
	}
	/**
	* Update the selection for the supplied indices.
	*
	* @param indices
	*/
	void updateSelection(final int[] indices) {
	indicesToSelect = indices;
	if (readyForSelection) {
	selectAndNotify(indices);
	}
	}

	/**
	* Select the first element if there is no selection
	*/
	private void defaultSelect() {
	/**
	* Reset to the first selection if no index has been queued.
	*/
	selectAndNotify(new int[] { 0 });
	}

	/**
	* Select the supplied indices and notify any listeners
	*
	* @param indices
	*/
	private void selectAndNotify(final int[] indices) {
	// It is possible that the table was disposed
	// before the update finished. If so then leave
	if (fTable.isDisposed()) {
	return;
	}
	fTable.setSelection(indices);
	fTable.notifyListeners(SWT.Selection, new Event());
	}
	}

	/**
	* Returns whether or not duplicates are allowed.
	*
	* @return <code>true</code> indicates duplicates are allowed
	*/
	public boolean getAllowDuplicates() {
	return fAllowDuplicates;
	}

	/**
	* Sets whether or not duplicates are allowed. If this value is set the
	* items should be set again for this value to take effect.
	*
	* @param allowDuplicates
	* <code>true</code> indicates duplicates are allowed
	*/
	public void setAllowDuplicates(boolean allowDuplicates) {
	this.fAllowDuplicates = allowDuplicates;
	}

	/**
	* Returns whether or not case should be ignored.
	*
	* @return <code>true</code> if case should be ignored
	*/
	public boolean getIgnoreCase() {
	return fIgnoreCase;
	}

	/**
	* Sets whether or not case should be ignored If this value is set the items
	* should be set again for this value to take effect.
	*
	* @param ignoreCase
	* <code>true</code> if case should be ignored
	*/
	public void setIgnoreCase(boolean ignoreCase) {
	this.fIgnoreCase = ignoreCase;
	}

	/**
	* Returns whether empty filter strings should filter everything or nothing.
	*
	* @return <code>true</code> for the empty string to match all items,
	* <code>false</code> to match none
	*/
	public boolean getMatchEmptyString() {
	return fMatchEmptyString;
	}

	/**
	* Sets whether empty filter strings should filter everything or nothing. If
	* this value is set the items should be set again for this value to take
	* effect.
	*
	* @param matchEmptyString
	* <code>true</code> for the empty string to match all items,
	* <code>false</code> to match none
	*/
	public void setMatchEmptyString(boolean matchEmptyString) {
	this.fMatchEmptyString = matchEmptyString;
	}

	/**
	* Returns the label provider for the items.
	*
	* @return the label provider
	*/
	public ILabelProvider getLabelProvider() {
	return fLabelProvider;
	}

	/**
	* Sets the label provider. If this value is set the items should be set
	* again for this value to take effect.
	*
	* @param labelProvider
	* the label provider
	*/
	public void setLabelProvider(ILabelProvider labelProvider) {
	this.fLabelProvider = labelProvider;
	}

	/**
	* Returns the accessible object for the receiver.
	* If this is the first time this object is requested,
	* then the object is created and returned.
	*
	* @return the accessible object
	*
	* @exception SWTException <ul>
	* <li>ERROR_WIDGET_DISPOSED - if the receiver has been disposed</li>
	* <li>ERROR_THREAD_INVALID_ACCESS - if not called from the thread that created the receiver</li>
	* </ul>
	*
	* @see Accessible#addAccessibleListener
	* @see Accessible#addAccessibleControlListener
	*
	* @since 3.3
	*/
	public Accessible getAccessible() {
	return fList.getAccessible();
	}
	}