/*
 * Copyright 2005 The Apache Software Foundation.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at 
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software 
 * distributed under the License is distributed on an "AS IS" BASIS, 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 * See the License for the specific language governing permissions and 
 * limitations under the License.
 */
package javolution.util;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.lang.reflect.Array;

import javolution.lang.Reusable;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

/**
 * A weak HashSet. An element stored in the WeakHashSet might be
 * garbage collected, if there is no strong reference to this element.
 */

public class WeakFastSet <E>  implements Set <E> , Reusable  {

	/**
	 * Helps to detect garbage collected values.
	 */
	private ReferenceQueue <E>  queue = new ReferenceQueue <E> ();

	private FastSet <WeakReference<E>>  set;

	public WeakFastSet()
	{
		set = new FastSet <WeakReference<E>> ();
	}

	public WeakFastSet(boolean shared)
	{
		this();
		if (shared)
			set.shared();
	}

	public WeakFastSet(int capacity, boolean shared)
	{
		set = new FastSet <WeakReference<E>> (capacity);
		if (shared)
			set.shared();
	}

	/**
	 * Returns an iterator over the elements in this set.  The elements
	 * are returned in no particular order.
	 *
	 * @return an Iterator over the elements in this set.
	 */
	@Override
	public Iterator <E>  iterator() {
		// remove garbage collected elements
		processQueue();

		// get an iterator of the superclass WeakHashSet
		final Iterator <WeakReference<E>>  i = set.iterator();

		return new Iterator <E> () {
			public boolean hasNext() {
				return i.hasNext();
			}

			public  E  next() {
				// unwrap the element
				return getReferenceObject((WeakElement <E> ) i.next());
			}

			public void remove() {
				// remove the element from the HashSet
				i.remove();
			}
		};
	}

	/**
	 * Returns <code>true</code> if this set contains the specified element.
	 *
	 * @param o element whose presence in this set is to be tested.
	 * @return <code>true</code> if this set contains the specified element.
	 */
	@Override
	public boolean contains(Object o) {
		return set.contains(WeakElement.create(o));
	}

	/**
	 * Adds the specified element to this set if it is not already
	 * present.
	 *
	 * @param o element to be added to this set.
	 * @return <code>true</code> if the set did not already contain the specified
	 * element.
	 */
	@Override
	public boolean add( E  o) {
		processQueue();
		return set.add(WeakElement.create(o, this.queue));
	}

	/**
	 * Removes the given element from this set if it is present.
	 *
	 * @param o object to be removed from this set, if present.
	 * @return <code>true</code> if the set contained the specified element.
	 */
	@Override
	public boolean remove(Object o) {
		boolean ret = set.remove(WeakElement.create(o));
		processQueue();
		return ret;
	}

	/**
	 * A convenience method to return the object held by the
	 * weak reference or <code>null</code> if it does not exist.
	 */
	private final  E  getReferenceObject(WeakReference <E>  ref) {
		return (ref == null) ? null : ref.get();
	}

	/**
	 * Removes all garbage collected values with their keys from the map.
	 * Since we don't know how much the ReferenceQueue.poll() operation
	 * costs, we should call it only in the add() method.
	 */
	private final void processQueue() {
		WeakElement <E>  we = null;

		while ((we = (WeakElement <E> ) this.queue.poll()) != null) {
			set.remove(we);
		}
	}

	/**
	 * A WeakFastSet stores objects of class WeakElement.
	 * A WeakElement wraps the element that should be stored in the WeakFastSet.
	 * WeakElement inherits from java.lang.ref.WeakReference.
	 * It redefines equals and hashCode which delegate to the corresponding methods
	 * of the wrapped element.
	 */
	static private class WeakElement <E>  extends WeakReference <E>  {
		private int hash; /* Hashcode of key, stored here since the key
                               may be tossed by the GC */

		private WeakElement( E  o) {
			super(o);
			hash = o.hashCode();
		}

		private WeakElement( E  o, ReferenceQueue <E>  q) {
			super(o, q);
			hash = o.hashCode();
		}

		private static  <E>  WeakElement <E>  create( E  o) {
			return (o == null) ? null : new WeakElement <E> (o);
		}

		private static  <E>  WeakElement <E>  create( E  o, ReferenceQueue <E>  q) {
			return (o == null) ? null : new WeakElement <E> (o, q);
		}

		/* A WeakElement is equal to another WeakElement iff they both refer to objects
               that are, in turn, equal according to their own equals methods */
		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (!(o instanceof WeakElement))
				return false;
			Object t = this.get();
			Object u = ((WeakElement <E> ) o).get();
			if (t == u) 
				return true;
			if ((t == null) || (u == null))
				return false;
			return t.equals(u);
		}

		@Override
		public int hashCode() {
			return hash;
		}
	}

	@Override
	public boolean addAll(Collection <? extends E>  c)
	{
		boolean modified = false;
		Iterator <? extends E>  itr = c.iterator();
		while (itr.hasNext()) {
			if (add(itr.next())) {
				modified = true;
			}
		}
		return modified;
	}

	@Override
	public void clear()
	{
		set.clear();
		while (queue.poll() != null)
			;
	}

	public boolean containsAll(Collection <?>  c)
	{
		Iterator <?>  itr = c.iterator();
		while (itr.hasNext()) {
			if (!contains(itr.next()))
				return false;
		}
		return true;
	}

	@Override
	public boolean isEmpty()
	{
		processQueue();
		return set.isEmpty();
	}

	public boolean removeAll(Collection <?>  c) 
	{
		boolean modified = false;
		Iterator <E>  itr = iterator();
		while (itr.hasNext()) {
			if (c.contains(itr.next())) {
				itr.remove();
				modified = true;
			}
		}
		return modified;
	}

	@Override
	public boolean retainAll(Collection <?>  c)
	{
		boolean modified = false;
		Iterator <E>  itr = iterator();
		while (itr.hasNext()) {
			if (!c.contains(itr.next())) {
				itr.remove();
				modified = true;
			}
		}
		return modified;
	}

	@Override
	public int size()
	{
		processQueue();
		return set.size();
	}

	@Override
	public Object[] toArray()
	{
		return toArray(new Object[size()]);
	}

	@Override
	public  <T> T [] toArray( T [] a)
	{
		int size = size();
		if (size != a.length)
			a = ( T []) Array.newInstance(a.getClass().getComponentType(), size);
		int i = 0;
		Iterator <E>  itr = iterator();
		while (itr.hasNext())
			a[i++] = ( T )itr.next();
		return a;
	}

	@Override
	public void reset()
	{
		clear();
	}

}
