biased_binary_node.h

#ifndef BIASED_BINARY_NODE_H
#define BIASED_BINARY_NODE_H

#include "preprocessor_compilation_control.h"
#include <cstddef>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <memory>
#include <queue>

template <typename T>
class BiasedBinaryNode;

template <typename T>
std::ostream& operator<<(std::ostream&, BiasedBinaryNode<T>&);

template <typename T>
class BiasedBinaryNode : public std::enable_shared_from_this<BiasedBinaryNode<T>>{
private:
  T _value;

  unsigned long _rank;
  std::weak_ptr<BiasedBinaryNode<T>> _parent;
  std::shared_ptr<BiasedBinaryNode<T>> _left_child;
  std::shared_ptr<BiasedBinaryNode<T>> _right_child;

  std::shared_ptr<BiasedBinaryNode<T>> tilt_right();
  std::shared_ptr<BiasedBinaryNode<T>> tilt_left();
  std::shared_ptr<BiasedBinaryNode<T>> local_join(std::shared_ptr<BiasedBinaryNode<T>>);
public:
  BiasedBinaryNode(unsigned long);
  ~BiasedBinaryNode();
  friend std::ostream& operator<<<>(std::ostream&, BiasedBinaryNode<T>&);
  std::shared_ptr<BiasedBinaryNode<T>> me();

  bool is_leaf();
  bool is_left_child();
  T& value();
  size_t& rank();

  std::weak_ptr<BiasedBinaryNode<T>>& parent();
  std::shared_ptr<BiasedBinaryNode<T>>& left_child();
  std::shared_ptr<BiasedBinaryNode<T>>& right_child();

  void rewire_right_child_with(std::shared_ptr<BiasedBinaryNode<T>>);
  void rewire_left_child_with(std::shared_ptr<BiasedBinaryNode<T>>);
  void replace_with(std::shared_ptr<BiasedBinaryNode<T>>);

  void split_at(std::shared_ptr<BiasedBinaryNode<T>> split_pos,std::shared_ptr<BiasedBinaryNode<T>>& before, std::shared_ptr<BiasedBinaryNode<T>>& after);
  std::shared_ptr<BiasedBinaryNode<T>> global_join(std::shared_ptr<BiasedBinaryNode<T>>);
};


#include "biased_binary_node.cpp"

#endif