ArcadeFighterDemo/lib/ArcadeFighter/inc/toolbox/nary_tree_simple.hpp

/* License Notice:
**
** 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/>.
*/

/**
 * @file linked_list_simple.hpp
 * @author TooOld2Rock'nRoll
 * @date jan/2025
 * @version 0.0.2
 *
 * @attention "make CFLAGS:=-DUNIT_TESTING" to run unit testing on the library.
 *
 * @see Cormen, Thomas H. (...) - Introduction to Algorithms (3ºed)
 * @see https://cpputest.github.io/manual.html
 *
 * @todo To be truly simple, we should have a fixed number of leafs for the branches (with a array of leafs).
 * @todo maybe add a sort function!
 *
 * @brief Header file for the <i>Simple</i> version N-ary Tree data structure.
 */
#ifndef NTREE_S_HPP
#define NTREE_S_HPP

/*---- Includes ----*/
#include "linked_list_simple.hpp"

#ifdef UNIT_TESTING
#include <CppUTest/CommandLineTestRunner.h>
#include <CppUTest/MemoryLeakDetectorNewMacros.h>
#endif

/*---- Defines ----*/
// #define NTSI_ENABLE_BENCHMARK


/*---- Enumerations ----*/


/*---- Typedefs ----*/


/*---- Class Declaration ----*/
/**
 * @brief Simple N-ary Tree data structure.
 * @see https://en.wikipedia.org/wiki/M-ary_tree
 *
 * A N-ary Tree (or K Tree) is a dynamic data structure that is (usually) ordered and (traditionally) used to store and
 *   validade chains of data, like strings from a dictionary. Each node would represent a letter and traversing the tree
 *   successfully till a leaf would confirm the dictionary world is valid.<br>
 *
 * In practice, nothing more than a list of lists...<br>
 *
 * This algorithm is simples in the sense that it covers the most basic requirements to be considered a functional n-ary
 *   tree, it is <b>not</b> thread safe (traversing the list in parallel would break the reading head logic).<br>
 * This algorithm is also fast by only saving references to user data removing a good overhead of consistency checks,
 *   but this is not safe and difficult to debug in case of errors. Consider using the Safe version if such safeguards
 *   are necessary in your project.<br>
 *
 * The first call to insert() will create the root node, subsequent inserts will add leafs to the branch currently under
 *   the reading head.<br>
 * The next() function moves the read head forward into the list of leafs.<br>
 * The down() function moves the reading head to the selected leaf, moving the reading head to a different branch.<br>
 * The other functions are just helpers that make some jobs easier.<br>
 * There is no remove() method as N-ary Trees have no use for such, it would break any search logic applied to it after.<br>
 *
 * Example:
 * <code>
 *   int *buff = nullptr;
 *   NTree<int> TheTree;
 *
 *   //create root as 10
 *   TheTree.insert (new int (10));
 *
 *   //leaf is 20
 *   TheTree.insert (new int (20));
 *   //leaf is 30
 *   TheTree.insert (new int (30));
 *
 *   TheTree.next (); //read head points to first leaf (30)
 *   TheTree.next (); //read head points to second leaf (20)
 *   TheTree.down (); //we are at branch 20
 *
 *   //leaf is 400
 *   TheTree.insert (new int (400));
 *
 *   buff = TheTree.search (20);
 *   //buff will be 20 and readhread wil be at second leaf of the root branch
 *
 *   ...
 *
 *   //all user packages ()allocated memory) will be deleted at the destructor
 *   //a report may be printed
 * </code>
 *
 *  -Statistics:<br>
 *      N-ary Tree Statistics Report:<br>
 *      Unsorted 10 leafs per level.<br>
 *      Total Used Time: 103.1830s<br>
 *          Insert<br>
 *            -was called 50000 times.<br>
 *            -total used time: 0.018000s<br>
 *            -Average Delay: 0.000360ms<br>
 *          Clean<br>
 *            -was called 1 times.<br>
 *            -total used time: 0.028000s<br>
 *            -Average Delay: 28.000000ms<br>
 *          Search<br>
 *            -was called 50000 times.<br>
 *            -total used time: 103.137000s<br>
 *            -Average Delay: 2.062740ms<br>
 *     -Machine Specs:<br>
 *        Intel Core i7-7700HQ CPU @ 2.80GHz<br>
 *        16Gb RAM<br>
 *
 * @tparam T - data type to be stored in the tree.
 */
template <typename T>
class NTree
{
    public:
        /**
         * @brief Optional user callback to compare tree packages with search data.
         *
         * A barebones search callback would look like this:
         * <code>
         *  bool myPackageSearchCB (T &node_package, const T *key)
         *  { return (*pkgKey == *key); }
         * </code>
         *
         * And it would be used like this:
         * <code> thePackage = myList->search (&key2find, (LinkedList_Si::SearchNodeCallback)myPackageSearchCB); </code>
         *
         * @param node_package - the node package to compare.
         * @param user_data - pointer to what ever the user needs to find the correct node.
         *
         * @return Callback must return <b>true</b> to stop search when package is found or <b>false</b> to continue.
         */
        typedef bool (*SearchNodeCallback) (T &package, const void *user_data);


    private:
        //the node that builds the data structure
        struct node_s
        {
            std::size_t _depth = 0;//the distance (number of nodes) from the root

            T *tp_package = nullptr; //user data

            LinkedList_Si<node_s> *ll_leafs = nullptr; //this branch's list of leafs
        };//end node

        NTree::node_s *p_root = nullptr; //first node of the tree or null if empty
        NTree::node_s *p_readhead = nullptr; //current node being read or null if empty

        //we need to translate the NTree structure to what the user expects when making a custom search!
        const void *vp_search_key = nullptr;
        NTree::SearchNodeCallback _user_search_cb = nullptr;

    protected:
        static void cleanSubTree_r (NTree::node_s *node, bool del_packages);

        static NTree::node_s * searchSubTree_r (NTree::node_s *node, const T &data);
        static NTree::node_s * searchSubTree_r (NTree::node_s *node, const void *data, SearchNodeCallback search_cb);

        /** @brief To be used by LL to compares the contents of two leafs. */
        static bool compareLeafs_cb (NTree::node_s &node, const void *key)
        { return (*node.tp_package == *((T *)key)); }
        /** @brief We can't directly compare packages when using a custom search callback, so we need a intermediate step. */
        static bool customSearchLeafs_cb (NTree::node_s &node, const void *obj_this)
        { return ((NTree *)obj_this)->_user_search_cb (*node.tp_package, ((NTree *)obj_this)->vp_search_key); }


    public:
        /** @brief Start a new Tree. */
        // NTree ();
        ~NTree ();

        void reset ();
        void root ();

        void insert (T *package);
        T * read () const;
        /** @brief Returns the depth int he tree of the current branch under the reading head (0 if empty). */
        size_t depth () const { return (this->p_readhead ? this->p_readhead->_depth : 0); }
        /** @brief Returns the number of leafs in the branch under the reading head. */
        size_t leafs () const { return (this->p_readhead ? this->p_readhead->ll_leafs->size () : 0); }
        T * next ();
        T * down ();
        T * swap (T *new_package);

        T * search (const T &key);
        T * search (const void *data, NTree::SearchNodeCallback search_cb);
        T * searchInBranch (const T &key);
        T * searchInBranch (const void *data, NTree::SearchNodeCallback search_cb);

        void clean (bool del_packages);

        /** @brief Returns <b>true</b> if tree is empty, <b>false</b> otherwise. */
        bool empty () const { return (!this->p_root); }
};//END NTree


//it is truly a monstrosity to implement an entire library in a header file!
//but using templates "requires" it....
/*---- Methods Definition ----*/
/**
 * @brief Delete all nodes and free all data in the Tree.
 * @warning If the tree is not empty, all the stored user packages will be freed to avoid memory leaks!
 */
template <typename T>
NTree<T>::~NTree ()
{
    this->clean (true);
}//End Destructor


/**
 * @brief Adds a new leaf with the user data to the current branch at the readhead position.
 *
 * @remark If the tree is empty, this will be the tree root.
 * @warning The data on the new package will <b>NOT</b> be copied, only the reference saved!
 *
 * @param package - data pointer to be saved.
 *
 * @throws std::invalid_argument - if the new package is null (it makes no sense!).
 */
template <typename T>
void NTree<T>::insert (T *package)
{
    //New node to put in this
    NTree::node_s *new_node = nullptr;

    //check parameters
    if (!package)
        throw std::invalid_argument (fmt::format ("{0}:{1} - new package is NULL!", __LINE__, __FILE__));

    //Save information passed to function
    new_node = new NTree<T>::node_s ();
    new_node->tp_package = package;
    new_node->ll_leafs = new LinkedList_Si<NTree::node_s> ();

    if (this->p_readhead)
    {
        new_node->_depth = this->p_readhead->_depth + 1;
        this->p_readhead->ll_leafs->insert (new_node);
    }//end if (this->p_readhead)
    else //if (!this->p_root)
    {
        this->p_root = new_node;
        this->p_readhead = this->p_root;
    }//end else if (!this->p_root)
}//End insert ()


/**
 * @brief Resets the reading head to the first leaf in the branch.
 */
template <typename T>
void NTree<T>::reset ()
{
    if (!this->p_root)
    {
        // _debug ("INFO, tree is empty!");
        return;
    }//end if (!this->p_root)

    this->p_readhead->ll_leafs->reset ();
}//End reset ()


/**
 * @brief Takes the reading head back to the tree root.
 */
template <typename T>
void NTree<T>::root ()
{
    this->p_readhead = this->p_root;

    if (this->p_root)
        this->p_root->ll_leafs->reset ();
}//End root ()


/**
 * @brief Reads the package under the read head (the current branch package).
 *
 * @return Pointer to the package under the read head, null if tree is empty.
 */
template <typename T>
T * NTree<T>::read () const
{
    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO: tree is empty, nothing to read.");
        return nullptr;
    }//end if (!this->_head)

    return this->p_readhead->tp_package;
}//End read ()


/**
 * @brief Reads the next leaf in the branch.
 * @remark null will be returned <i>once</i> to mark the end of the list of leafs, the next call will reset to the first node.
 *
 * @return Pointer to the next package on the list of leafs, null if at the end of the list or if list is empty.
 */
template <typename T>
T * NTree<T>::next ()
{
    NTree<T>::node_s *leaf = nullptr;

    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO: tree is empty...");
        return nullptr;
    }//end if (!this->_head)

    leaf = this->p_readhead->ll_leafs->next ();
    return (leaf ? leaf->tp_package : nullptr);
}//End next ()


/**
 * @brief Move the reading head to the current leaf being read in the branch.
 *
 * @return Pointer to the leafs package or null if there is no leaf to read.
 */
template <typename T>
T * NTree<T>::down ()
{
    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO: tree is empty...");
        return nullptr;
    }//end if (!this->_head)
    else if (!this->p_readhead->ll_leafs->read ())
    {
        // _debug ("WARNING: end of leaf's list or empty, can't go down.");
        return nullptr;
    }//end else if (!)

    this->p_readhead = this->p_readhead->ll_leafs->read ();
    this->p_readhead->ll_leafs->reset ();

    return this->p_readhead->tp_package;
}//End down ()


/**
 * @brief Swaps the package in the branch under the read head for a new one.
 * @remark Client is responsible for freeing the returned package pointer!
 *
 * @param new_package - data pointer to be saved in place of the current one.
 *
 * @return Pointer to the old package under read head, null if tree is empty.
 *
 * @throws std::invalid_argument - if the new package is null (it makes no sense!).
 */
template <typename T>
T * NTree<T>::swap (T *new_package)
{
    T *old_package = nullptr;

    //check parameters
    if (!new_package)
        throw std::invalid_argument (fmt::format ("{0}:{1} - new package is null!", __LINE__, __FILE__));
    else if (!this->p_root)
    {
        // _debug ("WARNING, Tree is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    old_package = this->p_readhead->tp_package;
    this->p_readhead->tp_package = new_package;

    return old_package;
}//End swap ()

/** @brief Recursively traverse the tree (bottom/left first). */
template <typename T>
typename NTree<T>::node_s * NTree<T>::searchSubTree_r (NTree::node_s *node, const T &key)
{
    NTree::node_s *aux = nullptr,
                  *save = nullptr;

    aux = node->ll_leafs->reset ();
    while (aux)
    {
        save = NTree::searchSubTree_r (aux, key);

        if (save)
            return save;

        aux = node->ll_leafs->next ();
    }//end while ((aux = (NTree::node_s *)node->ll_leafs->remove ()))

    return (*node->tp_package == key ? node : nullptr);
}//end searchSubTree_r ()


/** @brief Recursively traverse the tree (bottom/left first) using a custom callback. */
template <typename T>
typename NTree<T>::node_s * NTree<T>::searchSubTree_r (NTree::node_s *node, const void *data, SearchNodeCallback search_cb)
{
    NTree::node_s *aux = nullptr,
                  *save = nullptr;

    aux = node->ll_leafs->reset ();
    while (aux)
    {
        save = NTree::searchSubTree_r (aux, data, search_cb);

        if (save)
            return save;

        aux = node->ll_leafs->next ();
    }//end while ((aux = (NTree::node_s *)node->ll_leafs->remove ()))

    return (search_cb (*node->tp_package, data) ? node : nullptr);
}//end searchSubTree_r ()


/**
 * @brief Search for a package in the tree using a custom callback.
 *
 * The search will begging from the read head current position till the end of the tree (remember to call reset before
 *   starting the search).<br>
 * The read head will stay at the position it stopped when the method returns, so you may repeat the search from that
 *   point, maybe to find more nodes with the same pattern (just remember to increment the reading head position or
 *   search will be stuck at the same node).
 *
 * @param key - key to search the tree packages to (compare operator will be used).
 *
 * @return Pointer to the matched package or null if no match is found.
 *
 * @throws std::invalid_argument - if the new search callback is null (it makes no sense!).
 */
template <typename T>
T * NTree<T>::search (const T &key)
{
    NTree::node_s *save = nullptr;

    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO, Tree is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    save = NTree::searchSubTree_r (this->p_readhead, key);

    if (save)
    {
        this->p_readhead = save;
        return save->tp_package;
    }//end if (save)
    else
    {
        this->p_readhead = this->p_root;
        return nullptr;
    }//end else
}//End search (operator==)

/**
 * @brief Search for a package in the tree using a custom callback.
 *
 * The search will begging from the read head current position till the end of the tree (remember to call reset before
 *   starting the search).<br>
 * The read head will stay at the position it stopped when the method returns, so you may repeat the search from that
 *   point, maybe to find more nodes with the same pattern (just remember to increment the reading head position or
 *   search will be stuck at the same node).
 *
 * @param data - client data to be passed to search the callback.
 * @param search_cb - the client search callback to compare the searched data with the packages.
 *
 * @return Pointer to the matched package or null if no match is found.
 *
 * @throws std::invalid_argument - if the new search callback is null (it makes no sense!).
 */
template <typename T>
T * NTree<T>::search (const void *data, SearchNodeCallback search_cb)
{
    NTree::node_s *save = nullptr;

    //check parameters
    if (!search_cb)
        throw std::invalid_argument (fmt::format ("{0}:{1} - search callback is null!", __LINE__, __FILE__));
    else if (!this->p_root)
    {
        // _debug ("INFO, Tree is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    save = NTree::searchSubTree_r (this->p_readhead, data, search_cb);

    if (save)
    {
        this->p_readhead = save;
        return save->tp_package;
    }//end if (save)
    else
    {
        this->p_readhead = this->p_root;
        return nullptr;
    }//end else
}//End search (callback)

/**
 * @brief Search the current branch leafs for a package.
 *
 * The search will always begging from the firs leaf in the branch.
 *
 * @param key - key to search the packages in the list of leafs (compare operator will be used).
 *
 * @return Pointer to the matched package or null if no match is found.
 */
template <typename T>
T * NTree<T>::searchInBranch (const T &key)
{
    NTree::node_s *aux = nullptr;

    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO, Tree is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    this->p_readhead->ll_leafs->reset ();
    aux = this->p_readhead->ll_leafs->search ((void *)&key, NTree::compareLeafs_cb);

    return (aux ? aux->tp_package : nullptr);
}//End searchInBranch ()


/**
 * @brief Search the current branch leafs for a package.
 *
 * The search will always begging from the firs leaf in the branch.
 *
 * @param data - client data to be passed to search the callback.
 * @param search_cb - the client search callback to compare the searched data with the packages.
 *
 * @return Pointer to the matched package or null if no match is found.
 *
 * @throws std::invalid_argument - if the new search callback is null (it makes no sense!).
 */
template <typename T>
T * NTree<T>::searchInBranch (const void *data, NTree::SearchNodeCallback search_cb)
{
    NTree::node_s *aux = nullptr;

    //check parameters
    if (!search_cb)
        throw std::invalid_argument (fmt::format ("{0}:{1} - search callback is null!", __LINE__, __FILE__));
    else if (!this->p_root)
    {
        // _debug ("INFO, Tree is empty, nothing to be done.");
        return nullptr;
    }//end else if (!this->_head)

    this->vp_search_key = data;
    this->_user_search_cb = search_cb;
    this->p_readhead->ll_leafs->reset ();
    aux = this->p_readhead->ll_leafs->search ((void *)this, NTree::customSearchLeafs_cb);

    return (aux ? aux->tp_package : nullptr);
}//End searchInBranch (callback)


/**
 * @brief Recursively traverse the tree removing all the nodes.
 */
template <typename T>
void NTree<T>::cleanSubTree_r (NTree::node_s *node, bool del_packages)
{
    NTree::node_s *aux = nullptr;

    if (!node)
    {
        // _debug ("ERROR, received an null node!");
        return;
    }//end if (!node)
    if (!node->ll_leafs)
    {
        // _debug ("ERROR, received an null list of leafs node!");
        return;
    }//end if (!node)

    //if branch has no leafs, it will not enter the while loop
    node->ll_leafs->reset ();
    while ((aux = node->ll_leafs->remove ()))
    {
        NTree::cleanSubTree_r (aux, del_packages);
        if (del_packages)
            delete (aux->tp_package);

        aux->tp_package = nullptr;
        delete (aux);
    }//end while ((aux = (NTree::node_s *)node->ll_leafs->remove ()))

    delete (node->ll_leafs);
    node->ll_leafs = nullptr;
}//end cleanSubTree_r ()


/**
 * @brief Remove all nodes from the tree.
 */
template <typename T>
void NTree<T>::clean (bool del_packages)
{
    //check parameters
    if (!this->p_root)
    {
        // _debug ("INFO, Tree is empty, nothing to clean.");
        return;
    }//end else if (!this->_head)

    NTree::cleanSubTree_r (this->p_root, del_packages);

    if (del_packages)
        delete (this->p_root->tp_package);
    delete (this->p_root);

    this->p_root = nullptr;
    this->p_readhead = nullptr;
}//End clean ()

#endif //NTREE_S_HPP