この記事は GMOアドマーケティング Advent Calendar 2023 15日目の記事です。

GMOアドマーケティングのT.Nです。

最近弊社の一部のプロダクトのJavaを、Java 21にバージョンアップしました。
Java 21でリリースされたSequenced Collectionsのreversedが気になったので、
実装について調べてみました。

Sequenced Collectionsとは

まずはSequenced Collectionsについてです。
JEP 431(https://openjdk.org/jeps/431)で以下のインターフェースが新しく追加されました。

SequencedCollection
SequencedSet
SequencedMap

IntelliJのDiagramsでクラス図を生成し、以前のバージョンと比較しました。
左がJava 21で、右がJava 20です。
(各インターフェースの例を一つずつ記載していますが、実装されているクラスは他にもあります。)

ArrayList(SequencedCollection)

ListとCollectionの間にSequencedCollectionが入っています。

LinkedHashSet(SequencedSet)

LinkedHashSetとCollectionの間にSequencedSetとSequencedCollectionが入っています。
SequencedSetはSetもextendsしています。

LinkedHashMap(SequencedMap)

LinkedHashMapとMapの間にSequencedMapが入っています。

Sequenced Collectionsの使い方

追加されたインターフェースにより、以下のような処理を行えるようになりました。

ArrayListの場合

List<Integer> list = Stream.of(1, 2, 3).collect(Collectors.toList());

// [0, 1, 2, 3]
list.addFirst(0);

// [0, 1, 2, 3, 4]
list.addLast(4);

// [1, 2, 3, 4]
list.removeFirst();

// [1, 2, 3]
list.removeLast();

// [3, 2, 1]
List<Integer> reversed = list.reversed();

List<Integer> list = Stream.of(1, 2, 3).collect(Collectors.toList());

// [0, 1, 2, 3]

list.addFirst(0);

// [0, 1, 2, 3, 4]

list.addLast(4);

// [1, 2, 3, 4]

list.removeFirst();

// [1, 2, 3]

list.removeLast();

// [3, 2, 1]

List<Integer> reversed = list.reversed();

LinkedHashSetの場合

LinkedHashSet<Integer> set = Stream.of(1, 2, 3)
                    .collect(Collectors.toCollection(LinkedHashSet::new));

// [0, 1, 2, 3]
set.addFirst(0);

// [0, 1, 2, 3, 4]
set.addLast(4);

// [1, 2, 3, 4]
set.removeFirst();

// [1, 2, 3]
set.removeLast();

// [3, 2, 1]
SequencedSet<Integer> reversed = set.reversed();

LinkedHashSet<Integer> set = Stream.of(1, 2, 3)

.collect(Collectors.toCollection(LinkedHashSet::new));

// [0, 1, 2, 3]

set.addFirst(0);

// [0, 1, 2, 3, 4]

set.addLast(4);

// [1, 2, 3, 4]

set.removeFirst();

// [1, 2, 3]

set.removeLast();

// [3, 2, 1]

SequencedSet<Integer> reversed = set.reversed();

LinkedHashMapの場合

LinkedHashMap<Integer, Integer> map = Stream.of(1, 2, 3)
                    .collect(Collectors.toMap(x -> x, x -> x, (x, y) -> x, LinkedHashMap::new));

// {0=0, 1=1, 2=2, 3=3}
map.putFirst(0, 0);

// {0=0, 1=1, 2=2, 3=3, 4=4}
map.putLast(4, 4);

// {1=1, 2=2, 3=3, 4=4}
map.pollFirstEntry();

// {1=1, 2=2, 3=3}
map.pollLastEntry();

// {3=3, 2=2, 1=1}
SequencedMap<Integer, Integer> reversed = map.reversed();

// [1, 2, 3]
SequencedSet<Integer> keySet = map.sequencedKeySet();

// [1, 2, 3]
SequencedCollection<Integer> values = map.sequencedValues();

// [1=1, 2=2, 3=3]
SequencedSet<Map.Entry<Integer, Integer>> entrySet = map.sequencedEntrySet();

LinkedHashMap<Integer, Integer> map = Stream.of(1, 2, 3)

.collect(Collectors.toMap(x -> x, x -> x, (x, y) -> x, LinkedHashMap::new));

// {0=0, 1=1, 2=2, 3=3}

map.putFirst(0, 0);

// {0=0, 1=1, 2=2, 3=3, 4=4}

map.putLast(4, 4);

// {1=1, 2=2, 3=3, 4=4}

map.pollFirstEntry();

// {1=1, 2=2, 3=3}

map.pollLastEntry();

// {3=3, 2=2, 1=1}

SequencedMap<Integer, Integer> reversed = map.reversed();

// [1, 2, 3]

SequencedSet<Integer> keySet = map.sequencedKeySet();

// [1, 2, 3]

SequencedCollection<Integer> values = map.sequencedValues();

// [1=1, 2=2, 3=3]

SequencedSet<Map.Entry<Integer, Integer>> entrySet = map.sequencedEntrySet();

reversedの実装について

ここからが実装についてです。
今回はListのreversedの実装について調べました。

reversedはListインターフェースに定義されています。
デフォルト実装では、ReverseOrderListViewというクラスを返すようになっています。

public interface List<E> extends SequencedCollection<E> {
    default List<E> reversed() {
        return ReverseOrderListView.of(this, true); // we must assume it's modifiable
    }
}

public interface List<E> extends SequencedCollection<E> {

default List<E> reversed() {

return ReverseOrderListView.of(this, true); // we must assume it's modifiable

}

上の処理で実行しているReverseOrderListViewのofメソッドは以下のようになっています。

class ReverseOrderListView<E> implements List<E> {

    final List<E> base;
    final boolean modifiable;

    public static <T> List<T> of(List<T> list, boolean modifiable) {
        if (list instanceof ReverseOrderListView<T> rolv) {
            return rolv.base;
        } else if (list instanceof RandomAccess) {
            return new ReverseOrderListView.Rand<>(list, modifiable);
        } else {
            return new ReverseOrderListView<>(list, modifiable);
        }
    }
}

class ReverseOrderListView<E> implements List<E> {

final List<E> base;

final boolean modifiable;

public static <T> List<T> of(List<T> list, boolean modifiable) {

if (list instanceof ReverseOrderListView<T> rolv) {

return rolv.base;

} else if (list instanceof RandomAccess) {

return new ReverseOrderListView.Rand<>(list, modifiable);

} else {

return new ReverseOrderListView<>(list, modifiable);

}

ofの一つ目の引数が対象のListで、二つ目の引数が変更可能であるかを表す変数です。
ImmutableCollectionsなどでは二つ目の引数にfalseが渡されています。
modifiableがfalseの場合は変更しようとすると例外が発生します。

一つ目の引数のListの種類に応じて返すクラスを変えています。
既にReverseOrderListViewのインスタンスの場合はフィールドのListを返しています。
この場合はreverseのreverseなので、元のListをそのまま返しているようです。

それ以外の場合は、RandomAccessのListであるかを判定して返すクラスを変えています。
ReverseOrderListView.Randの方は、RandomAccessを実装しています。

static class Rand<E> extends ReverseOrderListView<E> implements RandomAccess {
    Rand(List<E> list, boolean modifiable) {
        super(list, modifiable);
    }
}

static class Rand<E> extends ReverseOrderListView<E> implements RandomAccess {

Rand(List<E> list, boolean modifiable) {

super(list, modifiable);

}

Listを逆順にする処理は、DescendingIteratorというクラスで行われています。
ReverseOrderListViewのiteratorメソッドでDescendingIteratorを返しています。

public Iterator<E> iterator() {
    return new DescendingIterator();
}

public Iterator<E> iterator() {

return new DescendingIterator();

}

DescendingIteratorは以下のようになっています。

class DescendingIterator implements Iterator<E> {
    final ListIterator<E> it = base.listIterator(base.size());
    public boolean hasNext() { return it.hasPrevious(); }
    public E next() { return it.previous(); }
    public void remove() {
        checkModifiable();
        it.remove();
        // TODO - make sure ListIterator is positioned correctly afterward
    }
}

class DescendingIterator implements Iterator<E> {

final ListIterator<E> it = base.listIterator(base.size());

public boolean hasNext() { return it.hasPrevious(); }

public E next() { return it.previous(); }

public void remove() {

checkModifiable();

it.remove();

// TODO - make sure ListIterator is positioned correctly afterward

}

元のListをListIteratorに変換してフィールドで保持しています。

hasNextでhasPrevious、nextでpreviousを実行することで、
逆順のイテレーションを実現しているようです。

ちなみに、ReverseOrderListViewのaddメソッドは、
Listの先頭に要素を追加するようになっています。
先頭に追加することで、逆になったListの最後に追加する動作を実現しています。

public boolean add(E e) {
    checkModifiable();
    base.add(0, e);
    return true;
}

public boolean add(E e) {

checkModifiable();

base.add(0, e);

return true;

}

その他のListを操作するメソッドも、indexを反転させて処理しています。

public void add(int index, E element) {
    checkModifiable();
    int size = base.size();
    checkClosedRange(index, size);
    base.add(size - index, element);
}

public void add(int index, E element) {

checkModifiable();

int size = base.size();

checkClosedRange(index, size);

base.add(size - index, element);

}

まとめ

今回はSequenced Collectionについての簡単な説明と、
reversedの実装についての記事でした。

明日はK.Mさんによる「VSCodeでプロジェクトを開くとき、ついでにいろいろやる方法」です。

引き続き、GMOアドマーケティング Advent Calendar 2023 をお楽しみください！

■採用ページはこちら！
https://recruit.gmo-ap.jp/

■GMOアドパートナーズ公式noteはこちら！
https://note.gmo-ap.jp/

T.N

Sequenced Collectionsとは

ArrayList(SequencedCollection)

LinkedHashSet(SequencedSet)

LinkedHashMap(SequencedMap)

Sequenced Collectionsの使い方

ArrayListの場合

LinkedHashSetの場合

LinkedHashMapの場合

reversedの実装について

まとめ

おすすめ

Railsのタグ機能でN+1問題解消

Professional Scrum Master ⅠとⅡに合格しました

background-imageを活用して、アップする画像を1個で済ませたい