// Aqsis
// Copyright (c) 1997 - 2001, Paul C. Gregory
//
// Contact: pgregory@aqsis.com
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

/**
 * Copyright (C) 2006-2007  NTT DATA CORPORATION
 * 
 * Version: 1.0.0 2007/04/01
 *  
 */
package net.cellcomputing.himawari.library.types;

/**
 * 
 * 任意長のビット配列を提供するクラス
 * 
 * @author NTT DATA Corporation
 */
public strictfp class CqBitVector {
	
	
	private byte[]	m_aBits;			///< the array of bytes to store the byte vector.
	private int	m_cLength;			///< the size of the bitvector in bits.
	private int	m_cNumInts;			///< the size of the array in bytes.
	
	//マクロ
	private static final byte CHAR_BIT = 8;
	
	//内部使用の配列
	private static final int[] bitcount = new int[]
	{
		0, 1, 1, 2, 1, 2, 2, 3, 1, 
		2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 
		4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 
		3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 
		3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 
		4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 
		5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 
		2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 
		4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 
		4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 
		6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 
		4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 
		5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 
		6, 6, 7, 6, 7, 7, 8
	};
	
	/**
	 * デフォルトコンストラクタ
	 */
	public CqBitVector()
	{
		m_aBits = null; m_cLength = 0; m_cNumInts = 0;
	}
	
	/**
	 * 指定されたビット長で初期化する。
	 * @param size	初期ビット長
	 */
	public CqBitVector( int size )
	{
		m_aBits = null; m_cLength = 0; m_cNumInts = 0;
		if ( size > 0 ) SetSize( size );
	}
	
	
	/**
	 * コピーコンストラクタ。全要素をコピーする。
	 * @param from	コピー元
	 */
	public CqBitVector( final CqBitVector from )
	{
		this.assignment( from );
	}
	
	
	/**
	 * ビット長を取得する
	 * 
	 * @return	現在のビット長
	 */
	public int Size()
	{
		return ( m_cLength );
	}
	
	/**
	 * ビット長を設定する。
	 * 
	 * @param size	ビット長
	 */
	public void SetSize( int size )
	{
		int cNumInts = NumberOfInts( size );
		if ( m_cNumInts != cNumInts )
		{
			m_aBits = null;
			m_cNumInts = NumberOfInts( size );
			m_aBits = new byte[ m_cNumInts ];
		}
		m_cLength = size;
	}
	
	/** 
	 * 強制的に標準形へ整形する。<br>
	 * 例えば、全てのビットが未使用であれば、内部的なバイト配列は０サイズとなる。
	 * 
	 */
	public void Canonize()
	{
		( m_aBits ) [ m_cNumInts - 1 ] &= ( byte ) ~0 >>> ( CHAR_BIT - ( ( m_cLength % CHAR_BIT )!=0
				? ( m_cLength % CHAR_BIT )
				: CHAR_BIT ) )
				+ 24;// 24 = Integer.SIZE - Byte.SIZE
	}
	
	/**
	 * 指定位置のビットを設定
	 * 
	 * @param elem	設定するビットの位置
	 * @param value	設定するビット。true:1、false:0
	 */
	public void SetValue( int elem, boolean value )
	{
		assert( elem < m_cLength );
		if ( value )
			m_aBits[ elem / CHAR_BIT ] |= ( 1 << ( elem % CHAR_BIT ) );
		else
			m_aBits[ elem / CHAR_BIT ] &= ~( 1 << ( elem % CHAR_BIT ) );
	}
	
	/**
	 * 指定位置のビットを取得
	 * 
	 * @param elem	取得したいビットの位置
	 * @return	指定位置のビット
	 */
	public boolean Value( int elem )
	{
		assert( elem < m_cLength );
		return ( m_aBits[ elem / CHAR_BIT ] & ( 1 << ( elem % CHAR_BIT ) ) )!=0? true : false ;
	}
	
	/**
	 * 指定位置のビットを反転
	 * 
	 * @param elem	反転したいビットの位置
	 */
	public void Toggle( int elem )
	{
		assert( elem < m_cLength );
		m_aBits[ elem / CHAR_BIT ] ^= ( 1 << ( elem % CHAR_BIT ) );
	}
	
	/**
	 * 全てのビットを設定する
	 * 
	 * @param value	設定するビット。true:1、false:0
	 */
	public void SetAll( boolean value )
	{
		byte setval = ( value ) ? (byte)~0 : (byte)0;
		int i;
		
		for ( i = 0; i < m_cNumInts; i++ )
			m_aBits[ i ] = setval;
		Canonize();
	}
	
	/**
	 * 全てのビットを反転する
	 * 
	 */
	public void Complement()
	{
		int i;
		
		for ( i = 0; i < m_cNumInts; i++ )
			m_aBits[ i ] = (byte)~m_aBits[ i ];
		Canonize();
	}
	
	/**
	 * ONのビット数を算出
	 * 
	 * @return	ONのビット数
	 */
	public int Count()
	{
	    int count;
	    int i;
	    
		for( count = 0, i = 0; i < m_cNumInts; i++ ){
			int index = m_aBits[i]>=0 ? m_aBits[i] : m_aBits[i]+256; 
			count += bitcount[ index ];
		}
		return ( count );
	}
	
	/**
	 * 論理積。<br>
	 * 両者のサイズが異なる場合、その計算結果は保証されない。
	 * 
	 * @param from	対象のCqBitVector
	 * @return	計算結果（this）
	 */
	public CqBitVector	Intersect( CqBitVector from )
	{
	    int size = ( from.m_cLength < m_cLength ) ? from.m_cLength : m_cLength;
	    SetSize( size );
	    int numints = NumberOfInts( size );

	    int i;
	    for ( i = 0; i < numints; i++ )
	        m_aBits[ i ] = (byte)( m_aBits[ i ] & from.m_aBits[ i ] );

	    Canonize();

	    return ( this );
	}
	
	/**
	 * 論理和。<br>
	 * 両者のサイズが異なる場合、その計算結果は保証されない。
	 * 
	 * 
	 * @param from	対象のCqBitVector
	 * @return	計算結果（this）
	 */
	public CqBitVector	Union( CqBitVector from )
	{
	    int size = ( from.m_cLength > m_cLength ) ? from.m_cLength : m_cLength;
	    int ssize = ( from.m_cLength < m_cLength ) ? from.m_cLength : m_cLength;
	    SetSize( size );
	    int numints = NumberOfInts( ssize );

	    int i;
	    for ( i = 0; i < numints; i++ )
	        m_aBits[ i ] = (byte)( m_aBits[ i ] | from.m_aBits[ i ] );

	    Canonize();

	    return ( this );
	}
	
	/**
	 * 排他的論理和。<br>
	 * 両者のサイズが異なる場合、その計算結果は保証されない。
	 * 
	 * @param from	対象のCqBitVector
	 * @return	計算結果（this）
	 */
	public CqBitVector Difference( CqBitVector from )
	{
	    int size = ( from.m_cLength > m_cLength ) ? from.m_cLength : m_cLength;
	    int ssize = ( from.m_cLength < m_cLength ) ? from.m_cLength : m_cLength;
	    SetSize( size );
	    int numints = NumberOfInts( ssize );

	    int i;
	    for ( i = 0; i < numints; i++ )
	        m_aBits[ i ] = (byte)( m_aBits[ i ] ^ from.m_aBits[ i ] );

	    Canonize();

	    return ( this );
	}
	
	/**
	 * バイトでの配列サイズを返す
	 * 
	 * @return	バイトで考えた場合のバイト配列数
	 */
	public int ArraySize()
	{
		return( NumberOfInts(m_cLength) );
	}
	
	/**
	 * ビット配列の取得
	 * 
	 * @return	ビット配列
	 */
	public byte[] IntArray()
	{
		return ( m_aBits );
	}
	
	/**
	 * 指定ビット数を表現するのに必要なバイト数を算出する。
	 * 
	 * @param size	必要なビット数
	 * @return	必要なバイト数
	 */
	public static int NumberOfInts( int size )
	{
		return ( ( size + ( CHAR_BIT ) - 1 ) / ( CHAR_BIT ) );
	}
	
	//************************************************************************//
	//*** 演算子のオーバーロード
	//************************************************************************//
	
	/**
	 * 代入演算子
	 * 
	 * @param from	代入もとのCqBitVector
	 * @return	演算結果（this）
	 */
	public CqBitVector assignment( final CqBitVector from )
	{
		// Copy the array of bits
		SetSize( from.m_cLength );
		for ( int i = 0; i < m_cNumInts; i++ )
			m_aBits[ i ] = from.m_aBits[ i ];
		
		return ( this );
	}
	
	/**
	 * 論理積演算子
	 * @see #Intersect(CqBitVector)
	 * 
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果
	 */
	public CqBitVector and( CqBitVector from )
	{
		CqBitVector res = new CqBitVector( this );
		res.Intersect( from );
		return ( res );
	}
	
	/**
	 * 論理和演算子
	 * @see #Union(CqBitVector)
	 *  
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果
	 */
	public CqBitVector or( CqBitVector from )
	{
		CqBitVector res = new CqBitVector( this );
		res.Union( from );
		return ( res );
	}
	
	/**
	 * 排他的論理和演算子
	 * @see #Difference(CqBitVector)
	 * 
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果
	 */
	public CqBitVector xor( CqBitVector from )
	{
		CqBitVector res = new CqBitVector( this );
		res.Difference( from );
		return ( res );
	}
	
	/**
	 * 論理積代入
	 * @see #Intersect(CqBitVector)
	 * 
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果（this）
	 */
	public CqBitVector assignAnd( CqBitVector from )
	{
		Intersect( from );
		return ( this );
	}
	
	/**
	 * 論理和代入
	 * @see #Union(CqBitVector)
	 * 
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果（this）
	 */
	public CqBitVector assignOr( CqBitVector from )
	{
		Union( from );
		return ( this );
	}
	
	/**
	 * 排他的論理和代入
	 * @see #Difference(CqBitVector)
	 * 
	 * @param from	演算対象のCqBitVector
	 * @return	演算結果（this）
	 */
	public CqBitVector assignXor( CqBitVector from )
	{
		Difference( from );
		return ( this );
	}
	

	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		
		String Stream = "";

	    int numints = this.ArraySize();
	    if( numints == 0 ) return "0";
	    this.Canonize();

	    int i;
	    for ( i = 0; i < numints; i++ ){
			Stream += String.format( "%x" , IntArray()[i] );
	    }
	    
		return Stream;
	}
	
	
}
