1: <?php
2: /**
3: * Iterate over elements in a specific priority.
4: *
5: * $pl = new ElggPriorityList();
6: * $pl->add('Element 0');
7: * $pl->add('Element 10', 10);
8: * $pl->add('Element -10', -10);
9: *
10: * foreach ($pl as $priority => $element) {
11: * var_dump("$priority => $element");
12: * }
13: *
14: * Yields:
15: * -10 => Element -10
16: * 0 => Element 0
17: * 10 => Element 10
18: *
19: * Collisions on priority are handled by inserting the element at or as close to the
20: * requested priority as possible:
21: *
22: * $pl = new ElggPriorityList();
23: * $pl->add('Element 5', 5);
24: * $pl->add('Colliding element 5', 5);
25: * $pl->add('Another colliding element 5', 5);
26: *
27: * foreach ($pl as $priority => $element) {
28: * var_dump("$priority => $element");
29: * }
30: *
31: * Yields:
32: * 5 => 'Element 5',
33: * 6 => 'Colliding element 5',
34: * 7 => 'Another colliding element 5'
35: *
36: * You can do priority lookups by element:
37: *
38: * $pl = new ElggPriorityList();
39: * $pl->add('Element 0');
40: * $pl->add('Element -5', -5);
41: * $pl->add('Element 10', 10);
42: * $pl->add('Element -10', -10);
43: *
44: * $priority = $pl->getPriority('Element -5');
45: *
46: * Or element lookups by priority.
47: * $element = $pl->getElement(-5);
48: *
49: * To remove elements, pass the element.
50: * $pl->remove('Element -10');
51: *
52: * To check if an element exists:
53: * $pl->contains('Element -5');
54: *
55: * To move an element:
56: * $pl->move('Element -5', -3);
57: *
58: * ElggPriorityList only tracks priority. No checking is done in ElggPriorityList for duplicates or
59: * updating. If you need to track this use objects and an external map:
60: *
61: * function elgg_register_something($id, $display_name, $location, $priority = 500) {
62: * // $id => $element.
63: * static $map = array();
64: * static $list;
65: *
66: * if (!$list) {
67: * $list = new ElggPriorityList();
68: * }
69: *
70: * // update if already registered.
71: * if (isset($map[$id])) {
72: * $element = $map[$id];
73: * // move it first because we have to pass the original element.
74: * if (!$list->move($element, $priority)) {
75: * return false;
76: * }
77: * $element->display_name = $display_name;
78: * $element->location = $location;
79: * } else {
80: * $element = new stdClass();
81: * $element->display_name = $display_name;
82: * $element->location = $location;
83: * if (!$list->add($element, $priority)) {
84: * return false;
85: * }
86: * $map[$id] = $element;
87: * }
88: *
89: * return true;
90: * }
91: *
92: * @package Elgg.Core
93: * @subpackage Helpers
94: */
95: class ElggPriorityList
96: implements Iterator, Countable {
97:
98: /**
99: * The list of elements
100: *
101: * @var array
102: */
103: private $elements = array();
104:
105: /**
106: * Create a new priority list.
107: *
108: * @param array $elements An optional array of priorities => element
109: */
110: public function __construct(array $elements = array()) {
111: if ($elements) {
112: foreach ($elements as $priority => $element) {
113: $this->add($element, $priority);
114: }
115: }
116: }
117:
118: /**
119: * Adds an element to the list.
120: *
121: * @warning This returns the priority at which the element was added, which can be 0. Use
122: * !== false to check for success.
123: *
124: * @param mixed $element The element to add to the list.
125: * @param mixed $priority Priority to add the element. In priority collisions, the original element
126: * maintains its priority and the new element is to the next available
127: * slot, taking into consideration all previously registered elements.
128: * Negative elements are accepted.
129: * @param bool $exact unused
130: * @return int The priority of the added element.
131: * @todo remove $exact or implement it. Note we use variable name strict below.
132: */
133: public function add($element, $priority = null, $exact = false) {
134: if ($priority !== null && !is_numeric($priority)) {
135: return false;
136: } else {
137: $priority = $this->getNextPriority($priority);
138: }
139:
140: $this->elements[$priority] = $element;
141: $this->sorted = false;
142: return $priority;
143: }
144:
145: /**
146: * Removes an element from the list.
147: *
148: * @warning The element must have the same attributes / values. If using $strict, it must have
149: * the same types. array(10) will fail in strict against array('10') (str vs int).
150: *
151: * @param mixed $element The element to remove from the list
152: * @param bool $strict Whether to check the type of the element match
153: * @return bool
154: */
155: public function remove($element, $strict = false) {
156: $index = array_search($element, $this->elements, $strict);
157: if ($index !== false) {
158: unset($this->elements[$index]);
159: return true;
160: } else {
161: return false;
162: }
163: }
164:
165: /**
166: * Move an existing element to a new priority.
167: *
168: * @param mixed $element The element to move
169: * @param int $new_priority The new priority for the element
170: * @param bool $strict Whether to check the type of the element match
171: * @return bool
172: */
173: public function move($element, $new_priority, $strict = false) {
174: $new_priority = (int) $new_priority;
175:
176: $current_priority = $this->getPriority($element, $strict);
177: if ($current_priority === false) {
178: return false;
179: }
180:
181: if ($current_priority == $new_priority) {
182: return true;
183: }
184:
185: // move the actual element so strict operations still work
186: $element = $this->getElement($current_priority);
187: unset($this->elements[$current_priority]);
188: return $this->add($element, $new_priority);
189: }
190:
191: /**
192: * Returns the elements
193: *
194: * @return array
195: */
196: public function getElements() {
197: $this->sortIfUnsorted();
198: return $this->elements;
199: }
200:
201: /**
202: * Sort the elements optionally by a callback function.
203: *
204: * If no user function is provided the elements are sorted by priority registered.
205: *
206: * The callback function should accept the array of elements as the first
207: * argument and should return a sorted array.
208: *
209: * This function can be called multiple times.
210: *
211: * @param callback $callback The callback for sorting. Numeric sorting is the default.
212: * @return bool
213: */
214: public function sort($callback = null) {
215: if (!$callback) {
216: ksort($this->elements, SORT_NUMERIC);
217: } else {
218: $sorted = call_user_func($callback, $this->elements);
219:
220: if (!$sorted) {
221: return false;
222: }
223:
224: $this->elements = $sorted;
225: }
226:
227: $this->sorted = true;
228: return true;
229: }
230:
231: /**
232: * Sort the elements if they haven't been sorted yet.
233: *
234: * @return bool
235: */
236: private function sortIfUnsorted() {
237: if (!$this->sorted) {
238: return $this->sort();
239: }
240: }
241:
242: /**
243: * Returns the next priority available.
244: *
245: * @param int $near Make the priority as close to $near as possible.
246: * @return int
247: */
248: public function getNextPriority($near = 0) {
249: $near = (int) $near;
250:
251: while (array_key_exists($near, $this->elements)) {
252: $near++;
253: }
254:
255: return $near;
256: }
257:
258: /**
259: * Returns the priority of an element if it exists in the list.
260: *
261: * @warning This can return 0 if the element's priority is 0.
262: *
263: * @param mixed $element The element to check for.
264: * @param bool $strict Use strict checking?
265: * @return mixed False if the element doesn't exists, the priority if it does.
266: */
267: public function getPriority($element, $strict = false) {
268: return array_search($element, $this->elements, $strict);
269: }
270:
271: /**
272: * Returns the element at $priority.
273: *
274: * @param int $priority The priority
275: * @return mixed The element or false on fail.
276: */
277: public function getElement($priority) {
278: return (isset($this->elements[$priority])) ? $this->elements[$priority] : false;
279: }
280:
281: /**
282: * Returns if the list contains $element.
283: *
284: * @param mixed $element The element to check.
285: * @param bool $strict Use strict checking?
286: * @return bool
287: */
288: public function contains($element, $strict = false) {
289: return $this->getPriority($element, $strict) !== false;
290: }
291:
292:
293: /**********************
294: * Interface methods *
295: **********************/
296:
297: /**
298: * Iterator
299: */
300:
301: /**
302: * PHP Iterator Interface
303: *
304: * @see Iterator::rewind()
305: * @return void
306: */
307: public function rewind() {
308: $this->sortIfUnsorted();
309: return reset($this->elements);
310: }
311:
312: /**
313: * PHP Iterator Interface
314: *
315: * @see Iterator::current()
316: * @return mixed
317: */
318: public function current() {
319: $this->sortIfUnsorted();
320: return current($this->elements);
321: }
322:
323: /**
324: * PHP Iterator Interface
325: *
326: * @see Iterator::key()
327: * @return int
328: */
329: public function key() {
330: $this->sortIfUnsorted();
331: return key($this->elements);
332: }
333:
334: /**
335: * PHP Iterator Interface
336: *
337: * @see Iterator::next()
338: * @return mixed
339: */
340: public function next() {
341: $this->sortIfUnsorted();
342: return next($this->elements);
343: }
344:
345: /**
346: * PHP Iterator Interface
347: *
348: * @see Iterator::valid()
349: * @return bool
350: */
351: public function valid() {
352: $this->sortIfUnsorted();
353: $key = key($this->elements);
354: return ($key !== NULL && $key !== FALSE);
355: }
356:
357: /**
358: * Countable interface
359: *
360: * @see Countable::count()
361: * @return int
362: */
363: public function count() {
364: return count($this->elements);
365: }
366: }