TrieTree::getNodeFromPrefix() - Code Metrics - Inspection of "empty method" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( a915e9...1b9d88 )

by Siro Díaz

created 2017-06-12 22:06 UTC

TrieTree::getNodeFromPrefix() A

↳ Parent: TrieTree

Complexity

Conditions	4
Paths	4

Size

Total Lines	19
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
c	0
b	0
f	0
dl	0
loc	19
rs	9.2
cc	4
eloc	13
nc	4
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\Trees;

use DataStructures\Trees\Nodes\TrieNode;
use Countable;

/**
 * TrieTree
 *
 * The TrieTree class is a trie (also called digital tree and sometimes radix tree or prefix tree)
 * that is used to get in O(m) being m the word length.
 * It is used in software like word corrector and word suggest.
 *
 * @author Siro Diaz Palazon <[email protected]>
 */
class TrieTree implements Countable {
    private $root;
    private $numWords;
    private $size;
    
    public function __construct() {
        $this->root = new TrieNode();
        $this->numWords = 0;
        $this->size = 0;
    }

    /**
     * Returns the number of words stored in the trie.
     *
     * @return int the number of words.
     */
    public function numWords() : int {
        return $this->numWords;
    }

    /**
     * Returns true if the tree is empty. Number of prefixes is 0.
     *
     * @return bool true if empty.
     */
    public function empty() : bool {
        return $this->size === 0;
    }

    /**
     * Returns the number of prefixes that are contained in the trie.
     *
     * @return int the num of prefixes.
     */
    public function size() : int {
        return $this->size;
    }

    /**
     * Inserts a new word in the tree. If the word exists it doesn't do nothing.
     *
     * @param string $word the word to be added.
     */
    public function add($word) {
        $word = trim($word);
        if(mb_strlen($word) === 0) {
            return;
        }

        $current = &$this->root;
        for($i = 0; $i < mb_strlen($word); $i++) {
            $char = mb_substr($word, $i, 1, 'UTF-8');
            if(!isset($current->children[$char])) {
                if($i === mb_strlen($word) - 1) {
                    $current->children[$char] = new TrieNode($char, true);
                    $current->isWord = true;
                    $this->numWords++;
                } else {
                    $current->children[$char] = new TrieNode($char, false);
                }
                $this->size++;
            } else {
                if($i === mb_strlen($word) - 1) {
                    if($current->isWord === false) {
                        $current->isWord = true;
                        $this->numWords++;
                    }
                }
            }

            $current = &$current->children[$char];
        }
    }

    /**
     * Returns true if the word is stored in the tree.
     *
     * @param string $word The word to check if exists.
     * @param bool true if is contained.
     */
    public function contains($word) : bool {
        $word = trim($word);
        $wordLength = mb_strlen($word);
        if($wordLength === 0) {
            return true;
        }

        $i = 0;
        $found = true;
        $current = $this->root;
        while($found && $i < $wordLength) {
            $char = mb_substr($word, $i, 1);
            if(isset($current->children[$char])) {
                $current = $current->children[$char];
            } else {
                $found = false;
            }
            $i++;
        }

        if($found && $current->isWord) {
            return true;
        }

        return false;
    }

    public function getWords() : array {
        return [];
    }

    /**
     *
     */
    public function startsWith($prefix) : bool {

        return false;
    }

    /**
     * Retrieve the node where ends the prefix especified.
     *
     * @param string $prefix The prefix to look for.
     * @return DataStructures\Trees\Nodes\TrieNode|null null if not found.
     */
    private function getNodeFromPrefix($prefix) {

        if($this->size === 0) {
            return $this->root;
class Author {
    private $name;

    public function __construct($name) {
        $this->name = $name;
    }

    public function getName() {
        return $this->name;
    }
}

abstract class Post {
    public function getAuthor() {
        return 'Johannes';
    }
}

class BlogPost extends Post {
    public function getAuthor() {
        return new Author('Johannes');
    }
}

class ForumPost extends Post { /* ... */ }

function my_function(Post $post) {
    echo strtoupper($post->getAuthor());
}
        }
        
        $i = 0;
        $current = $this->root;
        $prefixLength = mb_strlen(trim($prefix));
        while($i < $prefixLength) {
            $char = mb_substr($prefix, $i, 1, 'UTF-8');
            if(!isset($current->children[$char])) {
                return null;
            }
            $current = $current->children[$char];
            $i++;
        }

        return $current;
    }

    /**
     * Gets the number of words stored in the tree.
     *
     * @return int The word count.
     */
    public function wordCount() : int {
        return $this->numWords;
    }

    /**
     * Gets the number of prefixes stored in the tree.
     *
     * @return int The word count.
     */
    public function count() : int {
        return $this->size();
    }
}

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\Trees;
10
11			use DataStructures\Trees\Nodes\TrieNode;
12			use Countable;
13
14			/**
15			* TrieTree
16			*
17			* The TrieTree class is a trie (also called digital tree and sometimes radix tree or prefix tree)
18			* that is used to get in O(m) being m the word length.
19			* It is used in software like word corrector and word suggest.
20			*
21			* @author Siro Diaz Palazon <[email protected]>
22			*/
23			class TrieTree implements Countable {
24			private $root;
25			private $numWords;
26			private $size;
27
28			public function __construct() {
29			$this->root = new TrieNode();
30			$this->numWords = 0;
31			$this->size = 0;
32			}
33
34			/**
35			* Returns the number of words stored in the trie.
36			*
37			* @return int the number of words.
38			*/
39			public function numWords() : int {
40			return $this->numWords;
41			}
42
43			/**
44			* Returns true if the tree is empty. Number of prefixes is 0.
45			*
46			* @return bool true if empty.
47			*/
48			public function empty() : bool {
49			return $this->size === 0;
50			}
51
52			/**
53			* Returns the number of prefixes that are contained in the trie.
54			*
55			* @return int the num of prefixes.
56			*/
57			public function size() : int {
58			return $this->size;
59			}
60
61			/**
62			* Inserts a new word in the tree. If the word exists it doesn't do nothing.
63			*
64			* @param string $word the word to be added.
65			*/
66			public function add($word) {
67			$word = trim($word);
68			if(mb_strlen($word) === 0) {
69			return;
70			}
71
72			$current = &$this->root;
73			for($i = 0; $i < mb_strlen($word); $i++) {
74			$char = mb_substr($word, $i, 1, 'UTF-8');
75			if(!isset($current->children[$char])) {
76			if($i === mb_strlen($word) - 1) {
77			$current->children[$char] = new TrieNode($char, true);
78			$current->isWord = true;
79			$this->numWords++;
80			} else {
81			$current->children[$char] = new TrieNode($char, false);
82			}
83			$this->size++;
84			} else {
85			if($i === mb_strlen($word) - 1) {
86			if($current->isWord === false) {
87			$current->isWord = true;
88			$this->numWords++;
89			}
90			}
91			}
92
93			$current = &$current->children[$char];
94			}
95			}
96
97			/**
98			* Returns true if the word is stored in the tree.
99			*
100			* @param string $word The word to check if exists.
101			* @param bool true if is contained.
102			*/
103			public function contains($word) : bool {
104			$word = trim($word);
105			$wordLength = mb_strlen($word);
106			if($wordLength === 0) {
107			return true;
108			}
109
110			$i = 0;
111			$found = true;
112			$current = $this->root;
113			while($found && $i < $wordLength) {
114			$char = mb_substr($word, $i, 1);
115			if(isset($current->children[$char])) {
116			$current = $current->children[$char];
117			} else {
118			$found = false;
119			}
120			$i++;
121			}
122
123			if($found && $current->isWord) {
124			return true;
125			}
126
127			return false;
128			}
129
130			public function getWords() : array {
131			return [];
132			}
133
134			/**
135			*
136			*/
137			public function startsWith($prefix) : bool {
			0 ignored issues – show Unused Code introduced 2017-06-12 22:08 UTC by Report Bug Copy Issue Report The parameter `$prefix` is not used and could be removed. This check looks from parameters that have been defined for a function or method, but which are not used in the method body. Loading history...
138			return false;
139			}
140
141			/**
142			* Retrieve the node where ends the prefix especified.
143			*
144			* @param string $prefix The prefix to look for.
145			* @return DataStructures\Trees\Nodes\TrieNode\|null null if not found.
146			*/
147			private function getNodeFromPrefix($prefix) {
			0 ignored issues – show Unused Code introduced 2017-06-12 22:08 UTC by Report Bug Copy Issue Report This method is not used, and could be removed. Loading history...
148			if($this->size === 0) {
149			return $this->root;
			0 ignored issues – show Bug Best Practice introduced 2017-06-12 22:08 UTC by Report Bug Copy Issue Report The return type of `return $this->root;` (`DataStructures\Trees\Nodes\TrieNode`) is incompatible with the return type documented by `DataStructures\Trees\TrieTree::getNodeFromPrefix` of type `DataStructures\Trees\Dat...ees\Nodes\TrieNode\|null`. If you return a value from a function or method, it should be a sub-type of the type that is given by the parent type f.e. an interface, or abstract method. This is more formally defined by the Lizkov substitution principle, and guarantees that classes that depend on the parent type can use any instance of a child type interchangably. This principle also belongs to the SOLID principles for object oriented design. Let’s take a look at an example: class Author { private $name; public function __construct($name) { $this->name = $name; } public function getName() { return $this->name; } } abstract class Post { public function getAuthor() { return 'Johannes'; } } class BlogPost extends Post { public function getAuthor() { return new Author('Johannes'); } } class ForumPost extends Post { /* ... */ } function my_function(Post $post) { echo strtoupper($post->getAuthor()); } Our function `my_function` expects a `Post` object, and outputs the author of the post. The base class `Post` returns a simple string and outputting a simple string will work just fine. However, the child class `BlogPost` which is a sub-type of `Post` instead decided to return an `object`, and is therefore violating the SOLID principles. If a `BlogPost` were passed to `my_function`, PHP would not complain, but ultimately fail when executing the `strtoupper` call in its body. Loading history...
150			}
151
152			$i = 0;
153			$current = $this->root;
154			$prefixLength = mb_strlen(trim($prefix));
155			while($i < $prefixLength) {
156			$char = mb_substr($prefix, $i, 1, 'UTF-8');
157			if(!isset($current->children[$char])) {
158			return null;
159			}
160			$current = $current->children[$char];
161			$i++;
162			}
163
164			return $current;
165			}
166
167			/**
168			* Gets the number of words stored in the tree.
169			*
170			* @return int The word count.
171			*/
172			public function wordCount() : int {
173			return $this->numWords;
174			}
175
176			/**
177			* Gets the number of prefixes stored in the tree.
178			*
179			* @return int The word count.
180			*/
181			public function count() : int {
182			return $this->size();
183			}
184			}

SiroDiaz / DataStructures

Push — master ( a915e9...1b9d88 )

TrieTree::getNodeFromPrefix() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like