linked_impl.h

Go to the documentation of this file.

/*
 * This file is part of the alglib project.
 *
 * (c) Divyanshu Kakwani <divkakwani@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE file
 * that was distributed with this source code.
 */

#include <memory>
#include <vector>
#include <stdexcept>

#pragma once

// Forward declaration
template<typename value_t> class Tree;

template<typename value_t>
struct Node {

    typedef value_t value_type;

    std::shared_ptr<Node> parent;
    
    value_type val;

    std::vector<std::shared_ptr<Tree<value_t>>> subtrees;

    Node(const value_type& value) {
        val = value;
        parent = 0;
        // Keep the subtrees list empty
    }

    std::shared_ptr<Tree<value_t>> get_ith_subtree(int i) {
        if(i >= subtrees.size())
            throw std::out_of_range("i is too big");
        return subtrees[i];
    }

    void set_ith_subtree(std::shared_ptr<Tree<value_type>> pT, int i) {
        if(i > subtrees.size())
            throw std::out_of_range("i is too big");
        if(subtrees.size() == i)
            subtrees.push_back(pT);
        else
            subtrees[i] = pT;
    }

    value_type get_val() {
        return val;
    }
    void set_val(const value_type& value) {
        val = value;
    }

    Node<value_type>& get_parent() {
        return parent;
    }
    void set_parent(std::shared_ptr<Node<value_type>> new_parent) {
        parent = new_parent;
    }

};    

template<typename value_t>
struct Tree {
 
 public:
    typedef value_t value_type;

    Node<value_type>& root;

    explicit Tree(const Node<value_type>& root_node) : root(root_node) {}
    
    // Iterators
    class PostIter;
    class PreIter;
    class InIter;

    // Inspection of the tree
    PreIter prebegin() const {}                                                                     
    PreIter preend() const {}                                                                       
    InIter inbegin() const {}                                                                       
    InIter inend() const {}                                                                            
    PostIter postbegin() const {}
    PostIter postend() const {}
};

// Node n(3);
// Tree T(n);
// Tree.root.set_ith_subtree(a tree or a node)