/*
 *                 Sun Public License Notice
 *
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"). You may not use this file except in
 * compliance with the License. A copy of the License is available at
 * http://www.sun.com/
 *
 * The Original Code is NetBeans. The Initial Developer of the Original
 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2004 Sun
 * Microsystems, Inc. All Rights Reserved.
 */

package org.netbeans.modules.javacore.scanning;

import org.netbeans.modules.javacore.JMManager;

/**
 * Fast set class for ints, loosely based java.util.HashTable, HashSet,
 * and the discussion of hashtables from "Data Structures & Algorithms
 * in Java" by Robert Lafore.
 *
 * @author Tom Ball
 */
final class IntSet {
    static class Entry {
	int value;
	int hash;
	Entry next;

	Entry(int v, int h, Entry n) {
	    value = v;
	    hash = h;
	    next = n;
	}
    }

    private Entry[] table;
    private int size;

    private static final int LOAD_FACTOR = 2;
    private static final int GROWTH_FACTOR = 2;

    public IntSet() {
	// 2048 is the max used by all of the JDK sources.
	// Use fewer only if the set is referenced longer than
	// the body of makeIndexes() above.
	this(2048);
    }

    public IntSet(int capacity) {
	table = new Entry[capacity];
    }

    public boolean add(int x) {
	if (contains(x))
	    return false;

	if (size > table.length / LOAD_FACTOR)
	    resize();

	int h = hash(x);
	int idx = indexFor(h, table.length);
	Entry e = new Entry(x, h, table[idx]);
	table[idx] = e;
	size++;
	return true;
    }

    public boolean contains(int x) {
	int h = hash(x);
	Entry e = table[indexFor(h, table.length)];
	while (e != null) {
	    if (e.value == x)
		return true;
	    e = e.next;
	}
	return false;
    }

    public int[] toArray() {
	int[] arr = new int[size];
	int n = 0;
	Entry eNext;
	for (int i = 0; i < table.length; i++)
	    for(Entry e = table[i]; e != null; e = e.next)
		arr[n++] = e.value;
	assert n == size;
	return arr;
    }

    private void resize() {
	Entry[] newt = new Entry[table.length * GROWTH_FACTOR];

	Entry eNext;
	for(int i = 0; i < table.length; i++)
	    for(Entry e = table[i]; e != null; e = eNext) {
		int idx = indexFor(e.hash, newt.length);
		eNext = e.next;
		e.next = newt[idx];
		newt[idx] = e;
	    }
	table = newt;
	JMManager.getLog().log("IntSet: table doubled to " + table.length);
    }

    // hash(), forIndex() from java.util.HashMap

    /**
     * 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.

     *
     * 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 index for hash code h. 
     */
    private static int indexFor(int h, int length) {
	return h & (length-1);
    }
}