Refs #3355. Added ElggPriorityList.

2 files changed, 561 insertions, 1 deletions

diff --git a/engine/classes/ElggPriorityList.php b/engine/classes/ElggPriorityList.php
new file mode 100644
index 000000000..39fe698da
--- /dev/null
+++ b/engine/classes/ElggPriorityList.php
@@ -0,0 +1,306 @@
+<?php
+/**
+ * Iterate over elements in a specific priority.
+ *
+ * You can add, remove, and access elements using OOP or array interfaces:
+ *
+ * // OOP
+ * $pl = new ElggPriorityList();
+ * $pl->add('Element 0');
+ * $pl->add('Element -5', -5);
+ * $pl->add('Element 10', 10);
+ * $pl->add('Element -10', -10);
+ *
+ * $pl->remove('Element -5');
+ *
+ * $elements = $pl->getElements();
+ * var_dump($elements);
+ *
+ * Yields:
+ *
+ * array(
+ *	-10 => 'Element -10',
+ * 	0 => 'Element 0',
+ * 	10 => 'Element 10',
+ * )
+ *
+ *
+ * // Array
+ * $pl = new ElggPriorityList();
+ * $pl[] = 'Element 0';
+ * $pl[-5] = 'Element -5';
+ * $pl[10] = 'Element 10';
+ * $pl[-10] = 'Element -10';
+ *
+ * $priority = $pl->getPriority('Element -5');
+ * unset($pl[$priority]);
+ *
+ * foreach ($pl as $priority => $element) {
+ *	var_dump("$priority => $element");
+ * }
+ *
+ * Yields:
+ * -10 => Element -10
+ * 0 => Element 0
+ * 10 => Element 10
+ *
+ *
+ * Collisions with priority are handled by inserting the element as close to the requested priority
+ * as possible.
+ *
+ * $pl = new ElggPriorityList();
+ * $pl[5] = 'Element 5';
+ * $pl[5] = 'Colliding element 5';
+ * $pl[5] = 'Another colliding element 5';
+ *
+ * var_dump($pl->getElements());
+ *
+ * Yields:
+ *
+ * array(
+ *	5 => 'Element 5',
+ *	6 => 'Colliding element 5',
+ *	7 => 'Another colliding element 5'
+ * )
+ *
+ * @package Elgg.Core
+ * @subpackage Helpers
+ */
+
+class ElggPriorityList
+	implements Iterator, ArrayAccess, Countable {
+
+	/**
+	 * The list of elements
+	 *
+	 * @var array
+	 */
+	private $elements = array();
+
+	/**
+	 * Create a new priority list.
+	 *
+	 * @param array $elements An optional array of priorities => element
+	 */
+	public function __construct(array $elements = array()) {
+		if ($elements) {
+			foreach ($elements as $priority => $element) {
+				$this->add($element, $priority);
+			}
+		}
+	}
+
+	/**
+	 * Adds an element to the list.
+	 *
+	 * @warning This returns the priority at which the element was added, which can be 0. Use
+	 *          !== false to check for success.
+	 *
+	 * @param mixed $element  The element to add to the list.
+	 * @param mixed $priority Priority to add the element. In priority collisions, the original element
+	 *                        maintains its priority and the new element is to the next available
+	 *                        slot, taking into consideration all previously registered elements.
+	 *                        Negative elements are accepted.
+	 * @return int            The priority the element was added at.
+	 */
+	public function add($element, $priority = null) {
+		if ($priority !== null && !is_numeric($priority)) {
+			return false;
+		} else {
+			$priority = $this->getNextPriority($priority);
+		}
+
+		$this->elements[$priority] = $element;
+		return $priority;
+	}
+
+	/**
+	 * Removes an element from the list.
+	 *
+	 * @warning The element must have the same attributes / values. If using $strict, it must have
+	 *          the same types. array(10) will fail in strict against array('10') (str vs int).
+	 *
+	 * @param type $element
+	 * @return bool
+	 */
+	public function remove($element, $strict = false) {
+		$index = array_search($element, $this->elements, $strict);
+		if ($index !== false) {
+			unset($this->elements[$index]);
+			return true;
+		} else {
+			return false;
+		}
+	}
+
+	/**
+	 * Returns the elements
+	 *
+	 * @param type $elements
+	 * @param type $sort
+	 */
+	public function getElements() {
+		$this->sortIfUnsorted();
+		return $this->elements;
+	}
+
+	/**
+	 * Sort the elements optionally by a callback function.
+	 *
+	 * If no user function is provided the elements are sorted by priority registered.
+	 *
+	 * The callback function should accept the array of elements as the first argument and should
+	 * return a sorted array.
+	 *
+	 * This function can be called multiple times.
+	 *
+	 * @param type $callback
+	 * @return bool
+	 */
+	public function sort($callback = null) {
+		if (!$callback) {
+			ksort($this->elements, SORT_NUMERIC);
+		} else {
+			$sorted = call_user_func($callback, $this->elements);
+
+			if (!$sorted) {
+				return false;
+			}
+
+			$this->elements = $sorted;
+		}
+		
+		$this->sorted = true;
+		return true;
+	}
+
+	/**
+	 * Sort the elements if they haven't been sorted yet.
+	 *
+	 * @return bool
+	 */
+	private function sortIfUnsorted() {
+		if (!$this->sorted) {
+			return $this->sort();
+		}
+	}
+
+	/**
+	 * Returns the next priority available.
+	 *
+	 * @param int $near Make the priority as close to $near as possible.
+	 * @return int
+	 */
+	public function getNextPriority($near = 0) {
+		$near = (int) $near;
+		
+		while (array_key_exists($near, $this->elements)) {
+			$near++;
+		}
+
+		return $near;
+	}
+
+
+	/**
+	 * Returns the priority of an element if it exists in the list.
+	 * 
+	 * @warning This can return 0 if the element's priority is 0. Use identical operator (===) to
+	 * check for false if you want to know if an element exists.
+	 *
+	 * @param mixed $element
+	 * @return mixed False if the element doesn't exists, the priority if it does.
+	 */
+	public function getPriority($element, $strict = false) {
+		return array_search($element, $this->elements, $strict);
+	}
+
+	/**********************
+	 * Interfaces methods *
+	 **********************/
+
+
+	/**
+	 * Iterator
+	 */
+
+	/**
+	 * PHP Iterator Interface
+	 *
+	 * @see Iterator::rewind()
+	 * @return void
+	 */
+	public function rewind() {
+		$this->sortIfUnsorted();
+		return rewind($this->elements);
+	}
+
+	/**
+	 * PHP Iterator Interface
+	 *
+	 * @see Iterator::current()
+	 * @return mixed
+	 */
+	public function current() {
+		$this->sortIfUnsorted();
+		return current($this->elements);
+	}
+
+	/**
+	 * PHP Iterator Interface
+	 *
+	 * @see Iterator::key()
+	 * @return int
+	 */
+	public function key() {
+		$this->sortIfUnsorted();
+		return key($this->elements);
+	}
+
+	/**
+	 * PHP Iterator Interface
+	 *
+	 * @see Iterator::next()
+	 * @return mixed
+	 */
+	public function next() {
+		$this->sortIfUnsorted();
+		return next($this->elements);
+	}
+
+	/**
+	 * PHP Iterator Interface
+	 *
+	 * @see Iterator::valid()
+	 * @return bool
+	 */
+	public function valid() {
+		$this->sortIfUnsorted();
+		$key = key($this->elements);
+		return ($key !== NULL && $key !== FALSE);
+	}
+
+	// Coutable
+	public function count() {
+		return count($this->elements);
+	}
+
+	// ArrayAccess
+	public function offsetExists($offset) {
+		return isset($this->elements[$offset]);
+	}
+
+	public function offsetGet($offset) {
+		return isset($this->elements[$offset]) ? $this->elements[$offset] : null;
+	}
+
+	public function offsetSet($offset, $value) {
+		return $this->add($value, $offset);
+	}
+
+	public function offsetUnset($offset) {
+		if (isset($this->elements[$offset])) {
+			unset($this->elements[$offset]);
+		}
+	}
+}
\ No newline at end of file
diff --git a/engine/tests/api/helpers.php b/engine/tests/api/helpers.php
index 461627547..033970359 100644
--- a/engine/tests/api/helpers.php
+++ b/engine/tests/api/helpers.php
@@ -187,4 +187,258 @@ class ElggCoreHelpersTest extends ElggCoreUnitTest {
 		$js_urls = elgg_get_loaded_js('footer');
 		$this->assertIdentical(array(), $js_urls);
 	}
-}
+
+	// test ElggPriorityList
+	public function testElggPriorityListAdd() {
+		$pl = new ElggPriorityList();
+		$elements = array(
+			'Test value',
+			'Test value 2',
+			'Test value 3'
+		);
+
+		shuffle($elements);
+
+		foreach ($elements as $element) {
+			$this->assertTrue($pl->add($element) !== false);
+		}
+
+		$test_elements = $pl->getElements();
+
+		$this->assertTrue(is_array($test_elements));
+
+		foreach ($test_elements as $i => $element) {
+			// should be in the array
+			$this->assertTrue(in_array($element, $elements));
+
+			// should be the only element, so priority 0
+			$this->assertEqual($i, array_search($element, $elements));
+		}
+	}
+
+	public function testElggPriorityListAddWithPriority() {
+		$pl = new ElggPriorityList();
+
+		$elements = array(
+			10 => 'Test Element 10',
+			5 => 'Test Element 5',
+			0 => 'Test Element 0',
+			100 => 'Test Element 100',
+			-1 => 'Test Element -1',
+			-5 => 'Test Element -5'
+		);
+
+		foreach ($elements as $priority => $element) {
+			$pl->add($element, $priority);
+		}
+
+		$test_elements = $pl->getElements();
+
+		// should be sorted by priority
+		$elements_sorted = array(
+			-5 => 'Test Element -5',
+			-1 => 'Test Element -1',
+			0 => 'Test Element 0',
+			5 => 'Test Element 5',
+			10 => 'Test Element 10',
+			100 => 'Test Element 100',
+		);
+
+		$this->assertIdentical($elements_sorted, $test_elements);
+
+		foreach ($test_elements as $priority => $element) {
+			$this->assertIdentical($elements[$priority], $element);
+		}
+	}
+
+	public function testElggPriorityListGetNextPriority() {
+		$pl = new ElggPriorityList();
+
+		$elements = array(
+			2 => 'Test Element',
+			0 => 'Test Element 2',
+			-2 => 'Test Element 3',
+		);
+
+		foreach ($elements as $priority => $element) {
+			$pl->add($element, $priority);
+		}
+
+		// we're not specifying a priority so it should be the next consecutive to 0.
+		$this->assertEqual(1, $pl->getNextPriority());
+
+		// add another one at priority 1
+		$pl->add('Test Element 1');
+
+		// next consecutive to 0 is now 3.
+		$this->assertEqual(3, $pl->getNextPriority());
+	}
+
+	public function testElggPriorityListRemove() {
+		$pl = new ElggPriorityList();
+
+		$elements = array();
+		for ($i=0; $i<3; $i++) {
+			$element = new stdClass();
+			$element->name = "Test Element $i";
+			$element->someAttribute = rand(0, 9999);
+			$elements[] = $element;
+			$pl->add($element);
+		}
+
+		$pl->remove($elements[1]);
+
+		$test_elements = $pl->getElements();
+
+		// make sure it's gone.
+		$this->assertTrue(2, count($test_elements));
+		$this->assertIdentical($elements[0], $test_elements[0]);
+		$this->assertIdentical($elements[2], $test_elements[2]);
+	}
+
+	public function testElggPriorityListConstructor() {
+		$elements = array(
+			10 => 'Test Element 10',
+			5 => 'Test Element 5',
+			0 => 'Test Element 0',
+			100 => 'Test Element 100',
+			-1 => 'Test Element -1',
+			-5 => 'Test Element -5'
+		);
+
+		$pl = new ElggPriorityList($elements);
+		$test_elements = $pl->getElements();
+
+		$elements_sorted = array(
+			-5 => 'Test Element -5',
+			-1 => 'Test Element -1',
+			0 => 'Test Element 0',
+			5 => 'Test Element 5',
+			10 => 'Test Element 10',
+			100 => 'Test Element 100',
+		);
+
+		$this->assertIdentical($elements_sorted, $test_elements);
+	}
+
+	public function testElggPriorityListGetPriority() {
+		$pl = new ElggPriorityList();
+
+		$elements = array(
+			'Test element 0',
+			'Test element 1',
+			'Test element 2',
+		);
+
+		foreach ($elements as $element) {
+			$pl->add($element);
+		}
+
+		$this->assertIdentical(0, $pl->getPriority($elements[0]));
+		$this->assertIdentical(1, $pl->getPriority($elements[1]));
+		$this->assertIdentical(2, $pl->getPriority($elements[2]));
+	}
+
+	public function testElggPriorityListPriorityCollision() {
+		$pl = new ElggPriorityList();
+		
+		$elements = array(
+			5 => 'Test element 5',
+			6 => 'Test element 6',
+			0 => 'Test element 0',
+		);
+
+		foreach ($elements as $priority => $element) {
+			$pl->add($element, $priority);
+		}
+
+		// add at a colliding priority
+		$pl->add('Colliding element', 5);
+
+		// should float to the top closest to 5, so 7
+		$this->assertEqual(7, $pl->getPriority('Colliding element'));
+	}
+
+	public function testElggPriorityListArrayAccess() {
+		$pl = new ElggPriorityList();
+		$pl[] = 'Test element 0';
+		$pl[-10] = 'Test element -10';
+		$pl[-1] = 'Test element -1';
+		$pl[] = 'Test element 1';
+		$pl[5] = 'Test element 5';
+		$pl[0] = 'Test element collision with 0 (should be 2)';
+
+		$elements = array(
+			-1 => 'Test element -1',
+			0 => 'Test element 0',
+			1 => 'Test element 1',
+			2 => 'Test element collision with 0 (should be 2)',
+			5 => 'Test element 5',
+		);
+
+		$priority = $pl->getPriority('Test element -10');
+		unset($pl[$priority]);
+
+		$test_elements = $pl->getElements();
+		$this->assertIdentical($elements, $test_elements);
+	}
+
+	public function testElggPriorityListIterator() {
+		$elements = array(
+			-5 => 'Test element -5',
+			0 => 'Test element 0',
+			5 => 'Test element 5'
+		);
+		
+		$pl = new ElggPriorityList($elements);
+
+		foreach ($pl as $priority => $element) {
+			$this->assertIdentical($elements[$priority], $element);
+		}
+	}
+
+	public function testElggPriorityListCountable() {
+		$pl = new ElggPriorityList();
+
+		$this->assertEqual(0, count($pl));
+
+		$pl[] = 'Test element 0';
+		$this->assertEqual(1, count($pl));
+
+		$pl[] = 'Test element 1';
+		$this->assertEqual(2, count($pl));
+
+		$pl[] = 'Test element 2';
+		$this->assertEqual(3, count($pl));
+	}
+
+	public function testElggPriorityListUserSort() {
+		$elements = array(
+			'A',
+			'B',
+			'C',
+			'D',
+			'E',
+		);
+
+		$elements_sorted_string = $elements;
+
+		shuffle($elements);
+		$pl = new ElggPriorityList($elements);
+
+		// will sort by priority
+		$test_elements = $pl->getElements();
+		$this->assertIdentical($elements, $test_elements);
+
+		function test_sort($elements) {
+			sort($elements, SORT_LOCALE_STRING);
+			return $elements;
+		}
+
+		// force a new sort using our function
+		$pl->sort('test_sort');
+		$test_elements = $pl->getElements();
+
+		$this->assertIdentical($elements_sorted_string, $test_elements);
+	}
+}
\ No newline at end of file