MFH: -Pointer doesn't move if we're moving forward and shifting at the same time

-Userland implementation
-Doxygen doc

5 files changed, 259 insertions, 47 deletions

diff --git a/ext/spl/internal/spldoublylinkedlist.inc b/ext/spl/internal/spldoublylinkedlist.inc
index dffcefd255..7105411202 100644
--- a/ext/spl/internal/spldoublylinkedlist.inc
+++ b/ext/spl/internal/spldoublylinkedlist.inc
@@ -1,5 +1,4 @@
 <?php
-
 /** @file spldoublylinkedlist.inc
  * @ingroup SPL
  * @brief class SplDoublyLinkedList
@@ -13,23 +12,29 @@
  * @brief Doubly Linked List
  * @since PHP 5.3
  *
- * The SplDoublyLinkedList class provides the main functionnalities of a
+ * The SplDoublyLinkedList class provides the main functionalities of a
  * doubly linked list (DLL).
+ * @note The following userland implementation of Iterator is a bit different
+ *        from the internal one. Internally, iterators generated by nested 
+ *        foreachs are independant, while they share the same traverse pointer 
+ *        in userland.
  */
-class SplDoublyLinkedList implements Traversable, ArrayAccess, Countable
+class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable
 {
+	protected $_llist   = array();
+	protected $_it_mode = 0;
+	protected $_it_pos  = 0;
 
 	/** Iterator mode
 	 * @see setIteratorMode
 	 */
-	const IT_MODE_LIFO     = 0x00000001;
+	const IT_MODE_LIFO     = 0x00000002;
 
 	/** Iterator mode
 	 * @see setIteratorMode
 	 */
 	const IT_MODE_FIFO     = 0x00000000;
 
-
 	/** Iterator mode
 	 * @see setIteratorMode
 	 */
@@ -38,41 +43,75 @@ class SplDoublyLinkedList implements Traversable, ArrayAccess, Countable
 	/** Iterator mode
 	 * @see setIteratorMode
 	 */
-	const IT_MODE_DELETE   = 0x00000002;
+	const IT_MODE_DELETE   = 0x00000001;
 
 	/** @return the element popped from the end of the DLL.
+	 * @throw RuntimeException If the datastructure is empty.
 	 */
-	function pop() {/**/}
+	public function pop()
+	{
+		if (count($this->_llist) == 0) {
+			throw new RuntimeException("Can't pop from an empty datastructure");
+		}
+		return array_pop($this->_llist);
+	}
 
 	/** @return the element shifted from the beginning of the DLL.
+	 * @throw RuntimeException If the datastructure is empty.
 	 */
-	function shift() {/**/}
+	public function shift()
+	{
+		if (count($this->_llist) == 0) {
+			throw new RuntimeException("Can't shift from an empty datastructure");
+		}
+		return array_shift($this->_llist);
+	}
 
 	/** Pushes an element to the end of the DLL.
 	 * @param $data variable to add to the DLL.
 	 */
-	function push($data) {/**/}
+	public function push($data)
+	{
+		array_push($this->_llist, $data);
+		return true;
+	}
 
 	/** Adds an element to the beginning of the DLL.
 	 * @param $data variable to add to the DLL.
 	 */
-	function unshift($data) {/**/}
+	public function unshift($data)
+	{
+		array_unshift($this->_llist, $data);
+		return true;
+	}
 
 	/** @return the element at the beginning of the DLL.
 	 */
-	function top() {/**/}
+	public function top()
+	{
+		return end($this->_llist);
+	}
 
 	/** @return the element at the end of the DLL.
 	 */
-	function bottom() {/**/}
+	public function bottom()
+	{
+		return reset($this->_llist);
+	}
 
 	/** @return number elements in the DLL.
 	 */
-	function count() {/**/}
+	public function count()
+	{
+		return count($this->_llist);
+	}
 
 	/** @return whether the DLL is empty.
 	 */
-	function isEmpty() {/**/}
+	public function isEmpty()
+	{
+		return ($this->count() == 0);
+	}
 
 	/** Changes the iteration mode. There are two orthogonal sets of modes that 
 	 * can be set:
@@ -88,13 +127,151 @@ class SplDoublyLinkedList implements Traversable, ArrayAccess, Countable
 	 *
 	 * @param $mode new mode of iteration
 	 */
-	function setIteratorMode($mode) {/**/}
+	public function setIteratorMode($mode)
+	{
+		$this->_it_mode = $mode;
+	}
 
 	/** @return the current iteration mode
 	 * @see setIteratorMode
 	 */
-	function getIteratorMode() {/**/}
+	public function getIteratorMode()
+	{
+		return $this->_it_mode;
+	}
+
+	/** Rewind to top iterator as set in constructor
+	 */
+	public function rewind()
+	{
+		if ($this->_it_mode & self::IT_MODE_LIFO) {
+			$this->_it_pos = count($this->_llist)-1;
+		} else {
+			$this->_it_pos = 0;
+		}
+	}
+
+	/** @return whether iterator is valid
+	 */
+	public function valid()
+	{
+		return array_key_exists($this->_it_pos, $this->_llist);
+	}
+
+	/** @return current key
+	 */
+	public function key()
+	{
+		return $this->_it_pos;
+	}
+
+	/** @return current object
+	 */
+	public function current()
+	{
+		return $this->_llist[$this->_it_pos];
+	}
+
+	/** Forward to next element
+	 */
+	public function next()
+	{
+		if ($this->_it_mode & self::IT_MODE_LIFO) {
+			if ($this->_it_mode & self::IT_MODE_DELETE) {
+				$this->pop();
+			}
+			$this->_it_pos--;
+		} else {
+			if ($this->_it_mode & self::IT_MODE_DELETE) {
+				$this->shift();
+			} else {
+				$this->_it_pos++;
+			}
+		}
+	}
+
+	/** @return whether a certain offset exists in the DLL
+	 *
+	 * @param $offset             The offset
+	 * @throw OutOfRangeException If the offset is either invalid or out of
+	 *                            range.
+	 */
+	public function offsetExists($offset)
+	{
+		if (!is_numeric($offset)) {
+			throw new OutOfRangeException("Offset invalid or out of range");
+		} else {
+			return array_key_exists($offset, $this->_llist);
+		}
+	}
+
+	/** @return the data at a certain offset in the DLL
+	 *
+	 * @param $offset             The offset
+	 * @throw OutOfRangeException If the offset is either invalid or out of
+	 *                            range.
+	 */
+	public function offsetGet($offset)
+	{
+		if ($this->_it_mode & self::IT_MODE_LIFO) {
+			$realOffset = count($this->_llist)-$offset;
+		} else {
+			$realOffset = $offset;
+		}
+
+		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
+			throw new OutOfRangeException("Offset invalid or out of range");
+		} else {
+			return $this->_llist[$realOffset];
+		}
+	}
+
+	/** Defines the data at a certain offset in the DLL
+	 *
+	 * @param $offset             The offset
+	 * @param $value              New value
+	 * @throw OutOfRangeException If the offset is either invalid or out of
+	 *                            range.
+	 */
+	public function offsetSet($offset, $value)
+	{
+		if ($offset === null) {
+			return $this->push($value);
+		}
+
+		if ($this->_it_mode & self::IT_MODE_LIFO) {
+			$realOffset = count($this->_llist)-$offset;
+		} else {
+			$realOffset = $offset;
+		}
+
+		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
+			throw new OutOfRangeException("Offset invalid or out of range");
+		} else {
+			$this->_llist[$realOffset] = $value;
+		}
+	}
+
+	/** Unsets the element at a certain offset in the DLL
+	 *
+	 * @param $offset             The offset
+	 * @throw OutOfRangeException If the offset is either invalid or out of
+	 *                            range.
+	 */
+	public function offsetUnset($offset)
+	{
+		if ($this->_it_mode & self::IT_MODE_LIFO) {
+			$realOffset = count($this->_llist)-$offset;
+		} else {
+			$realOffset = $offset;
+		}
 
+		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
+			throw new OutOfRangeException("Offset invalid or out of range");
+		} else {
+			array_splice($this->_llist, $realOffset, 1);
+		}
+	}
 }
 
 ?>
diff --git a/ext/spl/internal/splqueue.inc b/ext/spl/internal/splqueue.inc
index aaa62db843..f795eabbc9 100644
--- a/ext/spl/internal/splqueue.inc
+++ b/ext/spl/internal/splqueue.inc
@@ -10,41 +10,62 @@
  */
 
 /** @ingroup SPL
- * @brief Implementation of a Queue through a DoublyLinkedList. As SplQueue 
- * extends SplDoublyLinkedList, unshift() and pop() are still available even
- * though they don't make much sense for a queue. For convenience, two aliases
- * are available:
- * - enqueue() is an alias of push()
- * - dequeue() is an alias of shift()
+ * @brief Implementation of a Queue through a DoublyLinkedList. As SplQueue
+ *        extends SplDoublyLinkedList, unshift() and pop() are still available 
+ *        even though they don't make much sense for a queue. For convenience,
+ *        two aliases are available:
+ *         - enqueue() is an alias of push()
+ *         - dequeue() is an alias of shift()
  *
  * @since PHP 5.3
  *
- * The SplQueue class provides the main functionnalities of a
- * queue implemented by a doubly linked list.
+ * The SplQueue class provides the main functionalities of a
+ * queue implemented using a doubly linked list (DLL).
  */
 class SplQueue extends SplDoublyLinkedList
 {
-	/** Changes the iteration mode. For queues, the direction mode
-	 * is frozen. Attempting to modify it will result in an RuntimeException.
+	protected $_it_mode = parent::IT_MODE_FIFO;
+
+	/** Changes the iteration mode. There are two orthogonal sets of modes that 
+	 * can be set:
+	 *
+	 * - The behavior of the iterator (either one or the other)
+	 *  - SplDoublyLnkedList::IT_MODE_DELETE (Elements are deleted by the iterator)
+	 *  - SplDoublyLnkedList::IT_MODE_KEEP   (Elements are traversed by the iterator)
 	 *
-	 * @throws RuntimeException
-	 * @param $mode new mode of iteration
-	 * @see SplDoublyLinkedList::setIteratorMode
+	 * The default mode is 0 : SplDoublyLnkedList::IT_MODE_LIFO | SplDoublyLnkedList::IT_MODE_KEEP
+	 *
+	 * @note The iteration's direction is not modifiable for queue instances
+	 * @param $mode              New mode of iteration
+	 * @throw RuntimeException   If the new mode affects the iteration's direction.
 	 */
-	function setIteratorMode($mode) {/**/}
+	public function setIteratorMode($mode)
+	{
+		if ($mode & parent::IT_MODE_LIFO === parent::IT_MODE_LIFO) {
+			throw new RuntimeException("Iterators' LIFO/FIFO modes for SplStack/SplQueue objects are frozen");
+		}
+
+		$this->_it_mode = $mode;
+	}
 
 	/** @return the first element of the queue.
 	 * @note dequeue is an alias of push()
 	 * @see splDoublyLinkedList::push()
 	 */
-	function dequeue() {/**/}
+	public function dequeue()
+	{
+		return parent::shift();
+	}
 
 	/** Pushes an element at the end of the queue.
 	 * @param $data variable to add to the queue.
 	 * @note enqueue is an alias of shift()
 	 * @see splDoublyLinkedList::shift()
 	 */
-	function enqueue($data) {/**/}
+	public function enqueue($data)
+	{
+		return parent::push($data);
+	}
 }
 
 ?>
diff --git a/ext/spl/internal/splstack.inc b/ext/spl/internal/splstack.inc
index a83d2c4b8e..4d3c62babf 100644
--- a/ext/spl/internal/splstack.inc
+++ b/ext/spl/internal/splstack.inc
@@ -9,27 +9,40 @@
  * SPL - Standard PHP Library
  */
 
-
 /** @ingroup SPL
  * @brief Implementation of a stack through a DoublyLinkedList. As SplStack 
- * extends SplDoublyLinkedList, shift() and unshift() are still available even
- * though they don't make much sense for a stack.
- *
+ *        extends SplDoublyLinkedList, shift() and unshift() are still available even
+ *        though they don't make much sense for a stack.
  * @since PHP 5.3
  *
- * The SplStack class provides the main functionnalities of a
- * stack implemented by a doubly linked list.
+ * The SplStack class provides the main functionalities of a
+ * stack implemented using a doubly linked list (DLL).
  */
 class SplStack extends SplDoublyLinkedList
 {
-	/** Changes the iteration mode. For stacks, the direction mode
-	 * is frozen. Attempting to modify it will result in an RuntimeException.
+	protected $_it_mode = parent::IT_MODE_LIFO;
+
+	/** Changes the iteration mode. There are two orthogonal sets of modes that 
+	 * can be set:
 	 *
-	 * @throws RuntimeException
-	 * @param $mode new mode of iteration
-	 * @see SplDoublyLinkedList::setIteratorMode
+	 * - The behavior of the iterator (either one or the other)
+	 *  - SplDoublyLnkedList::IT_MODE_DELETE (Elements are deleted by the iterator)
+	 *  - SplDoublyLnkedList::IT_MODE_KEEP   (Elements are traversed by the iterator)
+	 *
+	 * The default mode is 0 : SplDoublyLnkedList::IT_MODE_LIFO | SplDoublyLnkedList::IT_MODE_KEEP
+	 *
+	 * @note The iteration's direction is not modifiable for stack instances
+	 * @param $mode              New mode of iteration
+	 * @throw RuntimeException   If the new mode affects the iteration's direction.
 	 */
-	function setIteratorMode($mode) {/**/}
+	public function setIteratorMode($mode)
+	{
+		if ($mode & parent::IT_MODE_LIFO !== parent::IT_MODE_LIFO) {
+			throw new RuntimeException("Iterators' LIFO/FIFO modes for SplStack/SplQueue objects are frozen");
+		}
+
+		$this->_it_mode = $mode;
+	}
 }
 
 ?>
diff --git a/ext/spl/spl_dllist.c b/ext/spl/spl_dllist.c
index 0e2d5f5f0f..c34b257007 100644
--- a/ext/spl/spl_dllist.c
+++ b/ext/spl/spl_dllist.c
@@ -908,7 +908,6 @@ static void spl_dllist_it_helper_move_forward(spl_ptr_llist_element **traverse_p
 			}
 		} else {
 			*traverse_pointer_ptr = old->next;
-			(*traverse_position_ptr)++;
 
 			if (flags & SPL_DLLIST_IT_DELETE) {
 				zval *prev = (zval *)spl_ptr_llist_shift(llist);
@@ -916,6 +915,8 @@ static void spl_dllist_it_helper_move_forward(spl_ptr_llist_element **traverse_p
 				if (prev) {
 					zval_ptr_dtor((zval **)&prev);
 				}
+			} else {
+				(*traverse_position_ptr)++;
 			}
 		}
 
diff --git a/ext/spl/tests/dllist_003.phpt b/ext/spl/tests/dllist_003.phpt
index 7c9eb6f0d7..8e62046374 100644
--- a/ext/spl/tests/dllist_003.phpt
+++ b/ext/spl/tests/dllist_003.phpt
@@ -39,7 +39,7 @@ var_dump($dll->count());
 2=>4
 int(3)
 0=>2
-1=>3
-2=>4
+0=>3
+0=>4
 int(0)
 ===DONE===