Commit | Line | Data |
---|---|---|
5177a1b5 FB |
1 | <?php |
2 | /*************************************************************************** | |
e92ecb8c | 3 | * Copyright (C) 2003-2011 Polytechnique.org * |
5177a1b5 FB |
4 | * http://opensource.polytechnique.org/ * |
5 | * * | |
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. * | |
10 | * * | |
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. * | |
15 | * * | |
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 * | |
18 | * Foundation, Inc., * | |
19 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * | |
20 | ***************************************************************************/ | |
21 | ||
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. | |
24 | */ | |
25 | class PlHeap | |
26 | { | |
27 | private $comparator; | |
28 | private $content = array(); | |
29 | ||
30 | public function __construct($comparator) | |
31 | { | |
32 | $this->comparator = $comparator; | |
33 | } | |
34 | ||
35 | public function pop() | |
36 | { | |
37 | if (empty($this->content)) { | |
38 | return null; | |
39 | } | |
40 | return array_shift($this->content); | |
41 | } | |
42 | ||
43 | public function push($elt) | |
44 | { | |
45 | $start = 0; | |
46 | $end = count($this->content); | |
47 | ||
48 | while ($start < $end) { | |
49 | $middle = floor(($start + $end) / 2); | |
50 | $comp = call_user_func($this->comparator, $elt, $this->content[$middle]); | |
51 | if ($comp < 0) { | |
52 | $end = $middle; | |
53 | } else if ($comp > 0) { | |
54 | $start = $middle + 1; | |
55 | } else { | |
56 | array_splice($this->content, $middle, 0, array($elt)); | |
57 | return; | |
58 | } | |
59 | } | |
60 | array_splice($this->content, $start, 0, array($elt)); | |
61 | } | |
62 | ||
63 | public function count() | |
64 | { | |
65 | return count($this->content); | |
66 | } | |
67 | ||
68 | public function iterator() | |
69 | { | |
446937ee | 70 | return PlIteratorUtils::fromArray($this->content, 1, true); |
5177a1b5 FB |
71 | } |
72 | } | |
73 | ||
74 | // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: | |
75 | ?> |