Subversion-Projekte lars-tiefland.prado

Revision

Details | Letzte Änderung | Log anzeigen | RSS feed

Revision Autor Zeilennr. Zeile
1 lars 1 
<?php
2 
/**
3 
 * TQueue, TQueueIterator classes
4 
 *
5 
 * @author Qiang Xue <qiang.xue@gmail.com>
6 
 * @link http://www.pradosoft.com/
7 
 * @copyright Copyright &copy; 2005-2008 PradoSoft
8 
 * @license http://www.pradosoft.com/license/
9 
 * @version $Id$
10 
 * @package System.Collections
11 
 */
12 
 
13 
/**
14 
 * TQueue class
15 
 *
16 
 * TQueue implements a queue.
17 
 *
18 
 * The typical queue operations are implemented, which include
19 
 * {@link enqueue()}, {@link dequeue()} and {@link peek()}. In addition,
20 
 * {@link contains()} can be used to check if an item is contained
21 
 * in the queue. To obtain the number of the items in the queue,
22 
 * check the {@link getCount Count} property.
23 
 *
24 
 * Items in the queue may be traversed using foreach as follows,
25 
 * <code>
26 
 * foreach($queue as $item) ...
27 
 * </code>
28 
 *
29 
 * @author Qiang Xue <qiang.xue@gmail.com>
30 
 * @author Knut Urdalen <knut.urdalen@gmail.com>
31 
 * @version $Id$
32 
 * @package System.Collections
33 
 * @since 3.1
34 
 */
35 
class TQueue extends TComponent implements IteratorAggregate,Countable
36 
{
37 
	/**
38 
	 * internal data storage
39 
	 * @var array
40 
	 */
41 
	private $_d=array();
42 
	/**
43 
	 * number of items
44 
	 * @var integer
45 
	 */
46 
	private $_c=0;
47 
 
48 
	/**
49 
	 * Constructor.
50 
	 * Initializes the queue with an array or an iterable object.
51 
	 * @param array|Iterator the intial data. Default is null, meaning no initialization.
52 
	 * @throws TInvalidDataTypeException If data is not null and neither an array nor an iterator.
53 
	 */
54 
	public function __construct($data=null)
55 
	{
56 
		if($data!==null)
57 
			$this->copyFrom($data);
58 
	}
59 
 
60 
	/**
61 
	 * @return array the list of items in queue
62 
	 */
63 
	public function toArray()
64 
	{
65 
		return $this->_d;
66 
	}
67 
 
68 
	/**
69 
	 * Copies iterable data into the queue.
70 
	 * Note, existing data in the list will be cleared first.
71 
	 * @param mixed the data to be copied from, must be an array or object implementing Traversable
72 
	 * @throws TInvalidDataTypeException If data is neither an array nor a Traversable.
73 
	 */
74 
	public function copyFrom($data)
75 
	{
76 
		if(is_array($data) || ($data instanceof Traversable))
77 
		{
78 
			$this->clear();
79 
			foreach($data as $item)
80 
			{
81 
				$this->_d[]=$item;
82 
				++$this->_c;
83 
			}
84 
		}
85 
		else if($data!==null)
86 
			throw new TInvalidDataTypeException('queue_data_not_iterable');
87 
	}
88 
 
89 
	/**
90 
	 * Removes all items in the queue.
91 
	 */
92 
	public function clear()
93 
	{
94 
		$this->_c=0;
95 
		$this->_d=array();
96 
	}
97 
 
98 
	/**
99 
	 * @param mixed the item
100 
	 * @return boolean whether the queue contains the item
101 
	 */
102 
	public function contains($item)
103 
	{
104 
		return array_search($item,$this->_d,true)!==false;
105 
	}
106 
 
107 
	/**
108 
	 * Returns the item at the top of the queue.
109 
	 * Unlike {@link pop()}, this method does not remove the item from the queue.
110 
	 * @return mixed item at the top of the queue
111 
	 * @throws TInvalidOperationException if the queue is empty
112 
	 */
113 
	public function peek()
114 
	{
115 
		if($this->_c===0)
116 
			throw new TInvalidOperationException('queue_empty');
117 
		else
118 
			return $this->_d[$this->_c-1];
119 
	}
120 
 
121 
	/**
122 
	 * Removes and returns the object at the beginning of the queue.
123 
	 * @return mixed the item at the beginning of the queue
124 
	 * @throws TInvalidOperationException if the queue is empty
125 
	 */
126 
	public function dequeue()
127 
	{
128 
		if($this->_c===0)
129 
			throw new TInvalidOperationException('queue_empty');
130 
		else
131 
		{
132 
			--$this->_c;
133 
			return array_shift($this->_d);
134 
		}
135 
	}
136 
 
137 
	/**
138 
	 * Adds an object to the end of the queue.
139 
	 * @param mixed the item to be appended into the queue
140 
	 */
141 
	public function enqueue($item)
142 
	{
143 
		++$this->_c;
144 
		array_push($this->_d,$item);
145 
	}
146 
 
147 
	/**
148 
	 * Returns an iterator for traversing the items in the queue.
149 
	 * This method is required by the interface IteratorAggregate.
150 
	 * @return Iterator an iterator for traversing the items in the queue.
151 
	 */
152 
	public function getIterator()
153 
	{
154 
		return new TQueueIterator($this->_d);
155 
	}
156 
 
157 
	/**
158 
	 * @return integer the number of items in the queue
159 
	 */
160 
	public function getCount()
161 
	{
162 
		return $this->_c;
163 
	}
164 
 
165 
	/**
166 
	 * Returns the number of items in the queue.
167 
	 * This method is required by Countable interface.
168 
	 * @return integer number of items in the queue.
169 
	 */
170 
	public function count()
171 
	{
172 
		return $this->getCount();
173 
	}
174 
}
175 
 
176 
/**
177 
 * TQueueIterator class
178 
 *
179 
 * TQueueIterator implements Iterator interface.
180 
 *
181 
 * TQueueIterator is used by TQueue. It allows TQueue to return a new iterator
182 
 * for traversing the items in the queue.
183 
 *
184 
 * @author Qiang Xue <qiang.xue@gmail.com>
185 
 * @version $Id$
186 
 * @package System.Collections
187 
 * @since 3.1
188 
 */
189 
class TQueueIterator implements Iterator
190 
{
191 
	/**
192 
	 * @var array the data to be iterated through
193 
	 */
194 
	private $_d;
195 
	/**
196 
	 * @var integer index of the current item
197 
	 */
198 
	private $_i;
199 
	/**
200 
	 * @var integer count of the data items
201 
	 */
202 
	private $_c;
203 
 
204 
	/**
205 
	 * Constructor.
206 
	 * @param array the data to be iterated through
207 
	 */
208 
	public function __construct(&$data)
209 
	{
210 
		$this->_d=&$data;
211 
		$this->_i=0;
212 
		$this->_c=count($this->_d);
213 
	}
214 
 
215 
	/**
216 
	 * Rewinds internal array pointer.
217 
	 * This method is required by the interface Iterator.
218 
	 */
219 
	public function rewind()
220 
	{
221 
		$this->_i=0;
222 
	}
223 
 
224 
	/**
225 
	 * Returns the key of the current array item.
226 
	 * This method is required by the interface Iterator.
227 
	 * @return integer the key of the current array item
228 
	 */
229 
	public function key()
230 
	{
231 
		return $this->_i;
232 
	}
233 
 
234 
	/**
235 
	 * Returns the current array item.
236 
	 * This method is required by the interface Iterator.
237 
	 * @return mixed the current array item
238 
	 */
239 
	public function current()
240 
	{
241 
		return $this->_d[$this->_i];
242 
	}
243 
 
244 
	/**
245 
	 * Moves the internal pointer to the next array item.
246 
	 * This method is required by the interface Iterator.
247 
	 */
248 
	public function next()
249 
	{
250 
		$this->_i++;
251 
	}
252 
 
253 
	/**
254 
	 * Returns whether there is an item at current position.
255 
	 * This method is required by the interface Iterator.
256 
	 * @return boolean
257 
	 */
258 
	public function valid()
259 
	{
260 
		return $this->_i<$this->_c;
261 
	}
262 
}
263