URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc4/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [detail/] [binary_heap_/] [binary_heap_.hpp] - Blame information for rev 519

Details | Compare with Previous | View Log


// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
 * @file binary_heap_.hpp
 * Contains an implementation class for a binary heap.
 */
 
#ifndef PB_DS_BINARY_HEAP_HPP
#define PB_DS_BINARY_HEAP_HPP
 
/*
 * Based on CLRS.
 */
 
#include <queue>
#include <algorithm>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>
#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>
#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>
#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp>
#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>
#ifdef PB_DS_BINARY_HEAP_TRACE_
#include <iostream>
#endif
#include <ext/pb_ds/detail/type_utils.hpp>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Value_Type, class Cmp_Fn, class Allocator>
 
#define PB_DS_CLASS_C_DEC \
    binary_heap_<Value_Type, Cmp_Fn, Allocator>
 
#define PB_DS_ENTRY_CMP_DEC \
    entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type
 
#define PB_DS_RESIZE_POLICY_DEC \
    __gnu_pbds::detail::resize_policy<typename Allocator::size_type>
 
    /**
     * class description = "Base class for some types of h3ap$">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class binary_heap_ : public PB_DS_ENTRY_CMP_DEC,
                         public PB_DS_RESIZE_POLICY_DEC
    {
 
    private:
      enum
        {
          simple_value = is_simple<Value_Type>::value
        };
 
      typedef integral_constant<int, simple_value> no_throw_copies_t;
 
      typedef
      typename Allocator::template rebind<
        Value_Type>::other
      value_allocator;
 
      typedef
      typename __conditional_type<
        simple_value,
        Value_Type,
        typename value_allocator::pointer>::__type
      entry;
 
      typedef
      typename Allocator::template rebind<
        entry>::other
      entry_allocator;
 
      typedef typename entry_allocator::pointer entry_pointer;
 
      typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;
 
      typedef PB_DS_RESIZE_POLICY_DEC resize_policy;
 
      typedef
      cond_dealtor<
        Value_Type,
        Allocator>
      cond_dealtor_t;
 
    public:
 
      typedef typename Allocator::size_type size_type;
 
      typedef typename Allocator::difference_type difference_type;
 
      typedef Value_Type value_type;
 
      typedef
      typename Allocator::template rebind<
        value_type>::other::pointer
      pointer;
 
      typedef
      typename Allocator::template rebind<
        value_type>::other::const_pointer
      const_pointer;
 
      typedef
      typename Allocator::template rebind<
        value_type>::other::reference
      reference;
 
      typedef
      typename Allocator::template rebind<
        value_type>::other::const_reference
      const_reference;
 
      typedef
      binary_heap_const_point_iterator_<
        value_type,
        entry,
        simple_value,
        Allocator>
      const_point_iterator;
 
      typedef const_point_iterator point_iterator;
 
      typedef
      binary_heap_const_iterator_<
        value_type,
        entry,
        simple_value,
        Allocator>
      const_iterator;
 
      typedef const_iterator iterator;
 
      typedef Cmp_Fn cmp_fn;
 
      typedef Allocator allocator_type;
 
    public:
 
      binary_heap_();
 
      binary_heap_(const Cmp_Fn& r_cmp_fn);
 
      binary_heap_(const PB_DS_CLASS_C_DEC& other);
 
      void
      swap(PB_DS_CLASS_C_DEC& other);
 
      ~binary_heap_();
 
      inline bool
      empty() const;
 
      inline size_type
      size() const;
 
      inline size_type
      max_size() const;
 
      Cmp_Fn&
      get_cmp_fn();
 
      const Cmp_Fn&
      get_cmp_fn() const;
 
      inline point_iterator
      push(const_reference r_val);
 
      void
      modify(point_iterator it, const_reference r_new_val);
 
      inline const_reference
      top() const;
 
      inline void
      pop();
 
      inline void
      erase(point_iterator it);
 
      template<typename Pred>
      typename PB_DS_CLASS_C_DEC::size_type
      erase_if(Pred pred);
 
      inline static void
      erase_at(entry_pointer a_entries, size_type size, false_type);
 
      inline static void
      erase_at(entry_pointer a_entries, size_type size, true_type);
 
      inline iterator
      begin();
 
      inline const_iterator
      begin() const;
 
      inline iterator
      end();
 
      inline const_iterator
      end() const;
 
      void
      clear();
 
      template<typename Pred>
      void
      split(Pred pred, PB_DS_CLASS_C_DEC& other);
 
      void
      join(PB_DS_CLASS_C_DEC& other);
 
#ifdef PB_DS_BINARY_HEAP_TRACE_
      void
      trace() const;
#endif 
 
    protected:
 
      template<typename It>
      void
      copy_from_range(It first_it, It last_it);
 
    private:
 
      void
      value_swap(PB_DS_CLASS_C_DEC& other);
 
      inline void
      insert_value(const_reference r_val, false_type);
 
      inline void
      insert_value(value_type val, true_type);
 
      inline void
      insert_entry(entry e);
 
      inline void
      resize_for_insert_if_needed();
 
      inline void
      swap_value_imp(entry_pointer p_e, value_type new_val, true_type);
 
      inline void
      swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type);
 
      void
      fix(entry_pointer p_e);
 
      inline const_reference
      top_imp(true_type) const;
 
      inline const_reference
      top_imp(false_type) const;
 
      inline static size_type
      left_child(size_type i);
 
      inline static size_type
      right_child(size_type i);
 
      inline static size_type
      parent(size_type i);
 
      inline void
      resize_for_erase_if_needed();
 
      template<typename Pred>
      size_type
      partition(Pred pred);
 
#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif 
 
#ifdef PB_DS_BINARY_HEAP_TRACE_
      void
      trace_entry(const entry& r_e, false_type) const;
 
      void
      trace_entry(const entry& r_e, true_type) const;
#endif 
 
    private:
      static entry_allocator s_entry_allocator;
 
      static value_allocator s_value_allocator;
 
      static no_throw_copies_t s_no_throw_copies_ind;
 
      size_type m_size;
 
      size_type m_actual_size;
 
      entry_pointer m_a_entries;
    };
 
#include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp>
 
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_ENTRY_CMP_DEC
#undef PB_DS_RESIZE_POLICY_DEC
 
  } // namespace detail
} // namespace __gnu_pbds
 
#endif 

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc4/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [detail/] [binary_heap_/] [binary_heap_.hpp] - Blame information for rev 519

Line No.	Rev	Author	Line
1	424	jeremybenn	`// -- C++ --`
2
3			`// Copyright (C) 2005, 2006, 2009 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_.hpp`
38			`* Contains an implementation class for a binary heap.`
39			`*/`
40
41			`#ifndef PB_DS_BINARY_HEAP_HPP`
42			`#define PB_DS_BINARY_HEAP_HPP`
43
44			`/*`
45			`* Based on CLRS.`
46			`*/`
47
48			`#include <queue>`
49			`#include <algorithm>`
50			`#include <ext/pb_ds/detail/cond_dealtor.hpp>`
51			`#include <ext/pb_ds/detail/cond_dealtor.hpp>`
52			`#include <ext/pb_ds/detail/type_utils.hpp>`
53			`#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>`
54			`#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>`
55			`#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>`
56			`#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp>`
57			`#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>`
58			`#ifdef PB_DS_BINARY_HEAP_TRACE_`
59			`#include <iostream>`
60			`#endif`
61			`#include <ext/pb_ds/detail/type_utils.hpp>`
62			`#include <debug/debug.h>`
63
64			`namespace __gnu_pbds`
65			`{`
66			`namespace detail`
67			`{`
68			`#define PB_DS_CLASS_T_DEC \`
69			`template<typename Value_Type, class Cmp_Fn, class Allocator>`
70
71			`#define PB_DS_CLASS_C_DEC \`
72			`binary_heap_<Value_Type, Cmp_Fn, Allocator>`
73
74			`#define PB_DS_ENTRY_CMP_DEC \`
75			`entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type`
76
77			`#define PB_DS_RESIZE_POLICY_DEC \`
78			`__gnu_pbds::detail::resize_policy<typename Allocator::size_type>`
79
80			`/**`
81			`* class description = "Base class for some types of h3ap$">`
82			`**/`
83			`template<typename Value_Type, class Cmp_Fn, class Allocator>`
84			`class binary_heap_ : public PB_DS_ENTRY_CMP_DEC,`
85			`public PB_DS_RESIZE_POLICY_DEC`
86			`{`
87
88			`private:`
89			`enum`
90			`{`
91			`simple_value = is_simple<Value_Type>::value`
92			`};`
93
94			`typedef integral_constant<int, simple_value> no_throw_copies_t;`
95
96			`typedef`
97			`typename Allocator::template rebind<`
98			`Value_Type>::other`
99			`value_allocator;`
100
101			`typedef`
102			`typename __conditional_type<`
103			`simple_value,`
104			`Value_Type,`
105			`typename value_allocator::pointer>::__type`
106			`entry;`
107
108			`typedef`
109			`typename Allocator::template rebind<`
110			`entry>::other`
111			`entry_allocator;`
112
113			`typedef typename entry_allocator::pointer entry_pointer;`
114
115			`typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;`
116
117			`typedef PB_DS_RESIZE_POLICY_DEC resize_policy;`
118
119			`typedef`
120			`cond_dealtor<`
121			`Value_Type,`
122			`Allocator>`
123			`cond_dealtor_t;`
124
125			`public:`
126
127			`typedef typename Allocator::size_type size_type;`
128
129			`typedef typename Allocator::difference_type difference_type;`
130
131			`typedef Value_Type value_type;`
132
133			`typedef`
134			`typename Allocator::template rebind<`
135			`value_type>::other::pointer`
136			`pointer;`
137
138			`typedef`
139			`typename Allocator::template rebind<`
140			`value_type>::other::const_pointer`
141			`const_pointer;`
142
143			`typedef`
144			`typename Allocator::template rebind<`
145			`value_type>::other::reference`
146			`reference;`
147
148			`typedef`
149			`typename Allocator::template rebind<`
150			`value_type>::other::const_reference`
151			`const_reference;`
152
153			`typedef`
154			`binary_heap_const_point_iterator_<`
155			`value_type,`
156			`entry,`
157			`simple_value,`
158			`Allocator>`
159			`const_point_iterator;`
160
161			`typedef const_point_iterator point_iterator;`
162
163			`typedef`
164			`binary_heap_const_iterator_<`
165			`value_type,`
166			`entry,`
167			`simple_value,`
168			`Allocator>`
169			`const_iterator;`
170
171			`typedef const_iterator iterator;`
172
173			`typedef Cmp_Fn cmp_fn;`
174
175			`typedef Allocator allocator_type;`
176
177			`public:`
178
179			`binary_heap_();`
180
181			`binary_heap_(const Cmp_Fn& r_cmp_fn);`
182
183			`binary_heap_(const PB_DS_CLASS_C_DEC& other);`
184
185			`void`
186			`swap(PB_DS_CLASS_C_DEC& other);`
187
188			`~binary_heap_();`
189
190			`inline bool`
191			`empty() const;`
192
193			`inline size_type`
194			`size() const;`
195
196			`inline size_type`
197			`max_size() const;`
198
199			`Cmp_Fn&`
200			`get_cmp_fn();`
201
202			`const Cmp_Fn&`
203			`get_cmp_fn() const;`
204
205			`inline point_iterator`
206			`push(const_reference r_val);`
207
208			`void`
209			`modify(point_iterator it, const_reference r_new_val);`
210
211			`inline const_reference`
212			`top() const;`
213
214			`inline void`
215			`pop();`
216
217			`inline void`
218			`erase(point_iterator it);`
219
220			`template<typename Pred>`
221			`typename PB_DS_CLASS_C_DEC::size_type`
222			`erase_if(Pred pred);`
223
224			`inline static void`
225			`erase_at(entry_pointer a_entries, size_type size, false_type);`
226
227			`inline static void`
228			`erase_at(entry_pointer a_entries, size_type size, true_type);`
229
230			`inline iterator`
231			`begin();`
232
233			`inline const_iterator`
234			`begin() const;`
235
236			`inline iterator`
237			`end();`
238
239			`inline const_iterator`
240			`end() const;`
241
242			`void`
243			`clear();`
244
245			`template<typename Pred>`
246			`void`
247			`split(Pred pred, PB_DS_CLASS_C_DEC& other);`
248
249			`void`
250			`join(PB_DS_CLASS_C_DEC& other);`
251
252			`#ifdef PB_DS_BINARY_HEAP_TRACE_`
253			`void`
254			`trace() const;`
255			`#endif`
256
257			`protected:`
258
259			`template<typename It>`
260			`void`
261			`copy_from_range(It first_it, It last_it);`
262
263			`private:`
264
265			`void`
266			`value_swap(PB_DS_CLASS_C_DEC& other);`
267
268			`inline void`
269			`insert_value(const_reference r_val, false_type);`
270
271			`inline void`
272			`insert_value(value_type val, true_type);`
273
274			`inline void`
275			`insert_entry(entry e);`
276
277			`inline void`
278			`resize_for_insert_if_needed();`
279
280			`inline void`
281			`swap_value_imp(entry_pointer p_e, value_type new_val, true_type);`
282
283			`inline void`
284			`swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type);`
285
286			`void`
287			`fix(entry_pointer p_e);`
288
289			`inline const_reference`
290			`top_imp(true_type) const;`
291
292			`inline const_reference`
293			`top_imp(false_type) const;`
294
295			`inline static size_type`
296			`left_child(size_type i);`
297
298			`inline static size_type`
299			`right_child(size_type i);`
300
301			`inline static size_type`
302			`parent(size_type i);`
303
304			`inline void`
305			`resize_for_erase_if_needed();`
306
307			`template<typename Pred>`
308			`size_type`
309			`partition(Pred pred);`
310
311			`#ifdef _GLIBCXX_DEBUG`
312			`void`
313			`assert_valid() const;`
314			`#endif`
315
316			`#ifdef PB_DS_BINARY_HEAP_TRACE_`
317			`void`
318			`trace_entry(const entry& r_e, false_type) const;`
319
320			`void`
321			`trace_entry(const entry& r_e, true_type) const;`
322			`#endif`
323
324			`private:`
325			`static entry_allocator s_entry_allocator;`
326
327			`static value_allocator s_value_allocator;`
328
329			`static no_throw_copies_t s_no_throw_copies_ind;`
330
331			`size_type m_size;`
332
333			`size_type m_actual_size;`
334
335			`entry_pointer m_a_entries;`
336			`};`
337
338			`#include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp>`
339			`#include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp>`
340			`#include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp>`
341			`#include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp>`
342			`#include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp>`
343			`#include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp>`
344			`#include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp>`
345			`#include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp>`
346			`#include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp>`
347			`#include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp>`
348
349			`#undef PB_DS_CLASS_C_DEC`
350			`#undef PB_DS_CLASS_T_DEC`
351			`#undef PB_DS_ENTRY_CMP_DEC`
352			`#undef PB_DS_RESIZE_POLICY_DEC`
353
354			`} // namespace detail`
355			`} // namespace __gnu_pbds`
356
357			`#endif`