<?php /** * TPriorityList, TPriorityListIterator classes * * @author Brad Anderson <javalizard@gmail.com> * @link http://www.pradosoft.com/ * @copyright Copyright © 2005-2010 PradoSoft * @license http://www.pradosoft.com/license/ * @version $Id: TPriorityList.php 2541 2008-10-21 15:05:13Z javalizard $ * @package System.Collections */ /** * TPriorityList class * * TPriorityList implements a priority ordered list collection class. It allows you to specify * floating numbers for priorities up to a specific precision. There is also a default priority if * no priority is specified. If you replace TList with this class it will work exactly the same with * priorities set to the default. * * As you access the array features of this class it flattens and caches the results. It flushes the * cache when elements are changed. * * You can access, append, insert, remove an item by using * {@link itemAt}, {@link add}, {@link insertAt}, {@link insertAtPriority}, and {@link remove}. * To get the number of the items in the list, use {@link getCount}. * TPriorityList can also be used like a regular array as follows, * <code> * $list[]=$item; // append with the default priority * $list[$index]=$item; // $index must be between 0 and $list->Count. This sets the element regardless of priority. Priority stays the same. * unset($list[$index]); // remove the item at $index * if(isset($list[$index])) // if the list has an item at $index * foreach($list as $index=>$item) // traverse each item in the list in proper priority order and add/insert order * $n=count($list); // returns the number of items in the list * </code> * ** To extend TPriorityList by doing additional operations with each addition or removal ** operation, override {@link insertAtIndexInPriority()} and {@link removeAtIndexInPriority()}. * * @author Brad Anderson <javalizard@gmail.com> * @version $Id: TPriorityList.php 2541 2008-10-21 15:05:13Z javalizard $ * @package System.Collections * @since 3.2a */ class TPriorityList extends TList { /** * @var array internal data storage */ private $_d=array(); /** * @var boolean tells if the _d is currently ordered. */ private $_o=0; /** * @var array cached flattened internal data storage */ private $_fd=null; /** * @var array cached flattened internal data storage */ private $_c=0; /** * @var numeric the default priority of items added if not specified */ private $_dp=10; /** * @var numeric the precision of the floating point priorities within this priority list */ private $_p=10; /** * Constructor. * Initializes the list with an array or an iterable object. * @param array|Iterator the intial data. Default is null, meaning no initialization. * @param boolean whether the list is read-only * @param float the default priority of items without priorities. * @param numeric the precision of the floating priorities * @throws TInvalidDataTypeException If data is not null and neither an array nor an iterator. */ public function __construct($data=null,$readOnly=false,$defaultPriority=10,$precision=8) { parent::__construct(); if($data!==null) $this->copyFrom($data); $this->setReadOnly($readOnly); $this->setDefaultPriority($defaultPriority); $this->setPrecision($precision); } /** * Returns the number of items in the list. * This method is required by Countable interface. * @return integer number of items in the list. */ public function count() { return $this->getCount(); } /** * @return integer the number of items in the list */ public function getCount() { return $this->_c; } /** * @param numeric optional priority at which to count items. if no parameter, it takes the default {@link getDefaultPriority} * @return int the number of items in the list at the */ public function getPriorityCount($priority=null) { if($priority === null) $priority = $this->DefaultPriority; $priority = (string)round(TPropertyValue::ensureFloat($priority), $this->_p); if(!isset($this->_d[$priority]) || !is_array($this->_d[$priority])) return false; return count($this->_d[$priority]); } /** * @return boolean whether this map is read-only or not. Defaults to false. */ public function getDefaultPriority() { return $this->_dp; } /** * @param boolean whether this list is read-only or not */ protected function setDefaultPriority($value) { $this->_dp=TPropertyValue::ensureFloat($value); } /** * @return int the precision of the floating priorities, defaults with 10 */ public function getPrecision() { return $this->_p; } /** * TPriorityList uses php function {@link round} on its priorities and thus it uses precision. * @param int this sets the precision of the floating point priorities. */ protected function setPrecision($value) { $this->_p=TPropertyValue::ensureInteger($value); } /** * Returns an iterator for traversing the items in the list. * This method is required by the interface IteratorAggregate. * @return Iterator an iterator for traversing the items in the list. */ public function getIterator() { return new TPriorityListIterator($this->flattenPriorities()); } /** * This is ordered lowest to highest. * @return array the array of priorities */ public function getPriorities() { $this->flattenPriorities(); return array_keys($this->_d); } /** * this orders the priority list and flattens it into an array [0,...,n-1] * @return array of the values in the list in priority order */ protected function sortPriorities() { if(!$this->_o) { ksort($this->_d, SORT_NUMERIC); $this->_o = true; } } /** * this orders the priority list and flattens it into an array [0,...,n-1] * @return array of the values in the list in priority order */ protected function flattenPriorities() { if(is_array($this->_fd)) return $this->_fd; $this->sortPriorities(); $this->_fd = array(); foreach($this->_d as $priority => $itemsatpriority) $this->_fd = array_merge($this->_fd, $itemsatpriority); return $this->_fd; } /** * Returns the item with the specified key. * This method is exactly the same as {@link offsetGet}. * @param mixed the key * @return mixed the element at the offset, null if no element is found at the offset */ public function itemAt($index) { if($index>=0 && $index<$this->_c) { $arr = $this->flattenPriorities(); return $arr[$index]; } else throw new TInvalidDataValueException('list_index_invalid',$index); } /** * @return array the key list */ public function itemsAtPriority($priority=null) { if($priority === null) $priority = $this->DefaultPriority; $priority = (string)round(TPropertyValue::ensureFloat($priority), $this->_p); return isset($this->_d[$priority]) ? $this->_d[$priority] : false; } /** * Returns the item with the specified key. * This method is exactly the same as {@link offsetGet}. * @param mixed the key * @return mixed the element at the offset, null if no element is found at the offset */ public function itemAtIndexPriority($index,$priority=null) { if($priority === null) $priority = $this->DefaultPriority; return !isset($this->_d[$priority]) ? false : ( isset($this->_d[$priority][$index]) ? $this->_d[$priority][$index] : false ); } /** * Adds an item into the map. * Note, if the specified key already exists, the old value will be overwritten. * @param mixed key * @param mixed value * @return int the index within the flattened array * @throws TInvalidOperationException if the map is read-only */ public function add($item, $priority=null) { return $this->insertAtIndexInPriority($item,false,$priority,true); } /** * Inserts an item at the specified position. * Original item at the position and the next items * will be moved one step towards the end. * @param integer the specified position. * @param mixed new item * @throws TInvalidDataValueException If the index specified exceeds the bound * @throws TInvalidOperationException if the list is read-only */ public function insertAt($index, $item) { if($this->ReadOnly) throw new TInvalidOperationException('list_readonly',get_class($this)); if(($priority=$this->priorityAt($index,true))!==false) $this->insertAtIndexInPriority($item,$priority[1],$priority[0]); else throw new TInvalidDataValueException('list_index_invalid',$index); } /** * Inserts an item at the specified position. * Original item at the position and the next items * will be moved one step towards the end. * @param integer the specified position. * @param mixed new item * @throws TInvalidDataValueException If the index specified exceeds the bound * @throws TInvalidOperationException if the list is read-only */ public function insertAtIndexInPriority($item,$index=false,$priority=null,$indexItem=false) { if(!$this->ReadOnly) { if($priority===null) $priority=$this->DefaultPriority; $priority=(string)round(TPropertyValue::ensureFloat($priority), $this->_p); if($indexItem) { $this->sortPriorities(); $cc=0; foreach($this->_d as $prioritykey => $items) if($prioritykey >= $priority) break; else $cc+=count($items); if($index === false) { //This string conversion allows floats as keys $c = count($this->_d[$priority]); if(!$c && $this->_c) $this->_o = false; $c += $cc; $this->_d[$priority][]=$item; } else if(isset($this->_d[$priority])) { $c = $index + $cc; array_splice($this->_d[$priority],$index,0,array($item)); } else { $c = $cc; $this->_o = false; $this->_d[$priority]=array($item); } if($this->_fd && is_array($this->_fd)) array_splice($this->_fd,$c,0,array($item)); } else { $c = null; if($index === false) { $cc = count($this->_d[$priority]); if(!$cc && $this->_c) $this->_o = false; $this->_d[$priority][]=$item; } else if(isset($this->_d[$priority])) { $cc = $index; array_splice($this->_d[$priority],$index,0,array($item)); } else { $cc = 0; $this->_o = false; $this->_d[$priority]=array($item); } if($this->_fd && is_array($this->_fd) && count($this->_d) == 1) array_splice($this->_fd,$cc,0,array($item)); else $this->_fd = null; } $this->_c++; return $c; } else throw new TInvalidOperationException('list_readonly',get_class($this)); } /** * Removes an item from the list. * The list will first search for the item. * The first item found will be removed from the list. * @param mixed the item to be removed. * @return integer the index at which the item is being removed * @throws TInvalidDataValueException If the item does not exist */ public function remove($item) { if(($priority=$this->priorityOf($item, true)) !== false) { $this->removeAtIndexInPriority($priority[1], $priority[0]); return $priority[2]; } else throw new TInvalidDataValueException('list_item_inexistent'); } /** * Removes an item at the specified position. * @param integer the index of the item to be removed. * @return mixed the removed item. * @throws TInvalidDataValueException If the index specified exceeds the bound * @throws TInvalidOperationException if the list is read-only */ public function removeAt($index) { if($this->ReadOnly) throw new TInvalidOperationException('list_readonly',get_class($this)); if(($priority = $this->priorityAt($index, true)) !== false) return $this->removeAtIndexInPriority($priority[1], $priority[0]); throw new TInvalidDataValueException('list_index_invalid',$index); } /** * Removes an item from the list. * The list will first search for the item. * The first item found will be removed from the list. * @param mixed the item to be removed. * @return integer the index at which the item is being removed * @throws TInvalidDataValueException If the item does not exist */ public function removeAtPriority($item, $priority=null) { if($priority === null) $priority = $this->DefaultPriority; if(isset($this->_d[$priority]) && ($index=array_search($item,$this->_d[$priority],true))!==false) return $this->removeAtIndexInPriority($index, $priority); throw new TInvalidDataValueException('list_item_inexistent'); } /** * Removes an item from the list. * The list will first search for the item. * The first item found will be removed from the list. * @param mixed the item to be removed. * @return integer the index at which the item is being removed * @throws TInvalidDataValueException If the item does not exist */ public function removeAtIndexInPriority($index, $priority=null) { if(!$this->ReadOnly) { if($priority === null) $priority = $this->DefaultPriority; $priority = (string)round(TPropertyValue::ensureFloat($priority), $this->_p); if(!isset($this->_d[$priority]) || !isset($this->_d[$priority][$index])) throw new TInvalidDataValueException('list_item_inexistent'); // $value is an array of elements removed, only one $value = array_splice($this->_d[$priority],$index,1); $value = $value[0]; if(!count($this->_d[$priority])) unset($this->_d[$priority]); $this->_c--; $this->_fd = null; return $value; } else throw new TInvalidOperationException('list_readonly',get_class($this)); } /** * Removes all items in the priority list. */ public function clear() { foreach($this->_d as $priority => $items) { $items = array_reverse($items); for($index = count($items) - 1; $index >= 0; $index--) $this->removeAtIndexInPriority($index, $priority); unset($this->_d[$priority]); } } /** * @param mixed the item * @return boolean whether the list contains the item */ public function contains($item) { return $this->indexOf($item)>=0; } /** * @param mixed the item * @return integer the index of the item in the list (0 based), -1 if not found. */ public function indexOf($item) { if(($index=array_search($item,$this->flattenPriorities(),true))===false) return -1; else return $index; } /** * @param mixed the item * @return integer the index of the item in the list (0 based), false if not found. */ public function priorityOf($item, $withindex = false) { // this is to ensure priority order $this->flattenPriorities(); $absindex = 0; foreach($this->_d as $priority => $items) { if(($index=array_search($item,$items,true))!==false) { $absindex += $index; return $withindex ? array($priority, $index, $absindex, 'priority' => $priority, 'index' => $index, 'absindex' => $absindex) : $priority; } else $absindex += count($items); } return false; } /** * @param mixed the item * @return integer the index of the item in the list (0 based), false if not found. */ public function priorityAt($index, $withindex = false) { if($index < 0 || $index >= $this->Count) throw new TInvalidDataValueException('list_index_invalid',$index); // this is to ensure priority order $absindex = $index; $this->flattenPriorities(); foreach($this->_d as $priority => $items) { if($index >= ($c = count($items))) $index -= $c; else return $withindex ? array($priority, $index, $absindex, 'priority' => $priority, 'index' => $inde, 'absindex' => $absindexx) : $priority; } return false; } /** * @param mixed the item to index * @param mixed the item */ public function insertBefore($indexitem, $item) { if(($priority = $this->priorityOf($indexitem, true)) === false) throw new TInvalidDataValueException('list_item_inexistent'); $this->insertAtIndexInPriority($item, $priority[1], $priority[0]); return $priority[2]; } /** * @param mixed the item to index * @param mixed the item */ public function insertAfter($indexitem, $item) { if(($priority = $this->priorityOf($indexitem, true)) === false) throw new TInvalidDataValueException('list_item_inexistent'); $this->insertAtIndexInPriority($item, $priority[1]+1, $priority[0]); return $priority[2]+1; } /** * @return array the list of items in array */ public function toArray() { return $this->flattenPriorities(); } /** * @return array the list of items in array with array keys as priorities and items as arrays of items */ public function toPriorityArray() { $this->flattenPriorities(); return $this->_d; } /** * Copies iterable data into the map. * Note, existing data in the map will be cleared first. * @param mixed the data to be copied from, must be an array or object implementing Traversable * @throws TInvalidDataTypeException If data is neither an array nor an iterator. */ public function copyFrom($data) { if($data instanceof TPriorityList) { if($this->getCount()>0) $this->clear(); foreach($data->Priorities as $priority) { foreach($data->itemsAtPriority($priority) as $index => $item) $this->insertAtIndexInPriority($item, $index, $priority); } } else if(is_array($data) || $data instanceof Traversable) { if($this->getCount()>0) $this->clear(); foreach($data as $key=>$item) $this->add($item); } else if($data!==null) throw new TInvalidDataTypeException('map_data_not_iterable'); } /** * Merges iterable data into the map. * Existing data in the map will be kept and overwritten if the keys are the same. * @param mixed the data to be merged with, must be an array or object implementing Traversable * @throws TInvalidDataTypeException If data is neither an array nor an iterator. */ public function mergeWith($data) { if($data instanceof TPriorityList) { foreach($data->Priorities as $priority) { foreach($data->itemsAtPriority($priority) as $index => $item) $this->insertAtIndexInPriority($item, $index, $priority); } } else if(is_array($data) || $data instanceof Traversable) { foreach($data as $priority=>$item) $this->add($item); } else if($data!==null) throw new TInvalidDataTypeException('map_data_not_iterable'); } /** * Returns whether there is an element at the specified offset. * This method is required by the interface ArrayAccess. * @param mixed the offset to check on * @return boolean */ public function offsetExists($offset) { return ($offset>=0 && $offset<$this->_c); } /** * Returns the element at the specified offset. * This method is required by the interface ArrayAccess. * @param integer the offset to retrieve element. * @return mixed the element at the offset, null if no element is found at the offset */ public function offsetGet($offset) { return $this->itemAt($offset); } /** * Sets the element at the specified offset. * This method is required by the interface ArrayAccess. * @param integer the offset to set element * @param mixed the element value */ public function offsetSet($offset,$item) { if($offset === null) return $this->add($item); $priority = $this->priorityAt($offset, true); $this->removeAtIndexInPriority($priority[1], $priority[0]); $this->insertAtIndexInPriority($item, $priority[1], $priority[0]); } /** * Unsets the element at the specified offset. * This method is required by the interface ArrayAccess. * @param mixed the offset to unset element */ public function offsetUnset($offset) { $this->removeAt($offset); } } /** * TPriorityListIterator class * * TPriorityListIterator implements Iterator interface. * * TPriorityListIterator is used by TPriorityList. It allows TPriorityList to return a new iterator * for traversing the items in the map. * * @author Qiang Xue <qiang.xue@gmail.com> * @version $Id: TPriorityList.php 2541 2008-10-21 15:05:13Z qiang.xue $ * @package System.Collections * @since 3.0 */ class TPriorityListIterator implements Iterator { /** * @var array the data to be iterated through */ private $_d; /** * @var array list of keys in the map */ private $_keys; /** * @var mixed current key */ private $_key; /** * Constructor. * @param array the data to be iterated through */ public function __construct(&$data) { $this->_d=&$data; $this->_keys=array_keys($data); } /** * Rewinds internal array pointer. * This method is required by the interface Iterator. */ public function rewind() { $this->_key=reset($this->_keys); } /** * Returns the key of the current array element. * This method is required by the interface Iterator. * @return mixed the key of the current array element */ public function key() { return $this->_key; } /** * Returns the current array element. * This method is required by the interface Iterator. * @return mixed the current array element */ public function current() { return $this->_d[$this->_key]; } /** * Moves the internal pointer to the next array element. * This method is required by the interface Iterator. */ public function next() { $this->_key=next($this->_keys); } /** * Returns whether there is an element at current position. * This method is required by the interface Iterator. * @return boolean */ public function valid() { return $this->_key!==false; } }