00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX_HEAP_HPP
00014 #define __MMX_HEAP_HPP
00015 #include <basix/vector.hpp>
00016
00018
00019 namespace mmx {
00020 #define TMPL_DEF template<typename C>
00021 #define TMPL template<typename C>
00022 #define Heap heap<C>
00023 #define Heap_rep heap_rep<C>
00024
00025 TMPL class heap_rep;
00026 TMPL class heap;
00027 TMPL Heap copy (const Heap& h);
00028 TMPL inline void set_top (Heap& h, const C& x);
00029 TMPL inline C get_top (const Heap& h);
00030 TMPL inline void push (Heap& h, const C& x);
00031 TMPL inline C pull (Heap& h);
00032 TMPL inline nat N (const Heap& h);
00033
00034
00035
00036
00037
00038 TMPL_DEF
00039 class heap_rep REP_STRUCT {
00040 typedef bool (*comparison) (const C&, const C&);
00041 comparison compare;
00042
00043 C* a;
00044 nat n;
00045 nat l;
00046
00047 public:
00048 inline Heap_rep (comparison compare2):
00049 compare (compare2), a (mmx_new<C> (0)), n (0), l (0) {}
00050 inline Heap_rep (C* a2, nat n2, nat l2, comparison compare2):
00051 compare (compare2), a (a2), n (n2), l (l2) {}
00052 inline ~Heap_rep () { mmx_delete<C> (a, l); }
00053
00054 void resize (nat n2);
00055 void correct_downwards ();
00056 void correct_upwards ();
00057 void Set_top (const C& x);
00058 C Get_top () const;
00059 void Push (const C& x);
00060 C Pull ();
00061
00062 friend class Heap;
00063 friend Heap copy LESSGTR (const Heap& h);
00064 friend void set_top LESSGTR (Heap& h, const C& x);
00065 friend C get_top LESSGTR (const Heap& h);
00066 friend void push LESSGTR (Heap& h, const C& x);
00067 friend C pull LESSGTR (Heap& h);
00068 friend nat N LESSGTR (const Heap& h);
00069 };
00070
00071
00072 TMPL_DEF
00073 class heap {
00074 INDIRECT_PROTO_1 (heap, heap_rep, C)
00075 typedef bool (*comparison) (const C&, const C&);
00076 inline heap (C* a, nat n, nat l, comparison compare):
00077 rep (new Heap_rep (a, n, l, compare)) {}
00078
00079 public:
00080 inline heap (comparison compare):
00081 rep (new Heap_rep (compare)) {}
00082 heap (const iterator<C>& it, comparison compare):
00083 rep (new Heap_rep (compare)) {
00084 while (busy (it)) { rep->Push (*it); ++it; } }
00085 inline C operator [] (nat i) const {
00086 ASSERT (i < rep->n, "out of range");
00087 return rep->a[i]; }
00088
00089 friend Heap copy LESSGTR (const Heap& h);
00090 friend void set_top LESSGTR (Heap& h, const C& x);
00091 friend C get_top LESSGTR (const Heap& h);
00092 friend void push LESSGTR (Heap& h, const C& x);
00093 friend C pull LESSGTR (Heap& h);
00094 friend nat N LESSGTR (const Heap& h);
00095 };
00096 INDIRECT_IMPL_1 (heap, heap_rep, typename C, C)
00097
00098
00099
00100
00101
00102 TMPL void
00103 Heap_rep::resize (nat n2) {
00104 if (n2 > l || n2 < ((l+1)>>1)) {
00105 nat l2= (((n2 < ((l+1)>>1)) || (n2 > (l<<1))) ? n2: l<<1);
00106 C* b= mmx_new<C> (l2);
00107 nat nn= min (n, n2);
00108 for (nat i=0; i<nn; i++) b[i]= a[i];
00109 mmx_delete<C> (a, l);
00110 a= b;
00111 l= l2;
00112 }
00113 n= n2;
00114 }
00115
00116 TMPL void
00117 Heap_rep::correct_downwards () {
00118 nat i= 0;
00119 while (true) {
00120 nat l= (i<<1) + 1, r= l+1;
00121 if (l >= n) break;
00122 if (compare (a[i], a[l])) {
00123 if (r >= n || compare (a[i], a[r])) break;
00124 else {
00125 swap (a[i], a[r]);
00126 i= r;
00127 }
00128 }
00129 else {
00130 if (r >= n || compare (a[i], a[r]) || compare (a[l], a[r])) {
00131 swap (a[i], a[l]);
00132 i= l;
00133 }
00134 else {
00135 swap (a[i], a[r]);
00136 i= r;
00137 }
00138 }
00139 }
00140 }
00141
00142 TMPL void
00143 Heap_rep::correct_upwards () {
00144 nat i= n-1;
00145 while (i>0) {
00146 nat u= (i-1) >> 1;
00147 if (compare (a[u], a[i])) break;
00148 else {
00149 swap (a[u], a[i]);
00150 i= u;
00151 }
00152 }
00153 }
00154
00155 TMPL void
00156 Heap_rep::Set_top (const C& x) {
00157 ASSERT (n>0, "non-empty heap expected");
00158 a[0]= x;
00159 correct_downwards ();
00160 }
00161
00162 TMPL C
00163 Heap_rep::Get_top () const {
00164 ASSERT (n>0, "non-empty heap expected");
00165 return a[0];
00166 }
00167
00168 TMPL void
00169 Heap_rep::Push (const C& x) {
00170 resize (n+1);
00171 a[n-1]= x;
00172 correct_upwards ();
00173 }
00174
00175 TMPL C
00176 Heap_rep::Pull () {
00177 ASSERT (n>0, "non-empty heap expected");
00178 C r = a[0];
00179 a[0]= a[n-1];
00180 resize (n-1);
00181 correct_downwards ();
00182 return r;
00183 }
00184
00185 TMPL inline void set_top (Heap& h, const C& x) {
00186 h.secure(); h.rep->Set_top (x); }
00187 TMPL inline C get_top (const Heap& h) {
00188 return h.rep->Get_top (); }
00189 TMPL inline void push (Heap& h, const C& x) {
00190 h.secure(); h.rep->Push (x); }
00191 TMPL inline C pull (Heap& h) {
00192 h.secure(); return h.rep->Pull (); }
00193 TMPL inline nat N (const Heap& l) {
00194 return l.rep->n; }
00195
00196 TMPL inline Heap& operator << (Heap& h, const C& x) {
00197 push (h, x); return h; }
00198 TMPL inline Heap& operator >> (Heap& h, C& x) {
00199 x= pull (h); return h; }
00200
00201
00202
00203
00204
00205 TMPL_DEF
00206 class heap_iterator_rep: public iterator_rep<C> {
00207 Heap h;
00208 protected:
00209 bool is_busy () { return N(h) != 0; }
00210 void advance () { (void) pull (h); }
00211 C current () { return get_top (h); }
00212 public:
00213 heap_iterator_rep (const Heap& h2): h (copy (h2)) {}
00214 };
00215
00216 TMPL iterator<C>
00217 iterate (const Heap& h) {
00218 return iterator<C> (new heap_iterator_rep<C> (h));
00219 }
00220
00221
00222
00223
00224
00225 template<typename Op, typename C> nat
00226 unary_hash (const Heap& HH) {
00227 Heap H= copy (HH);
00228 register nat h= 2531648;
00229 while (N(H) > 0)
00230 h= (h<<1) ^ (h<<5) ^ (h>>27) ^ Op::op (pull (H));
00231 return h;
00232 }
00233
00234 template<typename Op, typename C> bool
00235 binary_test (const Heap& h1b, const Heap& h2b) {
00236 if (N(h1b) != N(h2b)) return false;
00237 Heap h1= copy (h1b), h2= copy (h2b);
00238 while (N(h1) > 0)
00239 if (Op::not_op (pull (h1), pull (h2))) return false;
00240 return true;
00241 }
00242
00243 TRUE_IDENTITY_OP_SUGAR(TMPL,Heap)
00244 EXACT_IDENTITY_OP_SUGAR(TMPL,Heap)
00245
00246 TMPL Heap
00247 copy (const Heap& h) {
00248 C* b= mmx_new<C> (h->l);
00249 for (nat i=0; i<h->n; i++) b[i]= h->a[i];
00250 return Heap (b, h->n, h->l, h->compare);
00251 }
00252
00253 TMPL syntactic
00254 flatten (const Heap& h) {
00255 return flatten (syntactic ("heap"), iterate (h));
00256 }
00257
00258 TMPL
00259 struct binary_helper<Heap >: public void_binary_helper<Heap > {
00260 static inline string short_type_name () {
00261 return "H" * Short_type_name (C); }
00262 static inline generic full_type_name () {
00263 return gen ("Heap", Full_type_name (C)); }
00264 static inline nat size (const Heap& v) {
00265 return N(v); }
00266 static inline generic access (const Heap& v, nat i) {
00267 return as<generic> (v[i]); }
00268 static inline generic disassemble (const Heap& v) {
00269 vector<generic> r;
00270 for (nat i=0; i<N(v); i++) r << as<generic> (v[i]);
00271 return as<generic> (r); }
00272 static inline Heap assemble (const generic& x) {
00273 Heap h;
00274 vector<generic> v= as<vector<generic> > (x);
00275 for (nat i=0; i<N(v); i++) push (h, v[i]);
00276 return h; }
00277 static inline void write (const port& out, const Heap& h) {
00278 binary_write<nat> (out, N(h));
00279 Heap c= copy (h);
00280 for (nat i=0; i<N(h); i++)
00281 binary_write<C> (out, pull (c)); }
00282 static inline Heap read (const port& in) {
00283 nat n= binary_read<nat> (in);
00284 Heap h;
00285 for (nat i=0; i<n; i++)
00286 push (h, binary_read<C> (in));
00287 return h; }
00288 };
00289
00290 #undef TMPL_DEF
00291 #undef TMPL
00292 #undef Heap
00293 #undef Heap_rep
00294 }
00295 #endif // __MMX_HEAP_HPP