1// -*- C++ -*-
2
3// Copyright (C) 2005-2020 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 binomial_heap_base_/split_join_fn_imps.hpp
38 * Contains an implementation class for a base of binomial heaps.
39 */
40
41#ifdef PB_DS_CLASS_C_DEC
42
43PB_DS_CLASS_T_DEC
44template<typename Pred>
45void
46PB_DS_CLASS_C_DEC::
47split(Pred pred, PB_DS_CLASS_C_DEC& other)
48{
49  PB_DS_ASSERT_VALID_COND((*this),true)
50  PB_DS_ASSERT_VALID_COND(other,true)
51
52  other.clear();
53  if (base_type::empty())
54    {
55      PB_DS_ASSERT_VALID_COND((*this),true)
56      PB_DS_ASSERT_VALID_COND(other,true)
57      return;
58    }
59
60  base_type::to_linked_list();
61  node_pointer p_out = base_type::prune(pred);
62  while (p_out != 0)
63    {
64      _GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0);
65      --base_type::m_size;
66      ++other.m_size;
67
68      node_pointer p_next = p_out->m_p_next_sibling;
69      p_out->m_p_l_child = p_out->m_p_prev_or_parent = 0;
70      p_out->m_metadata = 0;
71
72      p_out->m_p_next_sibling = other.m_p_root;
73      if (other.m_p_root != 0)
74	other.m_p_root->m_p_prev_or_parent = p_out;
75
76      other.m_p_root = p_out;
77      other.m_p_root = other.fix(other.m_p_root);
78      p_out = p_next;
79    }
80
81  PB_DS_ASSERT_VALID_COND(other,true)
82  node_pointer p_cur = base_type::m_p_root;
83  base_type::m_p_root = 0;
84
85  while (p_cur != 0)
86    {
87      node_pointer p_next = p_cur->m_p_next_sibling;
88      p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = 0;
89      p_cur->m_metadata = 0;
90      p_cur->m_p_next_sibling = base_type::m_p_root;
91
92      if (base_type::m_p_root != 0)
93	base_type::m_p_root->m_p_prev_or_parent = p_cur;
94
95      base_type::m_p_root = p_cur;
96      base_type::m_p_root = fix(base_type::m_p_root);
97      p_cur = p_next;
98    }
99
100  m_p_max = 0;
101  PB_DS_ASSERT_VALID_COND((*this),true)
102  PB_DS_ASSERT_VALID_COND(other,true)
103}
104
105PB_DS_CLASS_T_DEC
106inline void
107PB_DS_CLASS_C_DEC::
108join(PB_DS_CLASS_C_DEC& other)
109{
110  PB_DS_ASSERT_VALID_COND((*this),true)
111  PB_DS_ASSERT_VALID_COND(other,true)
112
113  node_pointer p_other = other.m_p_root;
114  if (p_other != 0)
115    do
116      {
117	node_pointer p_next = p_other->m_p_next_sibling;
118	std::swap(p_other->m_p_next_sibling, p_other->m_p_prev_or_parent);
119	p_other = p_next;
120      }
121    while (p_other != 0);
122
123  base_type::m_p_root = join(base_type::m_p_root, other.m_p_root);
124  base_type::m_size += other.m_size;
125  m_p_max = 0;
126
127  other.m_p_root = 0;
128  other.m_size = 0;
129  other.m_p_max = 0;
130
131  PB_DS_ASSERT_VALID_COND((*this),true)
132  PB_DS_ASSERT_VALID_COND(other,true)
133}
134
135PB_DS_CLASS_T_DEC
136inline typename PB_DS_CLASS_C_DEC::node_pointer
137PB_DS_CLASS_C_DEC::
138join(node_pointer p_lhs, node_pointer p_rhs) const
139{
140  node_pointer p_ret = 0;
141  node_pointer p_cur = 0;
142
143  while (p_lhs != 0 || p_rhs != 0)
144    {
145      if (p_rhs == 0)
146	{
147	  if (p_cur == 0)
148	    p_ret = p_cur = p_lhs;
149	  else
150	    {
151	      p_cur->m_p_next_sibling = p_lhs;
152	      p_lhs->m_p_prev_or_parent = p_cur;
153	    }
154	  p_cur = p_lhs = 0;
155	}
156      else if (p_lhs == 0 || p_rhs->m_metadata < p_lhs->m_metadata)
157	{
158	  if (p_cur == 0)
159	    {
160	      p_ret = p_cur = p_rhs;
161	      p_rhs = p_rhs->m_p_prev_or_parent;
162	    }
163	  else
164	    {
165	      p_cur->m_p_next_sibling = p_rhs;
166	      p_rhs = p_rhs->m_p_prev_or_parent;
167	      p_cur->m_p_next_sibling->m_p_prev_or_parent = p_cur;
168	      p_cur = p_cur->m_p_next_sibling;
169	    }
170	}
171      else if (p_lhs->m_metadata < p_rhs->m_metadata)
172	{
173	  if (p_cur == 0)
174	    p_ret = p_cur = p_lhs;
175	  else
176	    {
177	      p_cur->m_p_next_sibling = p_lhs;
178	      p_lhs->m_p_prev_or_parent = p_cur;
179	      p_cur = p_cur->m_p_next_sibling;
180	    }
181	  p_lhs = p_cur->m_p_next_sibling;
182	}
183      else
184	{
185	  node_pointer p_next_rhs = p_rhs->m_p_prev_or_parent;
186	  p_rhs->m_p_next_sibling = p_lhs;
187	  p_lhs = fix(p_rhs);
188	  p_rhs = p_next_rhs;
189	}
190    }
191
192  if (p_cur != 0)
193    p_cur->m_p_next_sibling = 0;
194
195  if (p_ret != 0)
196    p_ret->m_p_prev_or_parent = 0;
197
198  return p_ret;
199}
200#endif
201