/**
 * @file trie_node.hpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */

#pragma once
#include <iostream>
#include <memory>
#include <map>

/** forward declaration. */
class TrieNode;

/**
 * @brief Fold the node into a output stream.
 *
 * Format:
 *
 * node: '[' <is_key> {' [' <symbol> <node> ']'}* ']'
 *
 * Where:
 *
 * <is_key>: 'T'|'F'
 *
 * <symbol>: is a quoted utf-8 encoded char.
 *
 * Examples:
 *
 * [ T ] -> a leaf node representing a key.
 *
 * [ F [ 'a' [ T ] ] [ 'b' [ T ] ] ] -> a branch node which not representing a key with two child nodes.
 *
 * @param out is the output stream.
 * @param node is the node to be folded.
 * @return the modified stream.
 */
std::ostream &operator<<(std::ostream &out, const TrieNode &node) noexcept;

/**
 * @brief Create a TrieNode unfolding from an input stream.
 * See operator<<(std::ostream &, const TrieNode &) for the expected input format.
 * @param in is the input stream.
 * @param node is the node to be created.
 * @return the modified stream.
 * @throw std::runtime_error("Wrong input format") when wrong input format
 *        is detected.
 */
std::istream &operator>>(std::istream &in, TrieNode &node) noexcept(false);

/**
 * @brief Models a node of a Trie.
 *
 * The path from the root node to this node represents a prefix and
 * the this node represents a key equal to this prefix and all the following
 * possible next prefixes where a new symbol was added.
 *
 * For example: if we have the keys '123', '1231', '1232, '1233' a node
 * will represent the key '123' and the prefix '123' with three child nodes
 * for symbols '1', '2' and '3' respectively.
 *
 */
class TrieNode
{
public:
  /** @brief a reference to a trie node.*/
  using Ref = std::shared_ptr<TrieNode>;

  /** @name Life cicle.*/
  /** @{*/
  /**
   * @brief Create a TrieNode.
   * @return a shared reference to the node created.
   * @post ret_val->is_key() == false
   * @post !ret_val->current_exists()
   */
  static Ref create();
  /** @}*/

  /** @name Observers. */
  /** @{*/

  /**
   * @brief Does the node represent a key value?
   * @return true if this node represents a key value.
   */
  bool is_key() const;

  /**
   * @brief Get the number of child nodes.
   * @return the number of child nodes.
   */
  size_t num_children() const;

  /**
   * @brief Has it the node a child for the symbol k?
   * @param k is the symbol.
   * @return true if the node has a child for the symbol k.
   */
  bool has(const std::string &k) const;

  /**
   * @brief The child for the symbol k?
   * @return a reference to the node.
   * @pre has(k)
   */
  const Ref &child(const std::string &k) const;

  /**
   * @brief Does current exist?
   * @return true if current is valid.
   */
  bool current_exists() const;

  /**
   * @brief Get the current child's node.
   * @return a reference to the current child node.
   * @pre current_exist()
   */
  const Ref &current_node() const;

  /**
   * @brief Get the current child's symbol.
   * @return the current next symbol (as a string).
   * @pre current_exist()
   */
  const std::string &current_symbol() const;

  /** @} */

  /** @name Modifiers. */
  /** @{*/

  /**
   * @brief Mark this node as a node representing (or not) a key.
   * @post is_key() == new_state
   */
  void set_is_key_state(bool new_state);

  /**
   * @brief Set a child node for a given symbol.
   * If none previous child was associated with the given symbol, a new child
   *    is create.
   * if a previous child existed for the given symbol, the child node is updated.
   * @arg[in] s is the symbol.
   * @arg[in] node is the new child node.
   * @pre node != nullptr
   * @post current_symbol()==s
   * @post current_node()==node
   */
  void set_child(const std::string &s, const Ref &node);

  /**
   * @brief Move current to first child.
   */
  void goto_first_child();

  /**
   * @brief Move current to the next child.
   * @pre current_exist()
   */
  void goto_next_child();

  /**
   * @brief Move current to the child associated with a symbol.
   * @return true if a child was found.
   * @post ret_val || !current_exists()
   * @post !ret_val || current_symbol()==s
   */
  bool find_child(const std::string &s);

  /**
   * @brief Compact this node recursively by merging with a single child.
   */
  void compact();

  /** @}*/

protected:
  friend std::ostream &operator<<(std::ostream &out, const TrieNode &node) noexcept;
  friend std::istream &operator>>(std::istream &in, TrieNode &node) noexcept(false);

  /**
   * @brief Default constructor.
   * @post !is_key()
   * @post !current_exists()
   * @post children().empty()
   */
  TrieNode();

  /**
   * @brief Get the children of the node.
   *
   * @return the children of the node.
   */
  const std::map<std::string, Ref> &children() const;

  /**
   * @brief Get the children of the node.
   *
   * @return the children of the node.
   */
  std::map<std::string, Ref> &children();

  /**
   * @brief Set the children of the node.
   *
   * @param new_children is the new children to be set.
   */
  void set_children(const std::map<std::string, Ref> &new_children);

  /**
   * @brief Get the current child.
   *
   * @return the current child.
   */
  const std::map<std::string, Ref>::const_iterator &current() const;

  /**
   * @brief Set the current child.
   *
   * @param new_current is the new current child to be set.
   */
  void set_current(const std::map<std::string, Ref>::const_iterator &new_current);

  std::map<std::string, TrieNode::Ref> dict_; 
  std::map<std::string, TrieNode::Ref>::const_iterator curr_;
  bool is_key_;

};