Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
42 / 42
100.00% covered (success)
100.00%
8 / 8
 CRAP
100.00% covered (success)
100.00%
1 / 1
CollectionOrdered
100.00% covered (success)
100.00%
42 / 42
100.00% covered (success)
100.00%
8 / 8
 16
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
 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\CollectionOrderedInterface;
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 CollectionOrderedInterface<ElementType>
27 */
28class CollectionOrdered extends Collection implements CollectionOrderedInterface
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        $newIndex = $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     * delete
106     * @param non-negative-int $key
107     *
108     * note that we do not need to sort the elements array after deleting an element - it is already in order.
109     */
110    public function delete(int $key): void
111    {
112        $existingIndex = $this->getElement($key)->getIndex();
113        parent::delete($key);
114        $this->shuffleIndices($existingIndex, self::SHUFFLE_DOWN);
115    }
116
117    /**
118     * @param non-negative-int $startIndex
119     * @param int<-1, 1> $direction
120     * @return void
121     */
122    private function shuffleIndices(int $startIndex, int $direction): void
123    {
124        foreach ($this->iterator as $element) {
125            $existingIndex = $element->getIndex();
126            $newIndex = max(0, $existingIndex + $direction);
127
128            if (
129                /**
130                 * make space before adding a new element at $startIndex
131                 */
132                ($direction == self::SHUFFLE_UP && $existingIndex >= $startIndex) ||
133                /**
134                 * remove space after deleting an element at $startIndex
135                 */
136                ($direction == self::SHUFFLE_DOWN && $existingIndex > $startIndex)
137            ) {
138                $element->setIndex($newIndex);
139            }
140        }
141    }
142
143    /**
144     * add
145     * @param non-negative-int $key
146     * @param ElementType $element
147     * @throws InvalidKeyException
148     *
149     * in order to keep the elements array in the proper order, we need to sort it by index so that iteration
150     * happens in the proper order
151     */
152    public function add(int $key, $element): void
153    {
154        /**
155         * 'trim' the index of the element first
156         */
157        $maxIndex = $this->count();
158        $index = $this->trimIndex($element->getIndex(), $maxIndex);
159        $element->setIndex($index);
160
161        /**
162         * shuffle the other indices before we add the element
163         */
164        $this->shuffleIndices($element->getIndex(), self::SHUFFLE_UP);
165
166        /**
167         * add and then sort the collection
168         */
169        parent::add($key, $element);
170        $this->iterator->uasort([$this, 'compareIndices']);
171    }
172
173    /**
174     * @param non-negative-int $key
175     * @param $element
176     * @return void
177     * @throws InvalidKeyException
178     *
179     * This method will reorder the collection if the index of $element has changed from the prior value of
180     * the index of the element with the same key
181     */
182    public function update(int $key, $element): void
183    {
184        $oldIndex = $this->getElement($key)->getIndex();
185        $newIndex = $element->getIndex();
186        $element->setIndex($oldIndex);
187        parent::update($key, $element);
188        $this->setIndex($key, $newIndex);
189    }
190
191    /**
192     * @param ElementType $a
193     * @param ElementType $b
194     * @return int
195     */
196    protected function compareIndices(mixed $a, mixed $b): int
197    {
198        return $a->getIndex() <=> $b->getIndex();
199    }
200
201    /**
202     * getIndex returns the index which corresponds to $key
203     *
204     * @param non-negative-int $key
205     * @return non-negative-int
206     */
207    public function getIndex(int $key): int
208    {
209        if (!$this->validateKey($key)) {
210            throw new InvalidKeyException($key);
211        }
212        if (!$this->validateExistingKey($key)) {
213            throw new NonExistentKeyException($key);
214        }
215        $element = $this->getElement($key);
216        assert(!is_null($element));
217        return $element->getIndex();
218    }
219}