SplPriorityQueue を継承したらちょっと複雑なPriorityQueueが実装したりできるのですが、なんかたまにうまく動かないことがあります。

正常に動く例: 長方形を面積が大きい順に並べる

SplPriorityQueue を継承して、 insertRectangle というメソッドで面積を計算してinsertします。

<?php

/** 長方形クラス */
class Rectangle {
    public $width, $height;
    public function __construct($width, $height) {
        $this->width = $width;
        $this->height = $height;
    }
}

/** Priority Queue */
class MyPriorityQueue extends SplPriorityQueue {

    /** 面積を計算してそれを優先度としてinsertするメソッド */
    public function insertRectangle(Rectangle $rectangle) {
        // 面積をpriorityに突っ込む
        $this->insert($rectangle, $rectangle->width * $rectangle->height);
    }
}

$queue = new MyPriorityQueue();

// 長方形を突っ込む
$queue->insertRectangle(new Rectangle(2, 4));
$queue->insertRectangle(new Rectangle(3, 3));
$queue->insertRectangle(new Rectangle(1, 7));

// 面積が大きい順に取り出される筈
while(!$queue->isEmpty()) {
    var_dump($queue->extract());
}

これを実行すると

$ php PriorityQueue3.php                                                                                                                                                                                                                      [master]
object(Rectangle)#3 (2) {
  ["width"]=>
  int(3)
  ["height"]=>
  int(3)
}
object(Rectangle)#2 (2) {
  ["width"]=>
  int(2)
  ["height"]=>
  int(4)
}
object(Rectangle)#4 (2) {
  ["width"]=>
  int(1)
  ["height"]=>
  int(7)
}

ちゃんと面積が大きい順に出てきますね。

正常に動かない例: 長方形を面積が小さい順に並べる

今度は面積が小さい順にするためにcompareメソッドをオーバーライドします。

/** Priority Queue */
class MyPriorityQueue extends SplPriorityQueue {
    /** priorityが低いものから取り出すようにする */
    public function compare($priority1, $priority2) {
        if($priority1 === $priority2) return 0;
        $priority1 < $priority2 ? -1 : 1;
    }

    /** 面積を計算してそれを優先度としてinsertするメソッド */
    public function insertRectangle(Rectangle $rectangle) {
        // 面積をpriorityに突っ込む
        $this->insert($rectangle, $rectangle->width * $rectangle->height);
    }
}

このようにします。これで

// 長方形を突っ込む
$queue->insertRectangle(new Rectangle(2, 4));
$queue->insertRectangle(new Rectangle(3, 3));
$queue->insertRectangle(new Rectangle(1, 7));

こうすると

$ php PriorityQueue3.php                                                                                                                                                                                                                      [master]
object(Rectangle)#2 (2) {
  ["width"]=>
  int(2)
  ["height"]=>
  int(4)
}
object(Rectangle)#4 (2) {
  ["width"]=>
  int(1)
  ["height"]=>
  int(7)
}
object(Rectangle)#3 (2) {
  ["width"]=>
  int(3)
  ["height"]=>
  int(3)
}

面積が小さい順にソートされず、かといって入れた順とも違う順で出てきてしまいます。

んー、何か継承して複数メソッドをオーバーライドするとバグるのか、継承の仕方とかが良くないのか。PHPの闇な感じがあります。もし何か実装ミスとかに気づいた人がいたら教えてほしいです。