Tree.h

Go to the documentation of this file.

#ifndef COMMA_PROJECT_TREE_H
#define COMMA_PROJECT_TREE_H
 
/*
 * CoMMA
 *
 * Copyright © 2024 ONERA
 *
 * Authors: Nicolas Lantos, Alberto Remigi, and Riccardo Milani
 * Contributors: Karim Anemiche
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */
 
#include <cassert>
#include <cstddef>
#include <iostream>
#include <memory>
#include <vector>
 
namespace comma {
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class Node {
public:
  Node(CoMMAIndexType index, CoMMAWeightType volume) :
    _index(index), _volume(volume){};
  CoMMAIndexType _index;
  CoMMAWeightType _volume;
  CoMMAIntType _sonc = 0;
  std::shared_ptr<Node> _father;
  std::shared_ptr<Node> _left_idx;
  std::shared_ptr<Node> _right_idx;
  std::shared_ptr<Node> _left_son_idx;
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class Tree {
public:
  using NodeType = Node<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
 
  explicit Tree(std::shared_ptr<NodeType> &root) :
    _root(root) {}
 
  ~Tree() = default;
 
  std::shared_ptr<NodeType> _root;
 
  void insertSon(
    const CoMMAIndexType &father_index,
    const CoMMAIndexType &index,
    const CoMMAWeightType &volume,
    const CoMMAIntType &root
  ) {
    std::shared_ptr<NodeType> insertion =
      std::make_shared<NodeType>(index, volume);
    auto u_p_father =
      root == 1 ? _root : search(_root->_left_son_idx, father_index);
    assert(u_p_father != nullptr);
    insertion->_father = u_p_father;
    auto left_idx = transverse(u_p_father->_left_son_idx);
    if (left_idx == nullptr) {
      u_p_father->_left_son_idx = insertion;
    } else {
      insertion->_left_idx = left_idx;
      left_idx->_right_idx = insertion;
    }
    u_p_father->_sonc = u_p_father->_sonc + 1;
    // std::cout << u_p_father->_sonc << std::endl;
  }
 
  std::shared_ptr<NodeType> search(
    std::shared_ptr<NodeType> &node, const CoMMAIndexType &value
  ) {
    if (node->_index == value && node->_father != nullptr) {
      return node;
    }
    if (node == nullptr || node->_right_idx == nullptr) {
      return nullptr;
    }
    return (search(node->_right_idx, value));
  }
 
  std::shared_ptr<NodeType> transverse(std::shared_ptr<NodeType> &node) {
    if (node == nullptr || node->_right_idx == nullptr) {
      return node;
    }
    return (transverse(node->_right_idx));
  }
 
  void deleteNode(const CoMMAIndexType &value) {
    delete_node(_root->_left_son_idx, value);
  }
 
  void delete_node(
    std::shared_ptr<NodeType> &searched_node, const CoMMAIndexType &value
  ) {
    if (searched_node == nullptr) {
      return;
    }
    if (searched_node->_index == value) {
      // case 0: leftest node
      if (searched_node->_left_idx == nullptr) {
        searched_node->_father->_sonc--;
        searched_node->_father->_left_son_idx = searched_node->_right_idx;
        searched_node->_right_idx->_left_idx = nullptr;
      }
      // case 1: rightest node
      else if (searched_node->_right_idx == nullptr) {
        searched_node->_father->_sonc = searched_node->_father->_sonc - 1;
        searched_node->_left_idx->_right_idx.reset();
      } else {
        searched_node->_father->_sonc--;
        searched_node->_left_idx->_right_idx = searched_node->_right_idx;
        searched_node->_right_idx->_left_idx = searched_node->_left_idx;
      }
      return;
    }
    delete_node(searched_node->_right_idx, value);
  }
 
  void print() { print_nodes(_root); }
 
  void print_nodes(std::shared_ptr<NodeType> &node) {
    if (node == nullptr) {
      return;
    }
    // std::cout << "node" << node->_index << std::endl;
    print_nodes(node->_left_son_idx);
    print_nodes(node->_right_idx);
  }
};
 
}  // end namespace comma
 
#endif  // COMMA_PROJECT_TREE_H