The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2005-2021 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_/insert_fn_imps.hpp
    38	 * Contains an implementation class for a base of binomial heaps.
    39	 */
    40	
    41	#ifdef PB_DS_CLASS_C_DEC
    42	
    43	PB_DS_CLASS_T_DEC
    44	inline typename PB_DS_CLASS_C_DEC::point_iterator
    45	PB_DS_CLASS_C_DEC::
    46	push(const_reference r_val)
    47	{
    48	  PB_DS_ASSERT_VALID_COND((*this),true)
    49	  node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
    50	  insert_node(p_nd);
    51	  m_p_max = 0;
    52	  PB_DS_ASSERT_VALID_COND((*this),true)
    53	  return point_iterator(p_nd);
    54	}
    55	
    56	PB_DS_CLASS_T_DEC
    57	inline void
    58	PB_DS_CLASS_C_DEC::
    59	insert_node(node_pointer p_nd)
    60	{
    61	  if (base_type::m_p_root == 0)
    62	    {
    63	      p_nd->m_p_next_sibling = 0;
    64	      p_nd->m_p_prev_or_parent = 0;
    65	      p_nd->m_p_l_child = 0;
    66	      p_nd->m_metadata = 0;
    67	      base_type::m_p_root = p_nd;
    68	      return;
    69	    }
    70	
    71	  if (base_type::m_p_root->m_metadata > 0)
    72	    {
    73	      p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0;
    74	      p_nd->m_p_next_sibling = base_type::m_p_root;
    75	      base_type::m_p_root->m_p_prev_or_parent = p_nd;
    76	      base_type::m_p_root = p_nd;
    77	      p_nd->m_metadata = 0;
    78	      return;
    79	    }
    80	
    81	  if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value))
    82	    {
    83	      p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling;
    84	      p_nd->m_p_prev_or_parent = 0;
    85	      p_nd->m_metadata = 1;
    86	      p_nd->m_p_l_child = base_type::m_p_root;
    87	      base_type::m_p_root->m_p_prev_or_parent = p_nd;
    88	      base_type::m_p_root->m_p_next_sibling = 0;
    89	      base_type::m_p_root = p_nd;
    90	    }
    91	  else
    92	    {
    93	      p_nd->m_p_next_sibling = 0;
    94	      p_nd->m_p_l_child = 0;
    95	      p_nd->m_p_prev_or_parent = base_type::m_p_root;
    96	      p_nd->m_metadata = 0;
    97	      _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0);
    98	      base_type::m_p_root->m_p_l_child = p_nd;
    99	      base_type::m_p_root->m_metadata = 1;
   100	    }
   101	
   102	  base_type::m_p_root = fix(base_type::m_p_root);
   103	}
   104	
   105	PB_DS_CLASS_T_DEC
   106	inline typename PB_DS_CLASS_C_DEC::node_pointer
   107	PB_DS_CLASS_C_DEC::
   108	fix(node_pointer p_nd) const
   109	{
   110	  while (p_nd->m_p_next_sibling != 0 &&
   111		 p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata)
   112	    {
   113	      node_pointer p_next = p_nd->m_p_next_sibling;
   114	      if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
   115		{
   116		  p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
   117	
   118		  if (p_nd->m_p_prev_or_parent != 0)
   119		    p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next;
   120	
   121		  base_type::make_child_of(p_nd, p_next);
   122		  ++p_next->m_metadata;
   123		  p_nd = p_next;
   124		}
   125	      else
   126		{
   127		  p_nd->m_p_next_sibling = p_next->m_p_next_sibling;
   128	
   129		  if (p_nd->m_p_next_sibling != 0)
   130		    p_next->m_p_next_sibling = 0;
   131	
   132		  base_type::make_child_of(p_next, p_nd);
   133		  ++p_nd->m_metadata;
   134		}
   135	    }
   136	
   137	  if (p_nd->m_p_next_sibling != 0)
   138	    p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd;
   139	
   140	  return p_nd;
   141	}
   142	
   143	PB_DS_CLASS_T_DEC
   144	void
   145	PB_DS_CLASS_C_DEC::
   146	modify(point_iterator it, const_reference r_new_val)
   147	{
   148	  PB_DS_ASSERT_VALID_COND((*this),true)
   149	  node_pointer p_nd = it.m_p_nd;
   150	
   151	  _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
   152	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd, false)
   153	
   154	  const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val);
   155	  p_nd->m_value = r_new_val;
   156	
   157	  if (bubble_up)
   158	    {
   159	      node_pointer p_parent = base_type::parent(p_nd);
   160	      while (p_parent != 0 &&
   161		     Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value))
   162		{
   163		  base_type::swap_with_parent(p_nd, p_parent);
   164		  p_parent = base_type::parent(p_nd);
   165		}
   166	
   167	      if (p_nd->m_p_prev_or_parent == 0)
   168		base_type::m_p_root = p_nd;
   169	
   170	      m_p_max = 0;
   171	      PB_DS_ASSERT_VALID_COND((*this),true)
   172	      return;
   173	    }
   174	
   175	  base_type::bubble_to_top(p_nd);
   176	  remove_parentless_node(p_nd);
   177	  insert_node(p_nd);
   178	  m_p_max = 0;
   179	  PB_DS_ASSERT_VALID_COND((*this),true)
   180	}
   181	#endif