equal
deleted
inserted
replaced
30 |
30 |
31 /// \addtogroup auxdat |
31 /// \addtogroup auxdat |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 /// A Binary Heap implementation. |
34 /// A Binary Heap implementation. |
|
35 |
|
36 ///\todo Please document... |
|
37 /// |
|
38 ///\sa FibHeap |
|
39 ///\sa Dijkstra |
35 template <typename Item, typename Prio, typename ItemIntMap, |
40 template <typename Item, typename Prio, typename ItemIntMap, |
36 typename Compare = std::less<Prio> > |
41 typename Compare = std::less<Prio> > |
37 class BinHeap { |
42 class BinHeap { |
38 |
43 |
39 public: |
44 public: |
65 Compare comp; |
70 Compare comp; |
66 // FIXME: jo ez igy??? |
71 // FIXME: jo ez igy??? |
67 ItemIntMap &iim; |
72 ItemIntMap &iim; |
68 |
73 |
69 public: |
74 public: |
|
75 ///\e |
70 BinHeap(ItemIntMap &_iim) : iim(_iim) {} |
76 BinHeap(ItemIntMap &_iim) : iim(_iim) {} |
|
77 ///\e |
71 BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {} |
78 BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {} |
72 |
79 |
73 |
80 |
|
81 ///\e |
74 int size() const { return data.size(); } |
82 int size() const { return data.size(); } |
|
83 ///\e |
75 bool empty() const { return data.empty(); } |
84 bool empty() const { return data.empty(); } |
76 |
85 |
77 private: |
86 private: |
78 static int parent(int i) { return (i-1)/2; } |
87 static int parent(int i) { return (i-1)/2; } |
79 static int second_child(int i) { return 2*i+2; } |
88 static int second_child(int i) { return 2*i+2; } |
99 data.pop_back(); |
108 data.pop_back(); |
100 } |
109 } |
101 } |
110 } |
102 |
111 |
103 public: |
112 public: |
|
113 ///\e |
104 void push(const PairType &p) { |
114 void push(const PairType &p) { |
105 int n = data.size(); |
115 int n = data.size(); |
106 data.resize(n+1); |
116 data.resize(n+1); |
107 bubble_up(n, p); |
117 bubble_up(n, p); |
108 } |
118 } |
|
119 ///\e |
109 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
120 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
110 |
121 |
|
122 ///\e |
111 Item top() const { |
123 Item top() const { |
112 return data[0].first; |
124 return data[0].first; |
113 } |
125 } |
114 /// Returns the prio of the top element of the heap. |
126 /// Returns the prio of the top element of the heap. |
115 Prio prio() const { |
127 Prio prio() const { |
116 return data[0].second; |
128 return data[0].second; |
117 } |
129 } |
118 |
130 |
|
131 ///\e |
119 void pop() { |
132 void pop() { |
120 rmidx(0); |
133 rmidx(0); |
121 } |
134 } |
122 |
135 |
|
136 ///\e |
123 void erase(const Item &i) { |
137 void erase(const Item &i) { |
124 rmidx(iim[i]); |
138 rmidx(iim[i]); |
125 } |
139 } |
126 |
140 |
|
141 ///\e |
127 Prio operator[](const Item &i) const { |
142 Prio operator[](const Item &i) const { |
128 int idx = iim[i]; |
143 int idx = iim[i]; |
129 return data[idx].second; |
144 return data[idx].second; |
130 } |
145 } |
131 |
146 |
|
147 ///\e |
132 void set(const Item &i, const Prio &p) { |
148 void set(const Item &i, const Prio &p) { |
133 int idx = iim[i]; |
149 int idx = iim[i]; |
134 if( idx < 0 ) { |
150 if( idx < 0 ) { |
135 push(i,p); |
151 push(i,p); |
136 } |
152 } |
140 else { |
156 else { |
141 bubble_down(idx, PairType(i,p), data.size()); |
157 bubble_down(idx, PairType(i,p), data.size()); |
142 } |
158 } |
143 } |
159 } |
144 |
160 |
|
161 ///\e |
145 void decrease(const Item &i, const Prio &p) { |
162 void decrease(const Item &i, const Prio &p) { |
146 int idx = iim[i]; |
163 int idx = iim[i]; |
147 bubble_up(idx, PairType(i,p)); |
164 bubble_up(idx, PairType(i,p)); |
148 } |
165 } |
|
166 ///\e |
149 void increase(const Item &i, const Prio &p) { |
167 void increase(const Item &i, const Prio &p) { |
150 int idx = iim[i]; |
168 int idx = iim[i]; |
151 bubble_down(idx, PairType(i,p), data.size()); |
169 bubble_down(idx, PairType(i,p), data.size()); |
152 } |
170 } |
153 |
171 |
|
172 ///\e |
154 state_enum state(const Item &i) const { |
173 state_enum state(const Item &i) const { |
155 int s = iim[i]; |
174 int s = iim[i]; |
156 if( s>=0 ) |
175 if( s>=0 ) |
157 s=0; |
176 s=0; |
158 return state_enum(s); |
177 return state_enum(s); |