<?php
/** @file spldoublylinkedlist.inc
 * @ingroup SPL
 * @brief class SplDoublyLinkedList
 * @author  Etienne Kneuss
 * @date    2008 - 2009
 *
 * SPL - Standard PHP Library
 */

/** @ingroup SPL
 * @brief Doubly Linked List
 * @since PHP 5.3
 *
 * 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 independent, while they share the same traverse pointer 
 *        in userland.
 */
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     = 0x00000002;

    /** Iterator mode
     * @see setIteratorMode
     */
    const IT_MODE_FIFO     = 0x00000000;

    /** Iterator mode
     * @see setIteratorMode
     */
    const IT_MODE_KEEP     = 0x00000000;

    /** Iterator mode
     * @see setIteratorMode
     */
    const IT_MODE_DELETE   = 0x00000001;

    /** @return the element popped from the end of the DLL.
     * @throw RuntimeException If the datastructure is empty.
     */
    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.
     */
    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.
     */
    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.
     */
    public function unshift($data)
    {
        array_unshift($this->_llist, $data);
        return true;
    }

    /** @return the element at the beginning of the DLL.
     */
    public function top()
    {
        return end($this->_llist);
    }

    /** @return the element at the end of the DLL.
     */
    public function bottom()
    {
        return reset($this->_llist);
    }

    /** @return number elements in the DLL.
     */
    public function count()
    {
        return count($this->_llist);
    }

    /** @return whether the DLL is empty.
     */
    public function isEmpty()
    {
        return ($this->count() == 0);
    }

    /** Changes the iteration mode. There are two orthogonal sets of modes that 
     * can be set:
     * - The direction of the iteration (either one or the other)
     *  - SplDoublyLnkedList::IT_MODE_LIFO (Stack style)
     *  - SplDoublyLnkedList::IT_MODE_FIFO (Queue style)
     *
     * - 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_FIFO | SplDoublyLnkedList::IT_MODE_KEEP
     *
     * @param $mode new mode of iteration
     */
    public function setIteratorMode($mode)
    {
        $this->_it_mode = $mode;
    }

    /** @return the current iteration mode
     * @see setIteratorMode
     */
    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);
        }
    }
}

?>