LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@muchosucho

一次元配列で二次元配列的な考えを真似てみる

Last updated at Posted at 2020-10-04

はじめに

データを2方向のインデックスで管理するやり方として、二次元配列を使うことが多いかと思います。

二次元配列の例
String[][] names = {
    {"山内", "森", "泉", "吉川", "渋谷"},
    {"松本", "河野", "水野", "川口", "牛尾"},
    {"嘉藤", "西村", "竹多", "吉田", "井藤"},
    {"川野", "加藤", "山田", "佐々木", "藤田"},
    {"柴田", "尾崎", "大森", "丘", "矢口"}
};
System.out.println(names[1][4]); // 牛尾

a.png
2方向のインデックスで管理するなら一次元配列であっても2方向のインデックスを用意すればデータ管理できるのではないかと思い、一次元配列で二次元配列的な考えを真似てみることにしました1。

準備

まずは二次元配列でいうところの横幅と縦幅を示す変数を2つ定義します。
以降、$width$を配列幅、$height$を配列高さと表現します。

int width = 5;
int height = 5;

そして先程の二次元配列を一次元化したものを、予め用意しておきます2。

String[] names = {
    "山内", "森", "泉", "吉川", "渋谷",
    "松本", "河野", "水野", "川口", "牛尾",
    "嘉藤", "西村", "竹多", "吉田", "井藤",
    "川野", "加藤", "山田", "佐々木", "藤田",
    "柴田", "尾崎", "大森", "丘", "矢口"
};
Iterator<String> nameTokens = Arrays.stream(names).iterator();
Person[] people = IntStream.range(0, width * height)
    .mapToObj(i -> new Person(nameTokens.next()))
    .toArray(Person[]::new);

b.png
配列を図にしたものを掲げます。この配列は、配列幅・配列高さ共に5の配列です。
各行の横方向のインデックスを$x$、各列の縦方向のインデックスを$y$とすると3、例えば「牛尾」を示すインデックスは、$x=4,\ y=1$となります。
また、各行の末尾の要素における横方向のインデックスは$$x=width-1$$となり、各列の末尾の要素における縦方向のインデックスは$$y=height-1$$となります。

実践

要素の走査

要素の走査は、次のコードを用いて行います。

走査コード
for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
    ...
    if (x == width - 1) {
        x = -1;
        y++;
    }
}

対象とする配列の要素を全て（インデックス0からarray.lengthまで）走査します。今回はpeople配列を定義しているので、array.lengthをpeople.lengthに置き換えます。for文で宣言されるカウンタ変数は次のとおりです。

変数 意味
i 配列のインデックス
x 配列の横方向のインデックスを示す値
y 配列の縦方向のインデックスを示す値

if (x == width - 1) {...}は、走査コードの...部分の処理を終えた後、その行の末尾の要素ならばyをインクリメントさせ、次の行に移ることを意味します。x = -1は調節用です。

要素の抽出と置換

これを利用して、例えば走査コードの...部分に

if (y == 1 && x == 4) System.out.println(people[i]);

と定義すれば、「牛尾」を出力することができます。

抽出例
for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
    if (y == 1 && x == 4) System.out.println(people[i]); // Person [name=牛尾]
    if (x == width - 1) {
        x = -1;
        y++;
    }
}

また、

if (y == 1 && x == 4) array[i] = new Person("ほげ");

と定義すれば、「牛尾」を「ほげ」に置き換えることができます。

置換例
for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
    if (y == 1 && x == 4) array[i] = new Person("ほげ");
    if (x == width - 1) {
        x = -1;
        y++;
    }
}

毎回手動で定義するのは面倒くさいことになると思い、モジュール化しました4。

Matrixクラス
class Matrix<T, R> {
    private T[] array;
    public final int width;
    public final int height;
    public int i;
    public int x;
    public int y;
    private Consumer<Matrix<T, R>> action;
    private Function<Matrix<T, R>, R> function;

    private Matrix(T[] array, int width, int height) {
        this.array = array;
        this.width = width;
        this.height = height;
    }

    static <T, R> Matrix<T, R> of(T[] array, int width, int height) {
        if (ObjectUtils.isEmpty(array))
            throw new IllegalArgumentException("第1引数にとる配列が空又はnullです。");
        if (array.length != width * height)
            throw new IllegalArgumentException("第1引数にとる配列の長さと「第2引数×第3引数」の値が一致しません。");
        return new Matrix<>(array, width, height);
    }

    Matrix<T, R> setAction(Consumer<Matrix<T, R>> action) {
        if (Objects.nonNull(function)) function = null;
        this.action = action;
        return this;
    }

    Matrix<T, R> setAction(Function<Matrix<T, R>, R> function) {
        if (Objects.nonNull(action)) action = null;
        this.function = function;
        return this;
    }

    @SuppressWarnings("unchecked")
    R get(int xIndex, int yIndex) {
        if (isIllegalIndex(xIndex, yIndex)) return null;
        return setAction(m -> {
            if (m.y == yIndex && m.x == xIndex) return (R) array[m.i];
            return null;
        })
        .run();
    }

    Matrix<T, R> put(T obj, int xIndex, int yIndex) {
        if (isIllegalIndex(xIndex, yIndex)) return this;
        setAction(m -> {
            if (m.y == yIndex && m.x == xIndex) array[m.i] = obj;
        })
        .run();
        return this;
    }

    T[] array() {
        return array;
    }

    Matrix<T, R> insertShiftLeft(T obj, int xIndex, int yIndex) {
        if (isIllegalIndex(xIndex, yIndex)) return this;
        setAction(m -> {
            if (m.i < width * yIndex + xIndex) array[m.i] = array[m.i + 1];
            if (m.y == yIndex && m.x == xIndex) array[m.i] = obj;
        })
        .run();
        return this;
    }

    Matrix<T, R> insertShiftRight(T obj, int xIndex, int yIndex) {
        if (isIllegalIndex(xIndex, yIndex)) return this;
        T[] cloneArray = array.clone();
        setAction(m -> {
            if (width * height - m.i - 1 > width * yIndex + xIndex)
                array[width * height - m.i - 1] = cloneArray[width * height - m.i - 2];
            if (m.y == yIndex && m.x == xIndex) array[m.i] = obj;
        })
        .run();
        return this;
    }

    R run() {
        if (Objects.isNull(action) && Objects.isNull(function))
            throw new IllegalStateException("順次処理を定義してください。");
        R result = null;
        Supplier<R> l_action = null;
        if (Objects.nonNull(action))
            l_action = () -> {action.accept(this); return null;};
        else if (Objects.nonNull(function))
            l_action = () -> function.apply(this);
        for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
            this.i = i;
            this.x = x;
            this.y = y;
            result = l_action.get();
            if (Objects.nonNull(result)) break;
            if (x == width - 1) {
                x = -1;
                y++;
            }
        }
        return result;
    }

    private boolean isIllegalIndex(int xIndex, int yIndex) {
        if (xIndex < 0 || width  - 1 < xIndex) return true;
        if (yIndex < 0 || height - 1 < yIndex) return true;
        return false;
    }
}

戻り値なしと戻り値ありの両方を想定しました。
<T, R>of(...)のTの部分に配列の型を指定します。
Rの部分については、戻り値ありの場合は戻り値の型を指定します。戻り値なしの場合はjava.lang.Voidを指定し、戻り値をなしとすることを明示します5。

使用例（戻り値なし）
Matrix.<Person, Void>of(people, width, height)
    .setAction(m -> {
        if (m.y == 1 && m.x == 4) System.out.println(people[m.i]); // Person [name=牛尾]
    })
    .run();

setActionメソッドで走査コードの...部分を定義してからrunメソッドを呼び出します。関数型インターフェースを用いており、i、x、yはそれぞれm.i、m.x、m.yと置き換えて使います。mはラムダ式の引数名6なので、mでなくても構いません。

戻り値ありの場合は、少し複雑ですが次のようにreturn付きの関数型インターフェースを利用します。
何らかの条件と一致するときに、null以外のオブジェクトを返すように定義して使います。また、条件と一致しないときはnullを返すようにします7。

使用例（戻り値あり）
String personName = Matrix.<Person, String>of(people, width, height)
    .setAction(m -> {
        if (m.y == 1 && m.x == 4) return people[m.i].toString();
        return null;
    })
    .run();
System.out.println(personName); // Person [name=牛尾]

これらの操作は、getメソッド・putメソッドとして実装しています。

Matrix<Person, Person> m = Matrix.of(people, width, height);
System.out.println(m.get(0, 3)); // Person [name=川野]
System.out.println(m.get(3, 2)); // Person [name=吉田]
System.out.println(m.get(4, 1)); // Person [name=牛尾]

m.put(new Person("ほげ"), 0, 3);
System.out.println(m.get(0, 3)); // Person [name=ほげ]

要素の挿入とシフト

一次元配列を利用しているので、次のように定義すれば要素を挿入することができます。
配列の長さは固定なので「山田」以前の要素は左に一つずつずれ、先頭の要素（山内）は消えます。

「山田」と「佐々木」の間に「ほげ」を挿入し、左にシフトする。
int xIndex = 2;
int yIndex = 3;
Matrix.<Person, Void>of(people, width, height)
    .setAction(m -> {
        if (m.i < width * yIndex + xIndex) array[m.i] = array[m.i + 1];
        if (m.y == yIndex && m.x == xIndex) array[m.i] = new Person("ほげ");
    })
    .run();

反対に、次のように定義すれば「山田」以降の要素は右に一つずつずれ、末尾の要素（矢口）は消えます。一つの配列だけで操作すると参照コピーの問題からか$x=0$指定時の要素のシフトが期待どおりとならないため、一旦配列を複製し、その配列から元の配列に対し操作を施すようにしています。

「加藤」と「山田」の間に「ほげ」を挿入し、右にシフトする。
int xIndex = 2;
int yIndex = 3;
Person[] cloneArray = people.clone();
Matrix.<Person, Void>of(people, width, height)
    .setAction(m -> {
        if (width * height - m.i - 1 > width * yIndex + xIndex)
            array[width * height - m.i - 1] = cloneArray[width * height - m.i - 2];
        if (m.y == yIndex && m.x == xIndex) array[m.i] = new Person("ほげ");
    })
    .run();

これらの操作は、insertShiftLeftメソッド・insertShiftRightメソッドとして実装しています。

Matrix.<Person, Void>of(people, width, height)
    .insertShiftLeft(new Person("ほげ"), 2, 4); // 「大森」と「丘」の間に「ほげ」を挿入し、左にシフトする。

Matrix.<Person, Void>of(people, width, height)
    .insertShiftRight(new Person("ほげ"), 2, 4); // 「尾崎」と「大森」の間に「ほげ」を挿入し、右にシフトする。

まとめ

一次元配列でも、二次元配列的なデータ管理を行うことができました。後で配列幅や配列高さを変えたくなっても$width$や$height$の値を変えるだけで対応することができます。

int width = 7;
int height = 2;
String[] names = {
    "山内", "森", "泉", "吉川", "渋谷", "松本", "河野",
    "嘉藤", "西村", "竹多", "吉田", "井藤", "川野", "加藤"
};
Iterator<String> nameTokens = Arrays.stream(names).iterator();
Person[] people = ... // 省略
Matrix<Person, Person> m = Matrix.of(people, width, height);
System.out.println(m.get(3, 1)); // Person [name=吉田]

他にも、やろうと思えば次のように各行の最も左側にあるnullでない要素を一つずつ抽出するメソッドをMatrixクラスに定義することもできます。走査コードの変数群を使えば、右側、上側、下側と、四方の要素を出力することができます。

@SuppressWarnings("unchecked")
public T[] getNonNullRightElements() {
    T[] elements = (T[]) Array.newInstance(array.getClass().getComponentType(), height);
    setAction(m -> {
        if (Objects.nonNull(array[m.i])) elements[m.y] = array[m.i];
    })
    .run();
    return ArrayUtils.removeAllOccurrences(elements, null);
}

これを応用すれば、次の図のような当たり判定があるマスをピンポイントに抽出することもできます。

c.png

追記

Matrixクラスの修正

@sdkei さんのコメントより、Matrixクラスにおけるご指摘をいただきました。ありがとうございます！
頂いた改善策をもとに、次のようにMatrixクラスを修正しました。

Matrixクラス
public final class Matrix<T, R> {
    private final T[] array;
    private final int width;
    private final int height;
    private MatrixRunner runner;
    private MatrixSupplier<R> supplier;

    private Matrix(T[] array, int width, int height) {
        this.array = array;
        this.width = width;
        this.height = height;
    }

    public static <T, R> Matrix<T, R> of(T[] array, int width, int height) {
        if (ObjectUtils.isEmpty(array))
            throw new IllegalArgumentException("第1引数にとる配列が空又はnullです。");
        if (array.length != width * height)
            throw new IllegalArgumentException("第1引数にとる配列の長さと「第2引数×第3引数」の値が一致しません。");
        return new Matrix<>(array.clone(), width, height); // 防御的コピー
    }

    public Matrix<T, R> setAction(MatrixRunner runner) {
        if (Objects.nonNull(supplier)) supplier= null;
        this.runner = runner;
        return this;
    }

    public Matrix<T, R> setAction(MatrixSupplier<R> supplier) {
        if (Objects.nonNull(runner)) runner= null;
        this.supplier = supplier;
        return this;
    }

    @SuppressWarnings("unchecked")
    public R get(int xIndex, int yIndex) {
        if (indexOutOfBounds(xIndex, yIndex)) return null;
        return (R) array[width * yIndex + xIndex];
    }

    public Matrix<T, R> put(T obj, int xIndex, int yIndex) {
        if (indexOutOfBounds(xIndex, yIndex)) return this;
        array[width * yIndex + xIndex] = obj;
        return this;
    }

    public T[] array() {
        return array.clone(); // 防御的コピー
    }

    public Matrix<T, R> insertShiftLeft(T obj, int xIndex, int yIndex) {
        if (indexOutOfBounds(xIndex, yIndex)) return this;
       setAction((i, x, y) -> {
            if (i < width * yIndex + xIndex) array[i] = array[i + 1];
            if (y == yIndex && x == xIndex) array[i] = obj;
        })
        .run();
        return this;
    }

    public Matrix<T, R> insertShiftRight(T obj, int xIndex, int yIndex) {
        if (indexOutOfBounds(xIndex, yIndex)) return this;
        T[] cloneArray = array.clone();
        setAction((i, x, y) -> {
            if (width * height - i - 1 > width * yIndex + xIndex)
                array[width * height - i - 1] = cloneArray[width * height - i - 2];
            if (y == yIndex && x == xIndex) array[i] = obj;
        })
        .run();
        return this;
    }

    public R run() {
        if (Objects.isNull(runner) && Objects.isNull(supplier))
            throw new IllegalStateException("順次処理を定義してください。");
        R result = null;
        MatrixSupplier<R> l_supplier = null;
        if (Objects.nonNull(runner))
           l_supplier = (i, x, y) -> { runner.run(i, x, y); return null; };
        else if (Objects.nonNull(supplier))
            l_supplier = (i, x, y) -> supplier.get(i, x, y);
        for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
            result = l_supplier.get(i, x, y);
            if (Objects.nonNull(result)) break;
            if (x == width - 1) {
                x = -1;
                y++;
            }
        }
        return result;
    }

    @FunctionalInterface
    public interface MatrixRunner {
        void run(int i, int x, int y);
    }

    @FunctionalInterface
    public interface MatrixSupplier<R> {
        R get(int i, int x, int y);
    }

    private boolean indexOutOfBounds(int xIndex, int yIndex) {
        if (xIndex < 0 || width  - 1 < xIndex) return true;
        if (yIndex < 0 || height - 1 < yIndex) return true;
        return false;
    }
}

修正点

  • 可変性の制限（final class化、フィールドの一部private final化、防御的コピーの実装）8。
  • get、putメソッドの軽量化
  • MatrixRunner、MatrixSupplierインターフェースの導入。これにより、走査コードの変数群を呼び出すための値をpublicフィールドとして持たせる必要がなくなりました。
  • その他メソッド名の修正、クラス・メソッドのpublic化など

関数型インターフェースを自作することにより、カプセル化をより強固なものとすることができました。
正直、感動しました。

更に、runnerフィールドとsupplierフィールドの可変性を利用するために、runOnlyメソッドを追加しました。

runOnlyメソッド
public Matrix<T, R> runOnly() {
    if (Objects.isNull(runner))
        throw new IllegalStateException("順次処理を定義してください。");
    for (int i = 0, x = 0, y = 0; i < array.length; i++, x++) {
        runner.run(i, x, y);
        if (x == width - 1) {
            x = -1;
            y++;
        }
    }
    return this;
}
使用例
@test 
public void testRunOnly() {
    List<String> people = new ArrayList<>();
    matrix.setAction((i, x, y) -> {
            if (x == 0 &&
                (this.people[i].name.contains("山") || this.people[i].name.contains("川"))
                people.add(this.people[i].name);
        })
        .runOnly()
        .setAction((i, x, y) -> {
            if (x == 3 && (this.people[i].name.contains("吉")))
                people.add(this.people[i].name);
        })
        .runOnly();
    assertThat(people, contains("山内", "川野", "吉川", "吉田"));
}

順次的に処理するとあまり実用的ではないと思いますが、runOnly()で一つの処理を施した後、一旦Matrixオブジェクトを別のメソッドやオブジェクトに投げ、他のメソッドやオブジェクト内で異なるアクションをsetActionメソッドで設定した後、runOnly()を呼び出し異なる処理を施すなどの使い方をすれば、多少処理の実装に幅が出るような気がします。

  1. あくまでも好奇心からなる実験的なものです。決してアンチ二次元配列などではありません。 ↩

  2. Personクラスでは、名前を表すフィールドを定義し、名前を出力するためのtoStringメソッドをオーバーライドさせています。 ↩

  3. $x,\ y$は、共に正の方向に1ずつ増加する（インクリメントする）ものとします。 ↩

  4. 戻り値なしと戻り値ありを想定し関数型インターフェースを導入したので、大分コードが汚くなってしまいました。可読性を向上させる方法などございましたら、教えていただけるとありがたいです。 ↩

  5. あくまでも明示するだけなので、実際にはnullなVoidオブジェクトが返されます。 ↩

  6. ここではMatrixの頭文字として使っています。 ↩

  7. 条件と一致しないときにnull以外を返してしまうと、必ずそのオブジェクトが返されてしまいます。 ↩

  8. runnerフィールドとsupplierフィールドについては可変性を想定しているので、完全な不変クラスではありません。 ↩

0
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?