content: /* 
   * Kodkod -- Copyright (c) 2005-present, Emina Torlak
   *
   * Permission is hereby granted, free of charge, to any person obtaining a copy
   * of this software and associated documentation files (the "Software"), to deal
   * in the Software without restriction, including without limitation the rights
   * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   * copies of the Software, and to permit persons to whom the Software is
   * furnished to do so, subject to the following conditions:
   *
   * The above copyright notice and this permission notice shall be included in
   * all copies or substantial portions of the Software.
   *
   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
   * THE SOFTWARE.
   */
  package kodkod.util.collections;
  
  import java.util.AbstractSet;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  /**
   * Implements the <tt>Set</tt> interface, backed by a hash table.  
   * It makes no guarantees as to the
   * iteration order of the set; in particular, it does not guarantee that the
   * order will remain constant over time.  This class does not permit the <tt>null</tt>
   * element.<p>
   *
   * This class offers constant time performance for the basic operations
   * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
   * assuming the hash function disperses the elements properly among the
   * buckets.  Iterating over this set requires time proportional to the sum of
   * the <tt>HashSet</tt> instance's size (the number of elements) plus the
   * "capacity" of the backing map (the number of
   * buckets).  Thus, it's very important not to set the initial capacity too
   * high (or the load factor too low) if iteration performance is important.<p>
   *
   * <p>This set differs from Java's HashSet in that it provides methods for 
   * retrieving elements with a particular <tt>hashcode</tt>.  This makes it 
   * easy to set as a cache in which cached objects' hashcodes are their keys.</p>
   * 
   * <p><b>Note that this implementation is not synchronized.</b> 
   * The iterators returned by this class's <tt>iterator</tt> method are
   * not <i>fail-fast</i></p>
   *
   * @specfield elts: set T
   * @author Emina Torlak
   */
  public final class CacheSet<E> extends AbstractSet<E> {
  	/* implementation adapted from java.util.HashMap and java.util.HashSet */
  	/**
  	 * The default initial capacity - MUST be a power of two.
  	 */
  	private static final int DEFAULT_INITIAL_CAPACITY = 16;
  	
  	/**
  	 * The maximum capacity, used if a higher value is implicitly specified
  	 * by either of the constructors with arguments.
  	 * MUST be a power of two <= 1<<30.
  	 */
  	private static final int MAXIMUM_CAPACITY = 1 << 30;
  	
  	/**
  	 * The load factor used when none specified in constructor.
  	 **/
  	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  	
  	/**
  	 * The table, resized as necessary. Length MUST Always be a power of two.
  	 */
  	private Entry<E>[] table;
  	
  	/**
  	 * The number of key-value mappings contained in this identity hash map.
  	 */
  	private int size;
  	
  	/**
  	 * The next size value at which to resize (capacity * load factor).
  	 */
  	private int threshold;
  	
  	/**
  	 * The load factor for the hash table.
  	 */
  	final float loadFactor;
  	
  	/**
  	 * Constructs a new, empty set; the backing map has
  	 * default initial capacity (16) and load factor (0.75).
  	 * @ensures no this.elts'
  	 */
  	@SuppressWarnings("unchecked")
  	public CacheSet() {
  		loadFactor = DEFAULT_LOAD_FACTOR;
  		threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  		table = new Entry[DEFAULT_INITIAL_CAPACITY];
  	}
  	
  	/**
  	 * Constructs a new, empty set; the backing map has
  	 * the specified initial capacity and the specified load factor.
  	 *
  	 * @param      initialCapacity   the initial capacity of the hash map.
  	 * @param      loadFactor        the load factor of the hash map.
  	 * @throws     IllegalArgumentException if the initial capacity is less
  	 *             than zero, or if the load factor is nonpositive.
  	 * @ensures no this.elts'
  	 */
  	@SuppressWarnings("unchecked")
  	public CacheSet(int initialCapacity, float loadFactor) {
  		if (initialCapacity < 0)
  			throw new IllegalArgumentException("Illegal initial capacity: " +
  					initialCapacity);
  		if (initialCapacity > MAXIMUM_CAPACITY)
  			initialCapacity = MAXIMUM_CAPACITY;
  		if (loadFactor <= 0 || Float.isNaN(loadFactor))
  			throw new IllegalArgumentException("Illegal load factor: " +
  					loadFactor);
  		
  		// Find a power of 2 >= initialCapacity
  		int capacity = 1;
  		while (capacity < initialCapacity) 
  			capacity <<= 1;
  		
  		this.loadFactor = loadFactor;
  		threshold = (int)(capacity * loadFactor);
  		table = new Entry[capacity];
  	}
  	
  	/**
  	 * Constructs a new set containing the elements in the specified
  	 * collection.  The <tt>HashMap</tt> is created with default load factor
  	 * (0.75) and an initial capacity sufficient to contain the elements in
  	 * the specified collection.
  	 *
  	 * @param c the collection whose elements are to be placed into this set.
  	 * @throws NullPointerException   if the specified collection is null.
  	 */
  	public CacheSet(Collection<? extends E> c) {
  		this(c.size(), .75f);
  		addAll(c);
  	}
  	
  	/**
  	 * Returns a hash value for the specified integer. 
  	 * The shift distances in this function were chosen as the result
  	 * of an automated search over the entire four-dimensional search space.
  	 */
  	private static int hash(int h) {
  		h += ~(h << 9);
  		h ^=  (h >>> 14);
  		h +=  (h << 4);
  		h ^=  (h >>> 10);
  		return h;
  	}
  	
  	/**
  	 * Returns a hash value for the specified object.  In addition to 
  	 * the object's own hashCode, this method applies a "supplemental
  	 * hash function," which defends against poor quality hash functions.
  	 * This is critical because HashMap uses power-of two length 
  	 * hash tables.<p>
  	 *
  	 * The shift distances in this function were chosen as the result
  	 * of an automated search over the entire four-dimensional search space.
  	 */
  	private static int hash(Object x) {
  		return hash(x.hashCode());
  	}
  	
  	/**
  	 * Returns index for hash code h. 
  	 */
  	private static int indexFor(int h, int length) {
  		return h & (length-1);
  	}
  	
  	/**
  	 * Returns the number of elements in this set.
  	 * @return #this.elts
  	 * @see java.util.Set#size()
  	 */
  	public int size() {
  		return size;
  	}
  	
  	/**
  	 * Returns true if this set is empty.
  	 * @return no this.elts
  	 * @see java.util.Set#isEmpty()
  	 */
  	public boolean isEmpty() {
  		return size==0;
  	}
  	
  	/**
  	 * Returns true if this set contains the given element.
  	 * @return elt in this.elts
  	 * @throws NullPointerException  elt = null
  	 * @see java.util.Set#contains(java.lang.Object)
  	 */
  	public boolean contains(Object elt) {
  		Entry<E> e = table[indexFor(hash(elt), table.length)]; 
  		while (e != null) {
  			if (e.val.equals(elt)) 
  				return true;
  			e = e.next;
  		}
  		return false;
  	}
  	
  	/** 
  	 * Returns an iterator over the elements in this set.
  	 * @return an iterator over this.elts.
  	 * @see java.util.Set#iterator()
  	 */
  	public Iterator<E> iterator() {
  		return new SetIterator();
  	}
  	
  	/**
  	 * Adds the given element to this set, if not already present.
  	 * @ensures this.elts' = this.elts + elt
  	 * @throws NullPointerException  elt = null
  	 * @return elt !in this.elts
  	 */
  	public boolean add(E elt) {
  		final int i = indexFor(hash(elt), table.length);
  		
  		for (Entry<E> e = table[i]; e != null; e = e.next) {
  			if (e.val.equals(elt)) {
  				return false;
  			}
  		}
  		
  		table[i] = new Entry<E>(elt, table[i]);
  		if (size++ >= threshold)
  			resize(2 * table.length);
  		
  		return true;
  	}
  	
  	/**
  	 * Rehashes the contents of this map into a new array with a
  	 * larger capacity.  This method is called automatically when the
  	 * number of keys in this map reaches its threshold.
  	 *
  	 * If current capacity is MAXIMUM_CAPACITY, this method does not
  	 * resize the map, but sets threshold to Integer.MAX_VALUE.
  	 * This has the effect of preventing future calls.
  	 *
  	 * @param newCapacity the new capacity, MUST be a power of two;
  	 *        must be greater than current capacity unless current
  	 *        capacity is MAXIMUM_CAPACITY (in which case value
  	 *        is irrelevant).
  	 */
  	@SuppressWarnings("unchecked")
  	private void resize(int newCapacity) {
  		Entry<E>[] oldTable = table;
  		int oldCapacity = oldTable.length;
  		if (oldCapacity == MAXIMUM_CAPACITY) {
  			threshold = Integer.MAX_VALUE;
  			return;
  		}
  		
  		Entry<E>[] newTable = new Entry[newCapacity];
  		transfer(newTable);
  		table = newTable;
  		threshold = (int)(newCapacity * loadFactor);
  	}
  	
  	/** 
  	 * Transfer all entries from current table to newTable.
  	 */
  	private void transfer(Entry<E>[] newTable) {
  		Entry<E>[] src = table;
  		int newCapacity = newTable.length;
  		for (int j = 0; j < src.length; j++) {
  			Entry<E> e = src[j];
  			if (e != null) {
  				src[j] = null;
  				do {
  					Entry<E> next = e.next;
  					int i = indexFor(hash(e.val), newCapacity);  
  					e.next = newTable[i];
  					newTable[i] = e;
  					e = next;
  				} while (e != null);
  			}
  		}
  	}
  	
  	/**
  	 * Removes the specified object from this set, if present.
  	 * @ensures this.elts' = this.elts - elt
  	 * @return elt in this.elts
  	 * @throws NullPointerException  elt = null
  	 * @see java.util.Set#remove(java.lang.Object)
  	 */
  	public boolean remove(Object elt) {
  		int i = indexFor(hash(elt), table.length);
  		Entry<E> prev = table[i];
  		Entry<E> e = prev;
  		
  		while (e != null) {
  			Entry<E> next = e.next;
  			if (e.val.equals(elt)) {
  				size--;
  				if (prev == e) 
  					table[i] = next;
  				else
  					prev.next = next;
  				return true;
  			}
  			prev = e;
  			e = next;
  		}
  		
  		return false;
  		
  	}
  	
  	/**
  	 * Returns an iterator over the elements 
  	 * whose hashcode() method returns the given hash.
  	 * @return an iterator over {e: this.elts | e.hashCode() = hash }
  	 */
  	public Iterator<E> get(final int hash) {
  		final int i = indexFor(hash(hash), table.length);
  		return new Iterator<E>() {
  			
  			Entry<E> current = null, next = table[i];
  			
  			public boolean hasNext() {
  				while(next != null && next.val.hashCode()!=hash) {
  					next = next.next;
  				}
  				return next != null;
  			}
  			
  			public E next() {
  				if (!hasNext()) throw new NoSuchElementException();
  				current = next;
  				next = next.next;
  				return current.val;
  			}
  			
  			public void remove() {
  				if (current==null)
  					throw new IllegalStateException();
  				Entry<E> prev = table[i];
  				Entry<E> e = prev;
  				
  				while (e.next != current) {
  					prev = e;
  					e = e.next;
  				}
  				
  				size--;
  				if (prev==e)
  					table[i] = next;
  				else 
  					prev.next = next;
  				current = null;
  			}
  			
  		};
  	}
  	
  	/**
  	 * Removes all elements from this set.
  	 * @ensures no this.elts'
  	 * @see java.util.Set#clear()
  	 */
  	public void clear() {
  		for (int i = 0; i < table.length; i++) 
  			table[i] = null;
  		size = 0;
  	}
  	
  	private static final class Entry<T> {
  		Entry<T> next;
  		T val;
  		
  		Entry(T val, Entry<T> next) {
  			this.val = val;
  			this.next = next;
  		}
  	}
  	
  	private final class SetIterator implements Iterator<E> {
  		Entry<E> next;	// next entry to return 
  		int index;		// current slot 
  		Entry<E> current;	// current entry
  		
  		SetIterator() {
  			index = table.length;
  			next = null;
  			if (size != 0) { // advance to first entry
  				while (index > 0 && (next = table[--index]) == null)
  					;
  			}
  		}
  		
  		public boolean hasNext() {
  			return next != null;
  		}
  		
  		public E next() {
  			Entry<E> e = next;
  			if (e == null) 
  				throw new NoSuchElementException();
  			
  			Entry<E> n = e.next;
  			while (n == null && index > 0)
  				n = table[--index];
  			next = n;
  			return (current = e).val;
  			
  		}
  		
  		public void remove() {
  			if (current == null)
  				throw new IllegalStateException();
  			
  			CacheSet.this.remove(current.val);
  			current = null;
  		}		
  	}
  	
  }
  