OrderedHashMap.php 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174
  1. <?php
  2. /*
  3. * This file is part of the Symfony package.
  4. *
  5. * (c) Fabien Potencier <fabien@symfony.com>
  6. *
  7. * For the full copyright and license information, please view the LICENSE
  8. * file that was distributed with this source code.
  9. */
  10. namespace Symfony\Component\Form\Util;
  11. /**
  12. * A hash map which keeps track of deletions and additions.
  13. *
  14. * Like in associative arrays, elements can be mapped to integer or string keys.
  15. * Unlike associative arrays, the map keeps track of the order in which keys
  16. * were added and removed. This order is reflected during iteration.
  17. *
  18. * The map supports concurrent modification during iteration. That means that
  19. * you can insert and remove elements from within a foreach loop and the
  20. * iterator will reflect those changes accordingly.
  21. *
  22. * While elements that are added during the loop are recognized by the iterator,
  23. * changed elements are not. Otherwise the loop could be infinite if each loop
  24. * changes the current element:
  25. *
  26. * $map = new OrderedHashMap();
  27. * $map[1] = 1;
  28. * $map[2] = 2;
  29. * $map[3] = 3;
  30. *
  31. * foreach ($map as $index => $value) {
  32. * echo "$index: $value\n"
  33. * if (1 === $index) {
  34. * $map[1] = 4;
  35. * $map[] = 5;
  36. * }
  37. * }
  38. *
  39. * print_r(iterator_to_array($map));
  40. *
  41. * // => 1: 1
  42. * // 2: 2
  43. * // 3: 3
  44. * // 4: 5
  45. * // Array
  46. * // (
  47. * // [1] => 4
  48. * // [2] => 2
  49. * // [3] => 3
  50. * // [4] => 5
  51. * // )
  52. *
  53. * The map also supports multiple parallel iterators. That means that you can
  54. * nest foreach loops without affecting each other's iteration:
  55. *
  56. * foreach ($map as $index => $value) {
  57. * foreach ($map as $index2 => $value2) {
  58. * // ...
  59. * }
  60. * }
  61. *
  62. * @author Bernhard Schussek <bschussek@gmail.com>
  63. */
  64. class OrderedHashMap implements \ArrayAccess, \IteratorAggregate, \Countable
  65. {
  66. /**
  67. * The elements of the map, indexed by their keys.
  68. *
  69. * @var array
  70. */
  71. private $elements = [];
  72. /**
  73. * The keys of the map in the order in which they were inserted or changed.
  74. *
  75. * @var array
  76. */
  77. private $orderedKeys = [];
  78. /**
  79. * References to the cursors of all open iterators.
  80. *
  81. * @var array
  82. */
  83. private $managedCursors = [];
  84. /**
  85. * Creates a new map.
  86. *
  87. * @param array $elements The elements to insert initially
  88. */
  89. public function __construct(array $elements = [])
  90. {
  91. $this->elements = $elements;
  92. $this->orderedKeys = array_keys($elements);
  93. }
  94. /**
  95. * @return bool
  96. */
  97. public function offsetExists($key)
  98. {
  99. return isset($this->elements[$key]);
  100. }
  101. /**
  102. * {@inheritdoc}
  103. */
  104. public function offsetGet($key)
  105. {
  106. if (!isset($this->elements[$key])) {
  107. throw new \OutOfBoundsException(sprintf('The offset "%s" does not exist.', $key));
  108. }
  109. return $this->elements[$key];
  110. }
  111. /**
  112. * {@inheritdoc}
  113. */
  114. public function offsetSet($key, $value)
  115. {
  116. if (null === $key || !isset($this->elements[$key])) {
  117. if (null === $key) {
  118. $key = [] === $this->orderedKeys
  119. // If the array is empty, use 0 as key
  120. ? 0
  121. // Imitate PHP behavior of generating a key that equals
  122. // the highest existing integer key + 1
  123. : 1 + (int) max($this->orderedKeys);
  124. }
  125. $this->orderedKeys[] = (string) $key;
  126. }
  127. $this->elements[$key] = $value;
  128. }
  129. /**
  130. * {@inheritdoc}
  131. */
  132. public function offsetUnset($key)
  133. {
  134. if (false !== ($position = array_search((string) $key, $this->orderedKeys))) {
  135. array_splice($this->orderedKeys, $position, 1);
  136. unset($this->elements[$key]);
  137. foreach ($this->managedCursors as $i => $cursor) {
  138. if ($cursor >= $position) {
  139. --$this->managedCursors[$i];
  140. }
  141. }
  142. }
  143. }
  144. /**
  145. * @return \Traversable
  146. */
  147. public function getIterator()
  148. {
  149. return new OrderedHashMapIterator($this->elements, $this->orderedKeys, $this->managedCursors);
  150. }
  151. /**
  152. * @return int
  153. */
  154. public function count()
  155. {
  156. return \count($this->elements);
  157. }
  158. }