/*******************************************************************************
 * Copyright (c) 2004, 2015 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
 *     Sergey Prigogin (Google) - use parameterized types (bug 442021)
 *******************************************************************************/
package org.eclipse.core.internal.runtime;

import java.lang.ref.*;

/**
 * A hashset whose values can be garbage collected.
 * This API is EXPERIMENTAL and provided as early access.
 * @since 3.1
 */
public class ReferenceHashSet<T> {

	private interface HashedReference<T> {
		@Override
		int hashCode();

		T get();
	}

	private class HashableWeakReference<U> extends WeakReference<U> implements HashedReference<U> {
		public int hashCode;

		public HashableWeakReference(U referent, ReferenceQueue<? super U> queue) {
			super(referent, queue);
			this.hashCode = referent.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof HashableWeakReference))
				return false;
			U referent = super.get();
			@SuppressWarnings("unchecked")
			Object other = ((HashableWeakReference<?>) obj).get();
			if (referent == null)
				return other == null;
			return referent.equals(other);
		}

		@Override
		public int hashCode() {
			return this.hashCode;
		}

		@Override
		public String toString() {
			Object referent = super.get();
			if (referent == null)
				return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$  //$NON-NLS-2$
			return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
		}
	}

	private class HashableSoftReference<U> extends SoftReference<U> implements HashedReference<U> {
		public int hashCode;

		public HashableSoftReference(U referent, ReferenceQueue<? super U> queue) {
			super(referent, queue);
			this.hashCode = referent.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof HashableWeakReference))
				return false;
			Object referent = super.get();
			@SuppressWarnings("unchecked")
			Object other = ((HashableWeakReference<?>) obj).get();
			if (referent == null)
				return other == null;
			return referent.equals(other);
		}

		@Override
		public int hashCode() {
			return this.hashCode;
		}

		@Override
		public String toString() {
			Object referent = super.get();
			if (referent == null)
				return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$  //$NON-NLS-2$
			return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
		}
	}

	private class StrongReference<U> implements HashedReference<U> {
		private U referent;

		public StrongReference(U referent, ReferenceQueue<? super U> queue) {
			this.referent = referent;
		}

		@Override
		public int hashCode() {
			return referent.hashCode();
		}

		@Override
		public U get() {
			return referent;
		}

		@Override
		public boolean equals(Object obj) {
			return referent.equals(obj);
		}
	}

	HashedReference<T>[] values;

	public int elementSize; // number of elements in the table

	int threshold;

	ReferenceQueue<T> referenceQueue = new ReferenceQueue<T>();

	public ReferenceHashSet() {
		this(5);
	}

	@SuppressWarnings("unchecked")
	public ReferenceHashSet(int size) {
		this.elementSize = 0;
		this.threshold = size; // size represents the expected
		// number of elements
		int extraRoom = (int) (size * 1.75f);
		if (this.threshold == extraRoom)
			extraRoom++;
		this.values = new HashedReference[extraRoom];
	}

	/**
	 * Constant indicating that hard references should be used.
	 */
	final public static int HARD = 0;

	/**
	 * Constant indiciating that soft references should be used.
	 */
	final public static int SOFT = 1;

	/**
	 * Constant indicating that weak references should be used.
	 */
	final public static int WEAK = 2;

	private HashedReference<T> toReference(int type, T referent) {
		switch (type) {
			case HARD :
				return new StrongReference<T>(referent, referenceQueue);
			case SOFT :
				return new HashableSoftReference<T>(referent, referenceQueue);
			case WEAK :
				return new HashableWeakReference<T>(referent, referenceQueue);
			default :
				throw new Error();
		}
	}

	/*
	 * Adds the given object to this set. If an object that is equals to the
	 * given object already exists, do nothing. Returns the existing object or
	 * the new object if not found.
	 */
	public T add(T obj, int referenceType) {
		cleanupGarbageCollectedValues();
		int index = (obj.hashCode() & 0x7FFFFFFF) % this.values.length;
		HashedReference<T> currentValue;
		while ((currentValue = this.values[index]) != null) {
			T referent;
			if (obj.equals(referent = currentValue.get())) {
				return referent;
			}
			index = (index + 1) % this.values.length;
		}
		this.values[index] = toReference(referenceType, obj);

		// assumes the threshold is never equal to the size of the table
		if (++this.elementSize > this.threshold)
			rehash();

		return obj;
	}

	private void addValue(HashedReference<T> value) {
		Object obj = value.get();
		if (obj == null)
			return;
		int valuesLength = this.values.length;
		int index = (value.hashCode() & 0x7FFFFFFF) % valuesLength;
		HashedReference<T> currentValue;
		while ((currentValue = this.values[index]) != null) {
			if (obj.equals(currentValue.get())) {
				return;
			}
			index = (index + 1) % valuesLength;
		}
		this.values[index] = value;

		// assumes the threshold is never equal to the size of the table
		if (++this.elementSize > this.threshold)
			rehash();
	}

	private void cleanupGarbageCollectedValues() {
		HashedReference<?> toBeRemoved;
		while ((toBeRemoved = (HashedReference<?>) this.referenceQueue.poll()) != null) {
			int hashCode = toBeRemoved.hashCode();
			int valuesLength = this.values.length;
			int index = (hashCode & 0x7FFFFFFF) % valuesLength;
			HashedReference<T> currentValue;
			while ((currentValue = this.values[index]) != null) {
				if (currentValue == toBeRemoved) {
					// replace the value at index with the last value with the
					// same hash
					int sameHash = index;
					int current;
					while ((currentValue = this.values[current = (sameHash + 1) % valuesLength]) != null && currentValue.hashCode() == hashCode)
						sameHash = current;
					this.values[index] = this.values[sameHash];
					this.values[sameHash] = null;
					this.elementSize--;
					break;
				}
				index = (index + 1) % valuesLength;
			}
		}
	}

	public boolean contains(T obj) {
		return get(obj) != null;
	}

	/*
	 * Return the object that is in this set and that is equals to the given
	 * object. Return null if not found.
	 */
	public T get(T obj) {
		cleanupGarbageCollectedValues();
		int valuesLength = this.values.length;
		int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
		HashedReference<T> currentValue;
		while ((currentValue = this.values[index]) != null) {
			T referent;
			if (obj.equals(referent = currentValue.get())) {
				return referent;
			}
			index = (index + 1) % valuesLength;
		}
		return null;
	}

	private void rehash() {
		ReferenceHashSet<T> newHashSet = new ReferenceHashSet<T>(this.elementSize * 2); // double the number of expected elements
		newHashSet.referenceQueue = this.referenceQueue;
		HashedReference<T> currentValue;
		for (int i = 0, length = this.values.length; i < length; i++)
			if ((currentValue = this.values[i]) != null)
				newHashSet.addValue(currentValue);

		this.values = newHashSet.values;
		this.threshold = newHashSet.threshold;
		this.elementSize = newHashSet.elementSize;
	}

	/*
	 * Removes the object that is in this set and that is equals to the given
	 * object. Return the object that was in the set, or null if not found.
	 */
	public Object remove(T obj) {
		cleanupGarbageCollectedValues();
		int valuesLength = this.values.length;
		int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
		HashedReference<T> currentValue;
		while ((currentValue = this.values[index]) != null) {
			Object referent;
			if (obj.equals(referent = currentValue.get())) {
				this.elementSize--;
				this.values[index] = null;
				rehash();
				return referent;
			}
			index = (index + 1) % valuesLength;
		}
		return null;
	}

	public int size() {
		return this.elementSize;
	}

	@Override
	public String toString() {
		StringBuffer buffer = new StringBuffer("{"); //$NON-NLS-1$
		for (int i = 0, length = this.values.length; i < length; i++) {
			HashedReference<T> value = this.values[i];
			if (value != null) {
				Object ref = value.get();
				if (ref != null) {
					buffer.append(ref.toString());
					buffer.append(", "); //$NON-NLS-1$
				}
			}
		}
		buffer.append("}"); //$NON-NLS-1$
		return buffer.toString();
	}

	public Object[] toArray() {
		cleanupGarbageCollectedValues();
		Object[] result = new Object[elementSize];
		int resultSize = 0;
		for (int i = 0; i < values.length; i++) {
			if (values[i] == null)
				continue;
			Object tmp = values[i].get();
			if (tmp != null)
				result[resultSize++] = tmp;
		}
		if (result.length == resultSize)
			return result;
		Object[] finalResult = new Object[resultSize];
		System.arraycopy(result, 0, finalResult, 0, resultSize);
		return finalResult;
	}
}