石頭閒語:Stack - Example for Operators of Array Overload

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:

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();
}
?>

呵~專案剛結案, 比較閒來和您以文會友~
您這個 Stack 範例存在有 memory leak 的問題.
而 Stack 範例剛好又在 Effective Java Programming Language Guide (Item 5: Eliminate obsolete object references) 有提到且很常發生.
在 PHP 其實問題不會很嚴重, 因為 PHP 目前並沒有 Application Server, 也就是物件不會被永續存在, 在每一次的 request 結束後, 問題也就消失了.

不過還是來探討一下:
如果這個 Stack 成長後縮小, 也就是假設 push 到 5 個, 而 pop 出 2 個, $this->table 依然還是暫有 5 個的記憶體, 因為被 popped off 的物件不會被回收, 即使它也將不會再被引用到
改成即可解決此問題:
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');
}

喔，那不是 memory leak，而是我的設計。

其實按 PHP 的陣列用法，我大可不指定 size ，反正可以隨時增加或縮減。但我給了 size ，我的意思就是要一個固定大小的 stack。隱含的效率意義是: 我就是要這麼大的stack放在那裡，系統不用管理這塊記憶體。

更正。剛剛回應太快，以為是指陣列大小的事。

我剛瞄了一下 pop() ，發現我還真的漏掉 unset 了。我明明記得我有寫...
嗯，一定是我在改的時候，不小心改錯了 (遠目

ps.回傳 reference 比較快，免得 copy object 兩次。
$r = $table[$sp] // copy 1
return $r // copy 2

姓名 :
Email :
URL :
回應狀態:	公開私密
驗證碼 :	( 請依顯示文字填入 ) 重新產生驗證碼
	記住我的資訊顯示我的圖像 ( 登入或申請個人圖像 )
回應內容 :

石頭閒語

2007年06月27日

Stack - Example for Operators of Array Overload

Stack.php

StackTest.php

引用URL