/*
 * Copyright (C) 2012 たかはしのんき. All rights reserved.
 *
 * History:
 *  v0.1 2012/02/04 新規作成。
 */

package nonkit.lib;

/**
 * 2進行列を扱うクラスです。
 * @version v0.1 2012/02/04 新規作成。
 * @author たかはしのんき
 */
public class BMatrix {

    private int[][] cell;
    private int n, m, m2;
    private int[] mask = {
        0x80000000, 0x40000000, 0x20000000, 0x10000000,
        0x08000000, 0x04000000, 0x02000000, 0x01000000,
        0x00800000, 0x00400000, 0x00200000, 0x00100000,
        0x00080000, 0x00040000, 0x00020000, 0x00010000,
        0x00008000, 0x00004000, 0x00002000, 0x00001000,
        0x00000800, 0x00000400, 0x00000200, 0x00000100,
        0x00000080, 0x00000040, 0x00000020, 0x00000010,
        0x00000008, 0x00000004, 0x00000002, 0x00000001
    };
    
    /**
     * n行m列の2進行列のコンストラクタです。
     * @param n 行の数を指定します。
     * @param m 列の数を指定します。
     */
    public BMatrix(int n, int m)
    {
        // 列の数をintのサイズ32ビットで割ります。
        this.n = n;
        this.m = m;
        m2 = (int) Math.ceil((double) m / 32.0);
        cell = new int[n][m2];
        clear();
    }
    
    /**
     * 2進行列のある要素ijに値(0か1)を設定します。
     * @param i 設定する要素の行(1 origin)
     * @param j 設定する要素の列(1 origin)
     * @param value 設定する値0か1
     */
    public void setValue(int i, int j, int value)
    {
        int i0 = i - 1;     // 0 originに変換
        int j0 = j - 1;     // 0 originに変換
        int j1 = j0 % 32;   // 剰余
        int j2 = j0 / 32;
        if (value == 1)
            cell[i0][j2] |= mask[j1];
        else if (value == 0)
            cell[i0][j2] &= ~mask[j1];
    }

    /**
     * 2進行列をゼロクリアします。
     */
    public void clear()
    {
        for (int i0 = 0; i0 < n; i0++)
            for (int j2 = 0; j2 < m2; j2++)
                cell[i0][j2] = 0;
    }

    /**
     * 2進行列のある要素ijに値(0か1)を返します。
     * @param i 返す要素の行(1 origin)
     * @param j 返す要素の列(1 origin)
     * @return 要素ijに値(0か1)を返します。
     */
    public int getValue(int i, int j)
    {
        int i0 = i - 1;     // 0 originに変換
        int j0 = j - 1;     // 0 originに変換
        int j1 = j0 % 32;   // 剰余
        int j2 = j0 / 32;
        return ((cell[i0][j2] & mask[j1]) == 0) ? 0 : 1;
    }

    /* (非 Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString()
    {
        String str = new String();
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                str = str + this.getValue(i, j);
                str = str + ' ';
            }
            str = str + '\n';
        }
        return str;
    }
}

/*
 * Copyright (C) 2012 たかはしのんき. All rights reserved.
 *
 * History:
 *  v0.1 2012/02/04 新規作成。
 */

package nonkit.test;

import static org.junit.Assert.*;

import nonkit.lib.BMatrix;

import org.junit.After;
import org.junit.Test;

public class BMatrixTest {

    @After
    public void tearDown() throws Exception {
    }

    @Test
    // BMatrix 正常ケースのテスト
    public void testBMatrix1() {
        BMatrix bmGoban = new BMatrix(3, 3);
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testBMatrix:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // BMatrix 正常ケースのテスト(32境界)
    public void testBMatrix2() {
        BMatrix bmGoban = new BMatrix(32, 32);
        for (int i = 1; i <= 32; i++)
            for (int j = 1; j <= 32; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testBMatrix:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // BMatrix 正常ケースのテスト(32境界)
    public void testBMatrix3() {
        BMatrix bmGoban = new BMatrix(33, 33);
        for (int i = 1; i <= 33; i++)
            for (int j = 1; j <= 33; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testBMatrix:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // BMatrix 異常ケースのテスト(nが0)
    public void testBMatrix4() {
        BMatrix bmGoban = new BMatrix(0, 3);
        for (int i = 1; i <= 0; i++)
            for (int j = 1; j <= 3; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testBMatrix:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // BMatrix 異常ケースのテスト(mが0)
    public void testBMatrix5() {
        BMatrix bmGoban = new BMatrix(3, 0);
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 0; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testBMatrix:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // setValue 正常ケースのテスト(1を設定)
    public void testSetValue1() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(2, 2, 1);
        if (bmGoban.getValue(2, 2) != 1)
            fail("testSetValue:(2,2)が1ではありません");
    }

    @Test
    // setValue 正常ケースのテスト(0を設定)
    public void testSetValue2() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(2, 2, 1);
        bmGoban.setValue(2, 2, 0);
        if (bmGoban.getValue(2, 2) != 0)
            fail("testSetValue:(2,2)が0ではありません");
    }

    @Test
    // clear 正常ケースのテスト
    public void testClear() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(1, 2, 1);
        bmGoban.setValue(2, 2, 1);
        bmGoban.setValue(3, 3, 1);
        bmGoban.clear();
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                if (bmGoban.getValue(i, j) != 0)
                    fail("testClear:(" + i + "," + j + ")が0ではありません");
    }

    @Test
    // getValue 正常ケースのテスト
    public void testGetValue1() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(2, 2, 2);
        if (bmGoban.getValue(2, 2) != 0)
            fail("testSetValue:(2,2)が0ではありません");
    }

    @Test
    // getValue 異常ケースのテスト(行がオーバーフロー)
    public void testGetValue2() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(4, 2, 1);
        if (bmGoban.getValue(4, 2) != 1)
            fail("testSetValue:(4,2)が1ではありません");
    }

    @Test
    // getValue 異常ケースのテスト(列がオーバーフロー)
    public void testGetValue3() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(2, 4, 1);
        if (bmGoban.getValue(2, 4) != 1)
            fail("testSetValue:(2,4)が1ではありません");
    }

    @Test
    // toString 正常ケースのテスト
    public void testToString() {
        BMatrix bmGoban = new BMatrix(3,3);
        bmGoban.setValue(2, 2, 1);
        String str1 = new String();
        String str2 = "0 0 0 \n0 1 0 \n0 0 0 \n";
        str1 = bmGoban.toString();
        if (!str1.equals(str2))
            fail("testToString:文字列が正しくありません");
    }

}

/*
 * Copyright (C) 2012 たかはしのんき. All rights reserved.
 *
 * History:
 *  v0.1 2012/02/04 新規作成。
 */

package nonkit.test;

import nonkit.lib.BMatrix;

/**
 * 2進行列を扱うクラスBMatrixを使ったサンプルアプリです。
 * @version v0.1
 * @author たかはしのんき
 */
public class Sample1 {

    public static void main(String args[])
    {
        int[][] graphT = {
                {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 5},
                {3, 1}, {3, 2}, {3, 5}, {3, 6},
                {4, 2}, {4, 5},
                {5, 2}, {5, 3}, {5, 4}, {5, 6},
                {6, 3}, {6, 5}
        };
        
        int[][] graphR = {
                {1, 2}, {1, 4},
                {2, 1}, {2, 3}, {2, 5},
                {3, 2}, {3, 6},
                {4, 1}, {4, 5}, {4, 6},
                {5, 2}, {5, 4}, {5, 6}, {5, 8},
                {6, 3}, {6, 5}, {6, 9},
                {7, 4}, {7, 8},
                {8, 5}, {8, 7}, {8, 9},
                {9, 6}, {9, 8}
        };
        
        BMatrix bmT = new BMatrix(6, 6);
        for (int i = 0; i < graphT.length; i++)
            bmT.setValue(graphT[i][0], graphT[i][1], 1);
        System.out.println(bmT);
        
        BMatrix bmR = new BMatrix(9, 9);
        for (int i = 0; i < graphR.length; i++)
            bmR.setValue(graphR[i][0], graphR[i][1], 1);
        System.out.println(bmR);
    }
}

0 1 1 0 0 0 
1 0 1 1 1 0 
1 1 0 0 1 1 
0 1 0 0 1 0 
0 1 1 1 0 1 
0 0 1 0 1 0 

0 1 0 1 0 0 0 0 0 
1 0 1 0 1 0 0 0 0 
0 1 0 0 0 1 0 0 0 
1 0 0 0 1 1 0 0 0 
0 1 0 1 0 1 0 1 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 1 0 
0 0 0 0 1 0 1 0 1 
0 0 0 0 0 1 0 1 0