1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
<HTML><HEAD>
<!!---------------------------------------------------------------------->
<!! Copyright (C) 1999 Dietmar Kuehl, Claas Solutions GmbH >
<!!>
<!! Permission to use, copy, modify, distribute and sell this >
<!! software for any purpose 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. Dietmar Kuehl and Claas Solutions make no >
<!! representations about the suitability of this software for any >
<!! purpose. It is provided "as is" without express or implied warranty. >
<!!---------------------------------------------------------------------->
<TITLE>d_heap.3</TITLE>
</HEAD>
<BODY BGCOLOR=white LINK="0000FF" VLINK="800080">
<IMG SRC=../../c++boost.gif ALIGN=TOP WIDTH=277 HEIGHT=86><BR>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=109 VALIGN=TOP><IMG SRC=sidebar.jpg WIDTH=109 HEIGHT=494>
</TD><TD>
<SPACER TYPE=VERTICAL SIZE=40>
<H1> Template Class <nobr><tt>d_heap<T, Comp, d></tt></nobr></H1>
<A NAME="Synopsis"><H1>Synopsis</H1></A>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=30 VALIGN=TOP></TD><TD>
<PRE>
#include "boost/d_heap.hpp"
template <typename T>
class boost::d_heap_base
{
public:
class const_iterator
{
public:
const_iterator();
T const& operator* () const;
T const* operator-> () const;
const_iterator& operator++ ();
const_iterator operator++ (int);
bool operator== (const_iterator const& it) const;
bool operator!= (const_iterator const& it) const;
};
d_heap_base();
const_reference <A HREF="heap-common.html#top">top</A>() const;
bool <A HREF="heap-common.html#empty">empty</A>() const;
size_type <A HREF="heap-common.html#size">size</A>() const;
const_iterator <A HREF="heap-common.html#begin">begin</A>() const;
const_iterator <A HREF="heap-common.html#end">end</A>() const;
protected:
~d_heap_base();
};
template <typename T, typename Comp = std::less<T>, int d = 2>
class boost::d_heap: public boost::d_heap_base<T>
{
public:
typedef T <A HREF="heap-common.html#value_type">value_type</A>;
typedef T& reference;
typedef T const& <A HREF="heap-common.html#const_reference">const_reference</A>;
typedef typename d_heap<T>::const_iterator <A HREF="heap-common.html#const_iterator">const_iterator</A>;
typedef typename std::list<node>::size_type <A HREF="heap-common.html#size_type">size_type</A>;
typedef Comp <A HREF="heap-common.html#compare_type">compare_type</A>;
explicit <A HREF="heap-common.html#default-ctor">d_heap</A>(Comp const& comp = Comp());
pointer <A HREF="heap-common.html#push">push</A>(const_reference val);
void <A HREF="heap-common.html#pop">pop</A>();
void <A HREF="heap-common.html#remove">remove</A>(pointer ptr);
template <typename K> void <A HREF="heap-common.html#change_top">change_top</A>(K const& val);
template <typename K> void <A HREF="heap-common.html#change">change</A>(pointer ptr, K const& val
template <typename K> void <A HREF="heap-common.html#decrease">decrease</A>(pointer ptr, K const& val);
template <typename K> void <A HREF="heap-common.html#increase">increase</A>(pointer ptr, K const& val);
};
</PRE></TD></TABLE>
<A NAME="Description"><H1>Description</H1></A>
The class <nobr><tt>d_heap<T, Comp, d></tt></nobr> represents the heap as a
balanced d-ary tree. Normally <nobr><tt>d == 2</tt></nobr> is used in which case
a binary tree is used to represent the heap. Internally, the tree is
represented as an array and the navigation in the tree is made using
simple index calculations. The type of objects stored in the heap is
<nobr><tt>T</tt></nobr> which are compared using the comparator type <nobr><tt>Comp</tt></nobr>.
During the heap manipulations the invariant is temporarily violated
and then restored by swapping the violating node appropriately with
its parent or its largest child depending on the whether the node has
to travel up or down, respectively. Note, that the swapped objects
are just pointers to the actual elements. Thus, even if copying and/or
assigning objects of type <nobr><tt>T</tt></nobr> is a relatively expensive operation,
the swaps performed to maintain the invariant are not.
<P>
The class <nobr><tt>d_heap_base<T></tt></nobr> is used to factor out all portions
of the code which are independent from the compare type and the
number of child nodes. This class is intended to be used only by
<nobr><tt>d_heap<T, Comp, d></tt></nobr> and is not intended to be used as generally
useful base class. Of course, you can use all public members defined
for <nobr><tt>d_heap_base<T></tt></nobr> on <nobr><tt>d_heap<T, Comp, d></tt></nobr> objects.
<P>
For a description of the methods of <nobr><tt>d_heap<T, Comp, d></tt></nobr> please
refer to the general description on the page describing <A HREF="heap.html">heaps</A>
and the page describing the <A HREF="heap-common.html">common methods</A>.
<A NAME="See Also"><H1>See Also</H1></A>
<A HREF="heap.html">heap(3)</A>
<A HREF="heap-common.html">heap-common(3)</A>
<HR>
Copyright © 1999 <A HREF=http://www.claas-solutions.de/kuehl>Dietmar Kühl</A> (<A HREF="mailto:dietmar.kuehl@claas-solutions.de">dietmar.kuehl@claas-solutions.de</A>)<BR>
<a href="http://www.claas-solutions.de/">Claas Solutions GmbH</a>
</FONT></FONT>
</TD></TR></TABLE>
</BODY></HTML>
|
