Added two methods for getting array elements out of TPriorityList above and below a specific priority, with inclusion. Added TPriorityMap and test cases.

1 files changed, 606 insertions, 0 deletions

diff --git a/framework/Collections/TPriorityMap.php b/framework/Collections/TPriorityMap.php
new file mode 100644
index 00000000..6f8ae8bd
--- /dev/null
+++ b/framework/Collections/TPriorityMap.php
@@ -0,0 +1,606 @@
+<?php
+/**
+ * TPriorityMap, TPriorityMapIterator classes
+ *
+ * @author Brad Anderson <javalizard@mac.com>
+ * @link http://www.pradosoft.com/
+ * @copyright Copyright &copy; 2005-2011 PradoSoft
+ * @license http://www.pradosoft.com/license/
+ * @version $Id: TPriorityMap.php 2817 2010-04-18 04:25:03Z javalizard $
+ * @package System.Collections
+ */
+
+/**
+ * TPriorityMap class
+ *
+ * TPriorityMap implements a collection that takes key-value pairs with 
+ * a priority to allow key-value pairs to be ordered.  This ordering is 
+ * important when flattening the map. When flattening the map, if some
+ * key-value pairs are required to be before or after others, use this 
+ * class to keep order to your map.
+ *
+ * You can access, add or remove an item with a key by using
+ * {@link itemAt}, {@link add}, and {@link remove}.  These functions 
+ * can optionally take a priority parameter to allow access to specific 
+ * priorities.  TPriorityMap is functionally backward compatible 
+ * with {@link TMap}.
+ * 
+ * To get the number of the items in the map, use {@link getCount}.
+ * TPriorityMap can also be used like a regular array as follows,
+ * <code>
+ * $map[$key]=$value; // add a key-value pair
+ * unset($map[$key]); // remove the value with the specified key
+ * if(isset($map[$key])) // if the map contains the key
+ * foreach($map as $key=>$value) // traverse the items in the map
+ * $n=count($map);  // returns the number of items in the map
+ * </code>
+ * Using standard array access method like these will always use
+ * the default priority.
+ *
+ * An item that doesn't specify a priority will receive the default
+ * priority.  The default priority is set during the instantiation
+ * of a new TPriorityMap. If no custom default priority is specified, 
+ * the standard default priority of 10 is used.
+ *
+ * Priorities with significant digits below precision will be rounded.
+ *
+ * A priority may also be a numeric with decimals.  This is set 
+ * during the instantiation of a new TPriorityMap. 
+ * The default is 8 decimal places for a priority.  If a negative number
+ * is used, rounding occurs into the integer space rather than in
+ * the decimal space.  See {@link round}.
+ *
+ * @author Brad Anderson <javalizard@mac.com>
+ * @version $Id: TPriorityMap.php 2817 2010-04-18 04:25:03Z javalizard $
+ * @package System.Collections
+ * @since 3.2a
+ */
+Prado::using('System.Collections.TMap');
+
+class TPriorityMap extends TMap
+{
+	/**
+	 * @var array internal data storage
+	 */
+	private $_d=array();
+	/**
+	 * @var boolean whether this list is read-only
+	 */
+	private $_r=false;
+	/**
+	 * @var boolean indicates if the _d is currently ordered.
+	 */
+	private $_o=false;
+	/**
+	 * @var array cached flattened internal data storage
+	 */
+	private $_fd=null;
+	/**
+	 * @var integer number of items contain within the map
+	 */
+	private $_c=0;
+	/**
+	 * @var numeric the default priority of items without specified priorities
+	 */
+	private $_dp=10;
+	/**
+	 * @var integer the precision of the numeric priorities within this priority list.
+	 */
+	private $_p=8;
+
+	/**
+	 * Constructor.
+	 * Initializes the array with an array or an iterable object.
+	 * @param map|array|Iterator|TPriorityMap the intial data. Default is null, meaning no initialization.
+	 * @param boolean whether the list is read-only
+	 * @param numeric the default priority of items without specified priorities.
+	 * @param integer the precision of the numeric 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)
+	{
+		if($data!==null)
+			$this->copyFrom($data);
+		$this->setReadOnly($readOnly);
+		$this->setPrecision($precision);
+		$this->setDefaultPriority($defaultPriority);
+	}
+
+	/**
+	 * @return boolean whether this map is read-only or not. Defaults to false.
+	 */
+	public function getReadOnly()
+	{
+		return $this->_r;
+	}
+
+	/**
+	 * @param boolean whether this list is read-only or not
+	 */
+	protected function setReadOnly($value)
+	{
+		$this->_r=TPropertyValue::ensureBoolean($value);
+	}
+	
+	/**
+	 * @return numeric gets the default priority of inserted items without a specified priority
+	 */
+	public function getDefaultPriority()
+	{
+		return $this->_dp;
+	}
+	
+	/**
+	 * This must be called internally or when instantiated.
+	 * @param numeric sets the default priority of inserted items without a specified priority
+	 */
+	protected function setDefaultPriority($value)
+	{
+		$this->_dp = (string)round(TPropertyValue::ensureFloat($value), $this->_p);
+	}
+	
+	/**
+	 * @return integer The precision of numeric priorities, defaults to 8
+	 */
+	public function getPrecision()
+	{
+		return $this->_p;
+	}
+	
+	/**
+	 * This must be called internally or when instantiated.
+	 * @param integer The precision of numeric priorities.
+	 */
+	protected function setPrecision($value)
+	{
+		$this->_p=TPropertyValue::ensureInteger($value);
+	}
+
+	/**
+	 * Returns an iterator for traversing the items in the map.
+	 * This method is required by the interface IteratorAggregate.
+	 * @return Iterator an iterator for traversing the items in the map.
+	 */
+	public function getIterator()
+	{
+		return new ArrayIterator($this->flattenPriorities());
+	}
+	
+	
+	/**
+	 * Orders the priority list internally.
+	 */
+	protected function sortPriorities() {
+		if(!$this->_o) {
+			ksort($this->_d, SORT_NUMERIC);
+			$this->_o=true;
+		}
+	}
+
+	/**
+	 * This flattens the priority map into a flat array [0,...,n-1]
+	 * @return array array of items in the list in priority and index 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 number of items in the map.
+	 * This method is required by Countable interface.
+	 * @return integer number of items in the map.
+	 */
+	public function count()
+	{
+		return $this->getCount();
+	}
+
+	/**
+	 * @return integer the number of items in the map
+	 */
+	public function getCount()
+	{
+		return $this->_c;
+	}
+	
+	/**
+	 * Gets the number of items at a priority within the map.
+	 * @param numeric optional priority at which to count items.  if no parameter, 
+	 * it will be set to the default {@link getDefaultPriority}
+	 * @return integer the number of items in the map at the specified priority
+	 */
+	public function getPriorityCount($priority=null)
+	{
+		if($priority===null)
+			$priority=$this->getDefaultPriority();
+		$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]);
+	}
+	
+	/**
+	 * This returns a list of the priorities within this map, ordered lowest to highest.
+	 * @return array the array of priority numerics in decreasing priority order
+	 */
+	public function getPriorities()
+	{
+		$this->sortPriorities();
+		return array_keys($this->_d);
+	}
+
+	/**
+	 * Returns the keys within the map ordered through the priority of each key-value pair
+	 * @return array the key list
+	 */
+	public function getKeys()
+	{
+		return array_keys($this->flattenPriorities());
+	}
+
+	/**
+	 * Returns the item with the specified key.  If a priority is specified, only items
+	 * within that specific priority will be selected
+	 * @param mixed the key
+	 * @param mixed the priority.  null is the default priority, false is any priority, 
+	 * and numeric is a specific priority.  default: false, any priority.
+	 * @return mixed the element at the offset, null if no element is found at the offset
+	 */
+	public function itemAt($key,$priority=false)
+	{
+		if($priority===false){
+			$map=$this->flattenPriorities();
+			return isset($map[$key])?$map[$key]:null;
+		} else {
+			if($priority===null)
+				$priority=$this->getDefaultPriority();
+			$priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
+			return (isset($this->_d[$priority])&&isset($this->_d[$priority][$key]))?$this->_d[$priority][$key]:null;
+		}
+	}
+
+	/**
+	 * This changes an item's priority.  Specify the item and the new priority.
+	 * This method is exactly the same as {@link offsetGet}.
+	 * @param mixed the key
+	 * @param numeric|null the priority.  default: null, filled in with the default priority numeric.
+	 * @return numeric old priority of the item
+	 */
+	public function setPriorityAt($key,$priority=null)
+	{
+		if($priority===null)
+			$priority=$this->getDefaultPriority();
+		$priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
+		
+		$oldpriority=$this->priorityAt($key);
+		if($oldpriority!==false&&$oldpriority!=$priority) {
+			$value=$this->remove($key,$oldpriority);
+			$this->add($key,$value,$priority);
+		}
+		return $oldpriority;
+	}
+
+	/**
+	 * Gets all the items at a specific priority.
+	 * @param numeric priority of the items to get.  Defaults to null, filled in with the default priority, if left blank.
+	 * @return array all items at priority in index order, null if there are no items at that priority
+	 */
+	public function itemsAtPriority($priority=null)
+	{
+		if($priority===null)
+			$priority=$this->getDefaultPriority();
+		$priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
+		
+		return isset($this->_d[$priority])?$this->_d[$priority]:null;
+	}
+
+	/**
+	 * Returns the priority of a particular item within the map.  This searches the map for the item.
+	 * @param mixed item to look for within the map
+	 * @return numeric priority of the item in the map
+	 */
+	public function priorityOf($item)
+	{
+		$this->sortPriorities();
+		foreach($this->_d as $priority=>$items)
+			if(($index=array_search($item,$items,true))!==false)
+				return $priority;
+		return false;
+	}
+
+	/**
+	 * Retutrns the priority of an item at a particular flattened index.
+	 * @param integer index of the item within the map
+	 * @return numeric priority of the item in the map
+	 */
+	public function priorityAt($key)
+	{
+		$this->sortPriorities();
+		foreach($this->_d as $priority=>$items)
+			if(array_key_exists($key,$items))
+				return $priority;
+		return false;
+	}
+
+	/**
+	 * Adds an item into the map.  A third parameter may be used to set the priority
+	 * of the item within the map.  Priority is primarily used during when flattening
+	 * the map into an array where order may be and important factor of the key-value
+	 * pairs within the array.
+	 * Note, if the specified key already exists, the old value will be overwritten.
+	 * No duplicate keys are allowed regardless of priority.
+	 * @param mixed key
+	 * @param mixed value
+	 * @param numeric|null priority, default: null, filled in with default priority
+	 * @return numeric priority at which the pair was added
+	 * @throws TInvalidOperationException if the map is read-only
+	 */
+	public function add($key,$value,$priority=null)
+	{
+		if($priority===null)
+			$priority=$this->getDefaultPriority();
+		$priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
+		
+		if(!$this->_r)
+		{
+			foreach($this->_d as $innerpriority=>$items)
+				if(array_key_exists($key,$items))
+				{
+					unset($this->_d[$innerpriority][$key]);
+					$this->_c--;
+					if(count($this->_d[$innerpriority])===0)
+						unset($this->_d[$innerpriority]);
+				}
+			if(!isset($this->_d[$priority])) {
+				$this->_d[$priority]=array($key=>$value);
+				$this->_o=false;
+			}
+			else
+				$this->_d[$priority][$key]=$value;
+			$this->_c++;
+			$this->_fd=null;
+		}
+		else
+			throw new TInvalidOperationException('map_readonly',get_class($this));
+		return $priority;
+	}
+
+	/**
+	 * Removes an item from the map by its key. If no priority, or false, is specified
+	 * then priority is irrelevant. If null is used as a parameter for priority, then
+	 * the priority will be the default priority.  If a priority is specified, or 
+	 * the default priority is specified, only key-value pairs in that priority
+	 * will be affected.
+	 * @param mixed the key of the item to be removed
+	 * @param numeric|false|null priority.  False is any priority, null is the 
+	 * default priority, and numeric is a specific priority
+	 * @return mixed the removed value, null if no such key exists.
+	 * @throws TInvalidOperationException if the map is read-only
+	 */
+	public function remove($key,$priority=false)
+	{
+		if(!$this->_r)
+		{
+			if($priority===null)
+				$priority=$this->getDefaultPriority();
+		
+			if($priority===false)
+			{
+				$this->sortPriorities();
+				foreach($this->_d as $priority=>$items)
+					if(array_key_exists($key,$items))
+					{
+						$value=$this->_d[$priority][$key];
+						unset($this->_d[$priority][$key]);
+						$this->_c--;
+						if(count($this->_d[$priority])===0)
+						{
+							unset($this->_d[$priority]);
+							$this->_o=false;
+						}
+						$this->_fd=null;
+						return $value;
+					}
+				return null;
+			}
+			else
+			{
+				$priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
+				if(isset($this->_d[$priority])&&(isset($this->_d[$priority][$key])||array_key_exists($key,$this->_d[$priority])))
+				{
+					$value=$this->_d[$priority][$key];
+					unset($this->_d[$priority][$key]);
+					$this->_c--;
+					if(count($this->_d[$priority])===0) {
+						unset($this->_d[$priority]);
+						$this->_o=false;
+					}
+					$this->_fd=null;
+					return $value;
+				}
+				else
+					return null;
+			}
+		}
+		else
+			throw new TInvalidOperationException('map_readonly',get_class($this));
+	}
+
+	/**
+	 * Removes all items in the map.  {@link remove} is called on all items.
+	 */
+	public function clear()
+	{
+		foreach($this->_d as $priority=>$items)
+			foreach(array_keys($items) as $key)
+				$this->remove($key);
+	}
+
+	/**
+	 * @param mixed the key
+	 * @return boolean whether the map contains an item with the specified key
+	 */
+	public function contains($key)
+	{
+		$map=$this->flattenPriorities();
+		return isset($map[$key])||array_key_exists($key,$map);
+	}
+
+	/**
+	 * When the map is flattened into an array, the priorities are taken into 
+	 * account and elements of the map are ordered in the array according to 
+	 * their priority.
+	 * @return array the list of items in array
+	 */
+	public function toArray()
+	{
+		return $this->flattenPriorities();
+	}
+
+	/**
+	 * Combines the map elements which have a priority below the parameter value
+	 * @param numeric the cut-off priority.  All items of priority less than this are returned.
+	 * @param boolean whether or not the input cut-off priority is inclusive.  Default: false, not inclusive.
+	 * @return array the array of priorities keys with values of arrays of items that are below a specified priority.  
+	 *  The priorities are sorted so important priorities, lower numerics, are first.
+	 */
+	public function toArrayBelowPriority($priority,$inclusive=false)
+	{
+		$this->sortPriorities();
+		$items=array();
+		foreach($this->_d as $itemspriority=>$itemsatpriority)
+		{
+			if((!$inclusive&&$itemspriority>=$priority)||$itemspriority>$priority)
+				break;
+			$items=array_merge($items,$itemsatpriority);
+		}
+		return $items;
+	}
+
+	/**
+	 * Combines the map elements which have a priority above the parameter value
+	 * @param numeric the cut-off priority.  All items of priority greater than this are returned.
+	 * @param boolean whether or not the input cut-off priority is inclusive.  Default: true, inclusive.
+	 * @return array the array of priorities keys with values of arrays of items that are above a specified priority.  
+	 *  The priorities are sorted so important priorities, lower numerics, are first.
+	 */
+	public function toArrayAbovePriority($priority,$inclusive=true)
+	{
+		$this->sortPriorities();
+		$items=array();
+		foreach($this->_d as $itemspriority=>$itemsatpriority)
+		{
+			if((!$inclusive&&$itemspriority<=$priority)||$itemspriority<$priority)
+				continue;
+			$items=array_merge($items,$itemsatpriority);
+		}
+		return $items;
+	}
+
+	/**
+	 * 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, object implementing 
+	 * Traversable, or a TPriorityMap
+	 * @throws TInvalidDataTypeException If data is neither an array nor an iterator.
+	 */
+	public function copyFrom($data)
+	{
+		if($data instanceof TPriorityMap)
+		{
+			if($this->getCount()>0)
+				$this->clear();
+			foreach($data->getPriorities() as $priority) {
+				foreach($data->itemsAtPriority($priority) as $key => $value) {
+					$this->add($key,$value,$priority);
+				}
+			}
+		}
+		else if(is_array($data)||$data instanceof Traversable)
+		{
+			if($this->getCount()>0)
+				$this->clear();
+			foreach($data as $key=>$value)
+				$this->add($key,$value);
+		}
+		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, object implementing 
+	 * Traversable, or a TPriorityMap
+	 * @throws TInvalidDataTypeException If data is neither an array nor an iterator.
+	 */
+	public function mergeWith($data)
+	{
+		if($data instanceof TPriorityMap)
+		{
+			foreach($data->getPriorities() as $priority)
+			{
+				foreach($data->itemsAtPriority($priority) as $key => $value)
+					$this->add($key,$value,$priority);
+			}
+		}
+		else if(is_array($data)||$data instanceof Traversable)
+		{
+			foreach($data as $key=>$value)
+				$this->add($key,$value);
+		}
+		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 $this->contains($offset);
+	}
+
+	/**
+	 * 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)
+	{
+		$this->add($offset,$item);
+	}
+
+	/**
+	 * 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->remove($offset);
+	}
+}
\ No newline at end of file