Queue::isEmpty() - Code Metrics - SuRaMoN/itertools - Measure and Improve Code Quality continuously with Scrutinizer

Queue::isEmpty() A
last analyzed 2020-05-28 15:38 UTC

↳ Parent: Queue

Complexity

Conditions	1
Paths	1

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	4
rs	10
c	0
b	0
f	0
cc	1
nc	1
nop	0

<?php

namespace itertools;

use OutOfBoundsException;
use Countable;
use ArrayAccess;
use IteratorAggregate;


/**
 * A queue implementation with random access with constant time complexity.
 * The SplQueue in the standard PHP library is implemented with a doubly linked
 * list. So it has linear time complexity to access elemenents by their index (
 * except for the bottom and top element). This queue implemntation addresses
 * this issue.
 *
 * This queue implementation has constant time complexity for:
 *  - push() / pop()
 *  - unshift() / shift()
 *  - offsetGet() / offsetSet()
 * It has linear time complexity for:
 *  - offsetUnset()
 */
class Queue implements ArrayAccess, Countable, IteratorAggregate
{
	protected $data;
	protected $headIndex;
	protected $tailIndex;
	protected $size;

	public function __construct($collection = array())
	{
		IterUtil::assertIsCollection($collection);
		$this->data = array_fill(0, 1, null);
		$this->size = 0;
		$this->headIndex = 0;
		$this->tailIndex = 0;
		$this->pushAll($collection);
	}

	public function getIterator()
	{
		return new ArrayAccessIterator($this);
	}

	public function getMemoryUsageDataStructure()
	{
		return count($this->data);
	}

	public function isEmpty()
	{
		return 0 == $this->size;
	}

	public function count()
	{
		return $this->size;
	}

	public function bottom()
	{
		return $this->offsetGet(0);
	}

	public function top()
	{
		return $this->offsetGet($this->count() - 1);
	}

	public function get($offset)
	{
		return $this->offsetGet($offset);
	}

	public function set($offset, $value)
	{
		return $this->offsetSet($offset, $value);
	}

	protected function doubleDataSize()
	{
		$newData = array_fill(0, count($this->data) * 2, null);
		foreach($this as $i => $element) {
			$newData[$i] = $element;
		}
		$this->headIndex = 0;
		$this->tailIndex = $this->size;
		$this->data = $newData;
	}

	protected function doubleDataSizeIfFull()
	{
		if($this->size == count($this->data)) {
			$this->doubleDataSize();
		}
	}

	public function pushAll($collection)
	{
		IterUtil::assertIsCollection($collection);
		foreach($collection as $element) {
			$this->push($element);
		}
		return $this;
	}

	public function push($value)
	{
		$this->doubleDataSizeIfFull();
		$this->data[$this->tailIndex] = $value;
		$this->size += 1;
		$this->tailIndex = ($this->tailIndex + 1) % count($this->data);
		return $this;
	}

	public function pop()
	{
		$oldValue = $this->offsetGet($this->size - 1);
		$this->tailIndex = ($this->tailIndex + count($this->data) - 1) % count($this->data);
		$this->size -= 1;
		return $oldValue;
	}

	public function unshiftAll($collection)
	{
		IterUtil::assertIsCollection($collection);
		foreach($collection as $element) {
			$this->unshift($element);
		}
		return $this;
	}

	public function asArray()
	{
		return iterator_to_array($this);
	}

	public function unshift($value)
	{
		$this->doubleDataSizeIfFull();
		$newHeadIndex = ($this->headIndex + count($this->data) - 1) % count($this->data);
		$this->data[$newHeadIndex] = $value;
		$this->size += 1;
		$this->headIndex = $newHeadIndex;
		return $this;
	}

	public function shift()
	{
		$oldValue = $this->offsetGet(0);
		$this->headIndex = ($this->headIndex + 1) % count($this->data);
		$this->size -= 1;
		return $oldValue;
	}

	protected function assertOffsetExists($offset)
	{
		if(!$this->offsetExists($offset)) {
			throw new OutOfBoundsException("Requested offset $offset for size {$this->size}");
		}
	}

	public function offsetExists($offset)
	{
		return 0 <= $offset && $offset < $this->size;
	}

	public function offsetGet($offset)
	{
		$this->assertOffsetExists($offset);
		return $this->data[($this->headIndex + $offset) % count($this->data)];
	}

	public function offsetSet($offset, $value)
	{
		if($offset == $this->size) {
			return $this->push($value);
		}
		$this->assertOffsetExists($offset);
		$this->data[($this->headIndex + $offset) % count($this->data)] = $value;
		return $this;
	}

	public function offsetUnset($offset)
	{
		$this->assertOffsetExists($offset);
		if(0 == $offset) {
			return $this->shift();
		} else if($offset == $this->size - 1) {
			return $this->pop();
		}
		$oldValue = $this->offsetGet($offset);
		$newData = array_fill(0, count($this->data), null);
		$i = 0;
		foreach($this as $oldIndex => $element) {
			if($oldIndex != $offset) {
				$newData[$i] = $element;
				$i += 1;
			}
		}
		$this->headIndex = 0;
		$this->tailIndex = $i;
		$this->size = $i;
		$this->data = $newData;
		return $oldValue;
	}
}



1			<?php
2
3			namespace itertools;
4
5			use OutOfBoundsException;
6			use Countable;
7			use ArrayAccess;
8			use IteratorAggregate;
9
10
11			/**
12			* A queue implementation with random access with constant time complexity.
13			* The SplQueue in the standard PHP library is implemented with a doubly linked
14			* list. So it has linear time complexity to access elemenents by their index (
15			* except for the bottom and top element). This queue implemntation addresses
16			* this issue.
17			*
18			* This queue implementation has constant time complexity for:
19			* - push() / pop()
20			* - unshift() / shift()
21			* - offsetGet() / offsetSet()
22			* It has linear time complexity for:
23			* - offsetUnset()
24			*/
25			class Queue implements ArrayAccess, Countable, IteratorAggregate
26			{
27			protected $data;
28			protected $headIndex;
29			protected $tailIndex;
30			protected $size;
31
32			public function __construct($collection = array())
33			{
34			IterUtil::assertIsCollection($collection);
35			$this->data = array_fill(0, 1, null);
36			$this->size = 0;
37			$this->headIndex = 0;
38			$this->tailIndex = 0;
39			$this->pushAll($collection);
40			}
41
42			public function getIterator()
43			{
44			return new ArrayAccessIterator($this);
45			}
46
47			public function getMemoryUsageDataStructure()
48			{
49			return count($this->data);
50			}
51
52			public function isEmpty()
53			{
54			return 0 == $this->size;
55			}
56
57			public function count()
58			{
59			return $this->size;
60			}
61
62			public function bottom()
63			{
64			return $this->offsetGet(0);
65			}
66
67			public function top()
68			{
69			return $this->offsetGet($this->count() - 1);
70			}
71
72			public function get($offset)
73			{
74			return $this->offsetGet($offset);
75			}
76
77			public function set($offset, $value)
78			{
79			return $this->offsetSet($offset, $value);
80			}
81
82			protected function doubleDataSize()
83			{
84			$newData = array_fill(0, count($this->data) * 2, null);
85			foreach($this as $i => $element) {
86			$newData[$i] = $element;
87			}
88			$this->headIndex = 0;
89			$this->tailIndex = $this->size;
90			$this->data = $newData;
91			}
92
93			protected function doubleDataSizeIfFull()
94			{
95			if($this->size == count($this->data)) {
96			$this->doubleDataSize();
97			}
98			}
99
100			public function pushAll($collection)
101			{
102			IterUtil::assertIsCollection($collection);
103			foreach($collection as $element) {
104			$this->push($element);
105			}
106			return $this;
107			}
108
109			public function push($value)
110			{
111			$this->doubleDataSizeIfFull();
112			$this->data[$this->tailIndex] = $value;
113			$this->size += 1;
114			$this->tailIndex = ($this->tailIndex + 1) % count($this->data);
115			return $this;
116			}
117
118			public function pop()
119			{
120			$oldValue = $this->offsetGet($this->size - 1);
121			$this->tailIndex = ($this->tailIndex + count($this->data) - 1) % count($this->data);
122			$this->size -= 1;
123			return $oldValue;
124			}
125
126			public function unshiftAll($collection)
127			{
128			IterUtil::assertIsCollection($collection);
129			foreach($collection as $element) {
130			$this->unshift($element);
131			}
132			return $this;
133			}
134
135			public function asArray()
136			{
137			return iterator_to_array($this);
138			}
139
140			public function unshift($value)
141			{
142			$this->doubleDataSizeIfFull();
143			$newHeadIndex = ($this->headIndex + count($this->data) - 1) % count($this->data);
144			$this->data[$newHeadIndex] = $value;
145			$this->size += 1;
146			$this->headIndex = $newHeadIndex;
147			return $this;
148			}
149
150			public function shift()
151			{
152			$oldValue = $this->offsetGet(0);
153			$this->headIndex = ($this->headIndex + 1) % count($this->data);
154			$this->size -= 1;
155			return $oldValue;
156			}
157
158			protected function assertOffsetExists($offset)
159			{
160			if(!$this->offsetExists($offset)) {
161			throw new OutOfBoundsException("Requested offset $offset for size {$this->size}");
162			}
163			}
164
165			public function offsetExists($offset)
166			{
167			return 0 <= $offset && $offset < $this->size;
168			}
169
170			public function offsetGet($offset)
171			{
172			$this->assertOffsetExists($offset);
173			return $this->data[($this->headIndex + $offset) % count($this->data)];
174			}
175
176			public function offsetSet($offset, $value)
177			{
178			if($offset == $this->size) {
179			return $this->push($value);
180			}
181			$this->assertOffsetExists($offset);
182			$this->data[($this->headIndex + $offset) % count($this->data)] = $value;
183			return $this;
184			}
185
186			public function offsetUnset($offset)
187			{
188			$this->assertOffsetExists($offset);
189			if(0 == $offset) {
190			return $this->shift();
191			} else if($offset == $this->size - 1) {
192			return $this->pop();
193			}
194			$oldValue = $this->offsetGet($offset);
195			$newData = array_fill(0, count($this->data), null);
196			$i = 0;
197			foreach($this as $oldIndex => $element) {
198			if($oldIndex != $offset) {
199			$newData[$i] = $element;
200			$i += 1;
201			}
202			}
203			$this->headIndex = 0;
204			$this->tailIndex = $i;
205			$this->size = $i;
206			$this->data = $newData;
207			return $oldValue;
208			}
209			}
210
211

SuRaMoN / itertools

Queue::isEmpty() A last analyzed 2020-05-28 15:38 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Queue::isEmpty() A
last analyzed 2020-05-28 15:38 UTC