TreeSearch.hpp

/* Binary tree data structure.
 *   Copyright (C) 2006 Free Software Foundation, Inc.
 *
 *   This program is free software; you can redistribute it and/or modify it
 *   under the terms of the GNU Library General Public License as published
 *   by the Free Software Foundation; either version 2, 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
 *   Library General Public License for more details.
 *
 *   You should have received a copy xof the GNU Library General Public
 *   License along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
 *   USA.
 *
 * Copyright 2015 Douglas Mark Royer.
 * Converted to a C++ template / object.
 * This file still under the FSF free license.
 */

#ifndef DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H
#define DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H


#ifdef BUILDING_SAS_COMMON_LIBRARY
#include "strsearch.hpp"
#else
#include <SaS/Common/strsearch.hpp>
#endif

namespace SoftwareAndServices
{
  namespace Library
  {
    namespace Common
    {

      template <class T> class Tree_t
      : public node_t
      {

    public:

    Tree_t<T>()
    {
      /*EMPTY*/

      return;
    }

    virtual ~Tree_t<T>()
    {
      /*EMPTY*/

      return;
    }

    typedef Tree_t<T>   *   Tree;

    typedef const Tree_t<T> *   const_Tree;

    typedef int (*TreeCompare_fn_t)(const T * One, const T * Two);

    typedef void    (*TreeAction_fn_t)(const Tree_t<T> **,
                       VISIT Leaf,
                       int Depth);

    typedef void    (*TreeFree_fn_t)(Tree_t<T> * TreeToFree);

    /*
     * Searches an element in the tree *VRootP that compares equal to KEY.
     * If one is found, it is returned.  Otherwise, a new element equal to
     * KEY is inserted in the tree and is returned.
     *
     * @param Key The key to search for.
     *
     * @param VRootP A pointer to the root Tree_t<T>.
     *
     * @param CompareFunction To method to call to compare.
     *
     * @return The T Found, or the new T inserted.
     */
    static T ** Search(const T * Key,
              Tree_t<T> * const * VRootP,
              TreeCompare_fn_t CompareFunction)
    {
      T **  Results = (T**) strsearch(Key,
                          (node_t*const*)VRootP,
                          (strcompare_fn_t)CompareFunction);

      return(Results);
    }

    /*
     * Searches an element in the tree *VRootP that compares equal to Key.
     * If one is found, it is returned.  Otherwise, nullptr is returned.
     *
     * @param Key The key to search for.
     *
     * @param VRootP A pointer to the root Tree_t<T>.
     *
     * @param CompareFunction To method to call to compare.
     *
     * @return The T found, or nullptr if none.
     */
    static T ** Find(const T * Key,
            Tree_t<T> * const * VRootP,
            TreeCompare_fn_t CompareFunction)
    {
      T **  Results = (T**)strfind(Key,
                           (node_t*const*)VRootP,
                           (strcompare_fn_t)CompareFunction);

      return(Results);
    }

    /*
     * Searches an element in the tree *VRootP that compares equal to Key.
     * If one is found, it is removed from the tree, and its parent node is
     * returned.  Otherwise, nullptr is returned.
     *
     * @param Key The key to search for.
     *
     * @param VRootP A pointer to the root Tree_t<T>.
     *
     * @param CompareFunction To method to call to compare.
     *
     */
    static T ** Delete(const void * Key,
              Tree_t<T> ** VRootP,
              TreeCompare_fn_t CompareFunction)
    {
      T **  Results = (T**)strdelete(Key,
                         (node_t**)VRootP,
                         (strcompare_fn_t)CompareFunction);

      return(Results);
    }

    /*
     * Perform a depth-first, left-to-right traversal of the tree VRoot.
     * The ACTION function is called:
     *
     * - for non-leaf nodes: 3 times, before the left subtree traversal,
     *   after the left subtree traversal but before the right subtree
     *   traversal, and after the right subtree traversal,
     * - for leaf nodes: once.
     *
     * The arguments passed to ACTION are:
     *
     * 1. The node; it can be casted to a 'const void * const *', i.e.
     *    into a pointer to the key,
     * 2. An indicator which visit of the node this is,
     * 3. The level of the node in the tree (0 for the root).
     *
     * @param VRoot The root of the tree.
     *
     * @param Action The method to call.
     */
    static void Walk(const Tree_t<T> * VRoot,
             TreeAction_fn_t Action)
    {
      strwalk(VRoot, (straction_fn_t)Action);

      return;
    }

      };


    }
  }
}

#endif // DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H