1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file pat_trie_/rotate_fn_imps.hpp
38 * Contains imps for rotating nodes.
39 */
40
41PB_DS_CLASS_T_DEC
42inline void
43PB_DS_CLASS_C_DEC::
44rotate_left(node_pointer p_x)
45{
46  node_pointer p_y = p_x->m_p_right;
47  p_x->m_p_right = p_y->m_p_left;
48
49  if (p_y->m_p_left != 0)
50    p_y->m_p_left->m_p_parent = p_x;
51
52  p_y->m_p_parent = p_x->m_p_parent;
53  if (p_x == m_p_head->m_p_parent)
54    m_p_head->m_p_parent = p_y;
55  else if (p_x == p_x->m_p_parent->m_p_left)
56    p_x->m_p_parent->m_p_left = p_y;
57  else
58    p_x->m_p_parent->m_p_right = p_y;
59
60  p_y->m_p_left = p_x;
61  p_x->m_p_parent = p_y;
62
63  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);)
64  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);)
65
66  apply_update(p_x, (Node_Update*)this);
67  apply_update(p_x->m_p_parent, (Node_Update*)this);
68}
69
70PB_DS_CLASS_T_DEC
71inline void
72PB_DS_CLASS_C_DEC::
73rotate_right(node_pointer p_x)
74{
75  node_pointer p_y = p_x->m_p_left;
76  p_x->m_p_left = p_y->m_p_right;
77
78  if (p_y->m_p_right != 0)
79    p_y->m_p_right->m_p_parent = p_x;
80
81  p_y->m_p_parent = p_x->m_p_parent;
82  if (p_x == m_p_head->m_p_parent)
83    m_p_head->m_p_parent = p_y;
84  else if (p_x == p_x->m_p_parent->m_p_right)
85    p_x->m_p_parent->m_p_right = p_y;
86  else
87    p_x->m_p_parent->m_p_left = p_y;
88
89  p_y->m_p_right = p_x;
90  p_x->m_p_parent = p_y;
91
92  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);)
93  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);)
94
95  apply_update(p_x, (Node_Update*)this);
96  apply_update(p_x->m_p_parent, (Node_Update*)this);
97}
98
99PB_DS_CLASS_T_DEC
100inline void
101PB_DS_CLASS_C_DEC::
102rotate_parent(node_pointer p_nd)
103{
104  node_pointer p_parent = p_nd->m_p_parent;
105  if (p_nd == p_parent->m_p_left)
106    rotate_right(p_parent);
107  else
108    rotate_left(p_parent);
109  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd);
110  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || p_nd->m_p_right == p_parent);
111}
112
113PB_DS_CLASS_T_DEC
114inline void
115PB_DS_CLASS_C_DEC::
116apply_update(node_pointer /*p_nd*/, __gnu_pbds::null_node_update*  /*p_update*/)
117{ }
118
119PB_DS_CLASS_T_DEC
120template<typename Node_Update_>
121inline void
122PB_DS_CLASS_C_DEC::
123apply_update(node_pointer p_nd, Node_Update_* p_update)
124{
125  p_update->operator()(& PB_DS_V2F(p_nd->m_value),(p_nd->m_p_left == 0) ?
126			0 :
127			& PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == 0) ?
128			0 :
129			& PB_DS_V2F(p_nd->m_p_right->m_value));
130}
131
132PB_DS_CLASS_T_DEC
133template<typename Node_Update_>
134inline void
135PB_DS_CLASS_C_DEC::
136update_to_top(node_pointer p_nd, Node_Update_* p_update)
137{
138  while (p_nd != m_p_head)
139    {
140      apply_update(p_nd, p_update);
141      p_nd = p_nd->m_p_parent;
142    }
143}
144
145PB_DS_CLASS_T_DEC
146inline void
147PB_DS_CLASS_C_DEC::
148update_to_top(node_pointer /*p_nd*/, __gnu_pbds::null_node_update*  /*p_update*/)
149{ }
150
151