Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/binary_heap_/erase_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 binary_heap_/erase_fn_imps.hpp
    38	 * Contains an implementation class for a binary_heap.
    39	 */
    40	
    41	#ifdef PB_DS_CLASS_C_DEC
    42	
    43	PB_DS_CLASS_T_DEC
    44	void
    45	PB_DS_CLASS_C_DEC::
    46	clear()
    47	{
    48	  for (size_type i = 0; i < m_size; ++i)
    49	    erase_at(m_a_entries, i, s_no_throw_copies_ind);
    50	
    51	  __try
    52	    {
    53	      const size_type new_size = resize_policy::get_new_size_for_arbitrary(0);
    54	      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
    55	      resize_policy::notify_arbitrary(new_size);
    56	      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
    57	      m_actual_size = new_size;
    58	      m_a_entries = new_entries;
    59	    }
    60	  __catch(...)
    61	    { }
    62	
    63	  m_size = 0;
    64	  PB_DS_ASSERT_VALID((*this))
    65	}
    66	
    67	PB_DS_CLASS_T_DEC
    68	void
    69	PB_DS_CLASS_C_DEC::
    70	erase_at(entry_pointer a_entries, size_type i, false_type)
    71	{
    72	  a_entries[i]->~value_type();
    73	  s_value_allocator.deallocate(a_entries[i], 1);
    74	}
    75	
    76	PB_DS_CLASS_T_DEC
    77	void
    78	PB_DS_CLASS_C_DEC::
    79	erase_at(entry_pointer, size_type, true_type)
    80	{ }
    81	
    82	PB_DS_CLASS_T_DEC
    83	inline void
    84	PB_DS_CLASS_C_DEC::
    85	pop()
    86	{
    87	  PB_DS_ASSERT_VALID((*this))
    88	  _GLIBCXX_DEBUG_ASSERT(!empty());
    89	
    90	  pop_heap();
    91	  erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
    92	  resize_for_erase_if_needed();
    93	  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
    94	  --m_size;
    95	
    96	  PB_DS_ASSERT_VALID((*this))
    97	}
    98	
    99	PB_DS_CLASS_T_DEC
   100	template<typename Pred>
   101	typename PB_DS_CLASS_C_DEC::size_type
   102	PB_DS_CLASS_C_DEC::
   103	erase_if(Pred pred)
   104	{
   105	  PB_DS_ASSERT_VALID((*this))
   106	
   107	  typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type
   108	    pred_t;
   109	
   110	  const size_type left = partition(pred_t(pred));
   111	  _GLIBCXX_DEBUG_ASSERT(m_size >= left);
   112	  const size_type ersd = m_size - left;
   113	  for (size_type i = left; i < m_size; ++i)
   114	    erase_at(m_a_entries, i, s_no_throw_copies_ind);
   115	
   116	  __try
   117	    {
   118	      const size_type new_size =
   119		resize_policy::get_new_size_for_arbitrary(left);
   120	
   121	      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
   122	      std::copy(m_a_entries, m_a_entries + left, new_entries);
   123	      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
   124	      m_actual_size = new_size;
   125	      resize_policy::notify_arbitrary(m_actual_size);
   126	    }
   127	  __catch(...)
   128	    { };
   129	
   130	  m_size = left;
   131	  make_heap();
   132	  PB_DS_ASSERT_VALID((*this))
   133	  return ersd;
   134	}
   135	
   136	PB_DS_CLASS_T_DEC
   137	inline void
   138	PB_DS_CLASS_C_DEC::
   139	erase(point_iterator it)
   140	{
   141	  PB_DS_ASSERT_VALID((*this))
   142	  _GLIBCXX_DEBUG_ASSERT(!empty());
   143	
   144	  const size_type fix_pos = it.m_p_e - m_a_entries;
   145	  std::swap(*it.m_p_e, m_a_entries[m_size - 1]);
   146	  erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
   147	  resize_for_erase_if_needed();
   148	
   149	  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   150	  --m_size;
   151	  _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);
   152	
   153	  if (fix_pos != m_size)
   154	    fix(m_a_entries + fix_pos);
   155	
   156	  PB_DS_ASSERT_VALID((*this))
   157	}
   158	
   159	PB_DS_CLASS_T_DEC
   160	inline void
   161	PB_DS_CLASS_C_DEC::
   162	resize_for_erase_if_needed()
   163	{
   164	  if (!resize_policy::resize_needed_for_shrink(m_size))
   165	    return;
   166	
   167	  __try
   168	    {
   169	      const size_type new_size = resize_policy::get_new_size_for_shrink();
   170	      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
   171	      resize_policy::notify_shrink_resize();
   172	
   173	      _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   174	      std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries);
   175	      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
   176	      m_actual_size = new_size;
   177	      m_a_entries = new_entries;
   178	    }
   179	  __catch(...)
   180	    { }
   181	}
   182	
   183	PB_DS_CLASS_T_DEC
   184	template<typename Pred>
   185	typename PB_DS_CLASS_C_DEC::size_type
   186	PB_DS_CLASS_C_DEC::
   187	partition(Pred pred)
   188	{
   189	  size_type left = 0;
   190	  size_type right = m_size - 1;
   191	
   192	  while (right + 1 != left)
   193	    {
   194	      _GLIBCXX_DEBUG_ASSERT(left <= m_size);
   195	
   196	      if (!pred(m_a_entries[left]))
   197		++left;
   198	      else if (pred(m_a_entries[right]))
   199		--right;
   200	      else
   201		{
   202		  _GLIBCXX_DEBUG_ASSERT(left < right);
   203		  std::swap(m_a_entries[left], m_a_entries[right]);
   204		  ++left;
   205		  --right;
   206		}
   207	    }
   208	
   209	  return left;
   210	}
   211	#endif