classes/plheap.php

   1 <?php
   2 /***************************************************************************
   3  *  Copyright (C) 2003-2011 Polytechnique.org                              *
   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     {
  70         return PlIteratorUtils::fromArray($this->content, 1, true);
  71     }
  72 }
  73
  74 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker fenc=utf-8:
  75 ?>