2 /***************************************************************************
3 * Copyright (C) 2003-2008 Polytechnique.org *
4 * http://opensource.polytechnique.org/ *
6 * This program is free software; you can redistribute it and/or modify *
7 * it under the terms of the GNU General Public License as published by *
8 * the Free Software Foundation; either version 2 of the License, or *
9 * (at your option) any later version. *
11 * This program is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14 * GNU General Public License for more details. *
16 * You should have received a copy of the GNU General Public License *
17 * along with this program; if not, write to the Free Software *
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
20 ***************************************************************************/
22 /** Implements a heap. The order of the elements is determined by the given
23 * comparator: the smaller element is the head of the heap.
28 private $content = array();
30 public function __construct($comparator)
32 $this->comparator
= $comparator;
37 if (empty($this->content
)) {
40 return array_shift($this->content
);
43 public function push($elt)
46 $end = count($this->content
);
48 while ($start < $end) {
49 $middle = floor(($start +
$end) / 2);
50 $comp = call_user_func($this->comparator
, $elt, $this->content
[$middle]);
53 } else if ($comp > 0) {
56 array_splice($this->content
, $middle, 0, array($elt));
60 array_splice($this->content
, $start, 0, array($elt));
63 public function count()
65 return count($this->content
);
68 public function iterator()
70 return PlIterator
::fromArray($this->content
);
74 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: