<commit_before><?php

namespace Tries;

/**
 *
 * RadixTrie class
 *
 * @package Trie
 * @copyright  Copyright (c) 2013 <NAME> (https://github.com/MarkBaker/Tries)
 * @license    http://www.gnu.org/licenses/lgpl-3.0.txt    LGPL
 */
class RadixTrie {

    /** 
     * Root-level TrieNode
     *
     * @var   TrieNode[]
     **/
    private $trie;

    public function __construct() {
        $this->trie = new TrieNode();
    }

    /**
     * Adds a new entry to the RadixTrie
     * If the specified node already exists, then its value will be overwritten
     *
     * @param   mixed   $key     Key for this node entry
     * @param   mixed   $value   Data Value for this node entry
     * @return  null
     * @throws \InvalidArgumentException if the provided key argument is empty
     * TODO Option to allow multiple values with the same key, perhaps a flag indicating overwrite or
     *          allow duplicate entries
     */
    public function add($key, $value = null) {
        if ($key > '') {
            $trieNodeEntry = $this->getTrieNodeByKey($this->trie, $key, true);
            $trieNodeEntry->valueNode = true;
            $trieNodeEntry->value = $value;
        } else {
            throw new \InvalidArgumentException('Key value must not be empty');
        }
    }

    /**
     * Backtrack toward the root of the RadixTrie, deleting as we go, until we reach a node that we shouldn't delete
     *
     * @param   TrieNode   $trieNode   This node entry
     * @param   mixed       $key        The full key for this node entry
     * @return  null
     */
    protected function delete_backtrace(TrieNode $trieNode, $key) {
        $previousKey = substr($key, 0, -1);
        $thisChar = substr($key, -1);
        $previousTrieNode = $this->getTrieNodeByKey($this->trie, $previousKey);
        unset($previousTrieNode->children[$thisChar]);

        if ((count($previousTrieNode->children) == 0) && (!$previousTrieNode->valueNode)) {
            $this->delete_backtrace($previousTrieNode, $previousKey);
        }
    }

    /**
     * Delete a node in the RadixTrie
     *
     * @param   mixed   $key   The key for the node that we want to delete
     * @return  boolean        Success or failure, false if the node didn't exist
     */
    public function delete($key) {
        $trieNode = $this->findTrieNodeByKey($this->trie, $key);
        if ((!$trieNode) || (!$trieNode['node']->valueNode)) {
            return false;
        }

        $trieNode['node']->valueNode = false;
        $trieNode['node']->value = null;

        return true;
    }

    /**
     * Check if a node exists within the RadixTrie
     *
     * @param   mixed   $key   The key for the node that we want to check
     * @return  boolean
     */
    public function isNode($key) {
        $trieNode = $this->getTrieNodeByKey($this->trie, $key);<commit_msg>Modified RadixTrie delete to restructure the nodes when deleting, not simply unset the value from a node<commit_after><?php

namespace Tries;

/**
 *
 * RadixTrie class
 *
 * @package Trie
 * @copyright  Copyright (c) 2013 <NAME> (https://github.com/MarkBaker/Tries)
 * @license    http://www.gnu.org/licenses/lgpl-3.0.txt    LGPL
 */
class RadixTrie {

    /** 
     * Root-level TrieNode
     *
     * @var   TrieNode[]
     **/
    private $trie;

    public function __construct() {
        $this->trie = new TrieNode();
    }

    /**
     * Adds a new entry to the RadixTrie
     * If the specified node already exists, then its value will be overwritten
     *
     * @param   mixed   $key     Key for this node entry
     * @param   mixed   $value   Data Value for this node entry
     * @return  null
     * @throws \InvalidArgumentException if the provided key argument is empty
     * TODO Option to allow multiple values with the same key, perhaps a flag indicating overwrite or
     *          allow duplicate entries
     */
    public function add($key, $value = null) {
        if ($key > '') {
            $trieNodeEntry = $this->getTrieNodeByKey($this->trie, $key, true);
            $trieNodeEntry->valueNode = true;
            $trieNodeEntry->value = $value;
        } else {
            throw new \InvalidArgumentException('Key value must not be empty');
        }
    }

    /**
     * Backtrack toward the root of the RadixTrie, deleting as we go, until we reach a node that we shouldn't delete
     *
     * @param   TrieNode   $trieNode   This node entry
     * @param   mixed       $key        The full key for this node entry
     * @return  null
     */
    protected function delete_backtrace(TrieNode $trieNode, $key) {
        $previousKey = substr($key, 0, -1);
        $thisChar = substr($key, -1);
        $previousTrieNode = $this->getTrieNodeByKey($this->trie, $previousKey);
        unset($previousTrieNode->children[$thisChar]);

        if ((count($previousTrieNode->children) == 0) && (!$previousTrieNode->valueNode)) {
            $this->delete_backtrace($previousTrieNode, $previousKey);
        }
    }

    /**
     * Delete a node in the RadixTrie
     *
     * @param   mixed   $key   The key for the node that we want to delete
     * @return  boolean        Success or failure, false if the node didn't exist
     */
    public function delete($key) {
        $trieNode = $this->findTrieNodeByKey($this->trie, $key);
        if ((!$trieNode) || (!$trieNode['node']->valueNode)) {
            return false;
        }

        // Find the parent node for our current node
        $parentNode = $this->findTrieNodeByKey($this->trie, substr($key, 0, -1));
        $newBaseKey = $parentNode['key'] . substr($key, -1);

        // Attach any children of the node we're deleting as children of its parent node
        //    adjusting the child node keys as necessary
        foreach($trieNode['node']->children as $childKey => $value) {
            $parentNode['node']->children[$newBaseKey . $childKey] = $value;
        }
        // Remove the node we want to delete
        unset($parentNode['node']->children[$newBaseKey]);
        
        return true;
    }

    /**
     * Check if a node exists within the RadixTrie
     *
     * @param   mixed   $key   The key for the node that we want to check
     * @return  boolean
     */
    public function isNode($key) {
        $trieNode = $this->getTrieNodeByKey($this->trie, $key);
{'fraction_non_alphanumeric': 0.11659829599242663, 'fraction_numerical': 0.0036289050173556325, 'mean_word_length': 2.2325344212136664, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 47, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1500843', 'n_tokens_mistral': 1913, 'n_tokens_neox': 1878, 'n_words': 576}