package org.eclipse.jdt.internal.core.builder.impl;
/*
 * (c) Copyright IBM Corp. 2000, 2001.
 * All Rights Reserved.
 */
import org.eclipse.jdt.core.*;

public class OrderedSet {
	protected int elementCount;
	protected Object [] elementKeys;
	protected int [] elementIndexes;
	protected Object [] orderedList;

	protected float loadFactor;

	private static final int DEFAULT_SIZE = 101;

/**
 * Constructs a new OrderedSet using the default capacity
 * and load factor.
 */
public OrderedSet() {
	this (DEFAULT_SIZE);
}
/**
 * Constructs a new OrderedSet using the specified capacity
 * and the default load factor.
 *
 * @param       capacity    the initial capacity
 */
public OrderedSet (int capacity) {
	this(capacity, 0.75f);
}
/**
 * Constructs a new OrderedSet using the specified capacity
 * and load factor.
 *
 * @param       loadFactor  the initial load factor
 */
public OrderedSet (int capacity, float loadFactor) {
	if (capacity <= 0) throw new IllegalArgumentException();
	elementCount = 0;
	elementKeys = new Object [capacity];
	int[] indexes = new int [capacity];
	for (int i = capacity; --i >= 0; ) {
		indexes[i] = -1;
	}
	elementIndexes = indexes;
	orderedList = new Object[capacity];
	this.loadFactor = loadFactor;
}
private int findIndex (Object object, Object [] array) {
	Object key;
	int length = array.length;
	int index = (object.hashCode() & 0x7FFFFFFF) % length;
	for (int i=index; i<length; i++) {
		if (((key = array [i]) == null) || (key == object)) return i;
		if (key.equals (object)) return i;
	}
	for (int i=0; i<index; i++) {
		if (((key = array [i]) == null) || (key == object)) return i;
		if (key.equals (object)) return i;
	}
	return -1;  // unreacheable
}
/**
 * Answers the object associated with the specified index in
 * this OrderedSet. 
 *
 * @param       index the index to use
 * @return      the object associated with the specified index
 * @throws      ArrayIndexOutOfBoundsException if the index is out of range
 *
 * @see         #put
 */
public Object get(int index) {
	if (index >= elementCount) {
		throw new ArrayIndexOutOfBoundsException();
	}
	return orderedList[index];
}
/**
 * Answers whether the specified object is in
 * this OrderedSet.
 *
 * @param       obj the object, which must not be null
 * @return      true if the object is in the set, false otherwise
 *
 * @see         #put
 */
public boolean includes(Object obj) {
	if (obj == null) {
		throw new NullPointerException();
	}
	int index = elementIndexes[findIndex (obj, elementKeys)];
	return index != -1;
}
/**
 * Answers the index associated with the specified object in
 * this OrderedSet.
 *
 * @param       obj the object, which must not be null
 * @return      the index associated with the object
 * @throws      IllegalArgumentException if the key is not in the pool
 *
 * @see         #put
 */
public int index(Object obj) {
	if (obj == null) {
		throw new NullPointerException();
	}
	int findIndex = findIndex (obj, elementKeys);
	int index = elementIndexes[findIndex];
	if (index == -1) {
		throw new IllegalArgumentException();
	}
	return index;
}
/**
 * Associate the given object with the given index in this OrderedSet.
 * The object's index is not retrievable using index(Object).
 * But the object is retrievable using get(int index).
 * The index must not yet have been assigned.
 *
 * @param       index the index of the object
 * @param       obj the object to add
 *
 * @see         #get
 * @see         java.lang.Object#equals
 */
public void put(int index, Object obj) {
	if (obj == null) throw new NullPointerException ();
	if (orderedList.length <= index) {
		int[] newOrderedList = new int[orderedList.length*2];
		System.arraycopy(orderedList, 0, newOrderedList, 0, elementCount);
	}
	if (orderedList[index] != null) {
		throw new IllegalArgumentException();
	}
	orderedList[index] = obj;
	if (index >= elementCount) {
		elementCount = index + 1;
	}
}
/**
 * Associate the given object with the next index in this OrderedSet.
 * If the object is already present, its index is unchanged. The object cannot be null.
 *
 * @param       obj the object to add
 * @return      the index associated with the specified obj
 *
 * @see         #index
 * @see         java.lang.Object#equals
 */
public int put (Object obj) {
	if (obj == null) throw new NullPointerException ();
	int index = findIndex (obj, elementKeys);
	int resultIndex = elementIndexes [index];
	if (resultIndex == -1) {
		int size = (int)(elementKeys.length * loadFactor + 1);
		if ((elementCount + 1) >= size) {
			rehash ();
			index = findIndex (obj, elementKeys);
		}
		orderedList [elementCount] = elementKeys [index] = obj;
		return elementIndexes [index] = elementCount++;
	}
	else {
		return resultIndex;
	}
}
/**
 * Increases the capacity of this OrderedSet. This method is sent when
 * the size of this OrderedSet exceeds the load factor.
 */
protected void rehash () {
	Object key;
	int index, length = elementKeys.length<<1;
	Object [] newKeys = new Object [length];
	int [] newIndexes = new int [length];
	for (int i = length; --i >= 0; ) {
		newIndexes[i] = -1;
	}
	for (int i=0; i<elementKeys.length; i++) {
		if ((key = elementKeys [i]) != null) {
			index = findIndex (key, newKeys);
			newKeys [index] = key;
			newIndexes [index] = elementIndexes [i];
		}
	}
	Object [] newOrdered = new Object[length];
	System.arraycopy(orderedList, 0, newOrdered, 0, elementCount);
	elementKeys = newKeys;
	elementIndexes = newIndexes;
	orderedList = newOrdered;
}
/**
 * Answers the number of objects in this OrderedSet.
 *
 * @return      the number of objects in this OrderedSet
 */
public int size () {
	return elementCount;
}
/**
 * Answers the string representation of this OrderedSet.
 *
 * @return      the string representation of this OrderedSet
 */
public String toString () {
	Object key;
	StringBuffer buffer = new StringBuffer ();
	buffer.append ('{');
	for (int i=0; i<elementCount; i++) {
		if (i != 0) buffer.append (',');
		if (buffer.length() > 1000) {
			buffer.append("..."/*nonNLS*/);
			break;
		}
		buffer.append (orderedList[i]);
		buffer.append ('=');
		buffer.append (i);
	}
	buffer.append ('}');
	return buffer.toString ();
}
}