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 で使うときには、こういった複雑な挙動を示しますので、十分な注意が必要です。