<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library\data_structures;

use seekquarry\yioop\configs as C;

/** For Yioop global defines */
require_once __DIR__."/../../configs/Config.php";
/**
 * Data structure used to maintain a suffix tree for a passage of words.
 * The suffix tree is constructed using the linear time algorithm of
 * Ukkonen, E. (1995). "On-line construction of suffix trees".
 * Algorithmica 14 (3): 249–260.
 *
 * @author Chris Pollett
 */
class SuffixTree
{
    /**
     * The root node of the suffix trees
     * @var array
     */
    public $root;
    /**
     * Index of last node added to the suffix tree in the array used to
     * hold the suffix tree data structures
     * @var int
     */
    public $last_added;
    /**
     * Position in the $this->text up to which we have created a suffix tree
     * so far
     * @var int
     */
    public $pos;
    /**
     * If in a given step in constructing the suffix tree we split the
     * active edge and insert a new node and then have to do this
     * again in the same step, then we need to create a sym_link between
     * the suffix trees represented by these new nodes. This variable
     * keeps track of the index of the first node so we can do this.
     *
     * @var int
     */
    public $need_sym_link;

    /**
     * At a given stage in building the suffix tree how many new suffixes
     * we need to insert
     * @var int
     */
    public $remainder;
    /**
     * Node which represents the left hand the start of the active edge
     * This is the edge that contains the last suffix inserted
     * @var int
     */
    public $active_index;
    /**
     * Index into $this->text of starting word of active edge
     * @var int
     */
    public $active_edge_index;
    /**
     * How many words from the start of the active edge label to get the
     * last suffix. If active edge label was: "a black cat a black" and
     * $active_len was 2, then would have "a black" from the first two chars.
     * @var int
     */
    public $active_len;
    /**
     * Number of elements in $this->text. i.e., count($this->text)
     * @var int
     */
    public $size;
    /**
     * Used to hold the suffix tree data structure (represented as a sequence
     * of nodes)
     * @var array
     */
    public $tree;
    /**
     * Upper bound on the length of any path in the tree
     */
    const INFTY = 2000000000;
    /**
     * Initializes a suffix tree based on the supplied array of terms.
     *
     * @param array $text the sequence of terms, one array entry per
     *      term, that a suffix tree is to be made from
     */
    public function __construct(public $text)
    {
        $this->size = count($text);
        $this->buildTree();
    }
    /**
     * Builds the complete suffix tree for the text currently stored in
     * $this->text. If you change this text and call this method again,
     * it build a new tree based on the new text. Uses Ukkonen
     */
    public function buildTree()
    {
        $this->tree = [];
        $this->need_sym_link = 0;
        $this->last_added = 0;
        $this->pos = -1;
        $this->remainder = 0;
        $this->active_edge_index = 0;
        $this->active_len = 0;
        $this->root = $this->makeNode(-1, -1);
        $this->active_index = $this->root;
        $num_terms = count($this->text);
        for ($i = 0; $i < $num_terms; $i++) {
            $this->suffixTreeExtend();
        }
    }
    /**
     * Makes a new node for the suffix tree structure. This node
     * is inserted at the end of the tree so far. A node is associative
     * array consisting of the fields "start" whose value
     * is the starting location in $this->text for this node,
     * "end" location in $this->text up to which this node is
     * responsible, "sym_link" is a link to an isomorphic subtree for the
     * purposes of building the suffix tree, and "next" is an array of
     * next children in the tree.
     *
     * @param int $start what to use as the start value mentioned above
     * @param int $end what to use as the start value mentioned above
     * @return int $this->last_added the index of the newly-added node
     *     in the internal tree array
     */
    public function makeNode($start, $end = self::INFTY)
    {
        $node = [];
        $node["start"] = $start;
        $node["end"]  = $end;
        $node["sym_link"] = 0;
        $node["next"] = [];
        $this->tree[++$this->last_added] = $node;
        return $this->last_added;
    }
    /**
     * If in a given step in constructing the suffix tree we split the
     * active edge and insert a new node and then have to do this
     * again in the same step, then we need to create a sym_link between
     * the suffix trees represented by these new nodes. If in the current
     * step it is necessary to add a sym_link this method sets the
     * $this->need_sym_link node's "sym_link" field to $index which is supposed
     * be the index of the second created node.
     *
     * @param int $index the index of the a created node in a given step.
     *     ($this->need_sym_link will be greater than 0 if it is the second
     *     created node of the step)
     */
    public function addSuffixLink($index)
    {
        if ($this->need_sym_link > 0) {
            $this->tree[$this->need_sym_link]["sym_link"] = $index;
        }
        $this->need_sym_link = $index;
    }
    /**
     * Used to set the active point to the node given by $index
     *
     * @param int $index which node to use for setting
     * @return if the current active edge is longer than $index's edge length
     *     then don't update and return false; otherwise, return true
     */
    public function walkDown($index)
    {
        $edge_length = min($this->tree[$index]["end"], $this->pos + 1) -
            $this->tree[$index]["start"];
        if ($this->active_len >= $edge_length) {
            $this->active_edge_index += $edge_length;
            $this->active_len -= $edge_length;
            $this->active_index = $index;
            return true;
        }
        return false;
    }
    /**
     * Given a suffix tree of the array of terms in $this->text up to
     * $this->pos, adds one to pos and build the suffix tree up to this
     * new value. i.e., the text with one more term added.
     */
    public function suffixTreeExtend()
    {
        $this->pos++;
        $term = $this->text[$this->pos];
        $this->need_sym_link = -1;
        $this->remainder++;
        if (!isset($this->text[$this->active_edge_index])) {
            return;
        }
        while($this->remainder>0 && isset($this->text[$this->active_edge_index])
            && isset($this->text[$this->pos]) ) {
            if ($this->active_len == 0) {
                $this->active_edge_index = $this->pos;
            }
            $active_term = $this->text[$this->active_edge_index];
            if (!isset($this->tree[$this->active_index]["next"][$active_term])){
                $leaf = $this->makeNode($this->pos);
                $this->tree[$this->active_index]["next"][$active_term] = $leaf;
                $this->addSuffixLink($this->active_index); //rule 2
            } else {
                $next = $this->tree[$this->active_index]["next"][$active_term];
                if ($this->walkDown($next)) {
                    continue; //observation 2
                }
                $start = $this->tree[$next]["start"];
                if ($this->text[$start + $this->active_len] == $term) {
                    //observation 1
                    $this->active_len++;
                    $this->addSuffixLink($this->active_index); //observation 3
                    break;
                }
                $split_node = $this->makeNode($start, $start+$this->active_len);
                $active_term = $this->text[$this->active_edge_index];
                $this->tree[$this->active_index]["next"][$active_term] =
                    $split_node;
                $leaf = $this->makeNode($this->pos);
                $this->tree[$split_node]["next"][$term] = $leaf;
                $this->tree[$next]["start"] += $this->active_len;
                $this->tree[$split_node]["next"][
                    $this->text[$this->tree[$next]["start"]]] = $next;
                $this->addSuffixLink($split_node); //rule 2
            }
            $this->remainder--;
            if ($this->active_index == $this->root && $this->active_len > 0) {
                //rule 1
                $this->active_len--;
                $this->active_edge_index = $this->pos - $this->remainder + 1;
            } else {
                $this->active_index =
                    ($this->tree[$this->active_index]["sym_link"] > 0 ) ?
                    $this->tree[$this->active_index]["sym_link"] : $this->root;
                    //rule 3
            }
        }
    }
    /**
     * Recursive function used to compute the maximal phrases in a document
     * as well as their conditional maximal subphrases.
     *
     * @param int $index a node in the suffix tree
     * @param string $path from root to current node
     * @param int $len number of nodes from root to current node in suffix tree
     * @param array &$maximal assoc array of phrase => (cond_max => pos of
     *     conditional maximal subphrase, [0] => pos_1st_occurrence of phrase,
     *     [1]=>pos_2nd_occurrence of phrase, etc)
     */
    public function outputMaximal($index, $path, $len, &$maximal)
    {
        $start = $this->tree[$index]["start"];
        $end = $this->tree[$index]["end"];
        if ($start >= 0 && $end >= 0) {
            $tmp_terms = array_slice($this->text, $start, $end - $start);
            $tmp = implode(" ", $tmp_terms);
            $num = count($tmp_terms);
            if ($path != "") {
                $begin = $start - $len;
                $out_path = $path;
                if ($len > C\MAX_QUERY_TERMS) {
                    $out_path = implode(" ", array_slice($this->text, $begin,
                        C\MAX_QUERY_TERMS));
                }
                $maximal[$out_path][] = $begin;
                if (!isset($maximal[$out_path]["cond_max"])) {
                    $maximal[$out_path]["cond_max"] =
                        strpos($out_path, " ") + 1;
                }
                if ($len > 1 && $len < C\MAX_QUERY_TERMS) {
                    $cond_max = strlen($path) + 1;
                }
                $path .= " ".$tmp;
                $len += $num;
                if (isset($cond_max)) {
                    $out_path = $path;
                    if ($len > C\MAX_QUERY_TERMS) {
                        $out_path = implode(" ", array_slice($this->text,
                            $begin, C\MAX_QUERY_TERMS));
                    }
                    $maximal[$out_path]["cond_max"] = $cond_max;
                }
            } else {
                $len = $num;
                $path = $tmp;
            }
        }
        if ($end == self::INFTY) {
            $begin = $this->size - $len;
            $out_path = $path;
            if ($len > C\MAX_QUERY_TERMS) {
                $out_path = implode(" ", array_slice($this->text, $begin,
                    C\MAX_QUERY_TERMS));
            }
            $maximal[$out_path][] = $begin;
            if (!isset($maximal[$out_path]["cond_max"])) {
                $maximal[$out_path]["cond_max"] =
                    strpos($out_path, " ") + 1;
            }
            return;
        }
        foreach ($this->tree[$index]["next"] as $sub_index) {
            $this->outputMaximal($sub_index, $path, $len, $maximal);
        }
    }
}
