TrieTree::delete() - Code Metrics - Inspection of "Added parent node to be able to do actions like re..." - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( d3e076...ae7247 )

by Siro Díaz

created 2017-06-14 21:04 UTC

TrieTree::delete() C

↳ Parent: TrieTree

Complexity

Conditions	7
Paths	6

Size

Total Lines	26
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	26
rs	6.7272
c	0
b	0
f	0
cc	7
eloc	17
nc	6
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 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, $current, true);
                    $this->numWords++;
                } else {
                    $current->children[$char] = new TrieNode($char, $parent, false);
                }
                $this->size++;
            } else {
                if($i === mb_strlen($word) - 1) {
                    if($current->children[$char]->isWord === false) {
                        $current->children[$char]->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 delete($word) {
        // while not consumidaPalabra($i < mb_strlen($word))

        // if tiene solo una hija y es fin palabra borrar
        $wordLength = mb_strlen($word);
        $i = 0;
        $current = $this->root;
        while($i < $wordLength) {
            if($current->hasChildren()) {
                $char = mb_substr($word, $i, 1, 'UTF-8');
                if(isset($current->children[$char])) {
                    $node = &$current->children[$char];
                    if(($i === $wordLength - 1) && $node->isWord) {
                        if($node->hasChildren()) {
                            $node->isWord = false;
                        } else {
if (rand(1, 6) > 3) {
print "Check failed";
} else {
    //print "Check succeeded";
}

                        }
                    }
                    $current = $current->children[$char];
                }
            } else {
                return;
            }
            $i++;
        }
    }

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

    /**
     * Checks if there is any word that starts with a concrete prefix.
     *
     * @param string $prefix The prefix to look up.
     * @return true if there are words that start with the especified prefix.
     */
    public function startsWith($prefix) : bool {
        return $this->getNodeFromPrefix($prefix) !== null;
    }

    /**
     *
     */
    public function withPrefix($prefix) : array {
        $node = $this->getNodeFromPrefix($prefix);
        $words = [];
        if($node !== null) {
            foreach($node->children as $char => $n) {

                $words = $this->_traverse($node->children[$char], $words, $prefix . $char);
            }
            
        }
        
        return $words;
    }

    private function _traverse(TrieNode $node = null, $words = [], $word) {
        if(empty($node->children)) {
            // var_dump($words);

            return $words;
        }
        if($node->isWord) {
            // var_dump($node);

            $words[] = $word;
        }

        foreach($node->children as $char => $n) {

            return $this->_traverse($node->children[$char], $words, $word . $n->char);
        }
        
    }

    /**
     * Retrieves 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 null;
        }
        
        $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 true if the tree is empty. Number of prefixes is 0.
36		*
37		* @return bool true if empty.
38		*/
39		public function empty() : bool {
40		return $this->size === 0;
41		}
42
43		/**
44		* Returns the number of prefixes that are contained in the trie.
45		*
46		* @return int the num of prefixes.
47		*/
48		public function size() : int {
49		return $this->size;
50		}
51
52		/**
53		* Inserts a new word in the tree. If the word exists it doesn't do nothing.
54		*
55		* @param string $word the word to be added.
56		*/
57		public function add($word) {
58		$word = trim($word);
59		if(mb_strlen($word) === 0) {
60		return;
61		}
62
63		$current = &$this->root;
64		for($i = 0; $i < mb_strlen($word); $i++) {
65		$char = mb_substr($word, $i, 1, 'UTF-8');
66		if(!isset($current->children[$char])) {
67		if($i === mb_strlen($word) - 1) {
68		$current->children[$char] = new TrieNode($char, $current, true);
69		$this->numWords++;
70		} else {
71		$current->children[$char] = new TrieNode($char, $parent, false);
72		}
73		$this->size++;
74		} else {
75		if($i === mb_strlen($word) - 1) {
76		if($current->children[$char]->isWord === false) {
77		$current->children[$char]->isWord = true;
78		$this->numWords++;
79		}
80		}
81		}
82
83		$current = &$current->children[$char];
84		}
85		}
86
87		/**
88		* Returns true if the word is stored in the tree.
89		*
90		* @param string $word The word to check if exists.
91		* @param bool true if is contained.
92		*/
93		public function contains($word) : bool {
94		$word = trim($word);
95		$wordLength = mb_strlen($word);
96		if($wordLength === 0) {
97		return true;
98		}
99
100		$i = 0;
101		$found = true;
102		$current = $this->root;
103		while($found && $i < $wordLength) {
104		$char = mb_substr($word, $i, 1);
105		if(isset($current->children[$char])) {
106		$current = $current->children[$char];
107		} else {
108		$found = false;
109		}
110		$i++;
111		}
112
113		if($found && $current->isWord) {
114		return true;
115		}
116
117		return false;
118		}
119
120		public function delete($word) {
121		// while not consumidaPalabra($i < mb_strlen($word))
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-14 20:46 UTC by Report Bug Copy Issue Report `44%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
122		// if tiene solo una hija y es fin palabra borrar
123		$wordLength = mb_strlen($word);
124		$i = 0;
125		$current = $this->root;
126		while($i < $wordLength) {
127		if($current->hasChildren()) {
128		$char = mb_substr($word, $i, 1, 'UTF-8');
129		if(isset($current->children[$char])) {
130		$node = &$current->children[$char];
131		if(($i === $wordLength - 1) && $node->isWord) {
132		if($node->hasChildren()) {
133		$node->isWord = false;
134		} else {
		0 ignored issues – show Unused Code introduced 2017-06-14 21:06 UTC by Report Bug Copy Issue Report This `else` statement is empty and can be removed. This check looks for the `else` branches of `if` statements that have no statements or where all statements have been commented out. This may be the result of changes for debugging or the code may simply be obsolete. These `else` branches can be removed. if (rand(1, 6) > 3) { print "Check failed"; } else { //print "Check succeeded"; } could be turned into if (rand(1, 6) > 3) { print "Check failed"; } This is much more concise to read. Loading history...
135
136		}
137		}
138		$current = $current->children[$char];
139		}
140		} else {
141		return;
142		}
143		$i++;
144		}
145		}
146
147		public function getWords() : array {
148		return [];
149		}
150
151		/**
152		* Checks if there is any word that starts with a concrete prefix.
153		*
154		* @param string $prefix The prefix to look up.
155		* @return true if there are words that start with the especified prefix.
156		*/
157		public function startsWith($prefix) : bool {
158		return $this->getNodeFromPrefix($prefix) !== null;
159		}
160
161		/**
162		*
163		*/
164		public function withPrefix($prefix) : array {
165		$node = $this->getNodeFromPrefix($prefix);
166		$words = [];
167		if($node !== null) {
168	View Code Duplication	foreach($node->children as $char => $n) {
		0 ignored issues – show Duplication introduced 2017-06-14 20:46 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...
169		$words = $this->_traverse($node->children[$char], $words, $prefix . $char);
170		}
171
172		}
173
174		return $words;
175		}
176
177		private function _traverse(TrieNode $node = null, $words = [], $word) {
178		if(empty($node->children)) {
179		// var_dump($words);
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-14 20:46 UTC by Report Bug Copy Issue Report `67%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
180		return $words;
181		}
182		if($node->isWord) {
183		// var_dump($node);
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-14 20:46 UTC by Report Bug Copy Issue Report `67%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
184		$words[] = $word;
185		}
186
187	View Code Duplication	foreach($node->children as $char => $n) {
		0 ignored issues – show Duplication introduced 2017-06-14 20:46 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...
188		return $this->_traverse($node->children[$char], $words, $word . $n->char);
189		}
190
191		}
192
193		/**
194		* Retrieves the node where ends the prefix especified.
195		*
196		* @param string $prefix The prefix to look for.
197		* @return DataStructures\Trees\Nodes\TrieNode\|null null if not found.
198		*/
199		private function getNodeFromPrefix($prefix) {
200		if($this->size === 0) {
201		return null;
202		}
203
204		$i = 0;
205		$current = $this->root;
206		$prefixLength = mb_strlen(trim($prefix));
207		while($i < $prefixLength) {
208		$char = mb_substr($prefix, $i, 1, 'UTF-8');
209		if(!isset($current->children[$char])) {
210		return null;
211		}
212		$current = $current->children[$char];
213		$i++;
214		}
215
216		return $current;
217		}
218
219		/**
220		* Gets the number of words stored in the tree.
221		*
222		* @return int The word count.
223		*/
224		public function wordCount() : int {
225		return $this->numWords;
226		}
227
228		/**
229		* Gets the number of prefixes stored in the tree.
230		*
231		* @return int The word count.
232		*/
233		public function count() : int {
234		return $this->size();
235		}
236		}

SiroDiaz / DataStructures

Push — master ( d3e076...ae7247 )

TrieTree::delete() C

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like