git.sur5r.net Git - bacula/bacula/blob - gui/baculum/framework/Collections/TPriorityMap.php

   1 <?php
   2 /**
   3  * TPriorityMap, TPriorityMapIterator classes
   4  *
   5  * @author Brad Anderson <javalizard@mac.com>
   6  * @link http://www.pradosoft.com/
   7  * @copyright Copyright &copy; 2005-2014 PradoSoft
   8  * @license http://www.pradosoft.com/license/
   9  * @package System.Collections
  10  */
  11
  12 /**
  13  * TPriorityMap class
  14  *
  15  * TPriorityMap implements a collection that takes key-value pairs with
  16  * a priority to allow key-value pairs to be ordered.  This ordering is
  17  * important when flattening the map. When flattening the map, if some
  18  * key-value pairs are required to be before or after others, use this
  19  * class to keep order to your map.
  20  *
  21  * You can access, add or remove an item with a key by using
  22  * {@link itemAt}, {@link add}, and {@link remove}.  These functions
  23  * can optionally take a priority parameter to allow access to specific
  24  * priorities.  TPriorityMap is functionally backward compatible
  25  * with {@link TMap}.
  26  *
  27  * To get the number of the items in the map, use {@link getCount}.
  28  * TPriorityMap can also be used like a regular array as follows,
  29  * <code>
  30  * $map[$key]=$value; // add a key-value pair
  31  * unset($map[$key]); // remove the value with the specified key
  32  * if(isset($map[$key])) // if the map contains the key
  33  * foreach($map as $key=>$value) // traverse the items in the map
  34  * $n=count($map);  // returns the number of items in the map
  35  * </code>
  36  * Using standard array access method like these will always use
  37  * the default priority.
  38  *
  39  * An item that doesn't specify a priority will receive the default
  40  * priority.  The default priority is set during the instantiation
  41  * of a new TPriorityMap. If no custom default priority is specified,
  42  * the standard default priority of 10 is used.
  43  *
  44  * Priorities with significant digits below precision will be rounded.
  45  *
  46  * A priority may also be a numeric with decimals.  This is set
  47  * during the instantiation of a new TPriorityMap.
  48  * The default is 8 decimal places for a priority.  If a negative number
  49  * is used, rounding occurs into the integer space rather than in
  50  * the decimal space.  See {@link round}.
  51  *
  52  * @author Brad Anderson <javalizard@mac.com>
  53  * @package System.Collections
  54  * @since 3.2a
  55  */
  56 Prado::using('System.Collections.TMap');
  57
  58 class TPriorityMap extends TMap
  59 {
  60         /**
  61          * @var array internal data storage
  62          */
  63         private $_d=array();
  64         /**
  65          * @var boolean whether this list is read-only
  66          */
  67         private $_r=false;
  68         /**
  69          * @var boolean indicates if the _d is currently ordered.
  70          */
  71         private $_o=false;
  72         /**
  73          * @var array cached flattened internal data storage
  74          */
  75         private $_fd=null;
  76         /**
  77          * @var integer number of items contain within the map
  78          */
  79         private $_c=0;
  80         /**
  81          * @var numeric the default priority of items without specified priorities
  82          */
  83         private $_dp=10;
  84         /**
  85          * @var integer the precision of the numeric priorities within this priority list.
  86          */
  87         private $_p=8;
  88
  89         /**
  90          * Constructor.
  91          * Initializes the array with an array or an iterable object.
  92          * @param map|array|Iterator|TPriorityMap the intial data. Default is null, meaning no initialization.
  93          * @param boolean whether the list is read-only
  94          * @param numeric the default priority of items without specified priorities.
  95          * @param integer the precision of the numeric priorities
  96          * @throws TInvalidDataTypeException If data is not null and neither an array nor an iterator.
  97          */
  98         public function __construct($data=null,$readOnly=false,$defaultPriority=10,$precision=8)
  99         {
 100                 if($data!==null)
 101                         $this->copyFrom($data);
 102                 $this->setReadOnly($readOnly);
 103                 $this->setPrecision($precision);
 104                 $this->setDefaultPriority($defaultPriority);
 105         }
 106
 107         /**
 108          * @return boolean whether this map is read-only or not. Defaults to false.
 109          */
 110         public function getReadOnly()
 111         {
 112                 return $this->_r;
 113         }
 114
 115         /**
 116          * @param boolean whether this list is read-only or not
 117          */
 118         protected function setReadOnly($value)
 119         {
 120                 $this->_r=TPropertyValue::ensureBoolean($value);
 121         }
 122
 123         /**
 124          * @return numeric gets the default priority of inserted items without a specified priority
 125          */
 126         public function getDefaultPriority()
 127         {
 128                 return $this->_dp;
 129         }
 130
 131         /**
 132          * This must be called internally or when instantiated.
 133          * @param numeric sets the default priority of inserted items without a specified priority
 134          */
 135         protected function setDefaultPriority($value)
 136         {
 137                 $this->_dp = (string)round(TPropertyValue::ensureFloat($value), $this->_p);
 138         }
 139
 140         /**
 141          * @return integer The precision of numeric priorities, defaults to 8
 142          */
 143         public function getPrecision()
 144         {
 145                 return $this->_p;
 146         }
 147
 148         /**
 149          * This must be called internally or when instantiated.
 150          * @param integer The precision of numeric priorities.
 151          */
 152         protected function setPrecision($value)
 153         {
 154                 $this->_p=TPropertyValue::ensureInteger($value);
 155         }
 156
 157         /**
 158          * Returns an iterator for traversing the items in the map.
 159          * This method is required by the interface IteratorAggregate.
 160          * @return Iterator an iterator for traversing the items in the map.
 161          */
 162         public function getIterator()
 163         {
 164                 return new ArrayIterator($this->flattenPriorities());
 165         }
 166
 167
 168         /**
 169          * Orders the priority list internally.
 170          */
 171         protected function sortPriorities() {
 172                 if(!$this->_o) {
 173                         ksort($this->_d, SORT_NUMERIC);
 174                         $this->_o=true;
 175                 }
 176         }
 177
 178         /**
 179          * This flattens the priority map into a flat array [0,...,n-1]
 180          * @return array array of items in the list in priority and index order
 181          */
 182         protected function flattenPriorities() {
 183                 if(is_array($this->_fd))
 184                         return $this->_fd;
 185
 186                 $this->sortPriorities();
 187                 $this->_fd = array();
 188                 foreach($this->_d as $priority => $itemsatpriority)
 189                         $this->_fd = array_merge($this->_fd, $itemsatpriority);
 190                 return $this->_fd;
 191         }
 192
 193         /**
 194          * Returns the number of items in the map.
 195          * This method is required by Countable interface.
 196          * @return integer number of items in the map.
 197          */
 198         public function count()
 199         {
 200                 return $this->getCount();
 201         }
 202
 203         /**
 204          * @return integer the number of items in the map
 205          */
 206         public function getCount()
 207         {
 208                 return $this->_c;
 209         }
 210
 211         /**
 212          * Gets the number of items at a priority within the map.
 213          * @param numeric optional priority at which to count items.  if no parameter,
 214          * it will be set to the default {@link getDefaultPriority}
 215          * @return integer the number of items in the map at the specified priority
 216          */
 217         public function getPriorityCount($priority=null)
 218         {
 219                 if($priority===null)
 220                         $priority=$this->getDefaultPriority();
 221                 $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 222
 223                 if(!isset($this->_d[$priority])||!is_array($this->_d[$priority]))
 224                         return false;
 225                 return count($this->_d[$priority]);
 226         }
 227
 228         /**
 229          * This returns a list of the priorities within this map, ordered lowest to highest.
 230          * @return array the array of priority numerics in decreasing priority order
 231          */
 232         public function getPriorities()
 233         {
 234                 $this->sortPriorities();
 235                 return array_keys($this->_d);
 236         }
 237
 238         /**
 239          * Returns the keys within the map ordered through the priority of each key-value pair
 240          * @return array the key list
 241          */
 242         public function getKeys()
 243         {
 244                 return array_keys($this->flattenPriorities());
 245         }
 246
 247         /**
 248          * Returns the item with the specified key.  If a priority is specified, only items
 249          * within that specific priority will be selected
 250          * @param mixed the key
 251          * @param mixed the priority.  null is the default priority, false is any priority,
 252          * and numeric is a specific priority.  default: false, any priority.
 253          * @return mixed the element at the offset, null if no element is found at the offset
 254          */
 255         public function itemAt($key,$priority=false)
 256         {
 257                 if($priority===false){
 258                         $map=$this->flattenPriorities();
 259                         return isset($map[$key])?$map[$key]:null;
 260                 } else {
 261                         if($priority===null)
 262                                 $priority=$this->getDefaultPriority();
 263                         $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 264                         return (isset($this->_d[$priority])&&isset($this->_d[$priority][$key]))?$this->_d[$priority][$key]:null;
 265                 }
 266         }
 267
 268         /**
 269          * This changes an item's priority.  Specify the item and the new priority.
 270          * This method is exactly the same as {@link offsetGet}.
 271          * @param mixed the key
 272          * @param numeric|null the priority.  default: null, filled in with the default priority numeric.
 273          * @return numeric old priority of the item
 274          */
 275         public function setPriorityAt($key,$priority=null)
 276         {
 277                 if($priority===null)
 278                         $priority=$this->getDefaultPriority();
 279                 $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 280
 281                 $oldpriority=$this->priorityAt($key);
 282                 if($oldpriority!==false&&$oldpriority!=$priority) {
 283                         $value=$this->remove($key,$oldpriority);
 284                         $this->add($key,$value,$priority);
 285                 }
 286                 return $oldpriority;
 287         }
 288
 289         /**
 290          * Gets all the items at a specific priority.
 291          * @param numeric priority of the items to get.  Defaults to null, filled in with the default priority, if left blank.
 292          * @return array all items at priority in index order, null if there are no items at that priority
 293          */
 294         public function itemsAtPriority($priority=null)
 295         {
 296                 if($priority===null)
 297                         $priority=$this->getDefaultPriority();
 298                 $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 299
 300                 return isset($this->_d[$priority])?$this->_d[$priority]:null;
 301         }
 302
 303         /**
 304          * Returns the priority of a particular item within the map.  This searches the map for the item.
 305          * @param mixed item to look for within the map
 306          * @return numeric priority of the item in the map
 307          */
 308         public function priorityOf($item)
 309         {
 310                 $this->sortPriorities();
 311                 foreach($this->_d as $priority=>$items)
 312                         if(($index=array_search($item,$items,true))!==false)
 313                                 return $priority;
 314                 return false;
 315         }
 316
 317         /**
 318          * Retutrns the priority of an item at a particular flattened index.
 319          * @param integer index of the item within the map
 320          * @return numeric priority of the item in the map
 321          */
 322         public function priorityAt($key)
 323         {
 324                 $this->sortPriorities();
 325                 foreach($this->_d as $priority=>$items)
 326                         if(array_key_exists($key,$items))
 327                                 return $priority;
 328                 return false;
 329         }
 330
 331         /**
 332          * Adds an item into the map.  A third parameter may be used to set the priority
 333          * of the item within the map.  Priority is primarily used during when flattening
 334          * the map into an array where order may be and important factor of the key-value
 335          * pairs within the array.
 336          * Note, if the specified key already exists, the old value will be overwritten.
 337          * No duplicate keys are allowed regardless of priority.
 338          * @param mixed key
 339          * @param mixed value
 340          * @param numeric|null priority, default: null, filled in with default priority
 341          * @return numeric priority at which the pair was added
 342          * @throws TInvalidOperationException if the map is read-only
 343          */
 344         public function add($key,$value,$priority=null)
 345         {
 346                 if($priority===null)
 347                         $priority=$this->getDefaultPriority();
 348                 $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 349
 350                 if(!$this->_r)
 351                 {
 352                         foreach($this->_d as $innerpriority=>$items)
 353                                 if(array_key_exists($key,$items))
 354                                 {
 355                                         unset($this->_d[$innerpriority][$key]);
 356                                         $this->_c--;
 357                                         if(count($this->_d[$innerpriority])===0)
 358                                                 unset($this->_d[$innerpriority]);
 359                                 }
 360                         if(!isset($this->_d[$priority])) {
 361                                 $this->_d[$priority]=array($key=>$value);
 362                                 $this->_o=false;
 363                         }
 364                         else
 365                                 $this->_d[$priority][$key]=$value;
 366                         $this->_c++;
 367                         $this->_fd=null;
 368                 }
 369                 else
 370                         throw new TInvalidOperationException('map_readonly',get_class($this));
 371                 return $priority;
 372         }
 373
 374         /**
 375          * Removes an item from the map by its key. If no priority, or false, is specified
 376          * then priority is irrelevant. If null is used as a parameter for priority, then
 377          * the priority will be the default priority.  If a priority is specified, or
 378          * the default priority is specified, only key-value pairs in that priority
 379          * will be affected.
 380          * @param mixed the key of the item to be removed
 381          * @param numeric|false|null priority.  False is any priority, null is the
 382          * default priority, and numeric is a specific priority
 383          * @return mixed the removed value, null if no such key exists.
 384          * @throws TInvalidOperationException if the map is read-only
 385          */
 386         public function remove($key,$priority=false)
 387         {
 388                 if(!$this->_r)
 389                 {
 390                         if($priority===null)
 391                                 $priority=$this->getDefaultPriority();
 392
 393                         if($priority===false)
 394                         {
 395                                 $this->sortPriorities();
 396                                 foreach($this->_d as $priority=>$items)
 397                                         if(array_key_exists($key,$items))
 398                                         {
 399                                                 $value=$this->_d[$priority][$key];
 400                                                 unset($this->_d[$priority][$key]);
 401                                                 $this->_c--;
 402                                                 if(count($this->_d[$priority])===0)
 403                                                 {
 404                                                         unset($this->_d[$priority]);
 405                                                         $this->_o=false;
 406                                                 }
 407                                                 $this->_fd=null;
 408                                                 return $value;
 409                                         }
 410                                 return null;
 411                         }
 412                         else
 413                         {
 414                                 $priority=(string)round(TPropertyValue::ensureFloat($priority),$this->_p);
 415                                 if(isset($this->_d[$priority])&&(isset($this->_d[$priority][$key])||array_key_exists($key,$this->_d[$priority])))
 416                                 {
 417                                         $value=$this->_d[$priority][$key];
 418                                         unset($this->_d[$priority][$key]);
 419                                         $this->_c--;
 420                                         if(count($this->_d[$priority])===0) {
 421                                                 unset($this->_d[$priority]);
 422                                                 $this->_o=false;
 423                                         }
 424                                         $this->_fd=null;
 425                                         return $value;
 426                                 }
 427                                 else
 428                                         return null;
 429                         }
 430                 }
 431                 else
 432                         throw new TInvalidOperationException('map_readonly',get_class($this));
 433         }
 434
 435         /**
 436          * Removes all items in the map.  {@link remove} is called on all items.
 437          */
 438         public function clear()
 439         {
 440                 foreach($this->_d as $priority=>$items)
 441                         foreach(array_keys($items) as $key)
 442                                 $this->remove($key);
 443         }
 444
 445         /**
 446          * @param mixed the key
 447          * @return boolean whether the map contains an item with the specified key
 448          */
 449         public function contains($key)
 450         {
 451                 $map=$this->flattenPriorities();
 452                 return isset($map[$key])||array_key_exists($key,$map);
 453         }
 454
 455         /**
 456          * When the map is flattened into an array, the priorities are taken into
 457          * account and elements of the map are ordered in the array according to
 458          * their priority.
 459          * @return array the list of items in array
 460          */
 461         public function toArray()
 462         {
 463                 return $this->flattenPriorities();
 464         }
 465
 466         /**
 467          * Combines the map elements which have a priority below the parameter value
 468          * @param numeric the cut-off priority.  All items of priority less than this are returned.
 469          * @param boolean whether or not the input cut-off priority is inclusive.  Default: false, not inclusive.
 470          * @return array the array of priorities keys with values of arrays of items that are below a specified priority.
 471          *  The priorities are sorted so important priorities, lower numerics, are first.
 472          */
 473         public function toArrayBelowPriority($priority,$inclusive=false)
 474         {
 475                 $this->sortPriorities();
 476                 $items=array();
 477                 foreach($this->_d as $itemspriority=>$itemsatpriority)
 478                 {
 479                         if((!$inclusive&&$itemspriority>=$priority)||$itemspriority>$priority)
 480                                 break;
 481                         $items=array_merge($items,$itemsatpriority);
 482                 }
 483                 return $items;
 484         }
 485
 486         /**
 487          * Combines the map elements which have a priority above the parameter value
 488          * @param numeric the cut-off priority.  All items of priority greater than this are returned.
 489          * @param boolean whether or not the input cut-off priority is inclusive.  Default: true, inclusive.
 490          * @return array the array of priorities keys with values of arrays of items that are above a specified priority.
 491          *  The priorities are sorted so important priorities, lower numerics, are first.
 492          */
 493         public function toArrayAbovePriority($priority,$inclusive=true)
 494         {
 495                 $this->sortPriorities();
 496                 $items=array();
 497                 foreach($this->_d as $itemspriority=>$itemsatpriority)
 498                 {
 499                         if((!$inclusive&&$itemspriority<=$priority)||$itemspriority<$priority)
 500                                 continue;
 501                         $items=array_merge($items,$itemsatpriority);
 502                 }
 503                 return $items;
 504         }
 505
 506         /**
 507          * Copies iterable data into the map.
 508          * Note, existing data in the map will be cleared first.
 509          * @param mixed the data to be copied from, must be an array, object implementing
 510          * Traversable, or a TPriorityMap
 511          * @throws TInvalidDataTypeException If data is neither an array nor an iterator.
 512          */
 513         public function copyFrom($data)
 514         {
 515                 if($data instanceof TPriorityMap)
 516                 {
 517                         if($this->getCount()>0)
 518                                 $this->clear();
 519                         foreach($data->getPriorities() as $priority) {
 520                                 foreach($data->itemsAtPriority($priority) as $key => $value) {
 521                                         $this->add($key,$value,$priority);
 522                                 }
 523                         }
 524                 }
 525                 else if(is_array($data)||$data instanceof Traversable)
 526                 {
 527                         if($this->getCount()>0)
 528                                 $this->clear();
 529                         foreach($data as $key=>$value)
 530                                 $this->add($key,$value);
 531                 }
 532                 else if($data!==null)
 533                         throw new TInvalidDataTypeException('map_data_not_iterable');
 534         }
 535
 536         /**
 537          * Merges iterable data into the map.
 538          * Existing data in the map will be kept and overwritten if the keys are the same.
 539          * @param mixed the data to be merged with, must be an array, object implementing
 540          * Traversable, or a TPriorityMap
 541          * @throws TInvalidDataTypeException If data is neither an array nor an iterator.
 542          */
 543         public function mergeWith($data)
 544         {
 545                 if($data instanceof TPriorityMap)
 546                 {
 547                         foreach($data->getPriorities() as $priority)
 548                         {
 549                                 foreach($data->itemsAtPriority($priority) as $key => $value)
 550                                         $this->add($key,$value,$priority);
 551                         }
 552                 }
 553                 else if(is_array($data)||$data instanceof Traversable)
 554                 {
 555                         foreach($data as $key=>$value)
 556                                 $this->add($key,$value);
 557                 }
 558                 else if($data!==null)
 559                         throw new TInvalidDataTypeException('map_data_not_iterable');
 560         }
 561
 562         /**
 563          * Returns whether there is an element at the specified offset.
 564          * This method is required by the interface ArrayAccess.
 565          * @param mixed the offset to check on
 566          * @return boolean
 567          */
 568         public function offsetExists($offset)
 569         {
 570                 return $this->contains($offset);
 571         }
 572
 573         /**
 574          * Returns the element at the specified offset.
 575          * This method is required by the interface ArrayAccess.
 576          * @param integer the offset to retrieve element.
 577          * @return mixed the element at the offset, null if no element is found at the offset
 578          */
 579         public function offsetGet($offset)
 580         {
 581                 return $this->itemAt($offset);
 582         }
 583
 584         /**
 585          * Sets the element at the specified offset.
 586          * This method is required by the interface ArrayAccess.
 587          * @param integer the offset to set element
 588          * @param mixed the element value
 589          */
 590         public function offsetSet($offset,$item)
 591         {
 592                 $this->add($offset,$item);
 593         }
 594
 595         /**
 596          * Unsets the element at the specified offset.
 597          * This method is required by the interface ArrayAccess.
 598          * @param mixed the offset to unset element
 599          */
 600         public function offsetUnset($offset)
 601         {
 602                 $this->remove($offset);
 603         }
 604 }