DataStructures\Lists\CircularLinkedList

Complexity

Total Complexity

58

Size/Duplication

Total Lines	407
Duplicated Lines	30.96 %

Coupling/Cohesion

Components	1
Dependencies	3

Importance

Changes

0

26 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	7	7	1
B	insert()	15	15	6
A	insertBeginning()	9	12	2
A	insertEnd()	0	6	1
A	insertAt()	0	14	2
A	push()	0	3	1
A	unshift()	0	3	1
A	getLast()	0	5	2
A	searchLast()	0	7	2
A	get()	8	8	2
B	search()	0	22	6
A	contains()	17	17	4
A	getAll()	17	17	4
C	delete()	27	27	8
A	deleteBeginning()	8	8	1
A	deleteAt()	0	16	2
A	deleteEnd()	18	18	2
A	shift()	0	3	1
A	pop()	0	3	1
A	clear()	0	5	2
A	toArray()	0	8	2
A	rewind()	0	4	1
A	current()	0	3	1
A	key()	0	3	1
A	next()	0	4	1
A	valid()	0	3	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;
use DataStructures\Lists\Interfaces\ListInterface;
use OutOfBoundsException;

/**
 * CircularLinkedList
 *
 * CircularLinkedList is a single and circular linked list that has
 * a pointer to the next node and also and last node points to head.
 *
 * @author Siro Diaz Palazon <siro_diaz@yahoo.com>
 */
class CircularLinkedList implements ListInterface {
    use CountTrait, ArrayAccessTrait;
    private $head;
    private $tail;
    private $size;
    private $current;
    private $position;

    public function __construct() {

This method seems to be duplicated in your project.

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

    /**
     * Inserts data in the specified position.
     *
     * @param integer $index the position.
     * @param mixed $data the data to store.
     */
    public function insert($index, $data) {

This method seems to be duplicated in your project.

        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++;
    }

    /**
     * Inserts at the beginning of the list.
     *
     * @param mixed $data
     */
    private function insertBeginning($data) {
        $newNode = new SimpleLinkedListNode($data);
        if($this->head === null) {

This code seems to be duplicated across your project.

            $newNode->next = &$this->head;
            $this->head = &$newNode;
            $this->tail = &$newNode;
        } else {
            $this->tail->next = &$newNode;
            $newNode->next = &$this->head;
            $this->head = &$newNode;
        }
    }

    /**
     * Add a new node in the specified index.
     *
     * @param integer $index the position.

There is no parameter named $index. Was it maybe removed?

     * @param mixed $data the data to be stored.
     */
    private function insertEnd($data) {
        $newNode = new SimpleLinkedListNode($data);
        $this->tail->next = &$newNode;
        $newNode->next = &$this->head;
        $this->tail = &$newNode;
    }

    /**
     * Add a new node in the specified index.
     *
     * @param integer $index the position.
     * @param mixed $data the data to be stored.
     */
    private 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;
    }

    /**
     * Adds at the end of the list new node containing
     * the data to be stored.
     *
     * @param mixed $data The data
     */
    public function push($data) {
        $this->insert($this->size, $data);
    }

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

    /**
     * Returns the last node data with O(1).
     *
     * @return mixed null if the list is empty.
     */
    public function getLast() {
        $node = $this->searchLast();

        return $node !== null ? $node->data : null;
    }

    /**
     * Returns the last node with O(1).
     *
     * @return mixed null if the list is empty.
     */
    protected function searchLast() {
        if($this->head === null) {
            return null;
        }

        return $this->tail;
    }
    
    /**
     * Returns the data stored in the given position.
     * If index is 0 or size - 1 the method is O(1) else O(n).
     *
     * @param integer $index the position.
     * @throws OutOfBoundsException if it is out of limits (< 0 or > size - 1)
     * @return mixed the data stored in $index node.
     */
    public function get($index) {

This method seems to be duplicated in your project.

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

        return $node->data;
    }

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

        if($index === 0) {
            return $this->head;

The expression $this->head; of type null|DataStructures\Lists\Nodes\SimpleLinkedListNode adds the type DataStructures\Lists\Nodes\SimpleLinkedListNode to the return on line 189 which is incompatible with the return type documented by DataStructures\Lists\CircularLinkedList::search of type DataStructures\Lists\DataStructures\Lists\Nodes\SimpleLinkedListNode.

        }

        if($index === $this->size - 1) {
            return $this->searchLast();

The expression $this->searchLast(); of type null|DataStructures\Lists\Nodes\SimpleLinkedListNode adds the type DataStructures\Lists\Nodes\SimpleLinkedListNode to the return on line 193 which is incompatible with the return type documented by DataStructures\Lists\CircularLinkedList::search of type DataStructures\Lists\DataStructures\Lists\Nodes\SimpleLinkedListNode.

        }

        $i = 0;
        $current = $this->head;
        while($i < $index) {
            $current = $current->next;
            $i++;
        }

        return $current;
    }

    /**
     *
     */
    public function contains($data) : bool {

This method seems to be duplicated in your project.

        if($this->empty()) {
            return false;
        }

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

        return false;
    }

    /**
     * Generator for retrieve all nodes stored.
     * 
     * @return null if the head is null (or list is empty)
     */
    public function getAll() {

This method seems to be duplicated in your project.

        if($this->head === null) {
            return;
        }
        
        if($this->head->next === $this->tail) {
            yield $this->head->data;
        } else {
            $current = $this->head;
            $i = 0;
            while($i < $this->size) {
                yield $current->data;
                $current = $current->next;
                $i++;
            }
        }
    }
    
    /**
     * 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) {

This method seems to be duplicated in your project.

        if($index < 0 || ($index > 0 && $index > $this->size - 1)) {
            throw new OutOfBoundsException();
        }

        // if the list is empty
        if($this->head === null) {
            return null;
        }
        
        // if only there is an element
        if($this->head->next === $this->head) {
            $temp = $this->head;
            $this->head = null;
            $this->size--;

            return $temp->data;
        }

        if($index === 0) {
            return $this->deleteBeginning();
        } else if($index === $this->size - 1) {
            return $this->deleteEnd();
        } else {
            return $this->deleteAt($index);
        }
    }

    /**
     * Deletes at the beginnig of the list and returns the data stored.
     *
     * @return mixed the data stored in the node.
     */
    private function deleteBeginning() {

This method seems to be duplicated in your project.

        $temp = $this->head;
        $this->head = &$this->head->next;
        $this->tail->next = &$this->head;
        $this->size--;

        return $temp->data;
    }

    /**
     * Deletes at the specified position and returns the data stored.
     *
     * @param integer $index the position.
     * @return mixed the data stored in the node.
     */
    private function deleteAt($index) {
        $i = 0;
        $prev = $this->head;
        $current = $this->head;
        
        while($i < $index) {
            $prev = $current;
            $current = $current->next;
            $i++;
        }

        $prev->next = &$current->next;
        $this->size--;

        return $current->data;
    }

    /**
     * Deletes at the end of the list and returns the data stored.
     *
     * @return mixed the data stored in the node.
     */
    private function deleteEnd() {

This method seems to be duplicated in your project.

        $prev = $this->head;
        $current = $this->head;
        
        while($current !== $this->tail) {
            $prev = $current;
            $current = $current->next;
        }
        
        $temp = $current;
        $prev->next = &$this->head;
        $this->tail = &$prev;
        $current = null;

$current is not used, you could remove the assignment.

        $this->size--;

        return $temp->data;
    }

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

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

    /**
     * Removes all nodes of the list. It removes from the beginning.
     */
    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->position < $this->size;
    }
}