00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX_CHAIN_HPP
00014 #define __MMX_CHAIN_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 Format format<C>
00023 #define Chain chain<C>
00024 #define Chain_rep chain_rep<C>
00025 TMPL class chain_rep;
00026 TMPL class chain;
00027 TMPL inline Chain left (const Chain& c);
00028 TMPL inline C middle (const Chain& c);
00029 TMPL inline Chain right (const Chain& c);
00030 TMPL inline bool is_nil (const Chain& c);
00031 TMPL inline nat N (const Chain& c);
00032 TMPL Chain balance_left (const Chain& c);
00033 TMPL Chain balance_right (const Chain& c);
00034 TMPL Chain operator * (const Chain& l, const Chain& r);
00035
00036
00037
00038
00039
00040 TMPL_DEF
00041 class chain_rep REP_STRUCT {
00042 nat size;
00043 Chain l;
00044 C m;
00045 Chain r;
00046
00047
00048 public:
00049 inline Chain_rep (const Chain& l2, const C& m2, const Chain& r2);
00050 friend class Chain;
00051 friend Chain left LESSGTR (const Chain& c);
00052 friend C middle LESSGTR (const Chain& c);
00053 friend Chain right LESSGTR (const Chain& c);
00054 friend nat N LESSGTR (const Chain& c);
00055 };
00056
00057 TMPL_DEF
00058 class chain: public format<C> {
00059 INDIRECT_PROTO_1 (chain, chain_rep, C)
00060 public:
00061 inline chain ():
00062 Format (no_format ()),
00063 rep (NULL) {}
00064 inline chain (const C& c1):
00065 Format (get_format (c1)),
00066 rep (new Chain_rep (Chain (), c1, Chain ())) {}
00067 inline chain (const C& c1, const C& c2):
00068 Format (get_format (c1)),
00069 rep (new Chain_rep (Chain (c1), c2, Chain ())) {}
00070 inline chain (const C& c1, const C& c2, const C& c3):
00071 Format (get_format (c1)),
00072 rep (new Chain_rep (Chain (c1), c2, Chain (c3))) {}
00073 inline chain (const Chain& l, const C& m, const Chain& r):
00074 Format (get_format (m)),
00075 rep (new Chain_rep (l, m, r)) {}
00076 chain (const iterator<C>& it):
00077 Format (CF(it)) {
00078 rep= NULL;
00079 for (; busy (it); ++it) *this= (*this) * Chain (*it); }
00080 C operator [] (nat i) const {
00081 ASSERT (rep != NULL, "non-empty chain expected");
00082 if (i < N (rep->l)) return rep->l[i];
00083 if (i > N (rep->l)) return rep->r[i-N(rep->l)];
00084 return rep->m; }
00085 friend Chain left LESSGTR (const Chain& c);
00086 friend C middle LESSGTR (const Chain& c);
00087 friend Chain right LESSGTR (const Chain& c);
00088 friend bool is_nil LESSGTR (const Chain& c);
00089 friend nat N LESSGTR (const Chain& c);
00090 };
00091 DEFINE_UNARY_FORMAT_1 (chain)
00092
00093 TMPL inline Format CF (const Chain& l) {
00094 return (Format) l; }
00095 TMPL inline Chain::chain (Chain_rep* rep2):
00096 Format (no_format ()), rep(rep2) {}
00097 TMPL inline Chain::chain (const Chain_rep* rep2, bool with_inc):
00098 Format (no_format ()), rep((Chain_rep*) (void*) rep2) {
00099 (void) with_inc; INC_NULL_COUNT (rep); }
00100 TMPL inline Chain::chain (const Chain& x):
00101 Format (CF(x)), rep(x.rep) {
00102 INC_NULL_COUNT (rep); }
00103 TMPL inline Chain::~chain () {
00104 DEC_NULL_COUNT (rep); }
00105 TMPL inline const Chain_rep* Chain::operator -> () const {
00106 return rep; }
00107 TMPL inline Chain_rep* Chain::operator -> () {
00108 return rep; }
00109 TMPL inline Chain& Chain::operator = (const Chain& x) {
00110 INC_NULL_COUNT (x.rep); DEC_NULL_COUNT (rep);
00111 rep=x.rep; return *this; }
00112 TMPL inline void Chain::secure () {
00113 if (rep->ref_count>1) *this= copy (*this); }
00114 TMPL Chain_rep* inside (const Chain& x) {
00115 return const_cast<Chain_rep*> (x.operator -> ()); }
00116 TMPL inline nat hard_hash (const Chain& x) {
00117 return as_hash (x.operator -> ()); }
00118 TMPL inline bool hard_eq (const Chain& x, const Chain& y) {
00119 return (x.operator -> ()) == (y.operator -> ()); }
00120 TMPL inline bool hard_neq (const Chain& x, const Chain& y) {
00121 return (x.operator -> ()) != (y.operator -> ()); }
00122
00123
00124
00125
00126
00127 TMPL inline
00128 Chain_rep::chain_rep (const Chain& l2, const C& m2, const Chain& r2):
00129 size (N (l2) + N (r2) + 1), l (l2), m (m2), r (r2) {}
00130
00131 TMPL inline Chain left (const Chain& c) { return c.rep->l; }
00132 TMPL inline C middle (const Chain& c) { return c.rep->m; }
00133 TMPL inline Chain right (const Chain& c) { return c.rep->r; }
00134 TMPL inline bool is_nil (const Chain& c) { return c.rep == NULL; }
00135 TMPL inline nat N (const Chain& c) { return (c.rep == NULL? 0: c.rep->size); }
00136
00137
00138
00139
00140
00141 TMPL iterator<C>
00142 iterate (const Chain& c) {
00143 if (is_nil (c)) return iterator<C> ();
00144 return
00145 lazy_iterator<C,Chain > (left (c), get_format (middle (c))) *
00146 iterator<C> (middle (c)) *
00147 lazy_iterator<C,Chain > (right (c), get_format (middle (c)));
00148 }
00149
00150 TMPL syntactic
00151 flatten (const Chain& c) {
00152 return flatten (syntactic ("chain"), iterate (c));
00153 }
00154
00155 TMPL
00156 struct binary_helper<Chain >: public void_binary_helper<Chain > {
00157 static inline string short_type_name () {
00158 return "Ch" * Short_type_name (C); }
00159 static inline generic full_type_name () {
00160 return gen ("Chain", Full_type_name (C)); }
00161 static generic disassemble (const Chain& c) {
00162 if (N(c) == 0) return gen_vec ();
00163 else if (N(c) == 1) return gen_vec (as<generic> (middle (c)));
00164 else return gen_vec (as<generic> (left (c)),
00165 as<generic> (middle (c)),
00166 as<generic> (right (c))); }
00167 static Chain assemble (const generic& g) {
00168 vector<generic> v= as<vector<generic> > (g);
00169 if (N(v) == 0) return Chain ();
00170 else if (N(v) == 1) return Chain (as<C> (v[0]));
00171 else return Chain (as<Chain > (v[0]), as<C> (v[1]), as<Chain > (v[2])); }
00172 static void write_bis (const port& out, const Chain& c) {
00173 write_bis (out, left (c));
00174 binary_write<C> (out, middle (c));
00175 write_bis (out, right (c)); }
00176 static inline void write (const port& out, const Chain& c) {
00177 binary_write<nat> (out, N(c));
00178 write_bis (out, c); }
00179 static Chain read (const port& in, nat n) {
00180 if (n == 0) return Chain ();
00181 else if (n == 1) return Chain (binary_read<C> (in));
00182 else return Chain (binary_read<Chain > (in, n >> 1),
00183 binary_read<C> (in),
00184 binary_read<Chain > (in, (n-1) >> 1)); }
00185 static inline Chain read (const port& in) {
00186 nat n = binary_read<nat> (in);
00187 return read (in, n); }
00188 };
00189
00190
00191
00192
00193
00194 TMPL Chain
00195 copy (const Chain& c) {
00196 if (is_nil (c)) return c;
00197 return Chain (left (c), middle (c), right (c));
00198 }
00199
00200 TMPL Chain
00201 reverse (const Chain& c) {
00202 if (is_nil (c)) return c;
00203 return Chain (reverse (right (c)), middle (c), reverse (left (c)));
00204 }
00205
00206 TMPL C
00207 car (const Chain& c) {
00208 ASSERT (!is_nil (c), "non-empty chain expected");
00209 if (is_nil (left (c))) return middle (c);
00210 return car (left (c));
00211 }
00212
00213 TMPL C
00214 cAr (const Chain& c) {
00215 ASSERT (!is_nil (c), "non-empty chain expected");
00216 if (is_nil (right (c))) return middle (c);
00217 return cAr (right (c));
00218 }
00219
00220 template<typename Op, typename C> nat
00221 unary_hash (const Chain& c) {
00222 if (is_nil (c)) return 1928;
00223 nat h1= Op::op (left (c));
00224 nat h2= Op::op (middle (c));
00225 nat h3= Op::op (right (c));
00226 return h1 ^ (h2>>1) ^ (h2<<31) ^ (h3>>3) ^ (h3>>29);
00227 }
00228
00229 template<typename Op, typename C> bool
00230 binary_test (const Chain& c1, const Chain& c2) {
00231 if (N (c1) != N (c2)) return false;
00232 if (N (c1) == 0) return true;
00233 return binary_test<Op> (left (c1), left(c2)) &&
00234 Op::op (middle (c1), middle (c2)) &&
00235 binary_test<Op> (right (c1), right(c2));
00236 }
00237
00238 TRUE_IDENTITY_OP_SUGAR(TMPL,Chain)
00239 EXACT_IDENTITY_OP_SUGAR(TMPL,Chain)
00240
00241
00242
00243
00244
00245 TMPL Chain
00246 shift_left (const Chain& c) {
00247 return Chain (Chain (left (c), middle (c), left (right (c))),
00248 middle (right (c)),
00249 right (right (c)));
00250 }
00251
00252 TMPL Chain
00253 shift_right (const Chain& c) {
00254 return Chain (left (left (c)),
00255 middle (left (c)),
00256 Chain (right (left (c)), middle (c), right (c)));
00257 }
00258
00259 TMPL Chain
00260 balance_left (const Chain& c) {
00261
00262 switch (N(c)) {
00263 case 0:
00264 case 1:
00265 return c;
00266 case 2:
00267 if (is_nil (right (c))) return c;
00268 return Chain (Chain (middle (c)), middle (right (c)), Chain ());
00269 case 3:
00270 return c;
00271 default:
00272 if (N (left (c)) >= N (right (c))) return c;
00273 else {
00274 Chain aux= balance_right (right (c));
00275 return shift_left (Chain (left (c), middle (c), aux));
00276 }
00277 }
00278 }
00279
00280 TMPL Chain
00281 balance_right (const Chain& c) {
00282
00283 switch (N(c)) {
00284 case 0:
00285 case 1:
00286 return c;
00287 case 2:
00288 if (is_nil (left (c))) return c;
00289 return Chain (Chain (), middle (left (c)), Chain (middle (c)));
00290 case 3:
00291 return c;
00292 default:
00293 if (N (left (c)) <= N (right (c))) return c;
00294 else {
00295 Chain aux= balance_left (left (c));
00296 return shift_right (Chain (aux, middle (c), right (c)));
00297 }
00298 }
00299 }
00300
00301 TMPL Chain
00302 cdr (const Chain& c) {
00303 ASSERT (!is_nil (c), "non-empty chain expected");
00304 if (N (c) == 1) return Chain ();
00305 if (2 * N (left (c)) <= N (right (c))) return cdr (balance_left (c));
00306 return Chain (cdr (left (c)), middle (c), right (c));
00307 }
00308
00309 TMPL Chain
00310 cDr (const Chain& c) {
00311 ASSERT (!is_nil (c), "non-empty chain expected");
00312 if (N (c) == 1) return Chain ();
00313 if (2 * N (right (c)) <= N (left (c))) return cDr (balance_right (c));
00314 return Chain (left (c), middle (c), cDr (right (c)));
00315 }
00316
00317 TMPL Chain
00318 operator * (const Chain& l, const Chain& r) {
00319 nat nl= N (l), nr= N (r);
00320 if (nl < nr) {
00321 if (nl == 0) return r;
00322 if (nr < 2*nl + 3) return Chain (l, car (r), cdr (r));
00323 Chain br= balance_right (r);
00324 return Chain (l * left (br), middle (br), right (br));
00325 }
00326 else {
00327 if (nr == 0) return l;
00328 if (nl < 2*nr + 3) return Chain (cDr (l), cAr (l), r);
00329 Chain bl= balance_left (l);
00330 return Chain (left (bl), middle (bl), right (bl) * r);
00331 }
00332 }
00333
00334 TMPL Chain
00335 range (const Chain& c, nat start, nat end) {
00336 if (start >= end) return Chain ();
00337 ASSERT (!is_nil (c), "non-empty chain expected");
00338 nat n= N (left (c));
00339 if (end <= n) return range (left (c), start, end);
00340 if (start > n) return range (right (c), start-n-1, end-n-1);
00341 Chain l= range (left (c), start, n);
00342 C m= middle (c);
00343 Chain r= range (right (c), 0, end-n-1);
00344 if (N(l) < 2*(N(r) + 1) && N(r) < 2*(N(l) + 1)) return Chain (l, m, r);
00345 return l * Chain (m) * r;
00346 }
00347
00348
00349
00350
00351
00352 template<typename S1, typename D, typename Fun> chain<D>
00353 map (const Fun& fun, const chain<S1>& c1, const format<D>& fm) {
00354 if (is_nil (c1)) return chain<D> (fm);
00355 return chain<D> (map (fun, left (c1), fm),
00356 fun (middle (c1)),
00357 map (fun, right (c1), fm));
00358 }
00359
00360 #undef TMPL_DEF
00361 #undef TMPL
00362 #undef Format
00363 #undef Chain
00364 #undef Chain_rep
00365 }
00366 #endif // __MMX_CHAIN_HPP