URL https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk

Subversion Repositories openrisc_2011-10-31

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

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 left_child_next_sibling_heap_.hpp
 * Contains an implementation class for a basic heap.
 */
 
#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
 
/*
 * Based on CLRS.
 */
 
#include <iterator>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp>
#ifdef PB_DS_LC_NS_HEAP_TRACE_
#include <iostream>
#endif 
#include <debug/debug.h>
 
namespace __gnu_pbds
{
  namespace detail
  {
 
#ifdef _GLIBCXX_DEBUG
#define PB_DS_CLASS_T_DEC                                               \
    template<                                                           \
                                                typename Value_Type,    \
                                                class Cmp_Fn,           \
                                                typename Node_Metadata, \
                                                class Allocator,        \
                                                bool Single_Link_Roots>
#else 
#define PB_DS_CLASS_T_DEC                                               \
    template<                                                           \
                                                typename Value_Type,    \
                                                class Cmp_Fn,           \
                                                typename Node_Metadata, \
                                                class Allocator>
#endif 
 
#ifdef _GLIBCXX_DEBUG
#define PB_DS_CLASS_C_DEC                                               \
    left_child_next_sibling_heap_<                                      \
                                                        Value_Type,     \
                                                        Cmp_Fn,         \
                                                        Node_Metadata,  \
                                                        Allocator,      \
                                                        Single_Link_Roots>
#else 
#define PB_DS_CLASS_C_DEC                                               \
    left_child_next_sibling_heap_<                                      \
                                                        Value_Type,     \
                                                        Cmp_Fn,         \
                                                        Node_Metadata,  \
                                                        Allocator>
#endif 
 
    /**
     * class description = "Base class for some types of h3ap$">
     **/
#ifdef _GLIBCXX_DEBUG
    template<typename Value_Type,
             class Cmp_Fn,
             typename Node_Metadata,
             class Allocator,
             bool Single_Link_Roots>
#else 
    template<typename Value_Type,
             class Cmp_Fn,
             typename Node_Metadata,
             class Allocator>
#endif 
    class left_child_next_sibling_heap_ : public Cmp_Fn
    {
 
    protected:
      typedef
      typename Allocator::template rebind<
      left_child_next_sibling_heap_node_<
      Value_Type,
      Node_Metadata,
      Allocator> >::other
      node_allocator;
 
      typedef typename node_allocator::value_type node;
 
      typedef typename node_allocator::pointer node_pointer;
 
      typedef typename node_allocator::const_pointer const_node_pointer;
 
      typedef Node_Metadata node_metadata;
 
      typedef std::pair< node_pointer, node_pointer> node_pointer_pair;
 
    private:
      typedef cond_dealtor< node, Allocator> cond_dealtor_t;
 
      enum
        {
          simple_value = is_simple<Value_Type>::value
        };
 
      typedef integral_constant<int, simple_value> no_throw_copies_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
      left_child_next_sibling_heap_node_const_point_iterator_<
        node,
        Allocator>
      const_point_iterator;
 
      typedef const_point_iterator point_iterator;
 
      typedef
      left_child_next_sibling_heap_const_iterator_<
        node,
        Allocator>
      const_iterator;
 
      typedef const_iterator iterator;
 
      typedef Cmp_Fn cmp_fn;
 
      typedef Allocator allocator_type;
 
    public:
 
      left_child_next_sibling_heap_();
 
      left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn);
 
      left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other);
 
      void
      swap(PB_DS_CLASS_C_DEC& other);
 
      ~left_child_next_sibling_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 iterator
      begin();
 
      inline const_iterator
      begin() const;
 
      inline iterator
      end();
 
      inline const_iterator
      end() const;
 
      void
      clear();
 
#ifdef PB_DS_LC_NS_HEAP_TRACE_
      void
      trace() const;
#endif 
 
    protected:
 
      inline node_pointer
      get_new_node_for_insert(const_reference r_val);
 
      inline static void
      make_child_of(node_pointer p_nd, node_pointer p_new_parent);
 
      void
      value_swap(PB_DS_CLASS_C_DEC& other);
 
      inline static node_pointer
      parent(node_pointer p_nd);
 
      inline void
      swap_with_parent(node_pointer p_nd, node_pointer p_parent);
 
      void
      bubble_to_top(node_pointer p_nd);
 
      inline void
      actual_erase_node(node_pointer p_nd);
 
      void
      clear_imp(node_pointer p_nd);
 
      void
      to_linked_list();
 
      template<typename Pred>
      node_pointer
      prune(Pred pred);
 
#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
 
      void
      assert_node_consistent(const_node_pointer p_nd, bool single_link) const;
 
      static size_type
      size_under_node(const_node_pointer p_nd);
 
      static size_type
      degree(const_node_pointer p_nd);
#endif 
 
#ifdef PB_DS_LC_NS_HEAP_TRACE_
      static void
      trace_node(const_node_pointer, size_type level);
#endif 
 
    protected:
      node_pointer m_p_root;
 
      size_type m_size;
 
    private:
#ifdef _GLIBCXX_DEBUG
      void
      assert_iterators() const;
 
      void
      assert_size() const;
 
      static size_type
      size_from_node(const_node_pointer p_nd);
#endif 
 
      node_pointer
      recursive_copy_node(const_node_pointer p_nd);
 
      inline node_pointer
      get_new_node_for_insert(const_reference r_val, false_type);
 
      inline node_pointer
      get_new_node_for_insert(const_reference r_val, true_type);
 
#ifdef PB_DS_LC_NS_HEAP_TRACE_
      template<typename Metadata_>
      static void
      trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);
 
      static void
      trace_node_metadata(const_node_pointer, type_to_type<null_left_child_next_sibling_heap_node_metadata>);
#endif 
 
    private:
      static node_allocator s_node_allocator;
 
      static no_throw_copies_t s_no_throw_copies_ind;
    };
 
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>
 
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
 
  } // namespace detail
} // namespace __gnu_pbds
 
#endif 

Browse

Tools

Subversion Repositories openrisc_2011-10-31

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

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 left_child_next_sibling_heap_.hpp`
38			`* Contains an implementation class for a basic heap.`
39			`*/`
40
41			`#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP`
42			`#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP`
43
44			`/*`
45			`* Based on CLRS.`
46			`*/`
47
48			`#include <iterator>`
49			`#include <ext/pb_ds/detail/cond_dealtor.hpp>`
50			`#include <ext/pb_ds/detail/type_utils.hpp>`
51			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp>`
52			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>`
53			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp>`
54			`#ifdef PB_DS_LC_NS_HEAP_TRACE_`
55			`#include <iostream>`
56			`#endif`
57			`#include <debug/debug.h>`
58
59			`namespace __gnu_pbds`
60			`{`
61			`namespace detail`
62			`{`
63
64			`#ifdef _GLIBCXX_DEBUG`
65			`#define PB_DS_CLASS_T_DEC \`
66			`template< \`
67			`typename Value_Type, \`
68			`class Cmp_Fn, \`
69			`typename Node_Metadata, \`
70			`class Allocator, \`
71			`bool Single_Link_Roots>`
72			`#else`
73			`#define PB_DS_CLASS_T_DEC \`
74			`template< \`
75			`typename Value_Type, \`
76			`class Cmp_Fn, \`
77			`typename Node_Metadata, \`
78			`class Allocator>`
79			`#endif`
80
81			`#ifdef _GLIBCXX_DEBUG`
82			`#define PB_DS_CLASS_C_DEC \`
83			`left_child_next_sibling_heap_< \`
84			`Value_Type, \`
85			`Cmp_Fn, \`
86			`Node_Metadata, \`
87			`Allocator, \`
88			`Single_Link_Roots>`
89			`#else`
90			`#define PB_DS_CLASS_C_DEC \`
91			`left_child_next_sibling_heap_< \`
92			`Value_Type, \`
93			`Cmp_Fn, \`
94			`Node_Metadata, \`
95			`Allocator>`
96			`#endif`
97
98			`/**`
99			`* class description = "Base class for some types of h3ap$">`
100			`**/`
101			`#ifdef _GLIBCXX_DEBUG`
102			`template<typename Value_Type,`
103			`class Cmp_Fn,`
104			`typename Node_Metadata,`
105			`class Allocator,`
106			`bool Single_Link_Roots>`
107			`#else`
108			`template<typename Value_Type,`
109			`class Cmp_Fn,`
110			`typename Node_Metadata,`
111			`class Allocator>`
112			`#endif`
113			`class left_child_next_sibling_heap_ : public Cmp_Fn`
114			`{`
115
116			`protected:`
117			`typedef`
118			`typename Allocator::template rebind<`
119			`left_child_next_sibling_heap_node_<`
120			`Value_Type,`
121			`Node_Metadata,`
122			`Allocator> >::other`
123			`node_allocator;`
124
125			`typedef typename node_allocator::value_type node;`
126
127			`typedef typename node_allocator::pointer node_pointer;`
128
129			`typedef typename node_allocator::const_pointer const_node_pointer;`
130
131			`typedef Node_Metadata node_metadata;`
132
133			`typedef std::pair< node_pointer, node_pointer> node_pointer_pair;`
134
135			`private:`
136			`typedef cond_dealtor< node, Allocator> cond_dealtor_t;`
137
138			`enum`
139			`{`
140			`simple_value = is_simple<Value_Type>::value`
141			`};`
142
143			`typedef integral_constant<int, simple_value> no_throw_copies_t;`
144
145			`public:`
146
147			`typedef typename Allocator::size_type size_type;`
148
149			`typedef typename Allocator::difference_type difference_type;`
150
151			`typedef Value_Type value_type;`
152
153			`typedef`
154			`typename Allocator::template rebind<`
155			`value_type>::other::pointer`
156			`pointer;`
157
158			`typedef`
159			`typename Allocator::template rebind<`
160			`value_type>::other::const_pointer`
161			`const_pointer;`
162
163			`typedef`
164			`typename Allocator::template rebind<`
165			`value_type>::other::reference`
166			`reference;`
167
168			`typedef`
169			`typename Allocator::template rebind<`
170			`value_type>::other::const_reference`
171			`const_reference;`
172
173			`typedef`
174			`left_child_next_sibling_heap_node_const_point_iterator_<`
175			`node,`
176			`Allocator>`
177			`const_point_iterator;`
178
179			`typedef const_point_iterator point_iterator;`
180
181			`typedef`
182			`left_child_next_sibling_heap_const_iterator_<`
183			`node,`
184			`Allocator>`
185			`const_iterator;`
186
187			`typedef const_iterator iterator;`
188
189			`typedef Cmp_Fn cmp_fn;`
190
191			`typedef Allocator allocator_type;`
192
193			`public:`
194
195			`left_child_next_sibling_heap_();`
196
197			`left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn);`
198
199			`left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other);`
200
201			`void`
202			`swap(PB_DS_CLASS_C_DEC& other);`
203
204			`~left_child_next_sibling_heap_();`
205
206			`inline bool`
207			`empty() const;`
208
209			`inline size_type`
210			`size() const;`
211
212			`inline size_type`
213			`max_size() const;`
214
215			`Cmp_Fn&`
216			`get_cmp_fn();`
217
218			`const Cmp_Fn&`
219			`get_cmp_fn() const;`
220
221			`inline iterator`
222			`begin();`
223
224			`inline const_iterator`
225			`begin() const;`
226
227			`inline iterator`
228			`end();`
229
230			`inline const_iterator`
231			`end() const;`
232
233			`void`
234			`clear();`
235
236			`#ifdef PB_DS_LC_NS_HEAP_TRACE_`
237			`void`
238			`trace() const;`
239			`#endif`
240
241			`protected:`
242
243			`inline node_pointer`
244			`get_new_node_for_insert(const_reference r_val);`
245
246			`inline static void`
247			`make_child_of(node_pointer p_nd, node_pointer p_new_parent);`
248
249			`void`
250			`value_swap(PB_DS_CLASS_C_DEC& other);`
251
252			`inline static node_pointer`
253			`parent(node_pointer p_nd);`
254
255			`inline void`
256			`swap_with_parent(node_pointer p_nd, node_pointer p_parent);`
257
258			`void`
259			`bubble_to_top(node_pointer p_nd);`
260
261			`inline void`
262			`actual_erase_node(node_pointer p_nd);`
263
264			`void`
265			`clear_imp(node_pointer p_nd);`
266
267			`void`
268			`to_linked_list();`
269
270			`template<typename Pred>`
271			`node_pointer`
272			`prune(Pred pred);`
273
274			`#ifdef _GLIBCXX_DEBUG`
275			`void`
276			`assert_valid() const;`
277
278			`void`
279			`assert_node_consistent(const_node_pointer p_nd, bool single_link) const;`
280
281			`static size_type`
282			`size_under_node(const_node_pointer p_nd);`
283
284			`static size_type`
285			`degree(const_node_pointer p_nd);`
286			`#endif`
287
288			`#ifdef PB_DS_LC_NS_HEAP_TRACE_`
289			`static void`
290			`trace_node(const_node_pointer, size_type level);`
291			`#endif`
292
293			`protected:`
294			`node_pointer m_p_root;`
295
296			`size_type m_size;`
297
298			`private:`
299			`#ifdef _GLIBCXX_DEBUG`
300			`void`
301			`assert_iterators() const;`
302
303			`void`
304			`assert_size() const;`
305
306			`static size_type`
307			`size_from_node(const_node_pointer p_nd);`
308			`#endif`
309
310			`node_pointer`
311			`recursive_copy_node(const_node_pointer p_nd);`
312
313			`inline node_pointer`
314			`get_new_node_for_insert(const_reference r_val, false_type);`
315
316			`inline node_pointer`
317			`get_new_node_for_insert(const_reference r_val, true_type);`
318
319			`#ifdef PB_DS_LC_NS_HEAP_TRACE_`
320			`template<typename Metadata_>`
321			`static void`
322			`trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);`
323
324			`static void`
325			`trace_node_metadata(const_node_pointer, type_to_type<null_left_child_next_sibling_heap_node_metadata>);`
326			`#endif`
327
328			`private:`
329			`static node_allocator s_node_allocator;`
330
331			`static no_throw_copies_t s_no_throw_copies_ind;`
332			`};`
333
334			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>`
335			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>`
336			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>`
337			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>`
338			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>`
339			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>`
340			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>`
341			`#include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>`
342
343			`#undef PB_DS_CLASS_C_DEC`
344			`#undef PB_DS_CLASS_T_DEC`
345
346			`} // namespace detail`
347			`} // namespace __gnu_pbds`
348
349			`#endif`