Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
44 / 44
100.00% covered (success)
100.00%
9 / 9
 CRAP
100.00% covered (success)
100.00%
1 / 1
CollectionIndexed
100.00% covered (success)
100.00%
44 / 44
100.00% covered (success)
100.00%
9 / 9
 17
100.00% covered (success)
100.00%
1 / 1
 __construct
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
 2
 setIndex
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 1
 trimIndex
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
 delete
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
 1
 shuffleIndices
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 6
 add
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 1
 update
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
 1
 compareIndices
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 getIndex
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 3
1<?php
2
3/**
4 * @author: Doug Wilbourne (dougwilbourne@gmail.com)
5 */
6
7declare(strict_types=1);
8
9namespace pvc\struct\collection;
10
11use pvc\interfaces\struct\collection\CollectionInterface;
12use pvc\interfaces\struct\collection\IndexedElementInterface;
13use pvc\struct\collection\err\InvalidKeyException;
14use pvc\struct\collection\err\NonExistentKeyException;
15
16/**
17 * Class CollectionIndexed
18 *
19 * elements in an ordered collection must have a getter called getIndex.  That value is used to order the elements
20 * prior to returning them via get elements.  You can get the index of an element via its key.  You can also set the
21 * index of an element via its key and all the other elements in the collection will have their indices updated
22 * accordingly.
23 *
24 * @template ElementType of IndexedElementInterface
25 * @extends Collection<ElementType>
26 * @implements CollectionInterface<ElementType>
27 */
28class CollectionIndexed extends Collection implements CollectionInterface
29{
30    private const int SHUFFLE_UP = 1;
31    private const int SHUFFLE_DOWN = -1;
32
33    /**
34     * @var callable(ElementType, ElementType):int
35     * used by getElements to return the elements in order of index
36     */
37    protected $comparator;
38
39    /**
40     * @param array<non-negative-int, ElementType> $array
41     */
42    public function __construct(array $array = [])
43    {
44        $comparator = function($a, $b) {
45            /**
46             * @var ElementType $a
47             * @var ElementType $b
48             */
49            return $a->getIndex() <=> $b->getIndex();
50        };
51        parent::__construct($array, $comparator);
52
53        /**
54         * do not assume that the indices of the elements being imported are continuously ascending starting at 0.
55         */
56        $this->iterator->uasort($this->comparator);
57
58        /**
59         * renumber the indices
60         */
61        $i = 0;
62        foreach ($this->iterator as $element) {
63            $element->setIndex($i++);
64        }
65    }
66
67    /**
68     * setIndex allows you to move an existing element from one ordinal position in the collection to another.
69     *
70     * If $newIndex is greater than the largest index in the collection, then we adjust it to be the last index in
71     * the collection.  If $newIndex < 0, set it to 0.
72     *
73     * Rather than explicitly shuffling some indices down and some indices up, this algorithm just deletes the
74     * element and adds it back with the new index.
75     *
76     * @param non-negative-int $key
77     * @param non-negative-int $newIndex
78     */
79    public function setIndex(int $key, int $newIndex): void
80    {
81        $element = $this->getElement($key);
82
83        /**
84         * we know that there is at least one element in the collection because $key has been validated
85         * and $element is set, but the static analyzer does not.  It thinks that count() could be 0 and therefore
86         * $maxIndex could potentially be -1
87         */
88        $maxIndex = max(0, $this->count() - 1);
89
90        /**
91         * 'trim' the new index first
92         */
93        $newNewIndex = $this->trimIndex($maxIndex, $newIndex);
94
95        $this->delete($key);
96        $element->setIndex($newIndex);
97
98        /**
99         * the add method sorts the elements array by index so we do not need to call it separately
100         */
101        $this->add($key, $element);
102    }
103
104    /**
105     * @param non-negative-int $proposedIndex
106     * @param non-negative-int $maxIndex
107     * @return non-negative-int
108     *
109     * the add method and the setIndex method both need to ensure that the proposed index of the element is >= 0.
110     * If we are adding an element, the max index value is count(). If we are setting the index of an existing
111     * element to a new value, the max index value is count() - 1.
112     */
113    private function trimIndex(int $proposedIndex, int $maxIndex): int
114    {
115        $proposedIndex = max($proposedIndex, 0);
116        return min($proposedIndex, $maxIndex);
117    }
118
119    /**
120     * delete
121     * @param non-negative-int $key
122     *
123     * note that we do not need to sort the elements array after deleting an element - it is already in order.
124     */
125    public function delete(int $key): void
126    {
127        $existingIndex = $this->getElement($key)->getIndex();
128        parent::delete($key);
129        $this->shuffleIndices($existingIndex, self::SHUFFLE_DOWN);
130    }
131
132    /**
133     * @param non-negative-int $startIndex
134     * @param int<-1, 1> $direction
135     * @return void
136     */
137    private function shuffleIndices(int $startIndex, int $direction): void
138    {
139        foreach ($this->iterator as $element) {
140            $existingIndex = $element->getIndex();
141            $newIndex = max(0, $existingIndex + $direction);
142
143            if (
144                /**
145                 * make space before adding a new element at $startIndex
146                 */
147                ($direction == self::SHUFFLE_UP && $existingIndex >= $startIndex) ||
148                /**
149                 * remove space after deleting an element at $startIndex
150                 */
151                ($direction == self::SHUFFLE_DOWN && $existingIndex > $startIndex)
152            ) {
153                $element->setIndex($newIndex);
154            }
155        }
156    }
157
158    /**
159     * add
160     * @param non-negative-int $key
161     * @param ElementType $element
162     * @throws InvalidKeyException
163     *
164     * in order to keep the elements array in the proper order, we need to sort it by index so that iteration
165     * happens in the proper order
166     */
167    public function add(int $key, $element): void
168    {
169        /**
170         * 'trim' the index of the element first
171         */
172        $maxIndex = $this->count();
173        $index = $this->trimIndex($element->getIndex(), $maxIndex);
174        $element->setIndex($index);
175
176        /**
177         * shuffle the other indices before we add the element
178         */
179        $this->shuffleIndices($element->getIndex(), self::SHUFFLE_UP);
180
181        /**
182         * add and then sort the collection
183         */
184        parent::add($key, $element);
185        $this->iterator->uasort([$this, 'compareIndices']);
186    }
187
188    /**
189     * @param non-negative-int $key
190     * @param $element
191     * @return void
192     * @throws InvalidKeyException
193     *
194     * This method will reorder the collection if the index of $element has changed from the prior value of
195     * the index of the element with the same key
196     */
197    public function update(int $key, $element): void
198    {
199        $oldIndex = $this->getElement($key)->getIndex();
200        $newIndex = $element->getIndex();
201        $element->setIndex($oldIndex);
202        parent::update($key, $element);
203        $this->setIndex($key, $newIndex);
204    }
205
206    /**
207     * @param ElementType $a
208     * @param ElementType $b
209     * @return int
210     */
211    protected function compareIndices(mixed $a, mixed $b): int
212    {
213        return $a->getIndex() <=> $b->getIndex();
214    }
215
216    /**
217     * getIndex returns the index which corresponds to $key
218     *
219     * @param non-negative-int $key
220     * @return non-negative-int
221     */
222    public function getIndex(int $key): int
223    {
224        if (!$this->validateKey($key)) {
225            throw new InvalidKeyException($key);
226        }
227        if (!$this->validateExistingKey($key)) {
228            throw new NonExistentKeyException($key);
229        }
230        $element = $this->getElement($key);
231        assert(!is_null($element));
232        return $element->getIndex();
233    }
234}