1<?php
2/** @file spldoublylinkedlist.inc
3 * @ingroup SPL
4 * @brief class SplDoublyLinkedList
5 * @author  Etienne Kneuss
6 * @date    2008 - 2009
7 *
8 * SPL - Standard PHP Library
9 */
10
11/** @ingroup SPL
12 * @brief Doubly Linked List
13 * @since PHP 5.3
14 *
15 * The SplDoublyLinkedList class provides the main functionalities of a
16 * doubly linked list (DLL).
17 * @note The following userland implementation of Iterator is a bit different
18 *        from the internal one. Internally, iterators generated by nested
19 *        foreachs are independent, while they share the same traverse pointer
20 *        in userland.
21 */
22class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable
23{
24	protected $_llist   = array();
25	protected $_it_mode = 0;
26	protected $_it_pos  = 0;
27
28	/** Iterator mode
29	 * @see setIteratorMode
30	 */
31	const IT_MODE_LIFO     = 0x00000002;
32
33	/** Iterator mode
34	 * @see setIteratorMode
35	 */
36	const IT_MODE_FIFO     = 0x00000000;
37
38	/** Iterator mode
39	 * @see setIteratorMode
40	 */
41	const IT_MODE_KEEP     = 0x00000000;
42
43	/** Iterator mode
44	 * @see setIteratorMode
45	 */
46	const IT_MODE_DELETE   = 0x00000001;
47
48	/** @return the element popped from the end of the DLL.
49	 * @throw RuntimeException If the datastructure is empty.
50	 */
51	public function pop()
52	{
53		if (count($this->_llist) == 0) {
54			throw new RuntimeException("Can't pop from an empty datastructure");
55		}
56		return array_pop($this->_llist);
57	}
58
59	/** @return the element shifted from the beginning of the DLL.
60	 * @throw RuntimeException If the datastructure is empty.
61	 */
62	public function shift()
63	{
64		if (count($this->_llist) == 0) {
65			throw new RuntimeException("Can't shift from an empty datastructure");
66		}
67		return array_shift($this->_llist);
68	}
69
70	/** Pushes an element to the end of the DLL.
71	 * @param $data variable to add to the DLL.
72	 */
73	public function push($data)
74	{
75		array_push($this->_llist, $data);
76		return true;
77	}
78
79	/** Adds an element to the beginning of the DLL.
80	 * @param $data variable to add to the DLL.
81	 */
82	public function unshift($data)
83	{
84		array_unshift($this->_llist, $data);
85		return true;
86	}
87
88	/** @return the element at the beginning of the DLL.
89	 */
90	public function top()
91	{
92		return end($this->_llist);
93	}
94
95	/** @return the element at the end of the DLL.
96	 */
97	public function bottom()
98	{
99		return reset($this->_llist);
100	}
101
102	/** @return number elements in the DLL.
103	 */
104	public function count()
105	{
106		return count($this->_llist);
107	}
108
109	/** @return whether the DLL is empty.
110	 */
111	public function isEmpty()
112	{
113		return ($this->count() == 0);
114	}
115
116	/** Changes the iteration mode. There are two orthogonal sets of modes that
117	 * can be set:
118	 * - The direction of the iteration (either one or the other)
119	 *  - SplDoublyLnkedList::IT_MODE_LIFO (Stack style)
120	 *  - SplDoublyLnkedList::IT_MODE_FIFO (Queue style)
121	 *
122	 * - The behavior of the iterator (either one or the other)
123	 *  - SplDoublyLnkedList::IT_MODE_DELETE (Elements are deleted by the iterator)
124	 *  - SplDoublyLnkedList::IT_MODE_KEEP   (Elements are traversed by the iterator)
125	 *
126	 * The default mode is 0 : SplDoublyLnkedList::IT_MODE_FIFO | SplDoublyLnkedList::IT_MODE_KEEP
127	 *
128	 * @param $mode new mode of iteration
129	 */
130	public function setIteratorMode($mode)
131	{
132		$this->_it_mode = $mode;
133	}
134
135	/** @return the current iteration mode
136	 * @see setIteratorMode
137	 */
138	public function getIteratorMode()
139	{
140		return $this->_it_mode;
141	}
142
143	/** Rewind to top iterator as set in constructor
144	 */
145	public function rewind()
146	{
147		if ($this->_it_mode & self::IT_MODE_LIFO) {
148			$this->_it_pos = count($this->_llist)-1;
149		} else {
150			$this->_it_pos = 0;
151		}
152	}
153
154	/** @return whether iterator is valid
155	 */
156	public function valid()
157	{
158		return array_key_exists($this->_it_pos, $this->_llist);
159	}
160
161	/** @return current key
162	 */
163	public function key()
164	{
165		return $this->_it_pos;
166	}
167
168	/** @return current object
169	 */
170	public function current()
171	{
172		return $this->_llist[$this->_it_pos];
173	}
174
175	/** Forward to next element
176	 */
177	public function next()
178	{
179		if ($this->_it_mode & self::IT_MODE_LIFO) {
180			if ($this->_it_mode & self::IT_MODE_DELETE) {
181				$this->pop();
182			}
183			$this->_it_pos--;
184		} else {
185			if ($this->_it_mode & self::IT_MODE_DELETE) {
186				$this->shift();
187			} else {
188				$this->_it_pos++;
189			}
190		}
191	}
192
193	/** @return whether a certain offset exists in the DLL
194	 *
195	 * @param $offset             The offset
196	 * @throw OutOfRangeException If the offset is either invalid or out of
197	 *                            range.
198	 */
199	public function offsetExists($offset)
200	{
201		if (!is_numeric($offset)) {
202			throw new OutOfRangeException("Offset invalid or out of range");
203		} else {
204			return array_key_exists($offset, $this->_llist);
205		}
206	}
207
208	/** @return the data at a certain offset in the DLL
209	 *
210	 * @param $offset             The offset
211	 * @throw OutOfRangeException If the offset is either invalid or out of
212	 *                            range.
213	 */
214	public function offsetGet($offset)
215	{
216		if ($this->_it_mode & self::IT_MODE_LIFO) {
217			$realOffset = count($this->_llist)-$offset;
218		} else {
219			$realOffset = $offset;
220		}
221
222		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
223			throw new OutOfRangeException("Offset invalid or out of range");
224		} else {
225			return $this->_llist[$realOffset];
226		}
227	}
228
229	/** Defines the data at a certain offset in the DLL
230	 *
231	 * @param $offset             The offset
232	 * @param $value              New value
233	 * @throw OutOfRangeException If the offset is either invalid or out of
234	 *                            range.
235	 */
236	public function offsetSet($offset, $value)
237	{
238		if ($offset === null) {
239			return $this->push($value);
240		}
241
242		if ($this->_it_mode & self::IT_MODE_LIFO) {
243			$realOffset = count($this->_llist)-$offset;
244		} else {
245			$realOffset = $offset;
246		}
247
248		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
249			throw new OutOfRangeException("Offset invalid or out of range");
250		} else {
251			$this->_llist[$realOffset] = $value;
252		}
253	}
254
255	/** Unsets the element at a certain offset in the DLL
256	 *
257	 * @param $offset             The offset
258	 * @throw OutOfRangeException If the offset is either invalid or out of
259	 *                            range.
260	 */
261	public function offsetUnset($offset)
262	{
263		if ($this->_it_mode & self::IT_MODE_LIFO) {
264			$realOffset = count($this->_llist)-$offset;
265		} else {
266			$realOffset = $offset;
267		}
268
269		if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
270			throw new OutOfRangeException("Offset invalid or out of range");
271		} else {
272			array_splice($this->_llist, $realOffset, 1);
273		}
274	}
275}
276
277?>
278