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 left_child_next_sibling_heap_/erase_fn_imps.hpp
38 * Contains an implementation class for left_child_next_sibling_heap_.
39 */
40
41PB_DS_CLASS_T_DEC
42void
43PB_DS_CLASS_C_DEC::
44clear()
45{
46  clear_imp(m_p_root);
47  _GLIBCXX_DEBUG_ASSERT(m_size == 0);
48  m_p_root = 0;
49}
50
51PB_DS_CLASS_T_DEC
52inline void
53PB_DS_CLASS_C_DEC::
54actual_erase_node(node_pointer p_nd)
55{
56  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
57  --m_size;
58  p_nd->~node();
59  s_node_allocator.deallocate(p_nd, 1);
60}
61
62PB_DS_CLASS_T_DEC
63void
64PB_DS_CLASS_C_DEC::
65clear_imp(node_pointer p_nd)
66{
67  while (p_nd != 0)
68    {
69      clear_imp(p_nd->m_p_l_child);
70      node_pointer p_next = p_nd->m_p_next_sibling;
71      actual_erase_node(p_nd);
72      p_nd = p_next;
73    }
74}
75
76PB_DS_CLASS_T_DEC
77void
78PB_DS_CLASS_C_DEC::
79to_linked_list()
80{
81  PB_DS_ASSERT_VALID((*this))
82  node_pointer p_cur = m_p_root;
83  while (p_cur != 0)
84    if (p_cur->m_p_l_child != 0)
85      {
86	node_pointer p_child_next = p_cur->m_p_l_child->m_p_next_sibling;
87	p_cur->m_p_l_child->m_p_next_sibling = p_cur->m_p_next_sibling;
88	p_cur->m_p_next_sibling = p_cur->m_p_l_child;
89	p_cur->m_p_l_child = p_child_next;
90      }
91    else
92      p_cur = p_cur->m_p_next_sibling;
93
94#ifdef _GLIBCXX_DEBUG
95  node_const_pointer p_counter = m_p_root;
96  size_type count = 0;
97  while (p_counter != 0)
98    {
99      ++count;
100      _GLIBCXX_DEBUG_ASSERT(p_counter->m_p_l_child == 0);
101      p_counter = p_counter->m_p_next_sibling;
102    }
103  _GLIBCXX_DEBUG_ASSERT(count == m_size);
104#endif
105}
106
107PB_DS_CLASS_T_DEC
108template<typename Pred>
109typename PB_DS_CLASS_C_DEC::node_pointer
110PB_DS_CLASS_C_DEC::
111prune(Pred pred)
112{
113  node_pointer p_cur = m_p_root;
114  m_p_root = 0;
115  node_pointer p_out = 0;
116  while (p_cur != 0)
117    {
118      node_pointer p_next = p_cur->m_p_next_sibling;
119      if (pred(p_cur->m_value))
120        {
121	  p_cur->m_p_next_sibling = p_out;
122	  if (p_out != 0)
123	    p_out->m_p_prev_or_parent = p_cur;
124	  p_out = p_cur;
125        }
126      else
127        {
128	  p_cur->m_p_next_sibling = m_p_root;
129	  if (m_p_root != 0)
130	    m_p_root->m_p_prev_or_parent = p_cur;
131	  m_p_root = p_cur;
132        }
133      p_cur = p_next;
134    }
135  return p_out;
136}
137
138PB_DS_CLASS_T_DEC
139void
140PB_DS_CLASS_C_DEC::
141bubble_to_top(node_pointer p_nd)
142{
143  node_pointer p_parent = parent(p_nd);
144  while (p_parent != 0)
145    {
146      swap_with_parent(p_nd, p_parent);
147      p_parent = parent(p_nd);
148    }
149}
150
151