package mikera.indexz;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import mikera.vectorz.AVector;
import mikera.vectorz.impl.IndexVector;
import mikera.vectorz.util.ErrorMessages;
import mikera.vectorz.util.IntArrays;
import mikera.vectorz.util.VectorzException;

/**
 * Class to represent a mutable list of integer indexes, typically used for indexing into
 * vectors or matrices.
 * 
 * Backed by an int[] array.
 * 
 * @author Mike
 *
 */
@SuppressWarnings("deprecation")
public final class Index extends AIndex {
	private static final long serialVersionUID = 8698831088064498284L;

	public static final Index EMPTY = new Index(0);

	public final int[] data;
	
	public Index(int length) {
		this(new int[length]);
	}
	
	private Index(int[] indexes) {
		data=indexes;
	}
	
	/**
	 * Creates an Index using the values from the given ArrayList.
	 * 
	 * Values are cast to integers as needed, according to the semantics of (int)value
	 * 
	 * @param v
	 * @return
	 */
	public static Index create(ArrayList v) {
		int n=v.size();
		Index ind=new Index(n);
		for (int i=0; i v) {
		int n=v.size();
		Index ind=new Index(n);
		for (int i=0; i keySet) {
		int n=keySet.size();
		int[] data=new int[n];
		int i=0;
		for (int v:keySet) {
			data[i++]=v;
		}
		Arrays.sort(data);
		return wrap(data);
	}
	
	public static Index createSorted(SortedSet keySet) {
		int[] rs=new int[keySet.size()];
		int i=0;
		for (Integer x:keySet) {
			rs[i++]=x;
		}
		if (i!=rs.length) throw new VectorzException(ErrorMessages.impossible());
		return new Index(rs);
	}
	
	/**
	 * Creates an Index using the values from the given AVector.
	 * 
	 * Values are cast to integers as needed, according to the semantics of (int)value
	 * 
	 * @param v
	 * @return
	 */
	public static Index create(AVector v) {
		int n=v.length();
		Index ind=new Index(n);
		for (int i=0; i=data[i]) return false;
		}
		return true;
	}
	
	@Override
	public boolean isSorted() {
		int len=length();
		for (int i=1; idata[i]) return false;
		}
		return true;
	}
	
	@Override
	public boolean isPermutation() {
		int n=length();
		if (n>=64) {
			return isLongPermutation();
		} else {
			return isShortPermutation();
		}
	}
	
	private boolean isShortPermutation() {
		int n=length();
		long chk=0;
		for (int i=0; i=n)) return false;			
			chk=chk|(1L<=n)||chk[v]) return false;
			chk[v]=true;
		}
		for (int i=0; i is) {
		TreeSet ss=new TreeSet(this.toSet());
		for (Integer i:is) {
			ss.add(i);
		}
		return createSorted(ss);
	}
	
	public Index includeSorted(Index ind) {
		TreeSet ss=new TreeSet(this.toSet());
		for (Integer i:ind) {
			ss.add(i);
		}
		return createSorted(ss);
	}
	
	public Set toSet() {
		TreeSet ss=new TreeSet();
		for (int i=0; i toSortedSet() {
		TreeSet ss=new TreeSet();
		for (int i=0; i=0;
	}
	
	
	/**
	 * Returns a new Index with a value inserted at the specified position
	 */
	public Index insert(int position, int value) {
		return new Index(IntArrays.insert(data,position,value));
	}

	/**
	 * Finds a value in this Index and return's it's position, or -1 if not found
	 * 
	 * @param value
	 * @return
	 */
	public int find(int value) {
		for (int i=0; i=end)) return false;
		}
		return true;
	}

	public int[] getShape() {
		return new int[length()];
	}

	@Override
	public Index exactClone() {
		return create(this);
	}

	@Override
	public int last() {
		return data[data.length-1];
	}
}