mlContainers.h

Go to the documentation of this file.

/*************************************************************************************
**
** Copyright 2022, MeVis Medical Solutions AG
**
** The user may use this file in accordance with the license agreement provided with
** the Software or, alternatively, in accordance with the terms contained in a
** written agreement between the user and MeVis Medical Solutions AG.
**
** For further information use the contact form at https://www.mevislab.de/contact
**
**************************************************************************************/
 
#pragma once
 
#include "mlUtilsSystem.h"
#include <algorithm>
#include <vector>
 
ML_UTILS_START_NAMESPACE
 
/*
 * A structure that implements a value-based tree.
 */
template <typename T> struct tree_node
{
  T value;
  std::vector<tree_node> children;
};
 
/*
 * Flattens the given tree into a vector of elements.
 */
template <typename T> void flatten(const tree_node<T> &tree, std::vector<T> &flatten_elements)
{
  flatten_elements.push_back(tree.value);
  for (const auto &child : tree.children)
  {
    flatten(child, flatten_elements);
  }
}
 
/*
 * Inserts the given element into the tree as set operation.
 * operator<, operator>=, and operator== for the elements must be defined for the insert
 * operation. operator== is only needed to identify an element as zero.
 * @param tree The tree that shall be filled.
 * @param newValue The new value that shall be put into the tree.
 * @param zero A value that identifies an object of T as being empty.
 */
template <typename T>
void insert_set_sorted(tree_node<T> &tree, T newValue, T zero = {})
{
  // Is the new element less than the root? Then insert new root and add the tree as child.
  if (tree.value < newValue)
  {
    tree_node<T> newRoot;
    insert_set_sorted(newRoot, std::move(newValue));
 
    std::swap(tree, newRoot);
 
    tree.children.emplace_back(tree_node<T>{std::move(newRoot)});
    return;
  }
  bool reparent{};
  for (auto &child : tree.children)
  {
    if (child.value >= newValue)
    {
      insert_set_sorted(child, std::move(newValue));
      return;
    }
 
    // Is the child less than the new one?
    if (newValue >= child.value)
    {
      reparent = true;
      break;
    }
  }
 
  if (reparent)
  {
    // move the lesser childs to the end
    auto itToMoved =
        std::stable_partition(tree.children.begin(), tree.children.end(),
                       [&newValue](const auto &item) { return !(newValue >= item.value); });
 
    auto newChild = tree_node<T>{std::move(newValue), {}};
 
    // move all lesser childs as grandchild to the new child
    for (auto it = itToMoved; it != tree.children.end(); ++it)
    {
      newChild.children.emplace_back(std::move(*it));
    }
    tree.children.erase(itToMoved, tree.children.end());
    tree.children.emplace_back(std::move(newChild));
 
    return;
  }
 
  if (tree.value == zero)
  {
    tree.value = std::move(newValue);
  }
  else
  {
    tree.children.emplace_back(tree_node<T>{std::move(newValue), {}});
  }
}
 
 
ML_UTILS_END_NAMESPACE