Copyright (c) 2000, 2005 IBM Corporation and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
    IBM Corporation - initial API and implementation
/*******************************************************************************
 * Copyright (c) 2000, 2005 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * 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.
/**
 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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).
/**
	 * 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
/**
	 * 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
/**
	 * 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;
	}
}