gcc/splay-tree-utils.h

// Splay tree utilities                                             -*- C++ -*-
// Copyright (C) 2020-2021 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3, or (at your option) any later
// version.
//
// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3.  If not see
// <http://www.gnu.org/licenses/>.

// Implement splay tree node accessors for a class that stores its
// two child nodes in a member variable of the form:
//
//    Node m_children[2];
template<typename Node>
class default_splay_tree_accessors
{
public:
  using node_type = Node;

  static auto
  child (node_type node, unsigned int index)
    -> decltype (node->m_children[index]) &
  {
    return node->m_children[index];
  }
};

// Implement splay tree node accessors for a class that stores its
// two child nodes in a member variable of the form:
//
//    Node m_children[2];
//
// and also stores its parent node in a member variable of the form:
//
//    Node m_parent;
template<typename Node>
class default_splay_tree_accessors_with_parent
  : public default_splay_tree_accessors<Node>
{
public:
  using node_type = Node;

  static auto
  parent (node_type node) -> decltype (node->m_parent) &
  {
    return node->m_parent;
  }
};

// Base is a splay tree accessor class for nodes that have no parent field.
// Base therefore provides a Base::child method but does not provide a
// Base::parent method.  Extend Base with dummy routines for setting the
// parent, which is a no-op when the parent is not stored.
template<typename Base>
class splay_tree_accessors_without_parent : public Base
{
public:
  using typename Base::node_type;

  static void set_parent (node_type, node_type) {}
};

// Base is splay tree accessor class for nodes that have a parent field.
// Base therefore provides both Base::child and Base::parent methods.
// Extend Base with routines for setting the parent.
template<typename Base>
class splay_tree_accessors_with_parent : public Base
{
public:
  using typename Base::node_type;

  // Record that NODE's parent is now NEW_PARENT.
  static void
  set_parent (node_type node, node_type new_parent)
  {
    Base::parent (node) = new_parent;
  }
};

// A base class that provides some splay tree operations that are common
// to both rooted_splay_tree and rootless_splay_tree.
//
// Nodes in the splay tree have type Accessors::node_type; this is
// usually a pointer type.  The Accessors class provides the following
// static member functions for accessing nodes:
//
// - Accessors::child (NODE, INDEX)
//     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
//     to where NODE's left child is stored, otherwise return a reference
//     to where NODE's right child is stored.
//
// - Accessors::set_parent (NODE, PARENT)
//     Record that NODE's parent node is now PARENT.
template<typename Accessors>
class base_splay_tree : protected Accessors
{
public:
  using typename Accessors::node_type;

  // INDEX is either 0 or 1.  If INDEX is 0, insert CHILD immediately
  // before NODE, otherwise insert CHILD immediately after NODE.
  //
  // Complexity: O(1).
  static void insert_child (node_type node, unsigned int index,
			    node_type child);

  // Print NODE and its child nodes to PP for debugging purposes,
  // using PRINTER (PP, N) to print the data for node N.
  template<typename Printer>
  static void print (pretty_printer *pp, node_type node, Printer printer);

protected:
  using Accessors::set_parent;

  static node_type get_child (node_type, unsigned int);
  static void set_child (node_type, unsigned int, node_type);
  static node_type promote_child (node_type, unsigned int);
  static void promote_child (node_type, unsigned int, node_type);

  template<unsigned int N>
  static node_type splay_limit (node_type);

  static node_type remove_node_internal (node_type);

  template<typename Printer>
  static void print (pretty_printer *pp, node_type node, Printer printer,
		     char, vec<char> &);
};

// This class provides splay tree routines for cases in which the root
// of the splay tree is known.  It works with both nodes that store
// their parent node and nodes that don't.
//
// The class is lightweight: it only contains a single root node.
template<typename Accessors>
class rooted_splay_tree : public base_splay_tree<Accessors>
{
  using parent = base_splay_tree<Accessors>;

public:
  using typename Accessors::node_type;

protected:
  // The root of the splay tree, or node_type () if the tree is empty.
  node_type m_root;

public:
  rooted_splay_tree () : m_root () {}

  // Construct a tree with the specified root node.
  rooted_splay_tree (node_type root) : m_root (root) {}

  // Return the root of the tree.
  node_type root () const { return m_root; }

  // Return true if the tree contains any nodes.
  explicit operator bool () const { return m_root; }

  // Dereference the root node.
  node_type operator-> () { return m_root; }

  // Insert NEW_NODE into the splay tree, if no equivalent node already
  // exists.  For a given node N, COMPARE (N) should return:
  //
  // - a negative value if NEW_NODE should come before N
  // - zero if NEW_NODE and N are the same
  // - a positive value if NEW_NODE should come after N
  //
  // Return true if NEW_NODE was inserted.
  //
  // On return, NEW_NODE or its equivalent is the root of the tree.
  //
  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
  // the complexity of the comparison.
  template<typename Comparator>
  bool insert (node_type new_node, Comparator compare);

  // Insert NEW_NODE into the splay tree, given that NEW_NODE is the
  // maximum node of the new tree.  On return, NEW_NODE is also the
  // root of the tree.
  //
  // Complexity: O(1).
  void insert_max_node (node_type new_node);

  // Splice NEXT_TREE onto this one, given that all nodes in NEXT_TREE
  // are greater than the maximum node in this tree.  NEXT_TREE should
  // not be used afterwards.
  //
  // Complexity: O(1) if the root of the splay tree is already the maximum
  // node.  Otherwise amortized O(log N), worst-cast O(N).
  void splice_next_tree (rooted_splay_tree next_tree);

  // The root of the tree is currently the maximum node.  Replace it
  // with NEW_NODE.
  //
  // Complexity: O(1).
  void replace_max_node_at_root (node_type new_node);

  // Remove the root node of the splay tree.
  //
  // Complexity: O(1) if removing the maximum or minimum node.
  // Otherwise amortized O(log N), worst-cast O(N).
  void remove_root ();

  // Split the left child of the current root out into a separate tree
  // and return the new tree.
  rooted_splay_tree split_before_root ();

  // Split the right child of the current root out into a separate tree
  // and return the new tree.
  rooted_splay_tree split_after_root ();

  // If the root is not the minimum node of the splay tree, bring the previous
  // node to the root and return true, otherwise return false.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  bool splay_prev_node ();

  // If the root is not the maximum node of the splay tree, bring the next
  // node to the root and return true, otherwise return false.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  bool splay_next_node ();

  // Bring the minimum node of the splay tree to the root.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  void splay_min_node ();

  // Bring the maximum node of the splay tree to the root.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  void splay_max_node ();

  // Return the minimum node of the splay tree, or node_type () if the
  // tree is empty.  On return, the minimum node (if any) is also the
  // root of the tree.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  node_type min_node ();

  // Return the maximum node of the splay tree, or node_type () if the
  // tree is empty.  On return, the maximum node (if any) is also the
  // root of the tree.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  node_type max_node ();

  // Search the splay tree.  For a given node N, COMPARE (N) should return:
  //
  // - a negative value if N is bigger than the node being searched for
  // - zero if N is the node being searched for
  // - a positive value if N is smaller than the node being searched for
  //
  // If the node that COMPARE is looking for exists, install it as the root
  // node of the splay tree.  Otherwise, arbitrarily pick either:
  //
  // - the maximum node that is smaller than the node being searched for or
  // - the minimum node that is bigger than the node being searched for
  //
  // and install that node as the root instead.
  //
  // Return the result of COMPARE for the new root.
  //
  // This form of lookup is intended for cases in which both the following
  // are true:
  //
  // (a) The work that COMPARE needs to do to detect if a node is too big
  //     is the same as the work that COMPARE needs to do to detect if a
  //     node is too small.  (This is not true of range comparisons,
  //     for example.)
  //
  // (b) COMPARE is (or might be) relatively complex.
  //
  // This form of lookup is also useful if the items being compared naturally
  // provide a <=>-style comparison result, without the result having to be
  // forced by the equivalent of a ?: expression.
  //
  // The implementation only invokes COMPARE once per node.
  //
  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
  // the complexity of the comparison.
  template<typename Comparator>
  auto lookup (Comparator compare) -> decltype (compare (m_root));

  // Search the splay tree.  For a given node N, WANT_SOMETHING_SMALLER (N)
  // is true if N is too big and WANT_SOMETHING_BIGGER (N) is true if N
  // is too small.  Both functions return false if N is the node being
  // searched for.
  //
  // If the node that is being searched for exists, install it as the root
  // node of the splay tree and return 0.  Otherwise, arbitrarily choose
  // between these two options:
  //
  // - Install the maximum node that is smaller than the node being
  //   searched for as the root of the splay tree and return 1.
  //
  // - Install the minimum node that is bigger than the node being
  //   searched for and return -1.
  //
  // This form of lookup is intended for cases in which either of the
  // following are true:
  //
  // (a) WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER test different
  //     parts of the node's data.  For example, when comparing ranges,
  //     WANT_SOMETHING_SMALLER would test the lower limit of the given
  //     node's range while WANT_SOMETHING_BIGGER would test the upper
  //     limit of the given node's range.
  //
  // (b) There is no significant overhead to calling both
  //     WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node.
  //
  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
  // the complexity of the comparisons.
  template<typename LeftPredicate, typename RightPredicate>
  int lookup (LeftPredicate want_something_smaller,
	      RightPredicate want_something_bigger);

  // Keep the ability to print subtrees.
  using parent::print;

  // Print the tree to PP for debugging purposes, using PRINTER (PP, N)
  // to print the data for node N.
  template<typename Printer>
  void print (pretty_printer *pp, Printer printer) const;

protected:
  using parent::get_child;
  using parent::set_child;
  using parent::promote_child;

  using parent::set_parent;

  template<unsigned int N>
  bool splay_neighbor ();
};

// Provide splay tree routines for nodes of type Accessors::node_type,
// which doesn't have a parent field.  Use Accessors::child to access
// the children of a node.
template<typename Accessors>
using splay_tree_without_parent
  = rooted_splay_tree<splay_tree_accessors_without_parent<Accessors>>;

// A splay tree for nodes of type Node, which is usually a pointer type.
// The child nodes are stored in a member variable:
//
//    Node m_children[2];
//
// Node does not have a parent field.
template<typename Node>
using default_splay_tree
  = splay_tree_without_parent<default_splay_tree_accessors<Node>>;

// A simple splay tree node that stores a value of type T.
template<typename T>
class splay_tree_node
{
  friend class default_splay_tree_accessors<splay_tree_node *>;

public:
  splay_tree_node () = default;
  splay_tree_node (T value) : m_value (value), m_children () {}

  T &value () { return m_value; }
  const T &value () const { return m_value; }

private:
  T m_value;
  splay_tree_node *m_children[2];
};

// A splay tree whose nodes hold values of type T.
template<typename T>
using splay_tree = default_splay_tree<splay_tree_node<T> *>;

// Provide splay tree routines for cases in which the root of the tree
// is not explicitly stored.
//
// The nodes of the tree have type Accessors::node_type, which is usually
// a pointer type.  The nodes have a link back to their parent.
//
// The Accessors class provides the following static member functions:
//
// - Accessors::child (NODE, INDEX)
//     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
//     to where NODE's left child is stored, otherwise return a reference
//     to where NODE's right child is stored.
//
// - Accessors::parent (NODE)
//     Return a reference to where NODE's parent is stored.
template<typename Accessors>
class rootless_splay_tree
  : public base_splay_tree<splay_tree_accessors_with_parent<Accessors>>
{
  using full_accessors = splay_tree_accessors_with_parent<Accessors>;
  using parent = base_splay_tree<full_accessors>;

public:
  using rooted = rooted_splay_tree<full_accessors>;

  using typename Accessors::node_type;

  // Remove NODE from the splay tree.  Return the node that replaces it,
  // or null if NODE had no children.
  //
  // Complexity: O(1) if removing the maximum or minimum node.
  // Otherwise amortized O(log N), worst-cast O(N).
  static node_type remove_node (node_type node);

  // Splay NODE so that it becomes the root of the splay tree.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  static void splay (node_type node);

  // Like splay, but take advantage of the fact that NODE is known to be
  // the minimum node in the tree.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  static void splay_known_min_node (node_type node);

  // Like splay, but take advantage of the fact that NODE is known to be
  // the maximum node in the tree.
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  static void splay_known_max_node (node_type node);

  // Splay NODE while looking for an ancestor node N for which PREDICATE (N)
  // is true.  If such an ancestor node exists, stop the splay operation
  // early and return PREDICATE (N).  Otherwise, complete the splay operation
  // and return DEFAULT_RESULT.  In the latter case, NODE is now the root of
  // the splay tree.
  //
  // Note that this routine only examines nodes that happen to be ancestors
  // of NODE.  It does not search the full tree.
  //
  // Complexity: amortized O(P log N), worst-cast O(P N), where P is the
  // complexity of the predicate.
  template<typename DefaultResult, typename Predicate>
  static auto splay_and_search (node_type node, DefaultResult default_result,
				Predicate predicate)
    -> decltype (predicate (node, 0));

  // NODE1 and NODE2 are known to belong to the same splay tree.  Return:
  //
  // -1 if NODE1 < NODE2
  // 0 if NODE1 == NODE2
  // 1 if NODE1 > NODE2
  //
  // Complexity: amortized O(log N), worst-cast O(N).
  static int compare_nodes (node_type node1, node_type node2);

protected:
  using parent::get_child;
  using parent::set_child;
  using parent::promote_child;

  static node_type get_parent (node_type);
  using parent::set_parent;

  static unsigned int child_index (node_type, node_type);

  static int compare_nodes_one_way (node_type, node_type);

  template<unsigned int N>
  static void splay_known_limit (node_type);
};

// Provide rootless splay tree routines for nodes of type Node.
// The child nodes are stored in a member variable:
//
//    Node m_children[2];
//
// and the parent node is stored in a member variable:
//
//    Node m_parent;
template<typename Node>
using default_rootless_splay_tree
  = rootless_splay_tree<default_splay_tree_accessors_with_parent<Node>>;

#include "splay-tree-utils.tcc"