| // 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" |