ut/heaptest.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 require_once dirname(__FILE__) . '/../include/test.inc.php';
  23
  24 class HeapTest extends PlTestCase
  25 {
  26     public static function compare($a, $b)
  27     {
  28         return $a - $b;
  29     }
  30
  31     public function testHeap()
  32     {
  33         $heap = new PlHeap(array('HeapTest', 'compare'));
  34         $this->assertSame(0, $heap->count());
  35         $this->assertNull($heap->pop());
  36
  37         $heap->push(1);
  38         $this->assertSame(1, $heap->count());
  39         $this->assertSame(1, $heap->pop());
  40         $this->assertSame(0, $heap->count());
  41         $this->assertNull($heap->pop());
  42
  43         $heap->push(2);
  44         $heap->push(1);
  45         $heap->push(4);
  46         $heap->push(3);
  47         $this->assertSame(4, $heap->count());
  48         $this->assertSame(1, $heap->pop());
  49         $this->assertSame(3, $heap->count());
  50         $this->assertSame(2, $heap->pop());
  51         $this->assertSame(2, $heap->count());
  52         $heap->push(-1);
  53         $this->assertSame(3, $heap->count());
  54         $this->assertSame(-1, $heap->pop());
  55         $this->assertSame(2, $heap->count());
  56         $this->assertSame(3, $heap->pop());
  57         $this->assertSame(1, $heap->count());
  58         $this->assertSame(4, $heap->pop());
  59         $this->assertSame(0, $heap->count());
  60         $this->assertNull($heap->pop());
  61     }
  62
  63     public function testHeapIt()
  64     {
  65         $heap = new PlHeap(array('HeapTest', 'compare'));
  66         $heap->push(2);
  67         $heap->push(1);
  68         $heap->push(4);
  69         $heap->push(3);
  70
  71         $it = $heap->iterator();
  72         $this->assertSame(4, $it->total());
  73
  74         $this->assertSame(1, $it->next());
  75         $this->assertTrue($it->first());
  76         $this->assertFalse($it->last());
  77
  78         $this->assertSame(2, $it->next());
  79         $this->assertFalse($it->first());
  80         $this->assertFalse($it->last());
  81
  82         $this->assertSame(3, $it->next());
  83         $this->assertFalse($it->first());
  84         $this->assertFalse($it->last());
  85
  86         $this->assertSame(4, $it->next());
  87         $this->assertFalse($it->first());
  88         $this->assertTrue($it->last());
  89
  90         $this->assertNull($it->next());
  91         $this->assertSame(4, $heap->count());
  92     }
  93
  94     public function testMergeSortedIterator()
  95     {
  96         $its = array();
  97         $its[] = PlIteratorUtils::fromArray(array(2, 4, 8, 16), 1, true);
  98         $its[] = PlIteratorUtils::fromArray(array(3, 9, 27), 1, true);
  99         $its[] = PlIteratorUtils::fromArray(array(4, 16, 32), 1, true);
 100         $it = PlIteratorUtils::merge($its, array('HeapTest', 'compare'));
 101         $this->assertSame(10, $it->total());
 102
 103         $this->assertSame(2, $it->next());
 104         $this->assertTrue($it->first());
 105         $this->assertFalse($it->last());
 106
 107         $this->assertSame(3, $it->next());
 108         $this->assertFalse($it->first());
 109         $this->assertFalse($it->last());
 110
 111         $this->assertSame(4, $it->next());
 112         $this->assertFalse($it->first());
 113         $this->assertFalse($it->last());
 114
 115         $this->assertSame(4, $it->next());
 116         $this->assertFalse($it->first());
 117         $this->assertFalse($it->last());
 118
 119         $this->assertSame(8, $it->next());
 120         $this->assertFalse($it->first());
 121         $this->assertFalse($it->last());
 122
 123         $this->assertSame(9, $it->next());
 124         $this->assertFalse($it->first());
 125         $this->assertFalse($it->last());
 126
 127         $this->assertSame(16, $it->next());
 128         $this->assertFalse($it->first());
 129         $this->assertFalse($it->last());
 130
 131         $this->assertSame(16, $it->next());
 132         $this->assertFalse($it->first());
 133         $this->assertFalse($it->last());
 134
 135         $this->assertSame(27, $it->next());
 136         $this->assertFalse($it->first());
 137         $this->assertFalse($it->last());
 138
 139         $this->assertSame(32, $it->next());
 140         $this->assertFalse($it->first());
 141         $this->assertTrue($it->last());
 142
 143         $this->assertNull($it->next());
 144     }
 145
 146     public function testMergeUnsortedIterator()
 147     {
 148         $its = array();
 149         $its[] = PlIteratorUtils::fromArray(array(8, 4, 16, 2), 1, true);
 150         $its[] = PlIteratorUtils::fromArray(array(3, 27, 9), 1, true);
 151         $its[] = PlIteratorUtils::fromArray(array(32, 4, 16), 1, true);
 152         $it = PlIteratorUtils::merge($its, array('HeapTest', 'compare'), false);
 153         $this->assertSame(10, $it->total());
 154
 155         $this->assertSame(2, $it->next());
 156         $this->assertTrue($it->first());
 157         $this->assertFalse($it->last());
 158
 159         $this->assertSame(3, $it->next());
 160         $this->assertFalse($it->first());
 161         $this->assertFalse($it->last());
 162
 163         $this->assertSame(4, $it->next());
 164         $this->assertFalse($it->first());
 165         $this->assertFalse($it->last());
 166
 167         $this->assertSame(4, $it->next());
 168         $this->assertFalse($it->first());
 169         $this->assertFalse($it->last());
 170
 171         $this->assertSame(8, $it->next());
 172         $this->assertFalse($it->first());
 173         $this->assertFalse($it->last());
 174
 175         $this->assertSame(9, $it->next());
 176         $this->assertFalse($it->first());
 177         $this->assertFalse($it->last());
 178
 179         $this->assertSame(16, $it->next());
 180         $this->assertFalse($it->first());
 181         $this->assertFalse($it->last());
 182
 183         $this->assertSame(16, $it->next());
 184         $this->assertFalse($it->first());
 185         $this->assertFalse($it->last());
 186
 187         $this->assertSame(27, $it->next());
 188         $this->assertFalse($it->first());
 189         $this->assertFalse($it->last());
 190
 191         $this->assertSame(32, $it->next());
 192         $this->assertFalse($it->first());
 193         $this->assertTrue($it->last());
 194
 195         $this->assertNull($it->next());
 196     }
 197
 198 }
 199
 200
 201 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8:
 202 ?>