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

 * Copyright (c) 2000, 2005 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.core.internal.events;

import org.eclipse.core.runtime.IPath;

/**

 * A specialized map that maps Node IDs to their old and new paths.

 * Used for calculating moves during resource change notification.

 */

public class NodeIDMap {

	//using prime table sizes improves our hash function

	private static final int[] SIZES = new int[] {13, 29, 71, 173, 349, 733, 1511, 3079, 6133, 16381, 32653, 65543, 131111, 262139, 524287, 1051601};

	private static final double LOAD_FACTOR = 0.75;

	//2^32 * golden ratio

	private static final long LARGE_NUMBER = 2654435761L;

	int sizeOffset = 0;

	protected int elementCount = 0;

	protected long[] ids;

	protected IPath[] oldPaths;

	protected IPath[] newPaths;

	/**

	 * Creates a new node ID map of default capacity.

	 */

	public NodeIDMap() {

		this.sizeOffset = 0;

		this.ids = new long[SIZES[sizeOffset]];

		this.oldPaths = new IPath[SIZES[sizeOffset]];

		this.newPaths = new IPath[SIZES[sizeOffset]];

	}

	/**

	 * The array isn't large enough so double its size and rehash

	 * all its current values.

	 */

	protected void expand() {

		int newLength;

		try {

			newLength = SIZES[++sizeOffset];

		} catch (ArrayIndexOutOfBoundsException e) {

			//will only occur if there are > 1 million elements in delta

			newLength = ids.length * 2;

		}

		long[] grownIds = new long[newLength];

		IPath[] grownOldPaths = new IPath[newLength];

		IPath[] grownNewPaths = new IPath[newLength];

		int maxArrayIndex = newLength - 1;

		for (int i = 0; i < ids.length; i++) {

			long id = ids[i];

			if (id != 0) {

				int hash = hashFor(id, newLength);

				while (grownIds[hash] != 0) {

					hash++;

					if (hash > maxArrayIndex)

						hash = 0;

				}

				grownIds[hash] = id;

				grownOldPaths[hash] = oldPaths[i];

				grownNewPaths[hash] = newPaths[i];

			}

		}

		ids = grownIds;

		oldPaths = grownOldPaths;

		newPaths = grownNewPaths;

	}

	/**

	 * Returns the index of the given element in the map.  If not

	 * found, returns -1.

	 */

	private int getIndex(long searchID) {

		final int len = ids.length;

		int hash = hashFor(searchID, len);

		// search the last half of the array

		for (int i = hash; i < len; i++) {

			if (ids[i] == searchID)

				return i;

			// marker info not found so return -1

			if (ids[i] == 0)

				return -1;

		}

		// search the beginning of the array

		for (int i = 0; i < hash - 1; i++) {

			if (ids[i] == searchID)

				return i;

			// marker info not found so return -1

			if (ids[i] == 0)

				return -1;

		}

		// marker info not found so return -1

		return -1;

	}

	/**

	 * Returns the new path location for the given ID, or null

	 * if no new path is available.

	 */

	public IPath getNewPath(long nodeID) {

		int index = getIndex(nodeID);

		if (index == -1)

			return null;

		return newPaths[index];

	}

	/**

	 * Returns the old path location for the given ID, or null

	 * if no old path is available.

	 */

	public IPath getOldPath(long nodeID) {

		int index = getIndex(nodeID);

		if (index == -1)

			return null;

		return oldPaths[index];

	}

	private int hashFor(long id, int size) {

		//Knuth's hash function from Art of Computer Programming section 6.4

		return (int) Math.abs((id * LARGE_NUMBER) % size);

	}

	/**

	 * Returns true if there are no elements in the map, and

	 * false otherwise.

	 */

	public boolean isEmpty() {

		return elementCount == 0;

	}

	/**

	 * Adds the given path mappings to the map.  If either oldPath

	 * or newPath is null, they are ignored (old map values are not overwritten).

	 */

	private void put(long id, IPath oldPath, IPath newPath) {

		if (oldPath == null && newPath == null)

			return;

		int hash = hashFor(id, ids.length);

		// search for an empty slot at the end of the array

		for (int i = hash; i < ids.length; i++) {

			if (ids[i] == id) {

				//replace value for existing entry

				if (oldPath != null)

					oldPaths[i] = oldPath;

				if (newPath != null)

					newPaths[i] = newPath;

				return;

			}

			if (ids[i] == 0) {

				//add a new entry to the map

				ids[i] = id;

				if (oldPath != null)

					oldPaths[i] = oldPath;

				if (newPath != null)

					newPaths[i] = newPath;

				elementCount++;

				// grow if necessary

				if (shouldGrow())

					expand();

				return;

			}

		}

		// search for an empty slot at the beginning of the array

		for (int i = 0; i < hash - 1; i++) {

			if (ids[i] == id) {

				//replace value for existing entry

				if (oldPath != null)

					oldPaths[i] = oldPath;

				if (newPath != null)

					newPaths[i] = newPath;

				return;

			}

			if (ids[i] == 0) {

				//add a new entry to the map

				ids[i] = id;

				if (oldPath != null)

					oldPaths[i] = oldPath;

				if (newPath != null)

					newPaths[i] = newPath;

				elementCount++;

				// grow if necessary

				if (shouldGrow())

					expand();

				return;

			}

		}

		// if we didn't find a free slot, then try again with the expanded set

		expand();

		put(id, oldPath, newPath);

	}

	/**

	 * Adds an entry for a node's old path

	 */

	public void putOldPath(long id, IPath path) {

		put(id, path, null);

	}

	/**

	 * Adds an entry for a node's old path

	 */

	public void putNewPath(long id, IPath path) {

		put(id, null, path);

	}

	private boolean shouldGrow() {

		return elementCount > ids.length * LOAD_FACTOR;

	}

}