Very preliminary pass at Version 3 index, a=chris

<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2019  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 BTree class used to keep track of
 * etags during a crawl
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2019
 * @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\BTree;
use seekquarry\yioop\library\UnitTest;

/**
 * Yioop B-tree Unit Class
 *
 * Used to test insert, lookup, and deletion of key-value pairs on the B-Tree.
 * @author Akshat Kukreti
 */
 class BTreeTest extends UnitTest
{
    /**
     * Number of key value pairs to insert for unit tests
     */
    const NUM_VALS = 25;
    /**
     * Minimum degree of BTree
     */
    const DEGREE = 2;
    /**
     * Test directory to hold btree used for these unit tests
     */
    const TEST_DIR = '/test_files/btree_test';
    /**
     * Minimum degree is set to 2 and the number of key-value pairs is set to 25
     */
    public function setUp()
    {
        $this->test_objects['FILE1'] = new BTree(__DIR__ . self::TEST_DIR,
            self::DEGREE);
    }
    /**
     * Delete the B-Tree files created during the test
     */
    public function tearDown()
    {
        $model = new Model();
        $model->db->unlinkRecursive(__DIR__ . self::TEST_DIR);
    }
    /**
     * Test to check that an empty B-Tree is not saved to disk.
     * A B-Tree object is created. The test directory is checked for B-Tree
     * files. A value is inserted, the test directory is again checked. The
     * inserted value is removed and the test directory is again checked for
     * B-Tree files.
     */
    public function emptyBTreeNoSaveTestCase()
    {
        $all_files = glob(__DIR__ . self::TEST_DIR.'/*.txt');
        $this->assertEqual(0, count($all_files), 'Empty B-Tree not saved
            saved to disk');
        $this->test_objects['FILE1']->insert(array(1, 1));
        $all_files = glob(__DIR__ . self::TEST_DIR.'/*.txt');
        $this->assertEqual(2, count($all_files), 'Non-empty B-Tree successfully
            saved to disk');
        $this->test_objects['FILE1']->remove(1);
        $all_files = glob(__DIR__ . self::TEST_DIR.'/*.txt');
        $this->assertEqual(0, count($all_files), 'Empty B-Tree not saved
            saved to disk');
    }
    /**
     * Test to check insertion and lookup in a B-Tree
     * Key-value pairs are inserted in the B-Tree and then looked up using keys.
     */
    public function insertLookupTestCase()
    {
        //Insert values
        $key_value_pairs = [];
        for ($i = 1; $i <= self::NUM_VALS; $i++) {
            $value = L\crawlHash(rand(1, 1000), true);
            $key = L\crawlHash($value, true);
            $this->test_objects['FILE1']->insert(array($key, $value));
            $key_value_pairs[] = [$key, $value];
        }

        //Lookup values
        foreach ($key_value_pairs as $key_value_pair) {
            $key = $key_value_pair[0];
            $value = $key_value_pair[1];
            $lookup_entry = $this->test_objects['FILE1']->findValue($key);
            $lookup_value = $lookup_entry[1];
            $this->assertEqual($value, $lookup_value, 'Inserted value is equal
                to lookup value');
        }
    }
    /**
     * Test to check that a key is deleted successfully from a leaf node
     * Key-value pairs are inserted in the B-Tree. key-value pairs present in
     * leaf nodes are then deleted from the B-Tree. The deleted key-value pairs
     * are looked up to check if they were removed successfully.
     */
    public function deleteFromLeafNodeTestCase()
    {
        //Insert values
        for ($i = 1; $i <= self::NUM_VALS; $i++) {
            $this->test_objects['FILE1']->insert(array($i, $i));
        }
        //Keys in leaf nodes
        $leaf_keys = [1, 3, 5, 9, 10];
        foreach ($leaf_keys as $key) {
            $this->test_objects['FILE1']->remove($key);
        }
        //Lookup deleted keys
        foreach ($leaf_keys as $key) {
            $this->assertEqual(null,
                $this->test_objects['FILE1']->findValue($key),
                'Key successfully deleted from leaf node');
        }
    }
    /**
     * Test to check that a key is deleted successfully from an internal node
     * Key-value pairs are first added to the B-Tree. Key-value pairs are then
     * deleted successively from the root node. The deleted key-value pairs are
     * then looked up to check if they were successfully
     */
    public function deleteFromInternalNodeTestCase()
    {
        //Insert values
        for ($i = 1; $i <= self::NUM_VALS; $i++) {
            $value = L\crawlHash(rand(1, 1000), true);
            $key = L\crawlHash($value, true);
            $this->test_objects['FILE1']->insert(array($key, $value));
        }

        $deleted = [];
        for ($i = 1; $i <= self::NUM_VALS - 10; $i++) {
            $internal_key = $this->test_objects['FILE1']->root->keys[0][0];
            $this->test_objects['FILE1']->remove($internal_key);
            $this->assertEqual(null,
                $this->test_objects['FILE1']->findValue($internal_key),
                'Key deleted successfully from internal node');
        }
    }
    /**
     * Function to check that keys are successfully deleted from the B-Tree
     * Random key-value pairs are firs inserted in the B-Tree. From the inserted
     * key-value pairs, key-value pairs are randomly selected and deleted from
     * the B-Tree. The deleted key-value pairs are then looked up using their
     * keys to check if they were successfully deleted.
     */
    public function deleteLookupTestCase()
    {
        //Insert values
        $key_value_pairs = [];
        for ($i = 1; $i <= self::NUM_VALS; $i++) {
            $value = L\crawlHash(rand(1, 1000), true);
            $key = L\crawlHash($value, true);
            $this->test_objects['FILE1']->insert(array($key, $value));
            $key_value_pairs[] = [$key, $key];
        }
        //Delete Values
        $deleted = [];
        for ($i = 1; $i <= self::NUM_VALS; $i++) {
            $index = mt_rand(0, self::NUM_VALS - 1);
            $key = $key_value_pairs[$index][0];
            $this->test_objects['FILE1']->remove($key);
            $deleted[] = $key;
        }
        //Lookup values
        foreach ($deleted as $deleted_key) {
            $this->assertEqual(null,
                $this->test_objects['FILE1']->findValue($deleted_key),
                'Deleted Value not found');
        }
    }
}