/* WeakIdentityMap.java

	Purpose:
		
	Description:
		
	History:
		Sep 2, 2011 11:04:57 AM, Created by henrichen

Copyright (C) 2011 Potix Corporation. All Rights Reserved.
*/

package org.zkoss.bind.impl;

/*
 *  Copyright 2004 Brian S O'Neill
 *
 *  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.
 */

//revised from cojen

import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * WeakIdentityMap is like WeakHashMap, except it uses a key's identity
 * hashcode and equals methods. WeakIdentityMap is not thread-safe and must be
 * wrapped with Collections.synchronizedMap to be made thread-safe.
 * <p>
 * The documentation for WeakHashMap states that it is intended primarily for
 * use with key objects whose equals methods test for object identity using the
 * == operator. Because WeakIdentityMap strictly follows this behavior, it is
 * better suited for this purpose.
 * <p>
 * Note: Weakly referenced entries may be automatically removed during
 * either accessor or mutator operations, possibly causing a concurrent
 * modification to be detected. Therefore, even if multiple threads are only
 * accessing this map, be sure to synchronize this map first. Also, do not
 * rely on the value returned by size() when using an iterator from this map.
 * The iterators may return less entries than the amount reported by size().
 *
 * @author Brian S O'Neill
 * 
 * @since 6.0.0
 */
@SuppressWarnings("unchecked")
public class WeakIdentityMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
	// Types of Iterators
	static final int KEYS = 0;
	static final int VALUES = 1;
	static final int ENTRIES = 2;

	/**
	 * Converts a collection to string, supporting collections that contain
	 * self references
	 */
	static String toString(Collection c) {
		if (c.size() == 0) {
			return "[]";
		}
		StringBuffer buf = new StringBuffer(32 * c.size());
		buf.append('[');

		Iterator it = c.iterator();
		boolean hasNext = it.hasNext();
		while (hasNext) {
			Object obj = it.next();
			buf.append(obj == c ? "(this Collection)" : obj);
			hasNext = it.hasNext();
			if (hasNext) {
				buf.append(", ");
			}
		}
		buf.append("]");
		return buf.toString();
	}

	/**
	 * Converts a map to string, supporting maps that contain self references
	 */
	static String toString(Map m) {
		if (m.size() == 0) {
			return "{}";
		}
		StringBuffer buf = new StringBuffer(32 * m.size());
		buf.append('{');

		Iterator it = m.entrySet().iterator();
		boolean hasNext = it.hasNext();
		while (hasNext) {
			Map.Entry entry = (Map.Entry) it.next();
			Object key = entry.getKey();
			Object value = entry.getValue();
			buf.append(key == m ? "(this Map)" : key).append('=').append(value == m ? "(this Map)" : value);

			hasNext = it.hasNext();
			if (hasNext) {
				buf.append(',').append(' ');
			}
		}

		buf.append('}');
		return buf.toString();
	}

	/**
	 * Gets the map as a String.
	 * 
	 * @return a string version of the map
	 */
	public String toString() {
		return toString(this);
	}

	private transient Entry<K, V>[] table;
	private transient int count;
	private int threshold;
	private final float loadFactor;
	private final ReferenceQueue<K> queue;

	//this field volatile to detect concurrent modification, 
	//check line if (WeakIdentityMap.this.modCount != this.expectedModCount) {
	private transient AtomicInteger modCount = new AtomicInteger();

	// Views

	private transient Set<K> keySet;
	private transient Set<Map.Entry<K, V>> entrySet;
	private transient Collection<V> values;

	public WeakIdentityMap(int initialCapacity, float loadFactor) {
		if (initialCapacity <= 0) {
			throw new IllegalArgumentException("Initial capacity must be greater than 0");
		}
		if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
			throw new IllegalArgumentException("Load factor must be greater than 0");
		}
		this.loadFactor = loadFactor;
		this.table = new Entry[initialCapacity];
		this.threshold = (int) (initialCapacity * loadFactor);
		this.queue = new ReferenceQueue();
	}

	public WeakIdentityMap(int initialCapacity) {
		this(initialCapacity, 0.75f);
	}

	public WeakIdentityMap() {
		this(11, 0.75f);
	}

	public WeakIdentityMap(Map<? extends K, ? extends V> t) {
		this(Math.max(2 * t.size(), 11), 0.75f);
		putAll(t);
	}

	public int size() {
		// Cleanup right before, to report a more accurate size.
		cleanup();
		return this.count;
	}

	public boolean isEmpty() {
		return this.count == 0;
	}

	public boolean containsValue(Object value) {
		Entry[] tab = this.table;

		if (value == null) {
			for (int i = tab.length; i-- > 0;) {
				for (Entry e = tab[i], prev = null; e != null; e = e.next) {
					if (e.get() == null) {
						// Clean up after a cleared Reference.
						this.modCount.incrementAndGet();
						if (prev != null) {
							prev.next = e.next;
						} else {
							tab[i] = e.next;
						}
						this.count--;
					} else if (e.value == null) {
						return true;
					} else {
						prev = e;
					}
				}
			}
		} else {
			for (int i = tab.length; i-- > 0;) {
				for (Entry e = tab[i], prev = null; e != null; e = e.next) {
					if (e.get() == null) {
						// Clean up after a cleared Reference.
						this.modCount.incrementAndGet();
						if (prev != null) {
							prev.next = e.next;
						} else {
							tab[i] = e.next;
						}
						this.count--;
					} else if (value.equals(e.value)) {
						return true;
					} else {
						prev = e;
					}
				}
			}
		}

		return false;
	}

	public boolean containsKey(Object key) {
		if (key == null) {
			key = KeyFactory.NULL;
		}

		Entry[] tab = this.table;
		int hash = System.identityHashCode(key);
		int index = (hash & 0x7fffffff) % tab.length;

		for (Entry e = tab[index], prev = null; e != null; e = e.next) {
			Object entryKey = e.get();

			if (entryKey == null) {
				// Clean up after a cleared Reference.
				this.modCount.incrementAndGet();
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				this.count--;
			} else if (e.hash == hash && key == entryKey) {
				return true;
			} else {
				prev = e;
			}
		}

		return false;
	}

	public V get(Object key) {
		if (key == null) {
			key = KeyFactory.NULL;
		}

		Entry<K, V>[] tab = this.table;
		int hash = System.identityHashCode(key);
		int index = (hash & 0x7fffffff) % tab.length;

		for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
			Object entryKey = e.get();

			if (entryKey == null) {
				// Clean up after a cleared Reference.
				this.modCount.incrementAndGet();
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				this.count--;
			} else if (e.hash == hash && key == entryKey) {
				return e.value;
			} else {
				prev = e;
			}
		}

		return null;
	}

	private void cleanup() {
		// Cleanup after cleared References.
		Entry[] tab = this.table;
		ReferenceQueue queue = this.queue;
		Reference ref;
		while ((ref = queue.poll()) != null) {
			// Since buckets are single-linked, traverse entire list and
			// cleanup all cleared references in it.
			int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
			for (Entry e = tab[index], prev = null; e != null; e = e.next) {
				if (e.get() == null) {
					this.modCount.incrementAndGet();
					if (prev != null) {
						prev.next = e.next;
					} else {
						tab[index] = e.next;
					}
					this.count--;
				} else {
					prev = e;
				}
			}
		}
	}

	private void rehash() {
		int oldCapacity = this.table.length;
		Entry[] oldMap = this.table;

		int newCapacity = oldCapacity * 2 + 1;
		if (newCapacity <= 0) {
			// Overflow.
			if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
				return;
			}
		}
		Entry[] newMap = new Entry[newCapacity];

		this.modCount.incrementAndGet();
		this.threshold = (int) (newCapacity * this.loadFactor);
		this.table = newMap;

		for (int i = oldCapacity; i-- > 0;) {
			for (Entry old = oldMap[i]; old != null;) {
				Entry e = old;
				old = old.next;

				// Only copy entry if its key hasn't been cleared.
				if (e.get() == null) {
					this.count--;
				} else {
					int index = (e.hash & 0x7fffffff) % newCapacity;
					e.next = newMap[index];
					newMap[index] = e;
				}
			}
		}
	}

	public V put(K key, V value) {
		if (key == null) {
			key = (K) KeyFactory.NULL;
		}

		cleanup();

		// Make sure the key is not already in the WeakIdentityMap.
		Entry[] tab = this.table;
		int hash = System.identityHashCode(key);
		int index = (hash & 0x7fffffff) % tab.length;

		for (Entry e = tab[index], prev = null; e != null; e = e.next) {
			Object entryKey = e.get();

			if (entryKey == null) {
				// Clean up after a cleared Reference.
				this.modCount.incrementAndGet();
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				this.count--;
			} else if (e.hash == hash && key == entryKey) {
				Object old = e.value;
				e.value = value;
				return (V) old;
			} else {
				prev = e;
			}
		}

		this.modCount.incrementAndGet();

		if (this.count >= this.threshold) {
			// Rehash the table if the threshold is still exceeded.
			rehash();
			tab = this.table;
			index = (hash & 0x7fffffff) % tab.length;
		}

		// Creates the new entry.
		Entry e = new Entry(hash, key, this.queue, value, tab[index]);
		tab[index] = e;
		this.count++;
		return null;
	}

	public V remove(Object key) {
		if (key == null) {
			key = KeyFactory.NULL;
		}

		Entry<K, V>[] tab = this.table;
		int hash = System.identityHashCode(key);
		int index = (hash & 0x7fffffff) % tab.length;

		for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
			Object entryKey = e.get();

			if (entryKey == null) {
				// Clean up after a cleared Reference.
				this.modCount.incrementAndGet();
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				this.count--;
			} else if (e.hash == hash && key == entryKey) {
				this.modCount.incrementAndGet();
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}
				this.count--;

				V oldValue = e.value;
				e.value = null;
				return oldValue;
			} else {
				prev = e;
			}
		}

		return null;
	}

	public void putAll(Map<? extends K, ? extends V> t) {
		Iterator i = t.entrySet().iterator();
		while (i.hasNext()) {
			Map.Entry e = (Map.Entry) i.next();
			put((K) e.getKey(), (V) e.getValue());
		}
	}

	public void clear() {
		Entry[] tab = this.table;
		this.modCount.incrementAndGet();
		for (int index = tab.length; --index >= 0;) {
			tab[index] = null;
		}
		this.count = 0;
	}

	public Object clone() {
		try {
			WeakIdentityMap t = (WeakIdentityMap) super.clone();
			t.table = new Entry[this.table.length];
			for (int i = this.table.length; i-- > 0;) {
				t.table[i] = (this.table[i] != null) ? (Entry) this.table[i].copy(this.queue) : null;
			}
			t.keySet = null;
			t.entrySet = null;
			t.values = null;
			t.modCount.set(0);
			return t;
		} catch (CloneNotSupportedException e) {
			// this shouldn't happen, since we are Cloneable
			throw new InternalError();
		}
	}

	public Set<K> keySet() {
		if (this.keySet == null) {
			this.keySet = new AbstractSet<K>() {
				public Iterator iterator() {
					return createHashIterator(KEYS);
				}

				public int size() {
					return WeakIdentityMap.this.count;
				}

				public boolean contains(Object o) {
					return containsKey(o);
				}

				public boolean remove(Object o) {
					return o == null ? false : WeakIdentityMap.this.remove(o) == o;
				}

				//20140717, henrichen: ZK-2289
				public boolean add(K o) {
					final boolean contains = containsKey(o);
					WeakIdentityMap.this.put(o, null);
					return !contains;
				}

				//20140717, henrichen: ZK-2289
				public boolean addAll(Collection<? extends K> c) {
					boolean changed = false;
					for (K item : c) {
						final boolean ichanged = this.add(item);
						if (!changed && ichanged)
							changed = true;
					}
					return changed;
				}

				public void clear() {
					WeakIdentityMap.this.clear();
				}

				public String toString() {
					return WeakIdentityMap.toString(this);
				}
			};
		}
		return this.keySet;
	}

	public Collection<V> values() {
		if (this.values == null) {
			this.values = new AbstractCollection<V>() {
				public Iterator<V> iterator() {
					return createHashIterator(VALUES);
				}

				public int size() {
					return WeakIdentityMap.this.count;
				}

				public boolean contains(Object o) {
					return containsValue(o);
				}

				public void clear() {
					WeakIdentityMap.this.clear();
				}

				public String toString() {
					return WeakIdentityMap.toString(this);
				}
			};
		}
		return this.values;
	}

	public Set<Map.Entry<K, V>> entrySet() {
		if (this.entrySet == null) {
			this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
				public Iterator<Map.Entry<K, V>> iterator() {
					return createHashIterator(ENTRIES);
				}

				public boolean contains(Object o) {
					if (!(o instanceof Map.Entry)) {
						return false;
					}
					Map.Entry entry = (Map.Entry) o;
					Object key = entry.getKey();

					Entry[] tab = WeakIdentityMap.this.table;
					int hash = System.identityHashCode(key);
					int index = (hash & 0x7fffffff) % tab.length;

					for (Entry e = tab[index], prev = null; e != null; e = e.next) {
						Object entryKey = e.get();

						if (entryKey == null) {
							// Clean up after a cleared Reference.
							WeakIdentityMap.this.modCount.incrementAndGet();
							if (prev != null) {
								prev.next = e.next;
							} else {
								tab[index] = e.next;
							}
							WeakIdentityMap.this.count--;
						} else if (e.hash == hash && e.equals(entry)) {
							return true;
						} else {
							prev = e;
						}
					}

					return false;
				}

				public boolean remove(Object o) {
					if (!(o instanceof Map.Entry)) {
						return false;
					}
					Map.Entry entry = (Map.Entry) o;
					Object key = entry.getKey();
					Entry[] tab = WeakIdentityMap.this.table;
					int hash = System.identityHashCode(key);
					int index = (hash & 0x7fffffff) % tab.length;

					for (Entry e = tab[index], prev = null; e != null; e = e.next) {
						if (e.get() == null) {
							// Clean up after a cleared Reference.
							WeakIdentityMap.this.modCount.incrementAndGet();
							if (prev != null) {
								prev.next = e.next;
							} else {
								tab[index] = e.next;
							}
							WeakIdentityMap.this.count--;
						} else if (e.hash == hash && e.equals(entry)) {
							WeakIdentityMap.this.modCount.incrementAndGet();
							if (prev != null) {
								prev.next = e.next;
							} else {
								tab[index] = e.next;
							}
							WeakIdentityMap.this.count--;

							e.value = null;
							return true;
						} else {
							prev = e;
						}
					}
					return false;
				}

				public int size() {
					return WeakIdentityMap.this.count;
				}

				public void clear() {
					WeakIdentityMap.this.clear();
				}

				public String toString() {
					return WeakIdentityMap.toString(this);
				}
			};
		}

		return this.entrySet;
	}


	private Iterator createHashIterator(int type) {
		if (this.count == 0) {
			return Collections.EMPTY_SET.iterator();
		} else {
			return new HashIterator(type);
		}
	}

	/**
	 * WeakIdentityMap collision list entry.
	 */
	private static class Entry<K, V> extends WeakReference<K> implements Map.Entry<K, V> {
		int hash;
		V value;
		Entry<K, V> next;

		Entry(int hash, K key, ReferenceQueue<K> queue, V value, Entry<K, V> next) {
			super(key, queue);
			this.hash = hash;
			this.value = value;
			this.next = next;
		}

		public void clear() {
			// Do nothing if reference is explicity cleared. This prevents
			// backdoor modification of map entries.
		}

		public K getKey() {
			K key = Entry.this.get();
			return key == KeyFactory.NULL ? null : key;
		}

		public V getValue() {
			return this.value;
		}

		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		public boolean equals(Object obj) {
			if (!(obj instanceof Map.Entry)) {
				return false;
			}
			return equals((Map.Entry) obj);
		}

		boolean equals(Map.Entry<K, V> e) {
			Object thisKey = get();
			if (thisKey == null) {
				return false;
			} else if (thisKey == KeyFactory.NULL) {
				thisKey = null;
			}
			return (thisKey == e.getKey())
					&& (this.value == null ? e.getValue() == null : this.value.equals(e.getValue()));
		}

		public int hashCode() {
			return this.hash ^ (this.value == null ? 0 : this.value.hashCode());
		}

		public String toString() {
			return getKey() + "=" + this.value;
		}

		protected Object copy(ReferenceQueue queue) {
			return new Entry(this.hash, get(), queue, this.value,
					(this.next == null ? null : (Entry) this.next.copy(queue)));
		}
	}

	private class HashIterator implements Iterator {
		private final int type;
		private final Entry[] table;

		private int index;

		// To ensure that the iterator doesn't return cleared entries, keep a
		// hard reference to the key. Its existence will prevent the weak
		// key from being cleared.
		Object entryKey;
		Entry entry;

		Entry last;

		/**
		 * The modCount value that the iterator believes that the backing
		 * List should have. If this expectation is violated, the iterator
		 * has detected concurrent modification.
		 */
		private int expectedModCount = WeakIdentityMap.this.modCount.get();

		HashIterator(int type) {
			this.table = WeakIdentityMap.this.table;
			this.type = type;
			this.index = table.length;
		}

		public boolean hasNext() {
			while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
				if (this.entry != null) {
					// Clean up after a cleared Reference.
					remove(this.entry);
					this.entry = this.entry.next;
				} else {
					if (this.index <= 0) {
						return false;
					} else {
						this.entry = this.table[--this.index];
					}
				}
			}

			return true;
		}

		public Object next() {
			if (WeakIdentityMap.this.modCount.get() != this.expectedModCount) {
				throw new ConcurrentModificationException();
			}

			if (!hasNext()) {
				throw new NoSuchElementException();
			}

			this.last = this.entry;
			this.entry = this.entry.next;

			return this.type == KEYS ? this.last.getKey() : (this.type == VALUES ? this.last.getValue() : this.last);
		}

		public void remove() {
			if (this.last == null) {
				throw new IllegalStateException();
			}
			if (WeakIdentityMap.this.modCount.get() != this.expectedModCount) {
				throw new ConcurrentModificationException();
			}
			remove(this.last);
			this.last = null;
		}

		private void remove(Entry toRemove) {
			Entry[] tab = this.table;
			int index = (toRemove.hash & 0x7fffffff) % tab.length;

			for (Entry e = tab[index], prev = null; e != null; e = e.next) {
				if (e == toRemove) {
					WeakIdentityMap.this.modCount.incrementAndGet();
					expectedModCount++;
					if (prev == null) {
						tab[index] = e.next;
					} else {
						prev.next = e.next;
					}
					WeakIdentityMap.this.count--;
					return;
				} else {
					prev = e;
				}
			}

			throw new ConcurrentModificationException();
		}

		public String toString() {
			if (this.last != null) {
				return "Iterator[" + this.last + ']';
			} else {
				return "Iterator[]";
			}
		}
	}
}
