Completed
Push — indicesAreUpToDate ( 2c2f48 )
by no
15:26 queued 11:27
created

HashArray::indicesAreUpToDate()   A

Complexity

Conditions 4
Paths 4

Size

Total Lines 14
Code Lines 7

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 9
CRAP Score 4

Importance

Changes 0
Metric Value
dl 0
loc 14
ccs 9
cts 9
cp 1
rs 9.2
c 0
b 0
f 0
cc 4
eloc 7
nc 4
nop 0
crap 4

1 Method

Rating   Name   Duplication   Size   Complexity  
A HashArray::append() 0 3 1
1
<?php
2
3
namespace Wikibase\DataModel;
4
5
use ArrayObject;
6
use Comparable;
7
use Hashable;
8
use InvalidArgumentException;
9
use Traversable;
10
use Wikibase\DataModel\Internal\MapValueHasher;
11
12
/**
13
 * Generic array object with lookups based on hashes of the elements.
14
 *
15
 * Elements need to implement Hashable.
16
 *
17
 * Note that by default the getHash method uses @see MapValueHashesr
18
 * which returns a hash based on the contents of the list, regardless
19
 * of order and keys.
20
 *
21
 * Also note that if the Hashable elements are mutable, any modifications
22
 * made to them via their mutator methods will not cause an update of
23
 * their associated hash in this array.
24
 *
25
 * When acceptDuplicates is set to true, multiple elements with the same
26
 * hash can reside in the HashArray. Lookup by such a non-unique hash will
27
 * return only the first element and deletion will also delete only
28
 * the first such element.
29
 *
30
 * @since 0.1
31
 *
32
 * @license GPL-2.0+
33
 * @author Jeroen De Dauw < [email protected] >
34
 */
35
abstract class HashArray extends ArrayObject implements Hashable, Comparable {
36
37
	/**
38
	 * Maps element hashes to their offsets.
39
	 *
40
	 * @since 0.1
41
	 *
42
	 * @var array [ element hash (string) => array [ element offset (string|int) ] | element offset (string|int) ]
43
	 */
44
	protected $offsetHashes = [];
45
46
	/**
47
	 * If duplicate values (based on hash) should be accepted or not.
48
	 *
49
	 * @since 0.3
50
	 *
51
	 * @var bool
52
	 */
53
	protected $acceptDuplicates = false;
54
55
	/**
56
	 * @var integer
57
	 */
58
	protected $indexOffset = 0;
59
60
	/**
61
	 * Returns the name of an interface/class that the element should implement/extend.
62
	 *
63
	 * @since 0.4
64
	 *
65
	 * @return string
66
	 */
67
	abstract public function getObjectType();
68
69
	/**
70
	 * @see ArrayObject::__construct
71
	 *
72
	 * @param array|Traversable|null $input
73
	 * @param int $flags
74
	 * @param string $iteratorClass
75
	 *
76
	 * @throws InvalidArgumentException
77
	 */
78
	public function __construct( $input = null, $flags = 0, $iteratorClass = 'ArrayIterator' ) {
79
		parent::__construct( [], $flags, $iteratorClass );
80
81
		if ( $input !== null ) {
82
			if ( !is_array( $input ) && !( $input instanceof Traversable ) ) {
83
				throw new InvalidArgumentException( '$input must be an array or Traversable' );
84
			}
85
86
			foreach ( $input as $offset => $value ) {
87
				$this->offsetSet( $offset, $value );
88
			}
89
		}
90
	}
91
92
	/**
93
	 * Finds a new offset for when appending an element.
94
	 * The base class does this, so it would be better to integrate,
95
	 * but there does not appear to be any way to do this...
96
	 *
97
	 * @return integer
98
	 */
99
	protected function getNewOffset() {
100
		while ( $this->offsetExists( $this->indexOffset ) ) {
101
			$this->indexOffset++;
102
		}
103
104
		return $this->indexOffset;
105
	}
106
107
	/**
108
	 * Gets called before a new element is added to the ArrayObject.
109
	 *
110
	 * At this point the index is always set (ie not null) and the
111
	 * value is always of the type returned by @see getObjectType.
112
	 *
113
	 * Should return a boolean. When false is returned the element
114
	 * does not get added to the ArrayObject.
115
	 *
116
	 * @since 0.1
117
	 *
118
	 * @param int|string $index
119
	 * @param Hashable $hashable
120
	 *
121
	 * @return bool
122
	 */
123
	protected function preSetElement( $index, $hashable ) {
124
		$hash = $hashable->getHash();
125
126
		$hasHash = $this->hasElementHash( $hash );
127
128
		if ( !$this->acceptDuplicates && $hasHash ) {
129
			return false;
130
		}
131
		else {
132
			if ( $hasHash ) {
133
				if ( !is_array( $this->offsetHashes[$hash] ) ) {
134
					$this->offsetHashes[$hash] = [ $this->offsetHashes[$hash] ];
135
				}
136
137
				$this->offsetHashes[$hash][] = $index;
138
			}
139
			else {
140
				$this->offsetHashes[$hash] = $index;
141
			}
142
143
			return true;
144
		}
145
	}
146
147
	/**
148
	 * Returns if there is an element with the provided hash.
149
	 *
150
	 * @since 0.1
151
	 *
152
	 * @param string $elementHash
153
	 *
154
	 * @return bool
155
	 */
156
	public function hasElementHash( $elementHash ) {
157
		return array_key_exists( $elementHash, $this->offsetHashes );
158
	}
159
160
	/**
161
	 * Returns if there is an element with the same hash as the provided element in the list.
162
	 *
163
	 * @since 0.1
164
	 *
165
	 * @param Hashable $element
166
	 *
167
	 * @return bool
168
	 */
169
	public function hasElement( Hashable $element ) {
170
		return $this->hasElementHash( $element->getHash() );
171
	}
172
173
	/**
174
	 * Removes the element with the hash of the provided element, if there is such an element in the list.
175
	 *
176
	 * @since 0.1
177
	 *
178
	 * @param Hashable $element
179
	 */
180
	public function removeElement( Hashable $element ) {
181
		$this->removeByElementHash( $element->getHash() );
182
	}
183
184
	/**
185
	 * Removes the element with the provided hash, if there is such an element in the list.
186
	 *
187
	 * @since 0.1
188
	 *
189
	 * @param string $elementHash
190
	 */
191
	public function removeByElementHash( $elementHash ) {
192
		if ( $this->hasElementHash( $elementHash ) ) {
193
			$offset = $this->offsetHashes[$elementHash];
194
195
			if ( is_array( $offset ) ) {
196
				$offset = reset( $offset );
197
			}
198
199
			$this->offsetUnset( $offset );
200
		}
201
	}
202
203
	/**
204
	 * Adds the provided element to the list if there is no element with the same hash yet.
205
	 *
206
	 * @since 0.1
207
	 *
208
	 * @param Hashable $element
209
	 *
210
	 * @return bool Indicates if the element was added or not.
211
	 */
212
	public function addElement( Hashable $element ) {
213
		$append = $this->acceptDuplicates || !$this->hasElementHash( $element->getHash() );
214
215
		if ( $append ) {
216
			$this->append( $element );
217
		}
218
219
		return $append;
220
	}
221
222
	/**
223
	 * Returns the element with the provided hash or false if there is no such element.
224
	 *
225
	 * @since 0.1
226
	 *
227
	 * @param string $elementHash
228
	 *
229
	 * @return mixed|bool
230
	 */
231
	public function getByElementHash( $elementHash ) {
232
		if ( $this->hasElementHash( $elementHash ) ) {
233
			$offset = $this->offsetHashes[$elementHash];
234
235
			if ( is_array( $offset ) ) {
236
				$offset = reset( $offset );
237
			}
238
239
			return $this->offsetGet( $offset );
240
		}
241
		else {
242
			return false;
243
		}
244
	}
245
246
	/**
247
	 * @see ArrayObject::offsetUnset
248
	 *
249
	 * @since 0.1
250
	 *
251
	 * @param mixed $index
252
	 */
253
	public function offsetUnset( $index ) {
254
		if ( $this->offsetExists( $index ) ) {
255
			/**
256
			 * @var Hashable $element
257
			 */
258
			$element = $this->offsetGet( $index );
259
260
			$hash = $element->getHash();
261
262
			if ( array_key_exists( $hash, $this->offsetHashes )
263
				&& is_array( $this->offsetHashes[$hash] )
264
				&& count( $this->offsetHashes[$hash] ) > 1 ) {
265
				$this->offsetHashes[$hash] = array_filter(
266
					$this->offsetHashes[$hash],
267
					function( $value ) use ( $index ) {
268
						return $value !== $index;
269
					}
270
				);
271
			}
272
			else {
273
				unset( $this->offsetHashes[$hash] );
274
			}
275
276
			parent::offsetUnset( $index );
277
		}
278
	}
279
280
	/**
281
	 * @see Hashable::getHash
282
	 *
283
	 * The hash is purely valuer based. Order of the elements in the array is not held into account.
284
	 *
285
	 * @since 0.1
286
	 *
287
	 * @return string
288
	 */
289
	public function getHash() {
290
		$hasher = new MapValueHasher();
291
		return $hasher->hash( $this );
292
	}
293
294
	/**
295
	 * @see Comparable::equals
296
	 *
297
	 * The comparison is done purely value based, ignoring the order of the elements in the array.
298
	 *
299
	 * @since 0.3
300
	 *
301
	 * @param mixed $target
302
	 *
303
	 * @return bool
304
	 */
305
	public function equals( $target ) {
306
		if ( $this === $target ) {
307
			return true;
308
		}
309
310
		return $target instanceof self
311
			&& $this->getHash() === $target->getHash();
312
	}
313
314
	/**
315
	 * Removes duplicates bases on hash value.
316
	 *
317
	 * @since 0.3
318
	 */
319
	public function removeDuplicates() {
320
		$knownHashes = [];
321
322
		/**
323
		 * @var Hashable $hashable
324
		 */
325
		foreach ( iterator_to_array( $this ) as $hashable ) {
326
			$hash = $hashable->getHash();
327
328
			if ( in_array( $hash, $knownHashes ) ) {
329
				$this->removeByElementHash( $hash );
330
			}
331
			else {
332
				$knownHashes[] = $hash;
333
			}
334
		}
335
	}
336
337
	/**
338
	 * Removes and adds all elements, ensuring the indices are up to date.
339
	 *
340
	 * @since 0.4
341
	 */
342
	public function rebuildIndices() {
343
		$hashables = iterator_to_array( $this );
344
345
		$this->offsetHashes = [];
346
347
		foreach ( $hashables as $offset => $hashable ) {
348
			$this->offsetUnset( $offset );
349
			$this->offsetSet( $offset, $hashable );
350
		}
351
	}
352
353
	/**
354
	 * @see ArrayObject::append
355
	 *
356
	 * @param mixed $value
357
	 */
358
	public function append( $value ) {
359
		$this->setElement( null, $value );
360
	}
361
362
	/**
363
	 * @see ArrayObject::offsetSet()
364
	 *
365
	 * @param mixed $index
366
	 * @param mixed $value
367
	 */
368
	public function offsetSet( $index, $value ) {
369
		$this->setElement( $index, $value );
370
	}
371
372
	/**
373
	 * Returns if the provided value has the same type as the elements
374
	 * that can be added to this ArrayObject.
375
	 *
376
	 * @param mixed $value
377
	 *
378
	 * @return bool
379
	 */
380
	protected function hasValidType( $value ) {
381
		$class = $this->getObjectType();
382
		return $value instanceof $class;
383
	}
384
385
	/**
386
	 * Method that actually sets the element and holds
387
	 * all common code needed for set operations, including
388
	 * type checking and offset resolving.
389
	 *
390
	 * If you want to do additional indexing or have code that
391
	 * otherwise needs to be executed whenever an element is added,
392
	 * you can overload @see preSetElement.
393
	 *
394
	 * @param mixed $index
395
	 * @param mixed $value
396
	 *
397
	 * @throws InvalidArgumentException
398
	 */
399
	protected function setElement( $index, $value ) {
400
		if ( !$this->hasValidType( $value ) ) {
401
			$type = is_object( $value ) ? get_class( $value ) : gettype( $value );
402
403
			throw new InvalidArgumentException( '$value must be an instance of ' . $this->getObjectType() . '; got ' . $type );
404
		}
405
406
		if ( $index === null ) {
407
			$index = $this->getNewOffset();
408
		}
409
410
		if ( $this->preSetElement( $index, $value ) ) {
411
			parent::offsetSet( $index, $value );
0 ignored issues
show
Comprehensibility Bug introduced by
It seems like you call parent on a different method (offsetSet() instead of setElement()). Are you sure this is correct? If so, you might want to change this to $this->offsetSet().

This check looks for a call to a parent method whose name is different than the method from which it is called.

Consider the following code:

class Daddy
{
    protected function getFirstName()
    {
        return "Eidur";
    }

    protected function getSurName()
    {
        return "Gudjohnsen";
    }
}

class Son
{
    public function getFirstName()
    {
        return parent::getSurname();
    }
}

The getFirstName() method in the Son calls the wrong method in the parent class.

Loading history...
412
		}
413
	}
414
415
	/**
416
	 * @see Serializable::serialize
417
	 *
418
	 * @return string
419
	 */
420
	public function serialize() {
421
		return serialize( [
422
			'data' => $this->getArrayCopy(),
423
			'index' => $this->indexOffset,
424
		] );
425
	}
426
427
	/**
428
	 * @see Serializable::unserialize
429
	 *
430
	 * @param string $serialized
431
	 */
432
	public function unserialize( $serialized ) {
433
		$serializationData = unserialize( $serialized );
434
435
		foreach ( $serializationData['data'] as $offset => $value ) {
436
			// Just set the element, bypassing checks and offset resolving,
437
			// as these elements have already gone through this.
438
			parent::offsetSet( $offset, $value );
0 ignored issues
show
Comprehensibility Bug introduced by
It seems like you call parent on a different method (offsetSet() instead of unserialize()). Are you sure this is correct? If so, you might want to change this to $this->offsetSet().

This check looks for a call to a parent method whose name is different than the method from which it is called.

Consider the following code:

class Daddy
{
    protected function getFirstName()
    {
        return "Eidur";
    }

    protected function getSurName()
    {
        return "Gudjohnsen";
    }
}

class Son
{
    public function getFirstName()
    {
        return parent::getSurname();
    }
}

The getFirstName() method in the Son calls the wrong method in the parent class.

Loading history...
439
		}
440
441
		$this->indexOffset = $serializationData['index'];
442
	}
443
444
	/**
445
	 * Returns if the ArrayObject has no elements.
446
	 *
447
	 * @return bool
448
	 */
449
	public function isEmpty() {
450
		return !$this->getIterator()->valid();
451
	}
452
453
}
454