00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX_LIST_HPP
00014 #define __MMX_LIST_HPP
00015 #include <basix/vector.hpp>
00016
00018
00019
00020 namespace mmx {
00021 #define TMPL_DEF template<typename C>
00022 #define TMPL template<typename C>
00023 #define Format format<C>
00024 #define List list<C>
00025 #define List_rep list_rep<C>
00026 TMPL class list_rep;
00027 TMPL class list;
00029 TMPL inline List cons (const C& c, const List& l);
00031 TMPL inline const C& car (const List& l);
00033 TMPL inline C& car (List& l);
00035 TMPL inline const List& cdr (const List& l);
00037 TMPL inline List& cdr (List& l);
00039 TMPL inline bool is_nil (const List& l);
00040
00041
00042
00043
00044
00045 TMPL_DEF
00046 class list_rep REP_STRUCT {
00047 C item;
00048 List next;
00049
00050 public:
00051 inline List_rep (const C& item2, const List& next2):
00052 item(item2), next(next2) {}
00053 friend class List;
00054 friend const C& car LESSGTR (const List& l);
00055 friend C& car LESSGTR (List& l);
00056 friend const List& cdr LESSGTR (const List& l);
00057 friend List& cdr LESSGTR (List& l);
00058 };
00059
00060 TMPL_DEF
00061 class list: public format<C> {
00062 INDIRECT_PROTO_1 (list, list_rep, C)
00063 private:
00064 inline list (const C& item, const List& next):
00065 Format (get_format (item)), rep (new List_rep (item, next)) {}
00066 public:
00067 inline list ():
00068 Format (no_format ()), rep (NULL) {}
00069 inline list (const Format& fm):
00070 Format (fm), rep (NULL) {}
00071 inline list (const C& c1):
00072 Format (get_format (c1)), rep (new List_rep (c1, List ())) {}
00073 inline list (const C& c1, const C& c2):
00074 Format (get_format (c1)), rep (new List_rep (c1, List (c2))) {}
00075 inline list (const C& c1, const C& c2, const C& c3):
00076 Format (get_format (c1)), rep (new List_rep (c1, List (c2, c3))) {}
00077 inline list (const C& c1, const C& c2, const C& c3, const C& c4):
00078 Format (get_format (c1)), rep (new List_rep (c1, List (c2, c3, c4))) {}
00079 list (const vector<C>& v):
00080 Format (CF(v)), rep (NULL) {
00081 for (nat i=N(v)-1; i!=((nat) -1); i--) rep= new List_rep (v[i], *this); }
00082 list (const iterator<C>& it):
00083 Format (CF(it)) {
00084 if (busy (it)) { C c= *it; ++it; rep= new List_rep (c, it); }
00085 else rep= NULL; }
00086 const C& operator [] (nat i) const {
00087 ASSERT (rep != NULL, "non-empty list expected");
00088 return i==0? rep->item: read_only (rep->next) [i-1]; }
00089 C& operator [] (nat i) {
00090 ASSERT (rep != NULL, "non-empty list expected");
00091 secure ();
00092 return i==0? rep->item: rep->next[i-1]; }
00093 friend List cons LESSGTR (const C& c, const List& l);
00094 friend const C& car LESSGTR (const List& l);
00095 friend C& car LESSGTR (List& l);
00096 friend const List& cdr LESSGTR (const List& l);
00097 friend List& cdr LESSGTR (List& l);
00098 friend bool is_nil LESSGTR (const List& l);
00099 };
00100 DEFINE_UNARY_FORMAT_1 (list)
00101
00102 TMPL inline Format CF (const List& l) {
00103 return l.tfm (); }
00104 TMPL inline List::list (List_rep* rep2):
00105 Format (no_format ()), rep(rep2) {}
00106 TMPL inline List::list (const List_rep* rep2, bool with_inc):
00107 Format (no_format ()), rep((List_rep*) (void*) rep2) {
00108 (void) with_inc; INC_NULL_COUNT (rep); }
00109 TMPL inline List::list (const List& x):
00110 Format (CF(x)), rep(x.rep) {
00111 INC_NULL_COUNT (rep); }
00112 TMPL inline List::~list () {
00113 DEC_NULL_COUNT (rep); }
00114 TMPL inline const List_rep* List::operator -> () const {
00115 return rep; }
00116 TMPL inline List_rep* List::operator -> () {
00117 return rep; }
00118 TMPL inline List& List::operator = (const List& x) {
00119 INC_NULL_COUNT (x.rep); DEC_NULL_COUNT (rep);
00120 rep=x.rep; return *this; }
00121 TMPL inline void List::secure () {
00122 if (rep->ref_count>1) *this= copy (*this); }
00123 TMPL List_rep* inside (const List& x) {
00124 return const_cast<List_rep*> (x.operator -> ()); }
00125 TMPL inline nat hard_hash (const List& x) {
00126 return as_hash (x.operator -> ()); }
00127 TMPL inline bool hard_eq (const List& x, const List& y) {
00128 return (x.operator -> ()) == (y.operator -> ()); }
00129 TMPL inline bool hard_neq (const List& x, const List& y) {
00130 return (x.operator -> ()) != (y.operator -> ()); }
00131
00132 TMPL struct species_type_information<List > {
00133 static const nat id= SPECIES_LIST; };
00134
00135
00136
00137
00138
00139 TMPL inline List cons (const C& c, const List& l) { return List (c, l); }
00140 TMPL inline const C& car (const List& l) { return l.rep->item; }
00142 TMPL inline const C& read_car (const List& l) { return car (l); }
00144 TMPL inline C& car (List& l) { l.secure(); return l.rep->item; }
00145 TMPL inline const List& cdr (const List& l) { return l.rep->next; }
00147 TMPL inline const List& read_cdr (const List& l) { return cdr (l); }
00149 TMPL inline List& cdr (List& l) { l.secure(); return l.rep->next; }
00150 TMPL inline bool is_nil (const List& l) { return l.rep == NULL; }
00152 TMPL inline bool is_atom (const List& l) {
00153 return !is_nil (l) && is_nil (cdr (l)); }
00155 TMPL nat N (const List& l) { return is_nil (l)? 0: N (cdr (l)) + 1; }
00157 TMPL inline const C& read (const List& l, nat i) { return l[i]; }
00158
00159 template<typename T, typename F>
00160 struct as_helper<list<T>,list<F> > {
00161 static inline list<T>
00162 cv (const list<F>& l) {
00163 if (is_nil (l)) return list<T> ();
00164 else return cons (as<T> (car (l)), cv (cdr (l)));
00165 }
00166 };
00167
00168 template<typename T, typename F> inline void
00169 set_as (list<T>& r, const vector<F>& l) {
00170 if (is_nil (l)) r= list<T> (CF(r));
00171 else {
00172 T c; set_as (c, car (l));
00173 list<T> s (CF (r)); set_as (s, cdr (l));
00174 r= cons (c, s);
00175 }
00176 }
00177
00178 template<typename C, typename T> inline void
00179 set_as (List& r, const T& x) {
00180 C c; set_as (c, x);
00181 r= list<T> (c);
00182 }
00183
00184
00185
00186
00187
00188 TMPL_DEF
00189 class list_iterator_rep: public iterator_rep<C> {
00190 List l;
00191 public:
00192 list_iterator_rep (const List& l2):
00193 iterator_rep<C> (CF(l2)), l(l2) {}
00194 protected:
00195 bool is_busy () { return !is_nil (l); }
00196 void advance () { l= read_cdr (l); }
00197 C current () { return read_car (l); }
00198 iterator_rep<C>* clone () { return new list_iterator_rep (l); }
00199 };
00200
00201 TMPL iterator<C>
00202 iterate (const List& l) {
00203 return iterator<C> (new list_iterator_rep<C> (l));
00204 }
00205
00206
00207
00208
00209
00210 template<typename Op,typename C> nat
00211 unary_hash (const List& ll) {
00212 List l= ll;
00213 register nat h= 253648;
00214 while (!is_nil (l)) {
00215 h= (h<<1) ^ (h<<5) ^ (h>>27) ^ Op::op (read_car (l));
00216 l= read_cdr (l);
00217 }
00218 return h;
00219 }
00220
00221 template<typename Op, typename C> bool
00222 binary_test (const List& l1, const List& l2) {
00223 if (is_nil (l1) || is_nil (l2)) return is_nil (l1) && is_nil (l2);
00224 return Op::op (read_car (l1), read_car (l2)) &&
00225 binary_test<Op> (read_cdr (l1), read_cdr (l2));
00226 }
00227
00228 TRUE_IDENTITY_OP_SUGAR(TMPL,List)
00229 EXACT_IDENTITY_OP_SUGAR(TMPL,List)
00230
00231
00232
00233
00234
00235 TMPL syntactic
00236 flatten (const List& l) {
00237 vector<syntactic> v;
00238 List counter= l;
00239 while (!is_nil (counter)) {
00240 v << flatten (read_car (counter));
00241 counter= read_cdr (counter);
00242 }
00243 return apply (GEN_SQTUPLE, v);
00244 }
00245
00246 TMPL
00247 struct binary_helper<List >: public void_binary_helper<List > {
00248 static inline string short_type_name () {
00249 return "Li" * Short_type_name (C); }
00250 static inline generic full_type_name () {
00251 return gen ("List", Full_type_name (C)); }
00252 static inline generic disassemble (const List& l) {
00253 if (is_nil (l)) return gen_vec ();
00254 else return gen_vec (as<generic> (car (l)), as<generic> (cdr (l))); }
00255 static inline List assemble (const generic& x) {
00256 vector<generic> v= as<vector<generic> > (x);
00257 if (N(v) == 0) return List ();
00258 else return cons (as<C> (v[0]), as<List > (v[1])); }
00259 static inline void write (const port& out, const List& l) {
00260 if (is_nil (l)) binary_write<char> (out, '.');
00261 else {
00262 binary_write<char> (out, ',');
00263 binary_write<C> (out, car (l));
00264 binary_write<List > (out, cdr (l));
00265 } }
00266 static inline List read (const port& in) {
00267 if (binary_read<char> (in) == '.') return List ();
00268 else return cons (binary_read<C> (in), binary_read<List > (in)); }
00269 };
00270
00271
00272
00273
00274
00275 TMPL List
00276 copy (const List& l) {
00277 if (is_nil (l)) return l;
00278 return cons (car (l), cdr (l));
00279 }
00280
00282 TMPL List
00283 append (const List& l1, const List& l2) {
00284 if (is_nil (l1)) return copy (l2);
00285 return cons (car (l1), append (cdr (l1), l2));
00286 }
00287
00288 TMPL inline List
00289 operator * (const List& l1, const List& l2) {
00290 return append (l1, l2);
00291 }
00292
00294 TMPL List
00295 reverse (const List& ll) {
00296 List l= ll, r;
00297 while (!is_nil (l)) {
00298 r= cons (read_car (l), r);
00299 l= read_cdr (l);
00300 }
00301 return r;
00302 }
00303
00305 TMPL List
00306 range (const List& l, nat start, nat end) {
00307 if (start >= end) return List ();
00308 ASSERT (!is_nil (l), "non-empty list expected");
00309 if (start > 0) return range (cdr (l), start-1, end-1);
00310 return cons (car (l), range (cdr (l), 0, end-1));
00311 }
00312
00313 TMPL List
00314 insert (const List& l, const C& x) {
00315 if (is_nil (l)) return List (x);
00316 else if (car (l) == x) return l;
00317 else return cons (car (l), insert<C> (cdr (l), x));
00318 }
00319
00320 TMPL int
00321 find (const List& l, const C& x) {
00322 if (is_nil (l) || car (l) == x) return 0;
00323 else return find<C> (cdr (l), x) + 1;
00324 }
00325
00326 TMPL bool
00327 contains (const List& l, const C& x) {
00328 if (is_nil (l)) return false;
00329 else return car (l) == x || contains<C> (cdr (l), x);
00330 }
00331
00332
00333
00334
00335
00336 template<typename S1, typename D, typename Fun> list<D>
00337 map (const Fun& fun, const list<S1>& l1, const format<D>& fm) {
00338 if (is_nil (l1)) return list<D> (fm);
00339 else return cons (fun (car (l1)), map (fun, cdr (l1), fm));
00340 }
00341
00342 #undef TMPL_DEF
00343 #undef TMPL
00344 #undef Format
00345 #undef List
00346 #undef List_rep
00347 }
00348 #endif // __MMX_LIST_HPP