/*******************************************************************************
 * Copyright (c) 2002, 2003 Object Factory Inc.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-v10.html
 * 
 * Contributors:
 *		Object Factory Inc. - Initial implementation
 *******************************************************************************/
package org.eclipse.ant.internal.ui.dtd.util;

import java.util.Comparator;

/**
 * SortedSet is a flyweight set implementation that uses
 * an external array provided by a KeyHolder.
 * SortedSet provides both equality/comparison operations
 * and identity operations.
 * @author Bob Foster
 */
public class SortedSet {
	protected Comparator fComp;
	protected IKeyHolder fKeyHolder;
	protected SortedSet fNext;
	
	public SortedSet(IKeyHolder holder, Comparator comp) {
		fComp = comp;
		fKeyHolder = holder;
	}
	/**
	 * Constructor. A keyholder must be
	 * supplied by <code>setKeyHolder()</code> prior ot
	 * <i>any</i> operations.
	 */
	public SortedSet(Comparator comp) {
		fComp = comp;
	}
	/**
	 * Constructor, no comparator. Only identity operations
	 * may be performed in this set.
	 */
	public SortedSet(IKeyHolder holder) {
		fKeyHolder = holder;
	}
	/**
	 * Constructor, no comparator. Only identity operations
	 * may be performed in this set. A keyholder must be
	 * supplied by <code>setKeyHolder()</code> prior ot
	 * <i>any</i> operations.
	 */
	public SortedSet() {
	}
	public void setKeyHolder(IKeyHolder holder) {
		fKeyHolder = holder;
	}
	public void setComparator(Comparator comp) {
		fComp = comp;
	}
	/**
	 * Add to set (no duplicates allowed).
	 * @param obj Object to add
	 * @return true if object was added; false
	 * if object was already in the set.
	 */
	public boolean add(Object obj) {
		return internalAdd(obj, false) >= 0;
	}
	protected int internalAdd(Object obj, boolean always) {
		Object[] array = fKeyHolder.getKeys();
		if (array == null) {
			array = new Object[1];
			fKeyHolder.setKeys(array);
			array[0] = obj;
			return 0;
		}
		int i = 0;
		int comp = -1;
		
		for (; i < array.length; i++) {
			if ((comp = fComp.compare(obj, array[i])) <= 0) {
				break;
			}
		}
		if (comp == 0 && !always)
			return -1;
		internalAdd(i, obj);
		return i;
	}
	protected void internalAdd(int i, Object obj) {
		Object[] array = fKeyHolder.getKeys();
		if (array == null) {
			array = new Object[1];
			array[0] = obj;
			fKeyHolder.setKeys(array);
		}
		else {
			Object[] tmp = new Object[array.length+1];
			System.arraycopy(array,0,tmp,0,i);
			tmp[i] = obj;
			System.arraycopy(array,i,tmp,i+1,array.length-i);
			fKeyHolder.setKeys(tmp);
		}
	}
	/**
	 * Add allowing duplicates.
	 * @param obj Object to add
	 * @return index where object was added in sorted order.
	 */
	public int addAlways(Object obj) {
		return internalAdd(obj, true);
	}
	/**
	 * Append, a variant of add allowing duplicates that
	 * always puts the new member at the end of the set.
	 * Set can be used with identity operations only.
	 */
	public void append(Object obj) {
		Object[] array = fKeyHolder.getKeys();
		int len = array != null ? array.length : 0;
		internalAdd(len, obj);
	}
	public boolean contains(Object obj) {
		return indexOf(obj) >= 0;
	}
	public int indexOf(Object obj) {
		Object[] array = fKeyHolder.getKeys();
		if (array == null)
			return -1;
		for (int i = 0; i < array.length; i++) {
			int comp = fComp.compare(obj, array[i]);
			if (comp == 0)
				return i;
			if (comp < 0)
				return -1;
		}
		return -1;
	}
	public boolean containsIdentity(Object obj) {
		return indexOf(obj) >= 0;
	}
	public int indexOfIdentity(Object obj) {
		Object[] array = fKeyHolder.getKeys();
		if (array == null)
			return -1;
		for (int i = 0; i < array.length; i++) {
			if (obj == array[i])
				return i;
		}
		return -1;
	}
	public boolean equals(Object o) {
		if (this == o)
			return true;
		if (!(o instanceof SortedSet))
			return false;
		SortedSet other = (SortedSet) o;
		Object[] array = fKeyHolder.getKeys();
		Object[] otherarray = other.fKeyHolder.getKeys();
		if ((array == null) != (otherarray == null))
			return false;
		if (array == null)
			return true;
		if (array.length != otherarray.length)
			return false;
		for (int i = 0; i < array.length; i++) {
			if (array[i] != otherarray[i])
				return false;
		}
		return true;
	}
	public boolean equalsIdentify(Object o) {
		if (this == o)
			return true;
		if (!(o instanceof SortedSet))
			return false;
		SortedSet other = (SortedSet) o;
		Object[] array = fKeyHolder.getKeys();
		Object[] otherarray = other.fKeyHolder.getKeys();
		if ((array == null) != (otherarray == null))
			return false;
		if (array == null)
			return true;
		if (array.length != otherarray.length)
			return false;
		for (int i = 0; i < array.length; i++) {
			if (fComp.compare(array[i], otherarray[i]) != 0)
				return false;
		}
		return true;
	}
	public void merge(SortedSet other) {
		Object[] array = fKeyHolder.getKeys();
		Object[] otherarray = other.fKeyHolder.getKeys();
		if (otherarray == null)
			return;
		if (array == null) {
			array = otherarray;
			return;
		}
		int ithis = 0, iother = 0, i = 0;
		int mthis = array.length, mother = otherarray.length;
		Object[] tmp = new Object[mthis+mother];
		while (ithis < mthis && iother < mother) {
			int comp = fComp.compare(array[ithis], otherarray[iother]);
			if (comp <= 0) {
				tmp[i++] = array[ithis++];
			}
			else {
				tmp[i++] = otherarray[iother++];
			}
		}
		while (ithis < mthis) {
			tmp[i++] = array[ithis++];
		}
		while (iother < mother) {
			tmp[i++] = otherarray[iother++];
		}
	}
	public Object[] members() {
		Object[] array = fKeyHolder.getKeys();
		if (array == null)
			return new Object[0];
		return array;
	}
	public int size() {
		Object[] array = fKeyHolder.getKeys();
		return array == null ? 0 : array.length;
	}
	public void remove(int i) {
		Object[] array = fKeyHolder.getKeys();
		Object[] tmp = new Object[array.length-1];
		System.arraycopy(array,0,tmp,0,i);
		System.arraycopy(array,i+1,tmp,i,array.length-i-1);
		fKeyHolder.setKeys(tmp);
	}
	public boolean remove(Object obj) {
		int i = indexOf(obj);
		if (i >= 0) {
			remove(i);
			return true;
		}
		return false;
	}
	public boolean removeIdentity(Object obj) {
		int i = indexOfIdentity(obj);
		if (i >= 0) {
			remove(i);
			return true;
		}
		return false;
	}
	public SortedSet getNextSet() {
		return fNext;
	}
	public void setNextSet(SortedSet next) {
		fNext = next;
	}

}