/*******************************************************************************
 * 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 if the object matches the pattern,
		 *         <code>false otherwise. setFilter()
		 *         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 if the list is empty,
	 *         <code>false 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().
	 * 
	 * @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. 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
	 *         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 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 indicates duplicates are allowed
	 */
	public void setAllowDuplicates(boolean allowDuplicates) {
		this.fAllowDuplicates = allowDuplicates;
	}

	/**
	 * Returns whether or not case should be ignored.
	 * 
	 * @return <code>true 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 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 for the empty string to match all items,
	 *         <code>false 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 for the empty string to match all items,
	 *            <code>false 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>ERROR_THREAD_INVALID_ACCESS - if not called from the thread that created the receiver
	 * </ul>
	 * 
	 * @see Accessible#addAccessibleListener
	 * @see Accessible#addAccessibleControlListener
	 * 
	 * @since 3.3
	 */
	public Accessible getAccessible() {
		return fList.getAccessible();
	}
}