Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
95.24% covered (success)
95.24%
40 / 42
88.89% covered (warning)
88.89%
8 / 9
 CRAP
0.00% covered (danger)
0.00%
0 / 1
IndexedCollection
95.24% covered (success)
95.24%
40 / 42
88.89% covered (warning)
88.89%
8 / 9
 16
0.00% covered (danger)
0.00%
0 / 1
 __construct
81.82% covered (warning)
81.82%
9 / 11
0.00% covered (danger)
0.00%
0 / 1
 2.02
 setComparator
100.00% covered (success)
100.00%
1 / 1
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
 getIndex
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
 setIndex
100.00% covered (success)
100.00%
6 / 6
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%
8 / 8
100.00% covered (success)
100.00%
1 / 1
 6
 add
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 2
 update
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 1
1<?php
2
3/**
4 * @author: Doug Wilbourne (dougwilbourne@gmail.com)
5 */
6
7declare(strict_types=1);
8
9namespace pvc\struct\collection;
10
11use ArrayIterator;
12use pvc\interfaces\struct\collection\IndexedCollectionInterface;
13use pvc\interfaces\struct\collection\IndexedElementInterface;
14use pvc\struct\collection\err\ComparatorException;
15use pvc\struct\types\err\InvalidKeyException;
16use pvc\struct\types\err\InvalidValueException;
17use Throwable;
18
19/**
20 * Class CollectionOrderedByIndex
21 *
22 * @template KeyType of array-key
23 * @template ElementType of IndexedElementInterface
24 * @extends Collection<KeyType, ElementType>
25 * @implements IndexedCollectionInterface<KeyType, ElementType>
26 *
27 * this collection requires that its elements be objects and have getIndex
28 * and setIndex methods to allow keeping the elements in order according
29 * to the index property of each element (and to persist that order).
30 *
31 * The comparator in this class is immutable.
32 *
33 */
34class IndexedCollection extends Collection implements IndexedCollectionInterface
35{
36    private const int SHUFFLE_UP = 1;
37    private const int SHUFFLE_DOWN = -1;
38
39    /**
40     * @param  ?ArrayIterator<KeyType, ElementType>  $iterator
41     */
42    public function __construct(?ArrayIterator $iterator = null)
43    {
44        parent::__construct($iterator);
45
46        /**
47         * setting the comparator will sort the internal array
48         */
49        $comparator = function (
50            IndexedElementInterface $a,
51            IndexedElementInterface $b
52        ): int {
53            return $a->getIndex() <=> $b->getIndex();
54        };
55        parent::setComparator($comparator);
56
57        /**
58         * Do not assume $array is properly indexed - reindex it
59         */
60        $i = 0;
61        foreach ($this as $element) {
62            $element->setIndex($i++);
63        }
64    }
65
66    public function setComparator($comparator): void
67    {
68        /**
69         * this method should not be used in this class
70         */
71        throw new ComparatorException();
72    }
73
74    /**
75     * @param  non-negative-int  $proposedIndex
76     * @param  non-negative-int  $maxIndex
77     *
78     * @return non-negative-int
79     *
80     * there are several methods where we need to ensure the index argument
81     * is between 0 and maxIndex.  It is (count - 1) when we are looking for
82     * something and count when we are adding something
83     */
84    protected function trimIndex(int $proposedIndex, int $maxIndex): int
85    {
86        $proposedIndex = max($proposedIndex, 0);
87        return min($proposedIndex, $maxIndex);
88    }
89
90    public function getIndex($key): int
91    {
92        $this->validateExistingKey($key);
93        return $this->getElement($key)->getIndex();
94    }
95
96    /**
97     * setIndex allows you to move an existing element from one ordinal position in the collection to another.
98     *
99     * this method only does something if the $ordered flag is true
100     *
101     * If $newIndex is greater than the largest index in the collection, then we adjust it to be the last index in
102     * the collection.  If $newIndex < 0, set it to 0.
103     *
104     * Rather than explicitly shuffling some indices down and some indices up, this algorithm just deletes the
105     * element and adds it back with the new index.
106     *
107     * @param  KeyType  $key
108     * @param  non-negative-int  $index
109     */
110    public function setIndex($key, int $index): void
111    {
112        $element = $this->getElement($key);
113
114        /**
115         * we know that there is at least one element in the collection because $key has been validated
116         * and $element is set, but the static analyzer does not.  It thinks that count() could be 0 and therefore
117         * $maxIndex could potentially be -1
118         */
119        $maxIndex = max(0, $this->count() - 1);
120
121        /**
122         * 'trim' the new index first
123         */
124        $index = $this->trimIndex($maxIndex, $index);
125
126        $this->delete($key);
127        $element->setIndex($index);
128
129        /**
130         * the add method sorts the elements array by index so we do not need to call it separately
131         */
132        $this->add($key, $element);
133    }
134
135    /**
136     * delete
137     *
138     * @param  KeyType  $key
139     *
140     * note that we do not need to sort the elements array after deleting an element - it is already in order.
141     */
142    public function delete($key): void
143    {
144        $existingIndex = $this->getElement($key)->getIndex();
145        parent::delete($key);
146
147        $this->shuffleIndices($existingIndex, self::SHUFFLE_DOWN);
148    }
149
150    /**
151     * @param  non-negative-int  $startIndex
152     * @param  int<-1, 1>  $direction
153     *
154     * @return void
155     */
156    private function shuffleIndices(int $startIndex, int $direction): void
157    {
158        foreach ($this->iterator as $element) {
159            $existingIndex = $element->getIndex();
160            $newIndex = max(0, $existingIndex + $direction);
161
162            if (
163                /**
164                 * make space before adding a new element at $startIndex
165                 */
166                ($direction == self::SHUFFLE_UP
167                    && $existingIndex >= $startIndex)
168                || /**
169                 * remove space after deleting an element at $startIndex
170                 */
171                ($direction == self::SHUFFLE_DOWN
172                    && $existingIndex > $startIndex)
173            ) {
174                $element->setIndex($newIndex);
175            }
176        }
177    }
178
179    /**
180     * add
181     *
182     * @param  KeyType  $key
183     * @param  ElementType  $element
184     *
185     * @throws InvalidValueException|InvalidKeyException
186     *
187     * if the element does not already have its index property set, this method
188     * will add the element to the end of the collection and set the element's
189     * index to the appropriate value.
190     */
191    public function add($key, $element): void
192    {
193        /**
194         * ensure the index property of the element is set.
195         */
196        try {
197            $index = $element->getIndex();
198        } catch (Throwable $e) {
199            $index = $this->count();
200        }
201
202        /**
203         * 'trim' the index of the element so that it is not larger than
204         * the number of elements currently in the collection.
205         */
206        $index = $this->trimIndex($index, $this->count());
207        $element->setIndex($index);
208
209        /**
210         * shuffle the other indices before we add the element
211         */
212        $this->shuffleIndices($element->getIndex(), self::SHUFFLE_UP);
213
214
215        /**
216         * add to the collection
217         */
218        parent::add($key, $element);
219    }
220
221    /**
222     * @param  KeyType  $key
223     * @param $element
224     *
225     * @return void
226     * @throws InvalidKeyException
227     *
228     * The code is a little DRYer if we use delete and add rather than
229     * craft a separate set of code for update
230     */
231    public function update($key, $element): void
232    {
233        $this->delete($key);
234        $this->add($key, $element);
235    }
236}