/*******************************************************************************
 * Copyright 2011 See AUTHORS file.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ******************************************************************************/

package com.badlogic.gdx.utils;

/** A bitset, without size limitation, allows comparison via bitwise operators to other bitfields.
 * 
 * @author mzechner
 * @author jshapcott */
public class Bits {
  
	long[] bits = {0};

	public Bits () {
	}

	
	/** Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.
	 * @param nbits the initial size of the bit set
	 */
	public Bits (int nbits) {
		checkCapacity(nbits >>> 6);
	}

	/** @param index the index of the bit
	 * @return whether the bit is set
	 * @throws ArrayIndexOutOfBoundsException if index < 0 */
	public boolean get (int index) {
		final int word = index >>> 6;
		if (word >= bits.length) return false;
		return (bits[word] & (1L << (index & 0x3F))) != 0L;
	}

	/** Returns the bit at the given index and clears it in one go.
	 * @param index the index of the bit
	 * @return whether the bit was set before invocation
	 * @throws ArrayIndexOutOfBoundsException if index < 0 */
	public boolean getAndClear (int index) {
		final int word = index >>> 6;
		if (word >= bits.length) return false;
		long oldBits = bits[word];
		bits[word] &= ~(1L << (index & 0x3F));
		return bits[word] != oldBits;
	}

	/** Returns the bit at the given index and sets it in one go.
	 * @param index the index of the bit
	 * @return whether the bit was set before invocation
	 * @throws ArrayIndexOutOfBoundsException if index < 0 */
	public boolean getAndSet (int index) {
		final int word = index >>> 6;
		checkCapacity(word);
		long oldBits = bits[word];
		bits[word] |= 1L << (index & 0x3F);
		return bits[word] == oldBits;
	}

	/** @param index the index of the bit to set
	 * @throws ArrayIndexOutOfBoundsException if index < 0 */
	public void set (int index) {
		final int word = index >>> 6;
		checkCapacity(word);
		bits[word] |= 1L << (index & 0x3F);
	}

	/** @param index the index of the bit to flip */
	public void flip (int index) {
		final int word = index >>> 6;
		checkCapacity(word);
		bits[word] ^= 1L << (index & 0x3F);
	}

	private void checkCapacity (int len) {
		if (len >= bits.length) {
			long[] newBits = new long[len + 1];
			System.arraycopy(bits, 0, newBits, 0, bits.length);
			bits = newBits;
		}
	}

	/** @param index the index of the bit to clear
	 * @throws ArrayIndexOutOfBoundsException if index < 0 */
	public void clear (int index) {
		final int word = index >>> 6;
		if (word >= bits.length) return;
		bits[word] &= ~(1L << (index & 0x3F));
	}

	/** Clears the entire bitset */
	public void clear () {
		long[] bits = this.bits;
		int length = bits.length;
		for (int i = 0; i < length; i++) {
			bits[i] = 0L;
		}
	}

	/** @return the number of bits currently stored, <b>not</b> the highset set bit! */
	public int numBits () {
		return bits.length << 6;
	}

	/** Returns the "logical size" of this bitset: the index of the highest set bit in the bitset plus one. Returns zero if the
	 * bitset contains no set bits.
	 * 
	 * @return the logical size of this bitset */
	public int length () {
		long[] bits = this.bits;
		for (int word = bits.length - 1; word >= 0; --word) {
			long bitsAtWord = bits[word]; 
			if (bitsAtWord != 0) {
				for (int bit = 63; bit >= 0; --bit) {
					if ((bitsAtWord & (1L << (bit & 0x3F))) != 0L) {
						return (word << 6) + bit;
					}
				}
			}
		}
		return 0;
	}

	/** @return true if this bitset contains no bits that are set to true */
	public boolean isEmpty () {
		long[] bits = this.bits;
		int length = bits.length;
		for (int i = 0; i < length; i++) {
			if (bits[i] != 0L) {
				return false;
			}
		}
		return true;
	}

	/** Returns the index of the first bit that is set to true that occurs on or after the specified starting index. If no such bit
	 * exists then -1 is returned. */
	public int nextSetBit (int fromIndex) {
		long[] bits = this.bits;
		int word = fromIndex >>> 6;
		int bitsLength = bits.length;
		if (word >= bitsLength) return -1;
		long bitsAtWord = bits[word];
		if (bitsAtWord != 0) {
			for (int i = fromIndex & 0x3f; i < 64; i++) {
				if ((bitsAtWord & (1L << (i & 0x3F))) != 0L) {
					return (word << 6) + i;
				}
			}
		}
		for (word++; word < bitsLength; word++) {
			if (word != 0) {
				bitsAtWord = bits[word];
				if (bitsAtWord != 0) {
					for (int i = 0; i < 64; i++) {
						if ((bitsAtWord & (1L << (i & 0x3F))) != 0L) {
							return (word << 6) + i;
						}
					}
				}
			}
		}
		return -1;
	}

	/** Returns the index of the first bit that is set to false that occurs on or after the specified starting index. If no such bit
	 * exists then -1 is returned. */
	public int nextClearBit (int fromIndex) {
		long[] bits = this.bits;
		int word = fromIndex >>> 6;
		int bitsLength = bits.length;
		if (word >= bitsLength) return -1;
		long bitsAtWord = bits[word];
		for (int i = fromIndex & 0x3f; i < 64; i++) {
			if ((bitsAtWord & (1L << (i & 0x3F))) == 0L) {
				return (word << 6) + i;
			}
		}
		for (word++; word < bitsLength; word++) {
			if (word == 0) {
				return word << 6;
			}
			bitsAtWord = bits[word];
			for (int i = 0; i < 64; i++) {
				if ((bitsAtWord & (1L << (i & 0x3F))) == 0L) {
					return (word << 6) + i;
				}
			}
		}
		return -1;
	}

	/** Performs a logical <b>AND</b> of this target bit set with the argument bit set. This bit set is modified so that each bit in it has
	 * the value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also
	 * had the value true.
	 * @param other a bit set */
	public void and (Bits other) {
		for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {
			bits[i] &= other.bits[i];
		}
	}

	/** Clears all of the bits in this bit set whose corresponding bit is set in the specified bit set.
	 * 
	 * @param other a bit set */	
	public void andNot (Bits other) {
		for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {
			bits[i] &= ~other.bits[i];
		}
	}

	/** Performs a logical <b>OR</b> of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value
	 * true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value
	 * true.
	 * @param other a bit set */
	public void or (Bits other) {
		for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {
			bits[i] |= other.bits[i];
		}
	}
	
	/** Performs a logical <b>XOR</b> of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds: 
	 * <ul>
	 * <li>The bit initially has the value true, and the corresponding bit in the argument has the value false.</li> 
	 * <li>The bit initially has the value false, and the corresponding bit in the argument has the value true. </li>
	 * </ul>
	 * @param other
	 */
	public void xor (Bits other) {
		for (int i = 0, j = bits.length, k = other.bits.length; i < j && i < k; i++) {
			bits[i] ^= other.bits[i];
		}
	}

	/** Returns true if the specified BitSet has any bits set to true that are also set to true in this BitSet.
	 * 
	 * @param other a bit set
	 * @return boolean indicating whether this bit set intersects the specified bit set
	 */
	public boolean intersects (Bits other) {
		long[] bits = this.bits;
		long[] otherBits = other.bits;
		for (int i = Math.min(bits.length, otherBits.length) - 1; i >= 0; i--) {
			if ((bits[i] & otherBits[i]) != 0) {
				return true;
			}
		}
		return false;
	}

	/** Returns true if this bit set is a super set of the specified set, i.e. it has all bits set to true that are also set to true
	 * in the specified BitSet.
	 * 
	 * @param other a bit set
	 * @return boolean indicating whether this bit set is a super set of the specified set */
	public boolean containsAll (Bits other) {
		long[] bits = this.bits;
		long[] otherBits = other.bits;
		int otherBitsLength = otherBits.length;
		int bitsLength = bits.length;

		for (int i = bitsLength; i < otherBitsLength; i++) {
			if (otherBits[i] != 0) {
				return false;
			}
		}
		for (int i = Math.min(bitsLength, otherBitsLength) - 1; i >= 0; i--) {
			if ((bits[i] & otherBits[i]) != otherBits[i]) {
				return false;
			}
		}
		return true;
	}
}