SimpleLinkedList::remove() - Code Metrics - Inspection of "Fixed error in doubly linked list with indexOf" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 2cb83b...930afd )

by Siro Díaz

created 2017-07-12 16:30 UTC

SimpleLinkedList::remove() B

↳ Parent: SimpleLinkedList

Complexity

Conditions	5
Paths	5

Size

Total Lines	24
Code Lines	14

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	24
rs	8.5125
c	0
b	0
f	0
cc	5
eloc	14
nc	5
nop	1

<?php
/**
 * DataStructures for PHP
 *
 * @link      https://github.com/SiroDiaz/DataStructures
 * @copyright Copyright (c) 2017 Siro Díaz Palazón
 * @license   https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
 */
namespace DataStructures\Lists;

use DataStructures\Lists\Traits\{CountTrait, ArrayAccessTrait};
use DataStructures\Lists\Nodes\SimpleLinkedListNode as Node;
use DataStructures\Lists\Interfaces\ListInterface;
use OutOfBoundsException;
use Iterator;

/**
 * SimpleLinkedList
 *
 * SimpleLinkedList is a singly linked list that has
 * a pointer to the next node but last node points to null.
 *
 * @author Siro Diaz Palazon <[email protected]>
 */
class SimpleLinkedList implements ListInterface {
    use ArrayAccessTrait;
    
    private $head;
    private $size;
    private $position;
    private $current;

    public function __construct() {

        $this->head = null;
        $this->size = 0;
        $this->position = 0;
        $this->current = &$this->head;
    }

    /**
     * Adds at the end of the list new node containing
     * the data to be stored.
     *
     * @param mixed $data The data
     */
    public function push($data) {
        $newNode = new Node($data);
        if($this->head === null) {

            $this->head = &$newNode;
            $this->current = &$this->head;
        } else {
            $current = $this->head;
            while($current->next !== null) {
                $current = $current->next;
            }
            $current->next = &$newNode;
        }

        $this->size++;
    }

    /**
     * Gets the data stored in the position especified.
     *
     * @param integer $index Index that must be greater than 0
     *  and lower than the list size.
     * @return mixed The data stored in the given index
     * @throws OutOfBoundsException if index is out bounds.
     */
    public function get($index) {

        $node = $this->search($index);
        if($node === null) {
            return null;
        }

        return $node->data;
    }

    /**
     * Returns the node stored in the given position.
     *
     * @param integer $index the position.
     * @throws OutOfBoundsException if it is out of limits (< 0 or > size - 1)
     * @return DataStructures\Lists\Nodes\SimpleLinkedListNode|null the node stored in $index.
     */
    protected function search($index) {
        if($index > $this->size - 1 || $index < 0) {
            throw new OutOfBoundsException();
        }   

        $current = $this->head;
        $i = 0;
        while($i < $index && $current->next !== null) {

            $current = $current->next;
            $i++;
        }

        return $current;
    }

    /**
     * Generator for retrieve all nodes stored.
     * 
     * @return null if the head is null (or list is empty)
     */
    public function getAll() {
        if($this->head === null) {
            return;
        }

        $current = $this->head;
        while($current !== null) {
            yield $current->data;
            $current = $current->next;
        }
    }

    /**
     *
     */
    public function contains($data) : bool {
        if($this->empty()) {
            return false;
        }

        $current = $this->head;
        while($current !== null) {
            if($current->data === $data) {
                return true;
            }
            $current = $current->next;
        }

        return false;
    }

    /**
     *
     */
    public function indexOf($data) {

        if($this->head === null) {
            return false;
        }
        
        $current = $this->head;
        $i = 0;
        
        while($i < $this->size) {
            if($current->data == $data) {
                return $i;
            }

            $current = $current->next;
            $i++;
        }

        return false;
    }

    /**
     *
     */
    public function lastIndexOf($data) {

        if($this->head === null) {
            return false;
        }
        
        $current = $this->head;
        $i = 0;
        $pos = false;
        while($i < $this->size) {
            if($current->data == $data) {
                $pos = $i;
            }

            $current = $current->next;
            $i++;
        }

        return $pos;
    }

    /**
     *
     */
    public function remove($data) {
        $current = &$this->head;
        $i = 0;
        
        if($this->head === null) {
            return null;
        }

        if($this->head->data === $data) {
            $this->size--;
            return $data;
        }

        while($i < $this->size) {
            if($current->data === $data) {
                $this->size--;
                return $data;
            }

            $current = $current->next;
        }

        return null;
    }

    /**
     * Insert a node in the specified list position.
     *
     * @param integer $index position
     * @param mixed $data data to be saved
     */
    public function insert($index, $data) {
        if($this->head === null) {
            return $this->push($data);
        }

        $newNode = new Node($data);
        if($index === 0) {
            $aux = $this->head;
            $this->head = &$newNode;
            $newNode->next = &$aux;
            $this->current = $this->head;
        } else {
            $i = 0;
            $current = $this->head;
            $prev = $current;
            while($i < $index && $current->next !== null) {

                $prev = $current;
                $current = $current->next;
                $i++;
            }

            $prev->next = &$newNode;
            $newNode->next = &$current;
        }

        $this->size++;
    }

    /**
     * Delete a node in the given position and returns it back.
     *
     * @param integer $index the position.
     * @throws OutOfBoundsException if index is negative
     *  or is greater than the size of the list.
     */
    public function delete($index) {
        if($index < 0) {
            throw new OutOfBoundsException();
        }
        if($this->head === null) {
            return null;
        }

        if($index >= $this->size) {
            return null;    // It should return an exception
        }

        if($index === 0) {
            $node = $this->head;
            $this->head = $this->head->next;
            $this->current = &$this->head;
            $this->size--;
            return $node->data;
        }
        
        $i = 0;
        $current = $this->head;
        $prev = $current;
        while($i < $index && $current->next !== null) {

            $prev = $current;
            $current = $current->next;
        }

        if($index === $this->size - 1) {
            $prev->next = null;
            $this->size--;
            return $current->data;
        } else {
            $prev->next = $current->next;
        }
        $this->size--;

        return $prev->data;
    }

    /**
     * Removes and returns the last node in the list.
     *
     * @return mixed data in node.
     */
    public function pop() {
        return $this->delete($this->size - 1);
    }

    /**
     * Remove all nodes of the list using shift.
     */
    public function clear() {
        while($this->head !== null) {
            $this->shift();
        }
    }

    /**
     * Converts/exports the list content into array type.
     *
     * @return array data stored in all nodes.
     */
    public function toArray() : array {
        $arr = [];
        foreach($this->getAll() as $node) {
            $arr[] = $node;
        }

        return $arr;
    }

    /**
     * Adds at the beginning a node in the list.
     *
     * @param mixed $data
     * @return mixed the data stored.
     */
    public function unshift($data) {
        $this->insert(0, $data);
    }

    /**
     * Deletes the first node of the list and returns it.
     *
     * @return mixed the data.
     */
    public function shift() {
        return $this->delete(0);
    }

    /**
     * Reset the cursor position.
     */
    public function rewind() {
        $this->position = 0;
        $this->current = $this->head;
    }

    /**
     * Returns the current node data.
     *
     * @return mixed
     */
    public function current() {
        return $this->current->data;
    }

    /**
     * Key or index that indicates the cursor position.
     *
     * @return integer The current position.
     */
    public function key() {
        return $this->position;
    }

    /**
     * Move the cursor to the next node and increments the
     * position counter.
     */
    public function next() {
        ++$this->position;
        $this->current = $this->current->next;
    }

    /**
     * Returns if the current pointer position is valid.
     *
     * @return boolean true if pointer is not last, else false.
     */
    public function valid() {
        return $this->current !== null;
    }

    /**
     * Binds to count() method. This is equal to make $this->tree->size().
     *
     * @return integer the tree size. 0 if it is empty.
     */
    public function count() {
        return $this->size;
    }

    /**
     * Returns the array size.
     *
     * @return int the length
     */
    public function size() : int {
        return $this->size;
    }

    /**
     * Checks if the list is empty.
     *
     * @return boolean true if is empty, else false.
     */
    public function empty() : bool {
        return $this->size === 0;
    }
}

1		<?php
2		/**
3		* DataStructures for PHP
4		*
5		* @link https://github.com/SiroDiaz/DataStructures
6		* @copyright Copyright (c) 2017 Siro Díaz Palazón
7		* @license https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
8		*/
9		namespace DataStructures\Lists;
10
11		use DataStructures\Lists\Traits\{CountTrait, ArrayAccessTrait};
12		use DataStructures\Lists\Nodes\SimpleLinkedListNode as Node;
13		use DataStructures\Lists\Interfaces\ListInterface;
14		use OutOfBoundsException;
15		use Iterator;
16
17		/**
18		* SimpleLinkedList
19		*
20		* SimpleLinkedList is a singly linked list that has
21		* a pointer to the next node but last node points to null.
22		*
23		* @author Siro Diaz Palazon <[email protected]>
24		*/
25		class SimpleLinkedList implements ListInterface {
26		use ArrayAccessTrait;
27
28		private $head;
29		private $size;
30		private $position;
31		private $current;
32
33	View Code Duplication	public function __construct() {
		0 ignored issues – show Duplication introduced 2017-06-05 14:14 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
34		$this->head = null;
35		$this->size = 0;
36		$this->position = 0;
37		$this->current = &$this->head;
38		}
39
40		/**
41		* Adds at the end of the list new node containing
42		* the data to be stored.
43		*
44		* @param mixed $data The data
45		*/
46		public function push($data) {
47		$newNode = new Node($data);
48	View Code Duplication	if($this->head === null) {
		0 ignored issues – show Duplication introduced 2017-06-05 14:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
49		$this->head = &$newNode;
50		$this->current = &$this->head;
51		} else {
52		$current = $this->head;
53		while($current->next !== null) {
54		$current = $current->next;
55		}
56		$current->next = &$newNode;
57		}
58
59		$this->size++;
60		}
61
62		/**
63		* Gets the data stored in the position especified.
64		*
65		* @param integer $index Index that must be greater than 0
66		* and lower than the list size.
67		* @return mixed The data stored in the given index
68		* @throws OutOfBoundsException if index is out bounds.
69		*/
70	View Code Duplication	public function get($index) {
		0 ignored issues – show Duplication introduced 2017-06-24 20:15 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
71		$node = $this->search($index);
72		if($node === null) {
73		return null;
74		}
75
76		return $node->data;
77		}
78
79		/**
80		* Returns the node stored in the given position.
81		*
82		* @param integer $index the position.
83		* @throws OutOfBoundsException if it is out of limits (< 0 or > size - 1)
84		* @return DataStructures\Lists\Nodes\SimpleLinkedListNode\|null the node stored in $index.
85		*/
86		protected function search($index) {
87		if($index > $this->size - 1 \|\| $index < 0) {
88		throw new OutOfBoundsException();
89		}
90
91		$current = $this->head;
92		$i = 0;
93	View Code Duplication	while($i < $index && $current->next !== null) {
		0 ignored issues – show Duplication introduced 2017-06-05 14:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
94		$current = $current->next;
95		$i++;
96		}
97
98		return $current;
99		}
100
101		/**
102		* Generator for retrieve all nodes stored.
103		*
104		* @return null if the head is null (or list is empty)
105		*/
106		public function getAll() {
107		if($this->head === null) {
108		return;
109		}
110
111		$current = $this->head;
112		while($current !== null) {
113		yield $current->data;
114		$current = $current->next;
115		}
116		}
117
118		/**
119		*
120		*/
121		public function contains($data) : bool {
122		if($this->empty()) {
123		return false;
124		}
125
126		$current = $this->head;
127		while($current !== null) {
128		if($current->data === $data) {
129		return true;
130		}
131		$current = $current->next;
132		}
133
134		return false;
135		}
136
137		/**
138		*
139		*/
140	View Code Duplication	public function indexOf($data) {
		0 ignored issues – show Duplication introduced 2017-07-08 23:51 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
141		if($this->head === null) {
142		return false;
143		}
144
145		$current = $this->head;
146		$i = 0;
147
148		while($i < $this->size) {
149		if($current->data == $data) {
150		return $i;
151		}
152
153		$current = $current->next;
154		$i++;
155		}
156
157		return false;
158		}
159
160		/**
161		*
162		*/
163	View Code Duplication	public function lastIndexOf($data) {
		0 ignored issues – show Duplication introduced 2017-07-09 14:20 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
164		if($this->head === null) {
165		return false;
166		}
167
168		$current = $this->head;
169		$i = 0;
170		$pos = false;
171		while($i < $this->size) {
172		if($current->data == $data) {
173		$pos = $i;
174		}
175
176		$current = $current->next;
177		$i++;
178		}
179
180		return $pos;
181		}
182
183		/**
184		*
185		*/
186		public function remove($data) {
187		$current = &$this->head;
188		$i = 0;
189
190		if($this->head === null) {
191		return null;
192		}
193
194		if($this->head->data === $data) {
195		$this->size--;
196		return $data;
197		}
198
199		while($i < $this->size) {
200		if($current->data === $data) {
201		$this->size--;
202		return $data;
203		}
204
205		$current = $current->next;
206		}
207
208		return null;
209		}
210
211		/**
212		* Insert a node in the specified list position.
213		*
214		* @param integer $index position
215		* @param mixed $data data to be saved
216		*/
217		public function insert($index, $data) {
218		if($this->head === null) {
219		return $this->push($data);
220		}
221
222		$newNode = new Node($data);
223		if($index === 0) {
224		$aux = $this->head;
225		$this->head = &$newNode;
226		$newNode->next = &$aux;
227		$this->current = $this->head;
228		} else {
229		$i = 0;
230		$current = $this->head;
231		$prev = $current;
232	View Code Duplication	while($i < $index && $current->next !== null) {
		0 ignored issues – show Duplication introduced 2017-06-05 14:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
233		$prev = $current;
234		$current = $current->next;
235		$i++;
236		}
237
238		$prev->next = &$newNode;
239		$newNode->next = &$current;
240		}
241
242		$this->size++;
243		}
244
245		/**
246		* Delete a node in the given position and returns it back.
247		*
248		* @param integer $index the position.
249		* @throws OutOfBoundsException if index is negative
250		* or is greater than the size of the list.
251		*/
252		public function delete($index) {
253		if($index < 0) {
254		throw new OutOfBoundsException();
255		}
256		if($this->head === null) {
257		return null;
258		}
259
260		if($index >= $this->size) {
261		return null; // It should return an exception
262		}
263
264		if($index === 0) {
265		$node = $this->head;
266		$this->head = $this->head->next;
267		$this->current = &$this->head;
268		$this->size--;
269		return $node->data;
270		}
271
272		$i = 0;
273		$current = $this->head;
274		$prev = $current;
275	View Code Duplication	while($i < $index && $current->next !== null) {
		0 ignored issues – show Duplication introduced 2017-06-05 14:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
276		$prev = $current;
277		$current = $current->next;
278		}
279
280		if($index === $this->size - 1) {
281		$prev->next = null;
282		$this->size--;
283		return $current->data;
284		} else {
285		$prev->next = $current->next;
286		}
287		$this->size--;
288
289		return $prev->data;
290		}
291
292		/**
293		* Removes and returns the last node in the list.
294		*
295		* @return mixed data in node.
296		*/
297		public function pop() {
298		return $this->delete($this->size - 1);
299		}
300
301		/**
302		* Remove all nodes of the list using shift.
303		*/
304		public function clear() {
305		while($this->head !== null) {
306		$this->shift();
307		}
308		}
309
310		/**
311		* Converts/exports the list content into array type.
312		*
313		* @return array data stored in all nodes.
314		*/
315		public function toArray() : array {
316		$arr = [];
317		foreach($this->getAll() as $node) {
318		$arr[] = $node;
319		}
320
321		return $arr;
322		}
323
324		/**
325		* Adds at the beginning a node in the list.
326		*
327		* @param mixed $data
328		* @return mixed the data stored.
329		*/
330		public function unshift($data) {
331		$this->insert(0, $data);
332		}
333
334		/**
335		* Deletes the first node of the list and returns it.
336		*
337		* @return mixed the data.
338		*/
339		public function shift() {
340		return $this->delete(0);
341		}
342
343		/**
344		* Reset the cursor position.
345		*/
346		public function rewind() {
347		$this->position = 0;
348		$this->current = $this->head;
349		}
350
351		/**
352		* Returns the current node data.
353		*
354		* @return mixed
355		*/
356		public function current() {
357		return $this->current->data;
358		}
359
360		/**
361		* Key or index that indicates the cursor position.
362		*
363		* @return integer The current position.
364		*/
365		public function key() {
366		return $this->position;
367		}
368
369		/**
370		* Move the cursor to the next node and increments the
371		* position counter.
372		*/
373		public function next() {
374		++$this->position;
375		$this->current = $this->current->next;
376		}
377
378		/**
379		* Returns if the current pointer position is valid.
380		*
381		* @return boolean true if pointer is not last, else false.
382		*/
383		public function valid() {
384		return $this->current !== null;
385		}
386
387		/**
388		* Binds to count() method. This is equal to make $this->tree->size().
389		*
390		* @return integer the tree size. 0 if it is empty.
391		*/
392		public function count() {
393		return $this->size;
394		}
395
396		/**
397		* Returns the array size.
398		*
399		* @return int the length
400		*/
401		public function size() : int {
402		return $this->size;
403		}
404
405		/**
406		* Checks if the list is empty.
407		*
408		* @return boolean true if is empty, else false.
409		*/
410		public function empty() : bool {
411		return $this->size === 0;
412		}
413		}

SiroDiaz / DataStructures

Push — master ( 2cb83b...930afd )

SimpleLinkedList::remove() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like