# frozen_string_literal: true

class Trie
  def initialize(paths = [])
    @root = TrieNode.new
    @root.is_end = true

    paths.each { |path| insert(path) }
  end

  def insert(path)
    @root.is_end = false

    insert_recursive(@root, path)
  end

  def exists?(path)
    return false if @root.end?

    search_recursive(@root, path)
  end

  def size
    return 0 if @root.end?

    to_a.size
  end

  def to_a
    paths = []
    collect_paths(@root, [], paths)
    paths
  end

  private

  def insert_recursive(node, path, index = 0)
    if index == path.length
      node.is_end = true
      return
    end

    element = path[index]
    node.children[element] ||= TrieNode.new

    insert_recursive(node.children[element], path, index + 1)
  end

  def search_recursive(node, path, index = 0)
    return false if node.nil?
    return node.end? if index == path.length

    element = path[index]
    return node.end? unless node.children.key?(element)

    search_recursive(node.children[element], path, index + 1)
  end

  def collect_paths(node, current_path, paths)
    paths << current_path.dup if node.end?

    node.children.each do |element, child_node|
      current_path.push(element)
      collect_paths(child_node, current_path, paths)
      current_path.pop
    end
  end
end