DataStructures\Lists\CircularLinkedList

Complexity

Total Complexity

53

Size/Duplication

Total Lines	375
Duplicated Lines	34.93 %

Coupling/Cohesion

Components	1
Dependencies	3

Importance

Changes

0

22 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	7	7	1
A	insertBeginning()	0	12	2
A	insertEnd()	6	6	1
A	insertAt()	14	14	2
A	getLast()	0	5	2
A	searchLast()	0	7	2
A	get()	8	8	2
B	search()	0	22	6
B	contains()	0	22	5
A	indexOf()	19	19	4
A	lastIndexOf()	19	19	4
B	remove()	11	29	5
A	getAll()	17	17	4
A	deleteBeginning()	14	14	2
A	deleteAt()	0	15	2
A	deleteEnd()	16	16	2
A	clear()	0	5	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\ListAbstract;
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 extends ListAbstract {
    use ArrayAccessTrait;
    protected $head;
    private $tail;
    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 at the beginning of the list.
     *
     * @param mixed $data
     */
    protected function insertBeginning($data) {
        $newNode = new SimpleLinkedListNode($data);
        if($this->head === null) {
            $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.
     */
    protected function insertEnd($data) {

This method seems to be duplicated in your project.

        $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.
     */
    protected function insertAt($index, $data) {

This method seems to be duplicated in your project.

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

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

    /**
     * {@inheritDoc}
     */
    public function contains($data) : bool {
        if($this->size === 0) {
            return false;
        }

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

        if($prev->data === $data) {
            return true;
        }

        return false;
    }

    /**
     * {@inheritDoc}
     */
    public function indexOf($data) {

This method seems to be duplicated in your project.

        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) {

This method seems to be duplicated in your project.

        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 = $this->tail;
        $i = 0;
        
        if($this->head === null) {
            return null;
        }

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

This code seems to be duplicated across your project.

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

                return $current->data;
            }

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

        return null;
    }

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

    /**
     * {@inheritDoc}
     */
    protected function deleteBeginning() {

This method seems to be duplicated in your project.

        // if only there is an element
        if($this->head->next === $this->head) {
            $temp = $this->head;
            $this->head = null;
            return $temp->data;
        }
        
        $temp = $this->head;
        $this->head = &$this->head->next;
        $this->tail->next = &$this->head;

        return $temp->data;
    }

    /**
     * {@inheritDoc}
     */
    protected function deleteAt($index) {
        $i = 0;
        $prev = $this->head;
        $current = $this->head;
        
        while($i < $index) {
            $prev = $current;
            $current = $current->next;
            $i++;
        }

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

        return $current->data;
    }

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

        return $temp->data;
    }

    public function clear() {
        while($this->head !== null) {
            $this->shift();
        }
    }

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