dynamic_node.h

#ifndef DYNAMIC_NODE_H
#define DYNAMIC_NODE_H

#include "biased_binary_node.h"
#include <algorithm>

class DynamicNode;

/*
  class overrides operator so that DynamicNode(see below) can support its invariants
*/
class TreeRepresentative : public BiasedBinaryNode<DynamicNode*>{
protected:
  std::shared_ptr<BiasedBinaryNode<DynamicNode*>> tilt_right();
  std::shared_ptr<BiasedBinaryNode<DynamicNode*>> tilt_left();
  std::shared_ptr<BiasedBinaryNode<DynamicNode*>> local_join(std::shared_ptr<BiasedBinaryNode<DynamicNode*>>);
public:
  TreeRepresentative(unsigned long);

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

  void split_at(std::shared_ptr<BiasedBinaryNode<DynamicNode*>> split_pos,std::shared_ptr<BiasedBinaryNode<DynamicNode*>>& before, std::shared_ptr<BiasedBinaryNode<DynamicNode*>>& after, std::shared_ptr<BiasedBinaryNode<DynamicNode*>>& removed_interior_parent, std::shared_ptr<BiasedBinaryNode<DynamicNode*>>& removed_interior_root);
  std::shared_ptr<BiasedBinaryNode<DynamicNode*>> global_join(std::shared_ptr<BiasedBinaryNode<DynamicNode*>>, std::shared_ptr<BiasedBinaryNode<DynamicNode*>> = nullptr);
};

/*
  Realizes Sleator and Tarjans Dynamic Tree Datastruct (using Biased Trees)
*/
class DynamicNode{
  friend TreeRepresentative;
  std::shared_ptr<TreeRepresentative> const _node;

  bool _reversed;

  double _relative_path_weight;       // netcost in paper
  bool _rel_path_encoded;
  double _relative_structure_weight;  // netmin in paper
  bool _rel_struct_encoded;

  void decode_rel_path_and_struct_w();
  void encode_rel_path_and_struct_w();
  void decode_rel_struct_w();
protected:
  std::shared_ptr<TreeRepresentative> node();
  bool& reversed();
public:
  DynamicNode(unsigned long);

  bool global_reversed();
  void reverse();

  double weight();          // for interior nodes
  double min_path_weight(); // "
  double send(double);              // Pushes along the entire path to which the current node belongs


  std::shared_ptr<TreeRepresentative>& head();   // implementation differes from paper
  std::shared_ptr<TreeRepresentative>& tail();   // "

  std::shared_ptr<TreeRepresentative>& before(); // for leaves
  std::shared_ptr<TreeRepresentative>& after();  // "

private:
  // other data to reflect Graph
  bool is_leaf();
  std::vector<DynamicNode> reachable;
};

#endif