<?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
 *
 * This file contains unit tests of the LSMTree class used to keep track of
 *
 * @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\tests;

use seekquarry\yioop\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\models\Model;
use seekquarry\yioop\library\data_structures\LSMTree;
use seekquarry\yioop\library\data_structures\PackedTableTools;
use seekquarry\yioop\library\UnitTest;

/**
 * Yioop LSMTree Unit Class
 *
 * Used to test insert, lookup, and deletion of key-value pairs in a
 * Log-structured Merge Tree.
 * @author Chris Pollett
 */
class LSMTreeTest extends UnitTest
{
    /**
     * Test directory to hold LSMTree used for these unit tests
     */
    const TEST_DIR = '/test_files/lsm_tree_test';
    /**
     * Folder names to use for test LSMTree
     * @var array
     */
    public $table_dirs;
    /**
     * Minimum degree is set to 2 and the number of key-value pairs is set to 25
     */
    public function setUp()
    {
        $this->table_dirs = [];
    }
    /**
     * Delete the LSMTree files created during the test
     */
    public function tearDown()
    {
        $model = new Model();
        foreach ($this->table_dirs as $table_dir) {
            $model->db->unlinkRecursive($table_dir, true);
        }
        $this->table_dirs = [];
    }
    /**
     * Creates a single LSM tree under a per-parameter directory
     * derived from key size, file size, block factor, and suffix.
     * Each call tracks the directory so tearDown can clean it up.
     *
     * @param array $format column definitions for the tree
     * @param int $max_file_size maximum on-disk size of any single
     *      file in the tree
     * @param int $block_factor number of records per disk block
     * @param string $suffix optional suffix appended to the test
     *      directory name to disambiguate concurrent test trees
     * @return LSMTree freshly-constructed tree backed by the
     *      per-test directory
     */
    public function createTree($format, $max_file_size, $block_factor,
        $suffix = "")
    {
        $key_size = $format["PRIMARY KEY"][1];
        $table_dir = __DIR__ . self::TEST_DIR .
            "_{$key_size}_{$max_file_size}_{$block_factor}_$suffix";
        $this->table_dirs[] = $table_dir;
        return new LSMTree($table_dir, $format, $max_file_size,
            $block_factor);
    }
    /**
     * Test putting items in lsm-tree and
     * then seeing if the items can be retrieved
     */
    public function simplePutGetTierTestCase()
    {
        for ($max_file_size = 20; $max_file_size < 60; $max_file_size += 30) {
            for ($block_factor = 1; $block_factor < 3; $block_factor++) {
                for ($key_len = 16; $key_len > 5; $key_len -= 8) {
                    for ($cols = 0; $cols < 3; $cols++) {
                        $format = ["PRIMARY KEY" => ["KEY", $key_len],
                            "VALUE" => "TEXT"];
                        for ($j = 0; $j < $cols; $j++) {
                            $format["COL$j"] = "INT";
                        }
                        $lsm_tree = $this->createTree($format, $max_file_size,
                            $block_factor, "{$key_len}_$cols");
                        for ($i = 0; $i < 50; $i++) {
                            $key = str_pad("key$i", $key_len, "0",
                                STR_PAD_LEFT);
                            $entry = ["KEY" => $key, "VALUE" => "value$i"];
                            for ($j = 0; $j < $cols; $j++) {
                                $entry["COL$j"] = $i;
                            }
                            $lsm_tree->put($entry);
                        }
                        $lsm_tree->flush();
                        for  ($i = 0; $i < 50; $i++) {
                            $key = str_pad("key$i", $key_len, "0",
                                STR_PAD_LEFT);
                            $values = $lsm_tree->get($key);
                            $this->assertEqual("value$i", $values[0]["VALUE"],
                                "{$i}th insert key length $key_len, pad ".
                                "columns $j into single LSTM Tier ".
                                "{$values[0]["VALUE"]} should be retrieved ".
                                "as value$i");
                        }
                    }
                }
            }
        }
    }
    /**
     * Checks that the correct number of block folders are created when
     * inserting several items into am LSMTree with a small block factor
     * and max file size
     */
    public function blockFactorTestCase()
    {
        $max_file_size = 20;
        $block_factor = 2;
        $key_len = 16;
        $cols = 2;
        $format = ["PRIMARY KEY" => ["KEY", $key_len],
            "VALUE" => "TEXT"];
        $lsm_tree = $this->createTree($format, $max_file_size,
            $block_factor, "{$key_len}");
        for ($i = 0; $i < 15; $i++) {
            $key = str_pad("key$i", $key_len, "0",
                STR_PAD_LEFT);
            $entry = ["KEY" => $key, "VALUE" => "value$i"];
            $lsm_tree->put($entry);
        }
        $this->assertTrue(file_exists($lsm_tree->folder .
            "/Tier0000/A/F00000000000key12") && !file_exists($lsm_tree->folder .
                "/Tier0000/A/F00000000000key14"),
            "Correct number of block folders created");
    }
    /**
     * Checks that the correct number of data files are created when
     * inserting several items into am LSMTree with a small max file size
     */
    public function maxFileSizeTestCase()
    {
        $max_file_size = 50;
        $block_factor = 10000;
        $key_len = 16;
        $cols = 2;
        $format = ["PRIMARY KEY" => ["KEY", $key_len],
            "VALUE" => "TEXT"];
        $lsm_tree = $this->createTree($format, $max_file_size,
            $block_factor, "{$key_len}");
        for ($i = 0; $i < 15; $i++) {
            $key = str_pad("key$i", $key_len, "0",
                STR_PAD_LEFT);
            $entry = ["KEY" => $key, "VALUE" => "value$i"];
            $lsm_tree->put($entry);
        }
        $block_folder = $lsm_tree->folder . "/Tier0000/A/F000000000000key0";
        $this->assertTrue(file_exists("$block_folder/D00000000000key13") &&
            !file_exists("$block_folder/D00000000000key14"),
            "Correct number of data files created");
    }
    /**
     * Tests that values for identical keys are correctly merged when merge
     * two slots within a tier.
     */
    public function mergeRecordsTierTestCase()
    {
        $max_file_size = 50;
        $block_factor = 2;
        $key_len = 16;
        $cols = 2;
        $format = ["PRIMARY KEY" => ["KEY", $key_len],
            "VALUE" => "TEXT"];
        for ($j = 0; $j < $cols; $j++) {
            $format["COL$j"] = "INT";
        }
        $lsm_tree = $this->createTree($format, $max_file_size,
            $block_factor, "{$key_len}_$cols");
        foreach ([["A", 0, 10], ["B", 5, 15]] as $slot_info) {
            $lsm_tree->selectPutSlot($slot_info[0]);
            for ($i = $slot_info[1]; $i < $slot_info[2]; $i++) {
                $key = str_pad("key$i", $key_len, "0",
                    STR_PAD_LEFT);
                $entry = ["KEY" => $key, "VALUE" => "value{$slot_info[0]}$i"];
                for ($j = 0; $j < $cols; $j++) {
                    $entry["COL$j"] = $i;
                }
                $lsm_tree->put($entry);
            }
            $lsm_tree->flush();
        }
        $lsm_tree->mergeTiers();
        $key = str_pad("key10", $key_len, "0", STR_PAD_LEFT);
        $values = $lsm_tree->get($key);
        for ($i = 0; $i < 15; $i++) {
            $key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
            $values = $lsm_tree->get($key);
            if ($i < 10) {
                $this->assertEqual("valueA$i", $values[0]["VALUE"],
                    "Able to retrieve Slot A value $i");
            }
            if ($i > 4 && $i < 10) {
                $this->assertEqual("valueB$i", $values[1]["VALUE"],
                    "Able to retrieve Slot B value $i");
            }
            if ($i >= 10) {
                $this->assertEqual("valueB$i", $values[0]["VALUE"],
                    "Able to retrieve Slot B value $i");
            }
        }
    }
    /**
     * Tests that tiers are correctly created and merged when many items are
     * inserted into a tree with a small block factor and max file size.
     * Test correctness by seeing if each value can be retrieved with its key.
     */
    public function mergeTiersTestCase()
    {
        $max_file_size = 50;
        $block_factor = 2;
        $key_len = 16;
        $cols = 3;
        $format = ["PRIMARY KEY" => ["KEY", $key_len],
            "VALUE" => "TEXT"];
        for ($j = 0; $j < $cols; $j++) {
            $format["COL$j"] = "INT";
        }
        $lsm_tree = $this->createTree($format, $max_file_size,
            $block_factor, "{$key_len}_$cols");
        $slot = "B";
        for ($i = 0; $i < 250; $i++) {
            if ($i % 5 == 0) {
                $slot = ($slot == "B") ? "A" : "B";
                $lsm_tree->flush();
                $lsm_tree->selectPutSlot($slot);
            }
            if ($i > 0 && $i % 10 == 0) {
                $lsm_tree->mergeTiers();
            }
            $k = 10 * floor($i / 10);
            $k += ($slot == "A") ? 2 * ($i % 10) : 2 * (($i % 10) - 5) + 1;
            $key = str_pad("key$k", $key_len, "0", STR_PAD_LEFT);
            $entry = ["KEY" => $key, "VALUE" => "value$k"];
            for ($j = 0; $j < $cols; $j++) {
                $entry["COL$j"] = $k;
            }
            $lsm_tree->put($entry);
        }
        $lsm_tree->flush();
        $lsm_tree->mergeTiers();
        $this->assertEqual($lsm_tree->getMaxTier(), 5,
            "Final maxTiers is correct");
        $tiers = [false, true, false, false, true, true];
        for ($i = 0; $i <= 5; $i++) {
            $this->assertEqual($lsm_tree->occupiedTier($i), $tiers[$i],
                "{$i} th tier correctly occupied");
        }
        for ($i = 0; $i < 250; $i++) {
            $key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
            $values = $lsm_tree->get($key);
            $this->assertEqual("value$i", $values[0]["VALUE"],
                "Able to retrieve {$i}th value");
        }
    }
}
