prefix-tree.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#ifndef PREFIX_TREE_H
#define PREFIX_TREE_H
 
# include <tpl_tree_node.H>
# include <tpl_dynArray.H>
# include <tpl_dynList.H>
# include <tpl_arrayStack.H>
# include <ah-errors.H>
 
namespace Aleph
{
  class Cnode : public Tree_Node<char>
  {
  public:
    explicit Cnode(const char c) noexcept
    {
      this->get_key() = c;
    }
 
    [[nodiscard]] char symbol() const noexcept { return get_key(); }
 
    [[nodiscard]] DynList<Cnode *> children() const
    {
      DynList<Cnode *> r;
      for_each_child([&r](Tree_Node<char> *p)
                       {
                         r.append(static_cast<Cnode *>(p));
                       });
      return r;
    }
 
    [[nodiscard]] std::string to_str() const
    {
      std::string ret(1, symbol());
      children().for_each([&ret](Cnode *p)
                            {
                              ret += "(" + p->to_str() + ")";
                            });
      return ret;
    }
 
    [[nodiscard]] bool is_end_word() const noexcept
    {
      Tree_Node<char> *child = get_left_child();
      if (child == nullptr)
        return false;
      return child->get_key() == '$';
    }
 
    void mark_end_word()
    {
      assert(not is_end_word());
      insert_leftmost_child(new Cnode('$'));
    }
 
    [[nodiscard]] Cnode * search_child(const char c) const noexcept
    {
      for (Tree_Node<char> *child = get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        if (child->get_key() == c)
          return static_cast<Cnode *>(child);
 
      return nullptr;
    }
 
    [[nodiscard]] Cnode * greater_child(const char c) const noexcept
    {
      for (Tree_Node<char> *child = get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        if (child->get_key() > c)
          return static_cast<Cnode *>(child);
      return nullptr;
    }
 
    [[nodiscard]] std::tuple<const Cnode *, const char *>
    search_prefix(const char *prefix) const noexcept
    {
      assert(prefix != nullptr);
 
      if (*prefix == '\0')
        return std::make_tuple(this, "");
 
      const Cnode *p = search_child(*prefix);
      if (p == nullptr)
        return std::make_tuple(this, prefix);
 
      return p->search_prefix(prefix + 1);
    }
 
    [[nodiscard]] const Cnode * search_word(const char *word) const noexcept
    {
      if (*word == '\0')
        return is_end_word() ? this : nullptr;
 
      const Cnode *ptr = search_child(*word);
      if (ptr == nullptr)
        return nullptr;
 
      return ptr->search_word(word + 1);
    }
 
    [[nodiscard]] bool contains(const std::string & word) const noexcept
    {
      return search_word(word.c_str()) != nullptr;
    }
 
    [[nodiscard]] size_t count() const noexcept
    {
      size_t n = is_end_word() ? 1 : 0;
      for_each_child([&n](const Tree_Node<char> *p)
                       {
                         n += static_cast<const Cnode *>(p)->count();
                       });
      return n;
    }
 
    [[nodiscard]] DynArray<std::string> words_with_prefix(
        const std::string & prefix,
        const size_t max_word_length = 2048) const
    {
      auto [node, remaining] = search_prefix(prefix.c_str());
 
      // Prefix not fully matched
      if (*remaining != '\0')
        return {};
 
      // Get all words from the prefix node and prepend the prefix
      FixedStack<char> stack(max_word_length);
      DynArray<std::string> ret_val;
 
      // Push prefix (except last char which will be pushed by words_impl)
      for (size_t i = 0; i + 1 < prefix.size(); ++i)
        stack.push(prefix[i]);
 
      node->words_impl(stack, ret_val);
      return ret_val;
    }
 
    Cnode * insert_child(Cnode *child)
    {
      assert(search_child(child->symbol()) == nullptr);
 
      if (Cnode *sibling = greater_child(child->symbol()); sibling == nullptr)
        this->insert_rightmost_child(child);
      else
        sibling->insert_left_sibling(child);
 
      return child;
    }
 
    bool insert_word(const std::string & word)
    {
      auto [pp, rem] = search_prefix(word.c_str());
 
      if (*rem == '\0')
        {
          if (pp->is_end_word())
            return false;
          const_cast<Cnode *>(pp)->mark_end_word();
          return true;
        }
 
      // Insert nodes directly without intermediate list
      auto *parent = const_cast<Cnode *>(pp);
      for (const char *ptr = rem; *ptr; ++ptr)
        parent = parent->insert_child(new Cnode(*ptr));
 
      parent->mark_end_word();
      return true;
    }
 
    void destroy() noexcept
    {
      // Must copy children list first - can't iterate while deleting
      children().for_each([](Cnode *p) { destroy_tree(p); });
    }
 
  private:
    static std::string extract_word_from_stack(FixedStack<char> & stack)
    {
      std::string ret_val;
      ret_val.reserve(stack.size());
 
      const char *ptr = &stack.base();
      const char *last = &stack.top();
      while (ptr <= last)
        ret_val.append(1, *ptr++);
 
      return ret_val;
    }
 
    void words_impl(FixedStack<char> & stack, DynArray<std::string> & l) const
    {
      if (symbol() == '$')
        l.append(extract_word_from_stack(stack));
 
      stack.push(symbol());
 
      for (const Tree_Node<char> *child = get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        static_cast<const Cnode *>(child)->words_impl(stack, l);
 
      stack.pop();
    }
 
  public:
    [[nodiscard]] DynArray<std::string> words(size_t max_word_length = 2048) const
    {
      FixedStack<char> stack(max_word_length);
      DynArray<std::string> ret_val;
 
      for_each_child([&](Tree_Node<char> *p)
                       {
                         static_cast<const Cnode *>(p)->words_impl(stack, ret_val);
                       });
 
      return ret_val;
    }
 
    void print_words(const size_t max_word_length = 2048) const
    {
      words(max_word_length).for_each([](const std::string & w)
                                        {
                                          std::cout << w << '\n';
                                        });
    }
 
    static void clone(const Tree_Node<char> *src, Tree_Node<char> *tgt)
    {
      // First, create all children in target
      src->for_each_child([tgt](auto s)
                            {
                              tgt->insert_rightmost_child(new Cnode(s->get_key()));
                            });
 
      // Then recursively clone each child subtree
      const Tree_Node<char> *src_child = src->get_left_child();
      Tree_Node<char> *tgt_child = tgt->get_left_child();
      while (src_child != nullptr)
        {
          clone(src_child, tgt_child);
          src_child = src_child->get_right_sibling();
          tgt_child = tgt_child->get_right_sibling();
        }
    }
 
    [[nodiscard]] Cnode * clone() const
    {
      auto *ret = new Cnode(symbol());
      clone(this, ret);
      return ret;
    }
  };
} // end namespace Aleph
 
#endif // PREFIX_TREE_H