#include <iostream>
#include <istream>
#include <memory>
#include <string>
#include <string_view>
#include <tuple>

/* (EXTRA TODOs are for those who want to do some extra work)

TODO: implement methods `set_length` and `set_right` of the `Node` class

TODO: implement method find of the `Tree` class, it returns a `std::tuple` with three values:
    - the first value is a pointer to the node with the given value (or nullptr if the value is not in the tree)
    - the second value is a pointer to the parent of the node (or nullptr if the node is the root)
        - if the node is not in the tree, the second value is the parent of the node that would be its parent
    - the third value is whether the node is the left or right child of its parent (or None if it is the root)

TODO: implement methods `insert`, `remove`, `print` and `clear` of the `Tree` class
  there are two possible ways to do it:
    1. the first one is to implement them as Node methods using recursion
        (each tree method calls the corresponding method on the root node)

    2. the second one is to implement them using the `find` method

  ! we will use the second approach, because it is more efficient and educative !

TODO: implement program loop: (in all bullets, "the rest of the line" refers to just one string)
  - while (std::getline(in, line)):
    - if the line starts with "insert", it inserts the rest of the line into the tree
        - if the value is already in the tree, do nothing

    - if the line starts with "remove", it removes the rest of the line from the tree
        - if the value is not in the tree, do nothing

    - if the line starts with "print", it prints the tree in-order

    - if the line starts with "clear", it removes all nodes from the tree

    ! to parse the line, we can use std::istringstream(std::move(line)) ! <- move avoids a copy

    - std::istringstream from <sstream> is like std::cin, but it reads from a string instead of stdin
        - parse the first word into a std::string via the >> operator
        - then, parse std::ws via the >> operator (this skips all whitespace)
            remember, subsequent >> can be chained on the same line
        - then use std::getline to parse the rest of the line into a std::string

    EXTRA TODO: might be more efficient with string_views, but i wanted to show you istringstream

TODO: if main receives a command-line argument, open the file and pass it to program_loop
    - if the file cannot be opened, print an error message and exit with code 1

    ! use std::ifstream from <fstream> to open a file !

    EXTRA TODO: reimplement Tree and program_loop such that they take an extra std::ostream& argument
                and print all output to it (instead of std::cout) if main receives a second argument

EXTRA TODO: implement "rotate left" and "rotate right" commands
    - if the line starts with "rotate left",
        it rotates the subtree associated with the rest of the line to the left
          (the right child becomes the new root, the old root becomes the left child of the new root)

    - if the line starts with "rotate right",
        it rotates the subtree associated with the rest of the line to the right
          (the left child becomes the new root, the old root becomes the right child of the new root)

    - if the tree cannot be rotated, do nothing

EXTRA TODO: move the tree implementation into a separate .cpp file

*/

class Node {
    // TODO: it might be useful to make `Tree` a `friend class` of `Node`
    //   (this allows `Tree` to access private members of `Node`)
public:
    // C++ offers enums and enum classes; the latter is usually preferred
    //   the difference is that enum class value names are strictly scoped
    //     (e.g. Node::Child::Left; just Node::Left is not allowed)
    enum class Child { Left, Right, None };

    // notice that the `value_{value}` initialization is allowed in the *constructor initializer list* even though value_ is const
    //  (constructor initializer list begins with a colon after the constructor declarator and ends before the constructor body)
    //  (it would not be allowed in the constructor body via `value_ = value`)
    //  the same would apply to any references (e.g. `std::ostream& out` in some writer class)
    Node(const std::string& value) /* : constructor initializer list */ {
        value_ = value; // FIXME: this is not allowed
    } // copy the value into the node (the value is const, so we can't move it

    // this is a special reference called *rvalue reference*, the `value` can be std::move'd instead of copying
    // we can use this overload by calling `Node{std::move(value)}` or by passing a temporary: `Node(std::string{"value"})`
    Node(std::string&& value)  {
        value_ = std::move(value); // FIXME: this is not allowed
    } // move the value into the node
    // left_, right_ are initialized to nullptr by default

    // returns a read-only reference to the value
    const std::string& value() const { return value_; }

    // returns an observer pointer to the left/right child
    Node *left() const { return left_.get(); }
    Node *right() const { return right_.get(); }

    // call this method as `node.set_left(std::move(new_left))` or with a temporary: `node.set_left(std::make_unique<Node>(...))`,
    //   the source will be automatically set to nullptr
    void set_left(std::unique_ptr<Node>&& new_left) {
        // TODO move the ownership of the new left child to this node
    }

    void set_right(std::unique_ptr<Node>&& new_right) {
        // TODO move the ownership of the new right child to this node
    }

private:
    const std::string value_; // the value stored in the node, it can't be changed
    std::unique_ptr<Node> left_, right_;
};

class Tree {
public:
    // (implicitly defined) Tree() : root_{nullptr} {}

    // this is a special reference called *rvalue reference*, the `value` can be std::move'd instead of copying
    void insert(std::string&& value) {
        // insert the value into the tree
        // if the value is already in the tree, do nothing
    }

    // notice that the value is passed by value, as std::string_view already represents a reference
    void remove(std::string_view value) {
        // remove the value from the tree
        // if the value is not in the tree, do nothing
        //
        // if the removed node has two children, replace it with the smallest node from the right subtree
        //   and replace that node with its right child; correctly link all nodes
        // otherwise, replace it with the only child (or nullptr)
        //   (you can use the ternary operator to do this in one line: `condition ? value_if_true : value_if_false`)
    }

    std::tuple<Node*, Node*, Node::Child> find(std::string_view value) const {
        // find the node with the given value and return it
        // if the value is not in the tree, return nullptr
        //
        // also, return the parent of the node (or nullptr if the node is the root)
        //  (or the parent of the node that would be its parent if it was in the tree)
        // and return whether the node is the left or right child of its parent
        //  (or None if it is the root)

        return /* TODO: remove this */ {nullptr, nullptr, Node::Child::None};
    }

    void clear() {
        // remove all nodes from the tree
        // hint: node children are automatically deleted when the node is deleted
    }

    void print() const {
        // print the tree in-order: for each node, print the left subtree, then the node itself, then the right subtree
        // print each string on a separate line and indent it by the depth of the node (the root has depth 0)
        //   (use std::string(depth, '\t') to create the indentation string)
    }

private:
    std::unique_ptr<Node>& node_handle(Node* parent, Node::Child child) {
        // TODO: this helper function might be useful for the insert and remove methods
        //  try switch statement here (do not forget to put a break after each case)
        //  return root_ for Node::Child::None regardless of the parent

        // we could very similarly define Node::set_child(Node::Child which_one, std::unique_ptr<Node>&& new_child)
        //  and it would be arguably cleaner than this,
        //  but I personally like this better for the Node::Child::None case

        return /* TODO: remove this */ root_;
    }

    // static method as it doesn't require to access the Tree (might as well be a Node method, but it feels more natural here)
    static Node* min_parent(Node* node) {
        // TODO: this helper function might be useful for the remove method
        // return the parent of the minimum in the given subtree
        //  (nullptr if the parent is the minimum - has no parent in the subtree)

        return /* TODO: remove this */ nullptr;
    }

    std::unique_ptr<Node> root_;
};

void program_loop(Tree &tree, std::istream& in = std::cin) {
    // TODO implement the program loop
    //  try to use std::istringstream to parse the input line according to the specification
}

int main(int argc, char* argv[]) {
    // create the tree object on the stack
    Tree tree;
    program_loop(tree);
}