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