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