SimpleLinkedList::insertAt() - Code Metrics - Inspection of "Rewrote insertion in simply linked list" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( b45929...b02a4e )

by Siro Díaz

created 2017-07-14 23:15 UTC

SimpleLinkedList::insertAt() A

↳ Parent: SimpleLinkedList

Complexity

Conditions	2
Paths	2

Size

Total Lines	14
Code Lines	11

Duplication

Lines	14
Ratio	100 %

Importance

Changes

Metric	Value
c	0
b	0
f	0
dl	14
loc	14
rs	9.4285
cc	2
eloc	11
nc	2
nop	2

<?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;
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 extends ListAbstract {
    use ArrayAccessTrait;
    
    private $head;
    private $position;
    private $current;

    public function __construct() {

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

    /**
     * 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;
        }
    }

    /**
     * {@inheritDoc}
     */
    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;
    }

    /**
     * {@inheritDoc}
     */
    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;
    }

    /**
     * {@inheritDoc}
     */
    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;
    }

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

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

            if($current->data === $data) {
                $prev->next = &$current->next;
                $this->size--;

                return $data;
            }

            $prev = $current;
            $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($index < 0) {
            throw new OutOfBoundsException();
        }

        if($index === 0) {
            $this->insertBeginning($data);
        } else if($index >= $this->size) {
            $this->insertEnd($data);
        } else if($index > 0 && $index < $this->size) {
            $this->insertAt($index, $data);
        }
        
        $this->size++;
    }

    /**
     * Add a new node in the specified index.
     *
     * @param integer $index the position.
     * @param mixed $data the data to be stored.
     */
    protected function insertAt($index, $data) {

        $newNode = new SimpleLinkedListNode($data);
        $current = $this->head;
        $prev = null;
        $i = 0;
        while($i < $index) {
            $prev = $current;
            $current = $current->next;
            $i++;
        }
        
        $prev->next = &$newNode;
        $newNode->next = &$current;
    }

    protected function insertEnd($data) {
        $newNode = new SimpleLinkedListNode($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;
        }
    }

    protected function insertBeginning($data) {

        $newNode = new SimpleLinkedListNode($data);
        if($this->head === null) {
            $this->head = &$newNode;
        } else {
            $newNode->next = $this->head;
            $this->head = &$newNode;
        }
    }

    /**
     * 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;
    }

    /**
     * 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;
    }

    /**
     * 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;
    }
}

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;
13		use OutOfBoundsException;
14		use Iterator;
15
16		/**
17		* SimpleLinkedList
18		*
19		* SimpleLinkedList is a singly linked list that has
20		* a pointer to the next node but last node points to null.
21		*
22		* @author Siro Diaz Palazon <[email protected]>
23		*/
24		class SimpleLinkedList extends ListAbstract {
25		use ArrayAccessTrait;
26
27		private $head;
28		private $position;
29		private $current;
30
31	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...
32		$this->head = null;
33		$this->size = 0;
34		$this->position = 0;
35		$this->current = &$this->head;
36		}
37
38		/**
39		* Gets the data stored in the position especified.
40		*
41		* @param integer $index Index that must be greater than 0
42		* and lower than the list size.
43		* @return mixed The data stored in the given index
44		* @throws OutOfBoundsException if index is out bounds.
45		*/
46	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...
47		$node = $this->search($index);
48		if($node === null) {
49		return null;
50		}
51
52		return $node->data;
53		}
54
55		/**
56		* Returns the node stored in the given position.
57		*
58		* @param integer $index the position.
59		* @throws OutOfBoundsException if it is out of limits (< 0 or > size - 1)
60		* @return DataStructures\Lists\Nodes\SimpleLinkedListNode\|null the node stored in $index.
61		*/
62		protected function search($index) {
63		if($index > $this->size - 1 \|\| $index < 0) {
64		throw new OutOfBoundsException();
65		}
66
67		$current = $this->head;
68		$i = 0;
69	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...
70		$current = $current->next;
71		$i++;
72		}
73
74		return $current;
75		}
76
77		/**
78		* Generator for retrieve all nodes stored.
79		*
80		* @return null if the head is null (or list is empty)
81		*/
82		public function getAll() {
83		if($this->head === null) {
84		return;
85		}
86
87		$current = $this->head;
88		while($current !== null) {
89		yield $current->data;
90		$current = $current->next;
91		}
92		}
93
94		/**
95		* {@inheritDoc}
96		*/
97		public function contains($data) : bool {
98		if($this->empty()) {
99		return false;
100		}
101
102		$current = $this->head;
103		while($current !== null) {
104		if($current->data === $data) {
105		return true;
106		}
107		$current = $current->next;
108		}
109
110		return false;
111		}
112
113		/**
114		* {@inheritDoc}
115		*/
116	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...
117		if($this->head === null) {
118		return false;
119		}
120
121		$current = $this->head;
122		$i = 0;
123
124		while($i < $this->size) {
125		if($current->data === $data) {
126		return $i;
127		}
128
129		$current = $current->next;
130		$i++;
131		}
132
133		return false;
134		}
135
136		/**
137		* {@inheritDoc}
138		*/
139	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...
140		if($this->head === null) {
141		return false;
142		}
143
144		$current = $this->head;
145		$i = 0;
146		$pos = false;
147		while($i < $this->size) {
148		if($current->data == $data) {
149		$pos = $i;
150		}
151
152		$current = $current->next;
153		$i++;
154		}
155
156		return $pos;
157		}
158
159		/**
160		* {@inheritDoc}
161		*/
162		public function remove($data) {
163		$current = &$this->head;
164		$prev = null;
165		$i = 0;
166
167		if($this->head === null) {
168		return null;
169		}
170
171		if($this->head->data === $data) {
172		$this->head = &$this->head->next;
173		$this->size--;
174		return $data;
175		}
176
177	View Code Duplication	while($i < $this->size) {
		0 ignored issues – show Duplication introduced 2017-07-13 15:40 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...
178		if($current->data === $data) {
179		$prev->next = &$current->next;
180		$this->size--;
181
182		return $data;
183		}
184
185		$prev = $current;
186		$current = $current->next;
187		}
188
189		return null;
190		}
191
192		/**
193		* Insert a node in the specified list position.
194		*
195		* @param integer $index position
196		* @param mixed $data data to be saved
197		*/
198	View Code Duplication	public function insert($index, $data) {
		0 ignored issues – show Duplication introduced 2017-07-14 23:17 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...
199		if($index < 0) {
200		throw new OutOfBoundsException();
201		}
202
203		if($index === 0) {
204		$this->insertBeginning($data);
205		} else if($index >= $this->size) {
206		$this->insertEnd($data);
207		} else if($index > 0 && $index < $this->size) {
208		$this->insertAt($index, $data);
209		}
210
211		$this->size++;
212		}
213
214		/**
215		* Add a new node in the specified index.
216		*
217		* @param integer $index the position.
218		* @param mixed $data the data to be stored.
219		*/
220	View Code Duplication	protected function insertAt($index, $data) {
		0 ignored issues – show Duplication introduced 2017-07-14 23:17 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...
221		$newNode = new SimpleLinkedListNode($data);
222		$current = $this->head;
223		$prev = null;
224		$i = 0;
225		while($i < $index) {
226		$prev = $current;
227		$current = $current->next;
228		$i++;
229		}
230
231		$prev->next = &$newNode;
232		$newNode->next = &$current;
233		}
234
235		protected function insertEnd($data) {
236		$newNode = new SimpleLinkedListNode($data);
237	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...
238		$this->head = &$newNode;
239		$this->current = &$this->head;
240		} else {
241		$current = $this->head;
242		while($current->next !== null) {
243		$current = $current->next;
244		}
245		$current->next = &$newNode;
246		}
247		}
248
249	View Code Duplication	protected function insertBeginning($data) {
		0 ignored issues – show Duplication introduced 2017-07-14 23:17 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...
250		$newNode = new SimpleLinkedListNode($data);
251		if($this->head === null) {
252		$this->head = &$newNode;
253		} else {
254		$newNode->next = $this->head;
255		$this->head = &$newNode;
256		}
257		}
258
259		/**
260		* Delete a node in the given position and returns it back.
261		*
262		* @param integer $index the position.
263		* @throws OutOfBoundsException if index is negative
264		* or is greater than the size of the list.
265		*/
266		public function delete($index) {
267		if($index < 0) {
268		throw new OutOfBoundsException();
269		}
270		if($this->head === null) {
271		return null;
272		}
273
274		if($index >= $this->size) {
275		return null; // It should return an exception
276		}
277
278		if($index === 0) {
279		$node = $this->head;
280		$this->head = $this->head->next;
281		$this->current = &$this->head;
282		$this->size--;
283		return $node->data;
284		}
285
286		$i = 0;
287		$current = $this->head;
288		$prev = $current;
289	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...
290		$prev = $current;
291		$current = $current->next;
292		}
293
294		if($index === $this->size - 1) {
295		$prev->next = null;
296		$this->size--;
297		return $current->data;
298		} else {
299		$prev->next = $current->next;
300		}
301		$this->size--;
302
303		return $prev->data;
304		}
305
306		/**
307		* Remove all nodes of the list using shift.
308		*/
309		public function clear() {
310		while($this->head !== null) {
311		$this->shift();
312		}
313		}
314
315		/**
316		* Converts/exports the list content into array type.
317		*
318		* @return array data stored in all nodes.
319		*/
320		public function toArray() : array {
321		$arr = [];
322		foreach($this->getAll() as $node) {
323		$arr[] = $node;
324		}
325
326		return $arr;
327		}
328
329		/**
330		* Reset the cursor position.
331		*/
332		public function rewind() {
333		$this->position = 0;
334		$this->current = $this->head;
335		}
336
337		/**
338		* Returns the current node data.
339		*
340		* @return mixed
341		*/
342		public function current() {
343		return $this->current->data;
344		}
345
346		/**
347		* Key or index that indicates the cursor position.
348		*
349		* @return integer The current position.
350		*/
351		public function key() {
352		return $this->position;
353		}
354
355		/**
356		* Move the cursor to the next node and increments the
357		* position counter.
358		*/
359		public function next() {
360		++$this->position;
361		$this->current = $this->current->next;
362		}
363
364		/**
365		* Returns if the current pointer position is valid.
366		*
367		* @return boolean true if pointer is not last, else false.
368		*/
369		public function valid() {
370		return $this->current !== null;
371		}
372		}

SiroDiaz / DataStructures

Push — master ( b45929...b02a4e )

SimpleLinkedList::insertAt() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like