import org.eclipse.ui.internal.ide.filesystem.FileSystemStructureProvider;

    private FileSystemStructureProvider fileSystemStructureProvider = new FileSystemStructureProvider();

/*******************************************************************************

 * Copyright (c) 2007 Wind River Systems, Inc. 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: 

 * Martin Oberhuber (Wind River) - initial API and implementation for [105554] 

 *******************************************************************************/

package org.eclipse.ui.internal.ide.filesystem;

import java.util.Arrays;

/**

 * A pool of Strings for doing prefix checks against multiple

 * candidates.

 * <p>

 * Allows to enter a list of Strings, and then perform the

 * following checks:

 * <ul>

 *   <li>{@link #containsAsPrefix(String)} - check whether a given

 *       String s is a prefix of any String in the pool.</li>

 *   <li>{@link #hasPrefixOf(String)} - check whether any String

 *       in the pool is a prefix of the given String s. 

 * </ul>

 * The prefix pool is always kept normalized, i.e. no element of

 * the pool is a prefix of any other element in the pool. In order

 * to maintain this constraint, there are two methods for adding

 * Strings to the pool:

 * <ul>

 *   <li>{@link #insertLonger(String)} - add a String s to the pool,

 *       and remove any existing prefix of s from the pool.</li>

 *   <li>{@link #insertShorter(String)} - add a String s to the pool,

 *       and remove any existing Strings sx from the pool which 

 *       contain s as prefix.</li>

 * </ul>

 * The PrefixPool grows as needed when adding Strings. Typically,

 * it is used for prefix checks on absolute paths of a tree.

 * </p><p> 

 * This class is not thread-safe: no two threads may add or

 * check items at the same time.

 * 

 * @since 3.5.1

 * 

 * Class copied from org.eclipse.core.internal.localstore.PrefixPool

 * 

 */

public class PrefixPool {

	private String[] pool;

	private int size;

	/**

	 * Constructor.

	 * @param initialCapacity the initial size of the 

	 *     internal array holding the String pool. Must

	 *     be greater than 0.

	 */

	public PrefixPool(int initialCapacity) {

		if (initialCapacity <= 0)

			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); //$NON-NLS-1$

		pool = new String[initialCapacity];

		size = 0;

	}

	/**

	 * Clears the prefix pool, allowing all items to be

	 * garbage collected. Does not change the capacity

	 * of the pool.

	 */

	public/*synchronized*/void clear() {

		Arrays.fill(pool, 0, size, null);

		size = 0;

	}

	/**

	 * Return the current size of prefix pool.

	 * @return the number of elements in the pool. 

	 */

	public/*synchronized*/int size() {

		return size;

	}

	/**

	 * Ensure that there is room for at least one more element.

	 */

	private void checkCapacity() {

		if (size + 1 >= pool.length) {

			String[] newprefixList = new String[2 * pool.length];

			System.arraycopy(pool, 0, newprefixList, 0, pool.length);

			Arrays.fill(pool, null); //help the garbage collector

			pool = newprefixList;

		}

	}

	/**

	 * Insert a String s into the pool of known prefixes, removing

	 * any existing prefix of it.

	 * <p>

	 * If any existing prefix of this String is found in the pool,

	 * it is replaced by the new longer one in order to maintain

	 * the constraint of keeping the pool normalized.

	 * </p><p>

	 * If it turns out that s is actually a prefix or equal to

	 * an existing element in the pool (so it is essentially

	 * shorter), this method returns with no operation in order

	 * to maintain the constraint that the pool remains normalized.

	 * </p>

	 * @param s the String to insert.

	 */

	public/*synchronized*/void insertLonger(String s) {

		//check in reverse order since we expect some locality

		for (int i = size - 1; i >= 0; i--) {

			if (pool[i].startsWith(s)) {

				//prefix of an existing String --> no-op

				return;

			} else if (s.startsWith(pool[i])) {

				//replace, since a longer s has more prefixes than a short one

				pool[i] = s;

				return;

			}

		}

		checkCapacity();

		pool[size] = s;

		size++;

	}

	/**

	 * Insert a String s into the pool of known prefixes, removing

	 * any Strings that have s as prefix.

	 * <p>

	 * If this String is a prefix of any existing String in the pool,

	 * all elements that contain the new String as prefix are removed

	 * and return value <code>true</code> is returned.

	 * </p><p>

	 * Otherwise, the new String is added to the pool unless an 

	 * equal String or e prefix of it exists there already (so

	 * it is essentially equal or longer than an existing prefix).

	 * In all these cases, <code>false</code> is returned since

	 * no prefixes were replaced.

	 * </p>

	 * @param s the String to insert.

	 * @return <code>true</code>if any longer elements have been

	 *     removed.

	 */

	public/*synchronized*/boolean insertShorter(String s) {

		boolean replaced = false;

		//check in reverse order since we expect some locality

		for (int i = size - 1; i >= 0; i--) {

			if (s.startsWith(pool[i])) {

				//longer or equal to an existing prefix - nothing to do

				return false;

			} else if (pool[i].startsWith(s)) {

				if (replaced) {

					//replaced before, so shrink the array.

					//Safe since we are iterating in reverse order.

					System.arraycopy(pool, i + 1, pool, i, size - i - 1);

					size--;

					pool[size] = null;

				} else {

					//replace, since this is a shorter s

					pool[i] = s;

					replaced = true;

				}

			}

		}

		if (!replaced) {

			//append at the end

			checkCapacity();

			pool[size] = s;

			size++;

		}

		return replaced;

	}

	/**

	 * Check if the given String s is a prefix of any of Strings

	 * in the pool.

	 * @param s a s to check for being a prefix

	 * @return <code>true</code> if the passed s is a prefix

	 *     of any of the Strings contained in the pool.

	 */

	public/*synchronized*/boolean containsAsPrefix(String s) {

		//check in reverse order since we expect some locality

		for (int i = size - 1; i >= 0; i--) {

			if (pool[i].startsWith(s)) {

				return true;

			}

		}

		return false;

	}

	/**

	 * Test if the String pool contains any one that is a prefix

	 * of the given String s. 

	 * @param s the String to test

	 * @return <code>true</code> if the String pool contains a

	 *     prefix of the given String.

	 */

	public/*synchronized*/boolean hasPrefixOf(String s) {

		for (int i = size - 1; i >= 0; i--) {

			if (s.startsWith(pool[i])) {

				return true;

			}

		}

		return false;

	}

}

/*******************************************************************************

 * 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

 *******************************************************************************/

package org.eclipse.ui.internal.ide.filesystem;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStream;

import java.util.ArrayList;

import java.util.List;

import org.eclipse.ui.internal.ide.IDEWorkbenchPlugin;

import org.eclipse.ui.internal.ide.filesystem.PrefixPool;

import org.eclipse.ui.wizards.datatransfer.IImportStructureProvider;

/**

 * This class provides information regarding the structure and

 * content of specified file system File objects.

 * 

 * class copied from org.eclipse.ui.wizards.datatransfer.FileSystemStructureProvider as its singleton

 */

public class FileSystemStructureProvider implements IImportStructureProvider {

    private PrefixPool pathPrefixHistory;

    private PrefixPool rootPathHistory; 

    /**

     * Creates an instance of <code>FileSystemStructureProvider</code>.

     */

    public FileSystemStructureProvider() {

        super();

    }

    /* (non-Javadoc)

     * Method declared on IImportStructureProvider

     */

    public List getChildren(Object element) {

        File folder = (File) element;

        String[] children = folder.list();

        int childrenLength = children == null ? 0 : children.length;

        List result = new ArrayList(childrenLength);

        for (int i = 0; i < childrenLength; i++) {

        	File file = new File(folder, children[i]);

        	if(file.isDirectory() && isRecursiveLink(folder, file))

        		continue;

        	result.add(file);

		}

        return result;

    }

    private void initLinkHistoriesIfNeeded(){

    	if(pathPrefixHistory == null){

    		pathPrefixHistory = new PrefixPool(20);

    		rootPathHistory = new PrefixPool(20);

    	}

    }

	private boolean isRecursiveLink(File parentFile, File childFile) {

		boolean isRecursive = false;

		try {

			//Need canonical paths to check all other possibilities

			String parentPath = parentFile.getCanonicalPath() + '/';

			String childPath = childFile.getCanonicalPath() + '/';

			//get or instantiate the prefix and root path histories.

			//Might be done earlier - for now, do it on demand.

			initLinkHistoriesIfNeeded();

			//insert the parent for checking loops

			pathPrefixHistory.insertLonger(parentPath);

			if (pathPrefixHistory.containsAsPrefix(childPath)) {

				//found a potential loop: is it spanning up a new tree?

				if (!rootPathHistory.insertShorter(childPath)) {

					//not spanning up a new tree, so it is a real loop.

					isRecursive = true;

				}

			} else if (rootPathHistory.hasPrefixOf(childPath)) {

				//child points into a different portion of the tree that we visited already before, or will certainly visit.

				//This does not introduce a loop yet, but introduces duplicate resources.

				//TODO Ideally, such duplicates should be modelled as linked resources. See bug 105534

				isRecursive = false;

			} else {

				//child neither introduces a loop nor points to a known tree.

				//It probably spans up a new tree of potential prefixes.

				rootPathHistory.insertShorter(childPath);

			}

		} catch (IOException e) {

			//ignore

		}

		return isRecursive;

	}

	/* (non-Javadoc)

     * Method declared on IImportStructureProvider

     */

    public InputStream getContents(Object element) {

        try {

            return new FileInputStream((File) element);

        } catch (FileNotFoundException e) {

        	IDEWorkbenchPlugin.log(e.getLocalizedMessage(), e);

            return null;

        }

    }

    /* (non-Javadoc)

     * Method declared on IImportStructureProvider

     */

    public String getFullPath(Object element) {

        return ((File) element).getPath();

    }

    /* (non-Javadoc)

     * Method declared on IImportStructureProvider

     */

    public String getLabel(Object element) {

        //Get the name - if it is empty then return the path as it is a file root

        File file = (File) element;

        String name = file.getName();

        if (name.length() == 0) {

			return file.getPath();

		}

        return name;

    }

    /* (non-Javadoc)

     * Method declared on IImportStructureProvider

     */

    public boolean isFolder(Object element) {

        return ((File) element).isDirectory();

    }

}