![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to spldoublylinkedlist.inc CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / spl / internal|
Return to spldoublylinkedlist.inc CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / spl / internal |
1.1 misho 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: */
22: class 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: ?>