読者です 読者をやめる 読者になる 読者になる

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

SplDoublyLinkedList を LIFO で使うときの注意点

前回の記事の最後に書いたように、PHP の SplDoublyLinkedList を LIFO で使う場合には、いくつか注意しなければいけない挙動があります。

一つ目は、イテレータのキーについてです。まずは FIFO の場合について、以下のようなコードで確認してみます。各要素の値に 100 を加えているのはキーと区別しやすくするためで、特に意味はありません。

<?php

$list = new SplDoublyLinkedList();

for ($i = 0; $i < 5; ++$i) {
    $list->push($i + 100);
}

foreach ($list as $k => $v) {
    print "$k => $v\n";
}

実行すると、このようになります。ごく普通の結果です。

$ php fifo_iterator.php
0 => 100
1 => 101
2 => 102
3 => 103
4 => 104

同じことを LIFO で書いてみます。

<?php

$list = new SplDoublyLinkedList();
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);

for ($i = 0; $i < 5; ++$i) {
    $list->push($i + 100);
}

foreach ($list as $k => $v) {
    print "$k => $v\n";
}

実行するとこのようになります。

$ php lifo_iterator.php
4 => 104
3 => 103
2 => 102
1 => 101
0 => 100

キーが降順になってしまいました。setIteratorMode に LIFO を指定することで、イテレータはリストの末尾から先頭に向かって進むようになるのですが、キーの値はリストの先頭から振られます。これは foreach を使った場合に限らず、以下のように手動でイテレータを回して key() メソッドを用いた場合でも同じです。

<?php

for ($list->rewind(); $list->valid(); $list->next()) {
    print $list->key() . " => " . $list->current() . "\n";
}

この挙動が厄介なのは、ArrayAccess のメソッド群と整合性が取れなくなってしまうためです。以下のコードで確認してみます。

<?php

foreach ($list as $k => $v) {
    print "\$k = $k, \$v = $v, \$list[$k] = $list[$k]\n";
}

こうなります。

$ php lifo_iterator_and_arrayaccess.php
$k = 4, $v = 104, $list[4] = 100
$k = 3, $v = 103, $list[3] = 101
$k = 2, $v = 102, $list[2] = 102
$k = 1, $v = 101, $list[1] = 103
$k = 0, $v = 100, $list[0] = 104

二つ目は、add メソッドについてです。add メソッドはリストの途中に要素を追加するメソッドです。これは、まだマニュアルの更新が追いついていないようですが、PHP 5.5.0 で導入されています。
PHP: PHP 5 ChangeLog

まず、FIFO の場合で add メソッドの使い方を示します。といっても、特に難しいことはありません。add($index, $value) で、$index の場所に $value を挿入します。下記のコードでは、先頭、途中、末尾にそれぞれ追加しています。

<?php

$list = new SplDoublyLinkedList();

for ($i = 0; $i < 5; ++$i) {
    $list->push($i + 100);
}

$list->add(0, 1000);
$list->add(3, 2000);
$list->add($list->count(), 3000);

foreach ($list as $k => $v) {
    print "$k => $v\n";
}

実行すると以下のようになります。特におかしなことはありません。

$ php fifo_add.php
0 => 1000
1 => 100
2 => 101
3 => 2000
4 => 102
5 => 103
6 => 104
7 => 3000

それでは LIFO で同じように書いてみます。

<?php

$list = new SplDoublyLinkedList();
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);

for ($i = 0; $i < 5; ++$i) {
    $list->push($i + 100);
}

$list->add(0, 1000);
$list->add(3, 2000);
$list->add($list->count(), 3000);

foreach ($list as $k => $v) {
    print "$k => $v\n";
}

実行結果は以下のとおりです。何が起きているか分かるでしょうか。

$ php lifo_add.php
7 => 3000
6 => 104
5 => 1000
4 => 103
3 => 102
2 => 2000
1 => 101
0 => 100

以下のように書き換えてステップごとに詳細を出力させてみます。

<?php

$list = new SplDoublyLinkedList();
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);

for ($i = 0; $i < 5; ++$i) {
    $list->push($i + 100);
}

for ($i = 0; $i < $list->count(); ++$i) print "$i:$list[$i] "; print "\n";

$list->add(0, 1000);
for ($i = 0; $i < $list->count(); ++$i) print "$i:$list[$i] "; print "\n";

$list->add(3, 2000);
for ($i = 0; $i < $list->count(); ++$i) print "$i:$list[$i] "; print "\n";

$list->add($list->count(), 3000);
for ($i = 0; $i < $list->count(); ++$i) print "$i:$list[$i] "; print "\n";

$ php lifo_add_detail.php
0:104 1:103 2:102 3:101 4:100
0:104 1:1000 2:103 3:102 4:101 5:100
0:104 1:1000 2:103 3:102 4:2000 5:101 6:100
0:3000 1:104 2:1000 3:103 4:102 5:2000 6:101 7:100

最初は 5 要素のリストです。このリストに対して $list->add(0, 1000) が実行されます。add メソッドは、LIFO の場合には指定されたインデックスの次に要素を追加します。つまり、あくまでも FIFO として見たときの手前側に追加するという動作になっています。したがって、次の $list->add(3, 2000) の実行後は、3:102 の後ろに 4:2000 が追加された状態になります。

最後の $list->add($list->count(), 3000) はまったく意味不明だと思いますが、add メソッドは、指定されたインデックスが count() に等しい場合には、それが FIFO であっても LIFO であっても、push($value) します*1

SplDoublyLinkedList を IT_MODE_LIFO で使うときには、こういった複雑な挙動を示しますので、十分な注意が必要です。

*1:この挙動により、結果的には LIFO であっても先頭、末尾を含む任意の場所に要素を追加することができるわけですが。