From 8a2559a63b5eb09dbd736161247bc103c2c4d18a Mon Sep 17 00:00:00 2001 From: Brett Profitt Date: Mon, 15 Aug 2011 20:52:43 -0700 Subject: Refs #3355. Added ElggPriorityList. --- engine/classes/ElggPriorityList.php | 306 ++++++++++++++++++++++++++++++++++++ engine/tests/api/helpers.php | 256 +++++++++++++++++++++++++++++- 2 files changed, 561 insertions(+), 1 deletion(-) create mode 100644 engine/classes/ElggPriorityList.php (limited to 'engine') 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 @@ +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 -- cgit v1.2.3