6月
27
2007
分類:
最近更新:
2007-06-27
Stack - Example for Operators of Array Overload
實作一個 Stack 。具備下列特性:
- 後進先出。
- 順序走訪時,同樣按後進先出原則走訪。亦即由後往前走訪。
- 可用索引運算子
[]
窺探 Stack 的內容。 - 不允許用索引運算子改變 Stack 的內容。
本文之示範直接實作 Iterator, ArrayAccess, Countable 三個介面,而不繼承 ArrayIterator
等類別。ArrayIterator 類具有 sort() 等方法,但我並不打算對 Stack 進行排序,故我不繼承。若我繼承 ArrayIterator ,則我必須覆寫 sort 等方法,無此必要。
Stack.php
<?php
/**
* interface Iterator: +current(), +key(), +next(), +rewind(), +valid()
*
* interface ArrayAccess: +offsetExists(), +offsetGet(), +offsetSet(),
* +offsetUnset()
*
* interface Countable: +count()
*
* interface SeekableIterator: +seek()
*/
class Stack
implements Iterator, ArrayAccess, Countable
{
protected $size;
protected $table;
protected $sp;
protected $tp; //traval point
public function __construct($size) {
$this->size = $size;
for ($i = 0; $i < $size; ++$i)
$this->table[$i] = null;
$this->sp = $this->tp = 0;
}
/**
* Stack's method
* Note: I don't know how to overload empty().
*/
public function isEmpty() {
return ($this->sp <= 0);
}
/**
* Stack's method
* @return Top point of stack.
*/
public function push($value) {
if ($this->sp < $this->size) {
$this->table[$this->sp++] = $value;
return $this->sp;
}
else
throw new Exception('stack is full!');
}
/**
* Stack's method
*/
public function &pop() {
if ($this->sp > 0) {
$result = $this->table[--$this->sp];
unset($this->table[$this->sp]);
return $result;
}
else
throw new Exception('stack is empty');
}
/**
* implements methods of interface Countable.
* overload count()/hook into count()
* @return how many elements are pushed in the stack.
*/
public function count() {
return $this->sp;
}
/**
* implements methods of interface ArrayAccess.
*/
/**
* It means: $array[$index] = $v
*/
public function offsetSet($index, $v) {
throw new Exception('peak-only!');
return $this->table[$index] = $v;
}
/**
* It means: $v = $array[$index]
*/
public function offsetGet($index) {
/*if ($index > $this->sp or $index < 0)
throw new Exception('out of range');*/
return $this->table[$index];
}
/**
* It means: isset($array[$index])
*/
public function offsetExists($index) {
return ($this->table[$index] != null);
}
/**
* It means: unset($array[$index])
*/
public function offsetUnset($index) {
throw new Exception('peak-only!');
$this->table[$index] = null;
return $this;
}
/**
* implements methods of interface Iterator.
*/
public function current() {
return $this->table[$this->tp];
}
public function key() {
return $this->tp;
}
public function next() {
--$this->tp;
/*document said void, but I return self.*/
return $this;
}
public function rewind() {
$this->tp = $this->sp - 1;
return $this;
}
public function valid() {
return ($this->tp >= 0);
}
}
?>
Example:
<?php
require 'Stack.php';
$s = new Stack(10);
$s->push('apple');
$s->push('orange');
echo "There are ", count($s), " elements in stack\n";
foreach ($s as $i => $v) {
echo "stack[ $i ] is $v\n";
}
echo $s[0], "\n"; //peak the value of first element in stack.
?>
StackTest.php
<?php
if (!defined("PHPUnit_MAIN_METHOD")) {
define("PHPUnit_MAIN_METHOD", "StackTest::main");
}
require_once "PHPUnit/Framework/TestCase.php";
require_once "PHPUnit/Framework/TestSuite.php";
require_once 'Stack.php';
/**
* Test class for Stack.
* Generated by PHPUnit_Util_Skeleton on 2007-06-26 at 09:19:57.
*/
class StackTest extends PHPUnit_Framework_TestCase {
/**
* Runs the test methods of this class.
*
* @access public
* @static
*/
public static function main() {
require_once "PHPUnit/TextUI/TestRunner.php";
$suite = new PHPUnit_Framework_TestSuite("StackTest");
$result = PHPUnit_TextUI_TestRunner::run($suite);
}
/**
* Sets up the fixture, for example, open a network connection.
* This method is called before a test is executed.
*
* @access protected
*/
protected function setUp() {
$this->size = 10;
$this->q = new Stack($this->size);
}
/**
* @todo Implement testIsEmpty().
*/
public function testIsEmpty() {
$this->assertTrue($this->q->isEmpty());
}
/**
* @todo Implement testPush().
*/
public function testPush() {
for ($i = 0; $i < $this->size; ++$i) {
$this->assertEquals($i+1, $this->q->push( 100 ));
}
try {
$this->q->push('FULL');
}
catch (Exception $expected) {
return;
}
$this->fail('An expected Exception has not been raised.');
}
/**
* @todo Implement testPop().
*/
public function testPop() {
$this->q->push(100);
$this->q->push(200);
$this->assertEquals(200, $this->q->pop());
$this->assertEquals(100, $this->q->pop());
$this->assertTrue($this->q->isEmpty());
try {
$this->q->pop();
}
catch (Exception $expected) {
return;
}
$this->fail('An expected Exception has not been raised.');
}
/**
* @todo Implement testCount().
*/
public function testCount() {
$this->assertEquals(0, $this->q->count());
$this->assertEquals(0, count($this->q));
$this->q->push(100);
$this->assertEquals(1, count($this->q));
$this->q->pop();
$this->assertEquals(0, count($this->q));
}
/**
* @todo Implement testCurrent().
*/
public function testCurrent() {
$this->assertNull($this->q->current());
}
/**
* @todo Implement testKey().
*/
public function testKey() {
$this->assertEquals(0, $this->q->key());
}
/**
* @todo Implement testRewind().
*/
public function testRewind() {
$this->q->push(100);
$this->q->rewind();
$this->assertEquals(0, $this->q->key());
$this->assertEquals(100, $this->q->current());
}
/**
* @todo Implement testValid().
*/
public function testValid() {
$this->assertTrue($this->q->valid());
while ($this->q->valid()) {
$this->q->next();
}
$this->assertFalse($this->q->valid());
}
/**
* @todo Implement testOffsetSet().
*/
public function testOffsetSet() {
try {
$this->q->offsetSet(0, 100);
$this->q[0] = 100;
}
catch (Exception $expected) {
return;
}
$this->fail('An expected Exception has not been raised.');
}
/**
* @todo Implement testOffsetGet().
*/
public function testOffsetGet() {
$this->q->push(100);
$this->assertEquals(100, $this->q->offsetGet(0));
$this->q->push(200);
$this->assertEquals(200, $this->q[1]);
}
/**
* @todo Implement testOffsetExists().
*/
public function testOffsetExists() {
$this->assertFalse($this->q->offsetExists(0));
$this->assertFalse(isset($this->q[0]));
$this->q->push(100);
$this->assertTrue($this->q->offsetExists(0));
$this->assertTrue(isset($this->q[0]));
}
/**
* @todo Implement testOffsetUnset().
*/
public function testOffsetUnset() {
try {
$this->q->offsetUnset(0);
unset($this->q[0]);
}
catch (Exception $expected) {
return;
}
$this->fail('An expected Exception has not been raised.');
}
/**
* test foreach
*/
public function testForeach() {
$testArray = array('black', 'blue', 'red', 'green', 'white');
for ($i = 0; $i < count($testArray); ++$i) {
$this->assertEquals($i+1, $this->q->push($testArray[$i]));
$this->assertEquals($testArray[$i], $this->q[$i]);
}
$this->assertEquals(count($testArray), count($this->q));
$i = count($testArray) - 1;
foreach ($this->q as $k => $v) {
$this->assertEquals($i, $k);
$this->assertEquals($testArray[$i], $v);
--$i;
//echo "$k = $v\n";
}
$this->assertEquals(-1, $i);
$this->assertFalse($this->q->isEmpty());
}
}
if (PHPUnit_MAIN_METHOD == "StackTest::main") {
StackTest::main();
}
?>
樂多舊網址: http://blog.roodo.com/rocksaying/archives/3542135.html
樂多舊回應