btree.cpp

#ifndef __BTREE_CPP
#define __BTREE_CPP

#include "btree.h"

#include <fstream>
#include <iostream>
#include <functional>
#include <memory>
#include <queue>
#include <stack>
#include <cstdlib>
#include <vector>


/* Creates a tree from a preorder traversal and replaces the current tree.
* Istream =input= is the where input is read from and get_data_fn must process the input and return T data.
*/
template<typename T>
void btree<T>::read_preorder(
    std::istream& input,
    std::function<bool(std::istream&, T&)> get_data_fn)
{
    this->root = this->read_preorder_body(input, get_data_fn);
}

/* Creates a tree form a preorder traversal. */
template<typename T>
std::shared_ptr<typename btree<T>::Node>
btree<T>::read_preorder_body(
    std::istream& input,
    std::function<bool(std::istream&, T&)> get_data_fn)
{
    T data;
    if (get_data_fn(input, data) == false) {
        return nullptr;
    }

    std::shared_ptr<btree<T>::Node> new_node;

    /* Alocate memory for new_node. */
    new_node = std::make_shared<btree<T>::Node>();

    /* Initialize node. */
    new_node->data = data;

    /* Resolve left and right child. */
    new_node->left = this->read_preorder_body(input, get_data_fn);
    new_node->right = this->read_preorder_body(input, get_data_fn);

    return new_node;
}






/*
===============================
LAB1 - prb. 12
===============================
*/
/* Creates tree from an inorder and preorder traversal and replaces the current tree. */

/*
    input: istream p, istream i, get_data_fn, peek_data_fn, serach_vector, [std::vector prev_data]

    T data = get_data_fn(p);

    node = create_node(data);
    node.left = node.right = nullptr;

    if (node->data != peek_data_fn(i))  // check if node can have left child
        node->left = fn(...);
    else
        data = get_data_fn(i);

    if (!seen_before(peek_data_fn(i), vector)) // check if node can have right child
        this->right = fn(...);
    else
        data = get_data_fn(i);

    return node;
*/

template<typename T>
std::shared_ptr<typename btree<T>::Node> btree<T>::read_traversal_body(
    std::istream& preorder, std::istream& inorder,
    std::function<bool(std::istream&, T&)> get_data_fn,
    std::function<bool(std::istream&, T&)> peek_data_fn,
    std::function<bool(std::vector<T>, T)> search_vector,
    std::vector<T>& prev_data)
{
    T data;

    if (get_data_fn(preorder, data) == false) {
        return nullptr;
    }

    std::shared_ptr<btree<T>::Node> node;

    node = this->create_node(data);
    node->left = node->right = nullptr;

    prev_data.push_back(node->data);

    /* Check if there's more data. */
    if (peek_data_fn(inorder, data) == false) {
        return node;
    }

    /* Resolve left child. */
    if (node->data != data) {
        node->left = this->read_traversal_body(
            preorder, inorder,
            get_data_fn, peek_data_fn,
            search_vector, prev_data);
    }
    else {
        if (get_data_fn(inorder, data) == false) {
            std::cout << "WEIRD! Should not have failed." << '\n';
        }
    }

    /* Check if there's more data. */
    if (peek_data_fn(inorder, data) == false) {
        return node;
    }

    /* Resolve right child. */
    if (search_vector(prev_data, data) == false) {
        node->right = this->read_traversal_body(
            preorder, inorder,
            get_data_fn, peek_data_fn,
            search_vector, prev_data);
    }
    else {
        if (get_data_fn(inorder, data) == false) {
            std::cout << "WEIRD! Should not have failed." << '\n';
        }
    }

    return node;
}

template<typename T>
void btree<T>::read_traversal(
    std::istream& preorder, std::istream& inorder,
    std::function<bool(std::istream&, T&)> get_data_fn,
    std::function<bool(std::istream&, T&)> peek_data_fn,
    std::function<bool(std::vector<T>, T)> search_vector)
{
    std::vector<T> prev_nodes;
    this->root = this->read_traversal_body(
        preorder, inorder,
        get_data_fn, peek_data_fn,
        search_vector, prev_nodes);
}




/* Breadth traversal, applying =action= to each node data. */
template<typename T>
std::shared_ptr<typename btree<T>::Node>
btree<T>::breadth_traversal(std::function<void(T& data)> action)
{
    if (this->root == nullptr) {
        std::cout << "(null)" << '\n';
        return nullptr;
    }

    std::shared_ptr<btree<T>::Node> current_node;
    std::queue< std::shared_ptr<btree<T>::Node> > fringe;
    fringe.push(this->root);

    do {
        current_node = fringe.front();
        fringe.pop();

        action(current_node->data);

        if (current_node->left != nullptr) {
            fringe.push(current_node->left);
        }

        if (current_node->right != nullptr) {
            fringe.push(current_node->right);
        }

    } while (!fringe.empty());

    return current_node;
}





/*
===============================
LAB1 - prb. 11
===============================
*/
/* Traverse tree in preorder, applying an =action= to each node data
*    + Calculate depths and return the max depth.
*/
template<typename T>
int btree<T>::preorder_traversal(
    std::function<void(T& data)> action)
{
    if (this->root == nullptr) {
        std::cout << "(null)" << '\n';
        return -1;
    }

    std::shared_ptr<btree<T>::Node> current_node;
    std::stack< std::shared_ptr<btree<T>::Node> > fringe;

    fringe.push(this->root);
    this->root->depth = 0;

    int max_depth = 0;

    do {
        current_node = fringe.top();
        fringe.pop();

        action(current_node->data);

        if (current_node->depth > max_depth) {
            max_depth = current_node->depth;
        }

        if (current_node->right != nullptr) {
            current_node->right->depth = current_node->depth + 1;
            fringe.push(current_node->right);
        }

        if (current_node->left != nullptr) {
            current_node->left->depth = current_node->depth + 1;
            fringe.push(current_node->left);
        }

    } while (!fringe.empty());

    return max_depth;
}


/* Creates a node, sets data field and returns shared_ptr to the node. */
template<typename T>
std::shared_ptr<typename btree<T>::Node> btree<T>::create_node(T data)
{
    std::shared_ptr<btree<T>::Node> new_node = std::make_shared<btree<T>::Node>();

    new_node->data = data;

    return new_node;
}

#endif