diff options
Diffstat (limited to 'ext/spl/internal/spldoublylinkedlist.inc')
| -rw-r--r-- | ext/spl/internal/spldoublylinkedlist.inc | 277 |
1 files changed, 277 insertions, 0 deletions
diff --git a/ext/spl/internal/spldoublylinkedlist.inc b/ext/spl/internal/spldoublylinkedlist.inc new file mode 100644 index 0000000..e87e4b1 --- /dev/null +++ b/ext/spl/internal/spldoublylinkedlist.inc @@ -0,0 +1,277 @@ +<?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); + } + } +} + +?> |