diff options
Diffstat (limited to 'gcc/splay-tree-utils.tcc')
| -rw-r--r-- | gcc/splay-tree-utils.tcc | 69 |
1 files changed, 63 insertions, 6 deletions
diff --git a/gcc/splay-tree-utils.tcc b/gcc/splay-tree-utils.tcc index 5c36bb5..6118233 100644 --- a/gcc/splay-tree-utils.tcc +++ b/gcc/splay-tree-utils.tcc @@ -340,18 +340,33 @@ rooted_splay_tree<Accessors>::insert (node_type new_node, Comparator compare) if (comparison == 0) return false; - // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT - // otherwise. - set_child (new_node, comparison < 0, m_root); - set_child (new_node, comparison > 0, get_child (m_root, comparison > 0)); - set_child (m_root, comparison > 0, nullptr); - m_root = new_node; + insert_relative (comparison, new_node); return true; } // See the comment above the declaration. template<typename Accessors> inline void +rooted_splay_tree<Accessors>::insert_relative (int comparison, + node_type new_node) +{ + gcc_checking_assert (!get_child (new_node, 0) + && !get_child (new_node, 1) + && (!m_root || comparison != 0)); + if (m_root) + { + // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT + // otherwise. + set_child (new_node, comparison < 0, m_root); + set_child (new_node, comparison > 0, get_child (m_root, comparison > 0)); + set_child (m_root, comparison > 0, node_type ()); + } + m_root = new_node; +} + +// See the comment above the declaration. +template<typename Accessors> +inline void rooted_splay_tree<Accessors>::insert_max_node (node_type new_node) { gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1)); @@ -400,6 +415,35 @@ rooted_splay_tree<Accessors>::remove_root () // See the comment above the declaration. template<typename Accessors> +inline bool +rooted_splay_tree<Accessors>::remove_root_and_splay_next () +{ + node_type node = m_root; + node_type right = get_child (node, 1); + if (right) + { + // Bring the minimum right-hand node to the root. + if (get_child (right, 0)) + { + right = parent::template splay_limit<0> (right); + gcc_checking_assert (!get_child (right, 0)); + } + set_child (right, 0, get_child (node, 0)); + m_root = right; + } + else + m_root = get_child (node, 0); + if (m_root) + set_parent (m_root, node_type ()); + + // Clear the links from NODE. Its parent is already node_type (). + set_child (node, 0, node_type ()); + set_child (node, 1, node_type ()); + return right; +} + +// See the comment above the declaration. +template<typename Accessors> inline rooted_splay_tree<Accessors> rooted_splay_tree<Accessors>::split_before_root () { @@ -732,6 +776,19 @@ rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller, // See the comment above the declaration. template<typename Accessors> +template<typename LeftPredicate, typename RightPredicate> +int +rooted_splay_tree<Accessors>::lookup_le (LeftPredicate want_something_smaller, + RightPredicate want_something_bigger) +{ + int comparison = lookup (want_something_smaller, want_something_bigger); + if (comparison < 0 && splay_prev_node ()) + comparison = 1; + return comparison; +} + +// See the comment above the declaration. +template<typename Accessors> template<typename Printer> inline void rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const |