]>
Commit | Line | Data |
---|---|---|
1 | //////////////////////////////////////////////////////////////////////////// | |
2 | // lazy_list.hpp | |
3 | // | |
4 | // Build lazy operations for Phoenix equivalents for FC++ | |
5 | // | |
6 | // These are equivalents of the Boost FC++ functoids in list.hpp | |
7 | // | |
8 | // Implemented so far: | |
9 | // | |
10 | // head tail null | |
11 | // | |
12 | // strict_list<T> and associated iterator. | |
13 | // | |
14 | // list<T> and odd_list<T> | |
15 | // | |
16 | // cons cat | |
17 | // | |
18 | // Comparisons between list and odd_list types and separately for strict_list. | |
19 | // | |
20 | // NOTES: There is a fix at the moment as I have not yet sorted out | |
21 | // how to get back the return type of a functor returning a list type. | |
22 | // For the moment I have fixed this as odd_list<T> at two locations, | |
23 | // one in list<T> and one in Cons. I am going to leave it like this | |
24 | // for now as reading the code, odd_list<T> seems to be correct. | |
25 | // | |
26 | // I am also not happy at the details needed to detect types in Cons. | |
27 | // | |
28 | // I think the structure of this file is now complete. | |
29 | // John Fletcher February 2015. | |
30 | // | |
31 | //////////////////////////////////////////////////////////////////////////// | |
32 | /*============================================================================= | |
33 | Copyright (c) 2000-2003 Brian McNamara and Yannis Smaragdakis | |
34 | Copyright (c) 2001-2007 Joel de Guzman | |
35 | Copyright (c) 2015 John Fletcher | |
36 | ||
37 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
38 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
39 | ==============================================================================*/ | |
40 | ||
41 | /////////////////////////////////////////////////////////////////////// | |
42 | // This is from Boost FC++ list.hpp reimplemented without Fun0 or Full0 | |
43 | /////////////////////////////////////////////////////////////////////// | |
44 | ||
45 | /* | |
46 | concept ListLike: Given a list representation type L | |
47 | ||
48 | L<T> inherits ListLike and has | |
49 | // typedefs just show typical values | |
50 | typedef T value_type | |
51 | typedef L<T> force_result_type | |
52 | typedef L<T> delay_result_type | |
53 | typedef L<T> tail_result_type | |
54 | template <class UU> struct cons_rebind { | |
55 | typedef L<UU> type; // force type | |
56 | typedef L<UU> delay_type; // delay type | |
57 | }; | |
58 | ||
59 | L() | |
60 | L( a_unique_type_for_nil ) | |
61 | template <class F> L(F) // F :: ()->L | |
62 | ||
63 | constructor: force_result_type( T, L<T> ) | |
64 | template <class F> | |
65 | constructor: force_result_type( T, F ) // F :: ()->L | |
66 | ||
67 | template <class It> | |
68 | L( It, It ) | |
69 | ||
70 | // FIX THIS instead of operator bool(), does Boost have something better? | |
71 | operator bool() const | |
72 | force_result_type force() const | |
73 | delay_result_type delay() const | |
74 | T head() const | |
75 | tail_result_type tail() const | |
76 | ||
77 | static const bool is_lazy; // true if can represent infinite lists | |
78 | ||
79 | typedef const_iterator; | |
80 | typedef const_iterator iterator; // ListLikes are immutable | |
81 | iterator begin() const | |
82 | iterator end() const | |
83 | */ | |
84 | ||
85 | ////////////////////////////////////////////////////////////////////// | |
86 | // End of section from Boost FC++ list.hpp | |
87 | ////////////////////////////////////////////////////////////////////// | |
88 | ||
89 | #ifndef BOOST_PHOENIX_FUNCTION_LAZY_LIST | |
90 | #define BOOST_PHOENIX_FUNCTION_LAZY_LIST | |
91 | ||
92 | #include <boost/phoenix/core.hpp> | |
93 | #include <boost/phoenix/function.hpp> | |
94 | #include <boost/intrusive_ptr.hpp> | |
95 | #include <boost/function.hpp> | |
96 | #include <boost/type_traits/type_with_alignment.hpp> | |
97 | //#include "lazy_reuse.hpp" | |
98 | ||
99 | namespace boost { | |
100 | ||
101 | namespace phoenix { | |
102 | ||
103 | ////////////////////////////////////////////////////////////////////// | |
104 | // These are the list types being declared. | |
105 | ////////////////////////////////////////////////////////////////////// | |
106 | ||
107 | template <class T> class strict_list; | |
108 | namespace impl { | |
109 | template <class T> class list; | |
110 | template <class T> class odd_list; | |
111 | } | |
112 | // in ref_count.hpp in BoostFC++ now in lazy_operator.hpp | |
113 | //typedef unsigned int RefCountType; | |
114 | ||
115 | ////////////////////////////////////////////////////////////////////// | |
116 | // a_unique_type_for_nil moved to lazy_operator.hpp. | |
117 | ////////////////////////////////////////////////////////////////////// | |
118 | ||
119 | ||
120 | ////////////////////////////////////////////////////////////////////// | |
121 | // Distinguish lazy lists (list and odd_list) from strict_list. | |
122 | ////////////////////////////////////////////////////////////////////// | |
123 | ||
124 | namespace lazy { | |
125 | // Copied from Boost FC++ list.hpp | |
126 | template <class L, bool is_lazy> struct ensure_lazy_helper {}; | |
127 | template <class L> struct ensure_lazy_helper<L,true> { | |
128 | static void requires_lazy_list_to_prevent_infinite_recursion() {} | |
129 | }; | |
130 | template <class L> | |
131 | void ensure_lazy() { | |
132 | ensure_lazy_helper<L,L::is_lazy>:: | |
133 | requires_lazy_list_to_prevent_infinite_recursion(); | |
134 | } | |
135 | ||
136 | } | |
137 | ||
138 | ////////////////////////////////////////////////////////////////////// | |
139 | // Provide remove reference for types defined for list types. | |
140 | ////////////////////////////////////////////////////////////////////// | |
141 | ||
142 | namespace result_of { | |
143 | ||
144 | template < typename L > | |
145 | class ListType | |
146 | { | |
147 | public: | |
148 | typedef typename boost::remove_reference<L>::type LType; | |
149 | typedef typename LType::value_type value_type; | |
150 | typedef typename LType::tail_result_type tail_result_type; | |
151 | typedef typename LType::force_result_type force_result_type; | |
152 | typedef typename LType::delay_result_type delay_result_type; | |
153 | }; | |
154 | ||
155 | template <> | |
156 | class ListType<a_unique_type_for_nil> | |
157 | { | |
158 | public: | |
159 | typedef a_unique_type_for_nil LType; | |
160 | //typedef a_unique_type_for_nil value_type; | |
161 | }; | |
162 | ||
163 | template <typename F, typename T> | |
164 | struct ResultType { | |
165 | typedef typename impl::odd_list<T> type; | |
166 | }; | |
167 | ||
168 | } | |
169 | ||
170 | ////////////////////////////////////////////////////////////////////// | |
171 | // ListLike is a property inherited by any list type to enable it to | |
172 | // work with the functions being implemented in this file. | |
173 | // It provides the check for the structure described above. | |
174 | ////////////////////////////////////////////////////////////////////// | |
175 | ||
176 | namespace listlike { | |
177 | ||
178 | struct ListLike {}; // This lets us use is_base_and_derived() to see | |
179 | // (at compile-time) what classes are user-defined lists. | |
180 | ||
181 | ||
182 | template <class L, bool is_lazy> struct ensure_lazy_helper {}; | |
183 | template <class L> struct ensure_lazy_helper<L,true> { | |
184 | static void requires_lazy_list_to_prevent_infinite_recursion() {} | |
185 | }; | |
186 | template <class L> | |
187 | void ensure_lazy() { | |
188 | ensure_lazy_helper<L,L::is_lazy>:: | |
189 | requires_lazy_list_to_prevent_infinite_recursion(); | |
190 | } | |
191 | ||
192 | template <class L, bool b> | |
193 | struct EnsureListLikeHelp { | |
194 | static void trying_to_call_a_list_function_on_a_non_list() {} | |
195 | }; | |
196 | template <class L> struct EnsureListLikeHelp<L,false> { }; | |
197 | template <class L> | |
198 | void EnsureListLike() { | |
199 | typedef typename result_of::ListType<L>::LType LType; | |
200 | EnsureListLikeHelp<L,boost::is_base_and_derived<ListLike,LType>::value>:: | |
201 | trying_to_call_a_list_function_on_a_non_list(); | |
202 | } | |
203 | ||
204 | template <class L> | |
205 | bool is_a_unique_type_for_nil(const L& /*l*/) { | |
206 | return false; | |
207 | } | |
208 | ||
209 | template <> | |
210 | bool is_a_unique_type_for_nil<a_unique_type_for_nil> | |
211 | (const a_unique_type_for_nil& /* n */) { | |
212 | return true; | |
213 | } | |
214 | ||
215 | template <class L> | |
216 | struct detect_nil { | |
217 | static const bool is_nil = false; | |
218 | }; | |
219 | ||
220 | template <> | |
221 | struct detect_nil<a_unique_type_for_nil> { | |
222 | static const bool is_nil = true; | |
223 | }; | |
224 | ||
225 | template <> | |
226 | struct detect_nil<a_unique_type_for_nil&> { | |
227 | static const bool is_nil = true; | |
228 | }; | |
229 | ||
230 | template <> | |
231 | struct detect_nil<const a_unique_type_for_nil&> { | |
232 | static const bool is_nil = true; | |
233 | }; | |
234 | ||
235 | } | |
236 | ||
237 | ////////////////////////////////////////////////////////////////////// | |
238 | // Implement lazy functions for list types. cat and cons come later. | |
239 | ////////////////////////////////////////////////////////////////////// | |
240 | ||
241 | #ifndef BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH | |
242 | #define BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH 1000 | |
243 | #endif | |
244 | ||
245 | namespace impl { | |
246 | ||
247 | struct Head | |
248 | { | |
249 | template <typename Sig> | |
250 | struct result; | |
251 | ||
252 | template <typename This, typename L> | |
253 | struct result<This(L)> | |
254 | { | |
255 | typedef typename result_of::ListType<L>::value_type type; | |
256 | }; | |
257 | ||
258 | template <typename L> | |
259 | typename result<Head(L)>::type | |
260 | operator()(const L & l) const | |
261 | { | |
262 | listlike::EnsureListLike<L>(); | |
263 | return l.head(); | |
264 | } | |
265 | ||
266 | }; | |
267 | ||
268 | struct Tail | |
269 | { | |
270 | template <typename Sig> | |
271 | struct result; | |
272 | ||
273 | template <typename This, typename L> | |
274 | struct result<This(L)> | |
275 | { | |
276 | typedef typename result_of::ListType<L>::tail_result_type type; | |
277 | }; | |
278 | ||
279 | template <typename L> | |
280 | typename result<Tail(L)>::type | |
281 | operator()(const L & l) const | |
282 | { | |
283 | listlike::EnsureListLike<L>(); | |
284 | return l.tail(); | |
285 | } | |
286 | ||
287 | }; | |
288 | ||
289 | struct Null | |
290 | { | |
291 | template <typename Sig> | |
292 | struct result; | |
293 | ||
294 | template <typename This, typename L> | |
295 | struct result<This(L)> | |
296 | { | |
297 | typedef bool type; | |
298 | }; | |
299 | ||
300 | template <typename L> | |
301 | typename result<Null(L)>::type | |
302 | //bool | |
303 | operator()(const L& l) const | |
304 | { | |
305 | listlike::EnsureListLike<L>(); | |
306 | return !l; | |
307 | } | |
308 | ||
309 | }; | |
310 | ||
311 | struct Delay { | |
312 | template <typename Sig> | |
313 | struct result; | |
314 | ||
315 | template <typename This, typename L> | |
316 | struct result<This(L)> | |
317 | { | |
318 | typedef typename result_of::ListType<L>::delay_result_type type; | |
319 | }; | |
320 | ||
321 | template <typename L> | |
322 | typename result<Delay(L)>::type | |
323 | operator()(const L & l) const | |
324 | { | |
325 | listlike::EnsureListLike<L>(); | |
326 | return l.delay(); | |
327 | } | |
328 | ||
329 | }; | |
330 | ||
331 | struct Force { | |
332 | template <typename Sig> | |
333 | struct result; | |
334 | ||
335 | template <typename This, typename L> | |
336 | struct result<This(L)> | |
337 | { | |
338 | typedef typename result_of::ListType<L>::force_result_type type; | |
339 | }; | |
340 | ||
341 | template <typename L> | |
342 | typename result<Force(L)>::type | |
343 | operator()(const L & l) const | |
344 | { | |
345 | listlike::EnsureListLike<L>(); | |
346 | return l.force(); | |
347 | } | |
348 | ||
349 | }; | |
350 | ||
351 | } | |
352 | //BOOST_PHOENIX_ADAPT_CALLABLE(head, impl::head, 1) | |
353 | //BOOST_PHOENIX_ADAPT_CALLABLE(tail, impl::tail, 1) | |
354 | //BOOST_PHOENIX_ADAPT_CALLABLE(null, impl::null, 1) | |
355 | typedef boost::phoenix::function<impl::Head> Head; | |
356 | typedef boost::phoenix::function<impl::Tail> Tail; | |
357 | typedef boost::phoenix::function<impl::Null> Null; | |
358 | typedef boost::phoenix::function<impl::Delay> Delay; | |
359 | typedef boost::phoenix::function<impl::Force> Force; | |
360 | Head head; | |
361 | Tail tail; | |
362 | Null null; | |
363 | Delay delay; | |
364 | Force force; | |
365 | ||
366 | ////////////////////////////////////////////////////////////////////// | |
367 | // These definitions used for strict_list are imported from BoostFC++ | |
368 | // unchanged. | |
369 | ////////////////////////////////////////////////////////////////////// | |
370 | ||
371 | namespace impl { | |
372 | template <class T> | |
373 | struct strict_cons : public boost::noncopyable { | |
374 | mutable RefCountType refC; | |
375 | T head; | |
376 | typedef boost::intrusive_ptr<strict_cons> tail_type; | |
377 | tail_type tail; | |
378 | strict_cons( const T& h, const tail_type& t ) : refC(0), head(h), tail(t) {} | |
379 | ||
380 | }; | |
381 | template <class T> | |
382 | void intrusive_ptr_add_ref( const strict_cons<T>* p ) { | |
383 | ++ (p->refC); | |
384 | } | |
385 | template <class T> | |
386 | void intrusive_ptr_release( const strict_cons<T>* p ) { | |
387 | if( !--(p->refC) ) delete p; | |
388 | } | |
389 | ||
390 | template <class T> | |
391 | class strict_list_iterator | |
392 | : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> { | |
393 | typedef boost::intrusive_ptr<strict_cons<T> > rep_type; | |
394 | rep_type l; | |
395 | bool is_nil; | |
396 | void advance() { | |
397 | l = l->tail; | |
398 | if( !l ) | |
399 | is_nil = true; | |
400 | } | |
401 | class Proxy { // needed for operator-> | |
402 | const T x; | |
403 | friend class strict_list_iterator; | |
404 | Proxy( const T& xx ) : x(xx) {} | |
405 | public: | |
406 | const T* operator->() const { return &x; } | |
407 | }; | |
408 | public: | |
409 | strict_list_iterator() : l(), is_nil(true) {} | |
410 | explicit strict_list_iterator( const rep_type& ll ) : l(ll), is_nil(!ll) {} | |
411 | ||
412 | const T operator*() const { return l->head; } | |
413 | const Proxy operator->() const { return Proxy(l->head); } | |
414 | strict_list_iterator<T>& operator++() { | |
415 | advance(); | |
416 | return *this; | |
417 | } | |
418 | const strict_list_iterator<T> operator++(int) { | |
419 | strict_list_iterator<T> i( *this ); | |
420 | advance(); | |
421 | return i; | |
422 | } | |
423 | bool operator==( const strict_list_iterator<T>& i ) const { | |
424 | return is_nil && i.is_nil; | |
425 | } | |
426 | bool operator!=( const strict_list_iterator<T>& i ) const { | |
427 | return ! this->operator==(i); | |
428 | } | |
429 | }; | |
430 | } | |
431 | ||
432 | ////////////////////////////////////////////////////////////////////// | |
433 | ////////////////////////////////////////////////////////////////////// | |
434 | ||
435 | template <class T> | |
436 | class strict_list : public listlike::ListLike | |
437 | { | |
438 | typedef boost::intrusive_ptr<impl::strict_cons<T> > rep_type; | |
439 | rep_type rep; | |
440 | struct Make {}; | |
441 | ||
442 | template <class Iter> | |
443 | static rep_type help( Iter a, const Iter& b ) { | |
444 | rep_type r; | |
445 | while( a != b ) { | |
446 | T x( *a ); | |
447 | r = rep_type( new impl::strict_cons<T>( x, r ) ); | |
448 | ++a; | |
449 | } | |
450 | return r; | |
451 | } | |
452 | ||
453 | public: | |
454 | static const bool is_lazy = false; | |
455 | ||
456 | typedef T value_type; | |
457 | typedef strict_list force_result_type; | |
458 | typedef strict_list delay_result_type; | |
459 | typedef strict_list tail_result_type; | |
460 | template <class UU> struct cons_rebind { | |
461 | typedef strict_list<UU> type; | |
462 | typedef strict_list<UU> delay_type; | |
463 | }; | |
464 | ||
465 | ||
466 | strict_list( Make, const rep_type& r ) : rep(r) {} | |
467 | ||
468 | strict_list() : rep() {} | |
469 | ||
470 | strict_list( a_unique_type_for_nil ) : rep() {} | |
471 | ||
472 | template <class F> | |
473 | strict_list( const F& f ) : rep( f().rep ) { | |
474 | // I cannot do this yet. | |
475 | //functoid_traits<F>::template ensure_accepts<0>::args(); | |
476 | } | |
477 | ||
478 | strict_list( const T& x, const strict_list& y ) | |
479 | : rep( new impl::strict_cons<T>(x,y.rep) ) {} | |
480 | ||
481 | template <class F> | |
482 | strict_list( const T& x, const F& f ) | |
483 | : rep( new impl::strict_cons<T>(x,f().rep) ) {} | |
484 | ||
485 | operator bool() const { return (bool)rep; } | |
486 | force_result_type force() const { return *this; } | |
487 | delay_result_type delay() const { return *this; } | |
488 | T head() const { | |
489 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
490 | if( !*this ) | |
491 | throw lazy_exception("Tried to take head() of empty strict_list"); | |
492 | #endif | |
493 | return rep->head; | |
494 | } | |
495 | tail_result_type tail() const { | |
496 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
497 | if( !*this ) | |
498 | throw lazy_exception("Tried to take tail() of empty strict_list"); | |
499 | #endif | |
500 | return strict_list(Make(),rep->tail); | |
501 | } | |
502 | ||
503 | template <class Iter> | |
504 | strict_list( const Iter& a, const Iter& b ) : rep( rep_type() ) { | |
505 | // How ironic. We need to reverse the iterator range in order to | |
506 | // non-recursively build this! | |
507 | std::vector<T> tmp(a,b); | |
508 | rep = help( tmp.rbegin(), tmp.rend() ); | |
509 | } | |
510 | ||
511 | // Since the strict_cons destructor can't call the strict_list | |
512 | // destructor, the "simple" iterative destructor is correct and | |
513 | // efficient. Hurray. | |
514 | ~strict_list() { while(rep && (rep->refC == 1)) rep = rep->tail; } | |
515 | ||
516 | // The following helps makes strict_list almost an STL "container" | |
517 | typedef impl::strict_list_iterator<T> const_iterator; | |
518 | typedef const_iterator iterator; // strict_list is immutable | |
519 | iterator begin() const { return impl::strict_list_iterator<T>( rep ); } | |
520 | iterator end() const { return impl::strict_list_iterator<T>(); } | |
521 | ||
522 | }; | |
523 | ||
524 | // All of these null head and tail are now non lazy using e.g. null(a)(). | |
525 | // They need an extra () e.g. null(a)(). | |
526 | template <class T> | |
527 | bool operator==( const strict_list<T>& a, a_unique_type_for_nil ) { | |
528 | return null(a)(); | |
529 | } | |
530 | template <class T> | |
531 | bool operator==( a_unique_type_for_nil, const strict_list<T>& a ) { | |
532 | return null(a)(); | |
533 | } | |
534 | template <class T> | |
535 | bool operator==( const strict_list<T>& a, const strict_list<T>& b ) { | |
536 | if( null(a)() && null(b)() ) | |
537 | return true; | |
538 | if( null(a)() || null(b)() ) | |
539 | return false; | |
540 | return (head(a)()==head(b)()) && | |
541 | (tail(a)()==tail(b)()); | |
542 | } | |
543 | ||
544 | template <class T> | |
545 | bool operator<( const strict_list<T>& a, const strict_list<T>& b ) { | |
546 | if( null(a)() && !null(b)() ) return true; | |
547 | if( null(b)() ) return false; | |
548 | if( head(b)() < head(a)() ) return false; | |
549 | if( head(a)() < head(b)() ) return true; | |
550 | return (tail(a)() < tail(b)()); | |
551 | } | |
552 | template <class T> | |
553 | bool operator<( const strict_list<T>&, a_unique_type_for_nil ) { | |
554 | return false; | |
555 | } | |
556 | template <class T> | |
557 | bool operator<( a_unique_type_for_nil, const strict_list<T>& b ) { | |
558 | return !(null(b)()); | |
559 | } | |
560 | ||
561 | ////////////////////////////////////////////////////////////////////// | |
562 | // Class list<T> is the primary interface to the user for lazy lists. | |
563 | //////////////////////////////////////////////////////////////////////{ | |
564 | namespace impl { | |
565 | using fcpp::INV; | |
566 | using fcpp::VAR; | |
567 | using fcpp::reuser2; | |
568 | ||
569 | struct CacheEmpty {}; | |
570 | ||
571 | template <class T> class Cache; | |
572 | template <class T> class odd_list; | |
573 | template <class T> class list_iterator; | |
574 | template <class It, class T> | |
575 | struct ListItHelp2 /*: public c_fun_type<It,It,odd_list<T> >*/ { | |
576 | // This will need a return type. | |
577 | typedef odd_list<T> return_type; | |
578 | odd_list<T> operator()( It begin, const It& end, | |
579 | reuser2<INV,VAR,INV,ListItHelp2<It,T>,It,It> r = NIL ) const; | |
580 | }; | |
581 | template <class U,class F> struct cvt; | |
582 | template <class T, class F, class R> struct ListHelp; | |
583 | template <class T> Cache<T>* xempty_helper(); | |
584 | template <class T, class F, class L, bool b> struct ConsHelp2; | |
585 | ||
586 | struct ListRaw {}; | |
587 | ||
588 | template <class T> | |
589 | class list : public listlike::ListLike | |
590 | { | |
591 | // never NIL, unless an empty odd_list | |
592 | boost::intrusive_ptr<Cache<T> > rep; | |
593 | ||
594 | template <class U> friend class Cache; | |
595 | template <class U> friend class odd_list; | |
596 | template <class TT, class F, class L, bool b> friend struct ConsHelp2; | |
597 | template <class U,class F> friend struct cvt; | |
598 | ||
599 | list( const boost::intrusive_ptr<Cache<T> >& p ) : rep(p) { } | |
600 | list( ListRaw, Cache<T>* p ) : rep(p) { } | |
601 | ||
602 | bool priv_isEmpty() const { | |
603 | return rep->cache().second.rep == Cache<T>::XNIL(); | |
604 | } | |
605 | T priv_head() const { | |
606 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
607 | if( priv_isEmpty() ) | |
608 | throw lazy_exception("Tried to take head() of empty list"); | |
609 | #endif | |
610 | return rep->cache().first(); | |
611 | } | |
612 | list<T> priv_tail() const { | |
613 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
614 | if( priv_isEmpty() ) | |
615 | throw lazy_exception("Tried to take tail() of empty list"); | |
616 | #endif | |
617 | return rep->cache().second; | |
618 | } | |
619 | ||
620 | ||
621 | public: | |
622 | static const bool is_lazy = true; | |
623 | ||
624 | typedef T value_type; | |
625 | typedef list tail_result_type; | |
626 | typedef odd_list<T> force_result_type; | |
627 | typedef list delay_result_type; | |
628 | template <class UU> struct cons_rebind { | |
629 | typedef odd_list<UU> type; | |
630 | typedef list<UU> delay_type; | |
631 | }; | |
632 | ||
633 | list( a_unique_type_for_nil ) : rep( Cache<T>::XEMPTY() ) { } | |
634 | list() : rep( Cache<T>::XEMPTY() ) { } | |
635 | ||
636 | template <class F> // works on both ()->odd_list and ()->list | |
637 | // At the moment this is fixed for odd_list<T>. | |
638 | // I need to do more work to get the general result. | |
639 | list( const F& f ) | |
640 | : rep( ListHelp<T,F,odd_list<T> >()(f) ) { } | |
641 | //: rep( ListHelp<T,F,typename F::result_type>()(f) ) { } | |
642 | ||
643 | operator bool() const { return !priv_isEmpty(); } | |
644 | const force_result_type& force() const { return rep->cache(); } | |
645 | const delay_result_type& delay() const { return *this; } | |
646 | // Note: force returns a reference; | |
647 | // implicit conversion now returns a copy. | |
648 | operator odd_list<T>() const { return force(); } | |
649 | ||
650 | T head() const { return priv_head(); } | |
651 | tail_result_type tail() const { return priv_tail(); } | |
652 | ||
653 | // The following helps makes list almost an STL "container" | |
654 | typedef list_iterator<T> const_iterator; | |
655 | typedef const_iterator iterator; // list is immutable | |
656 | iterator begin() const { return list_iterator<T>( *this ); } | |
657 | iterator end() const { return list_iterator<T>(); } | |
658 | ||
659 | // end of list<T> | |
660 | }; | |
661 | ||
662 | ////////////////////////////////////////////////////////////////////// | |
663 | // Class odd_list<T> is not normally accessed by the user. | |
664 | ////////////////////////////////////////////////////////////////////// | |
665 | ||
666 | struct OddListDummyY {}; | |
667 | ||
668 | template <class T> | |
669 | class odd_list : public listlike::ListLike | |
670 | { | |
671 | public: | |
672 | typedef | |
673 | typename boost::type_with_alignment<boost::alignment_of<T>::value>::type | |
674 | xfst_type; | |
675 | private: | |
676 | union { xfst_type fst; unsigned char dummy[sizeof(T)]; }; | |
677 | ||
678 | const T& first() const { | |
679 | return *static_cast<const T*>(static_cast<const void*>(&fst)); | |
680 | } | |
681 | T& first() { | |
682 | return *static_cast<T*>(static_cast<void*>(&fst)); | |
683 | } | |
684 | list<T> second; // If XNIL, then this odd_list is NIL | |
685 | ||
686 | template <class U> friend class list; | |
687 | template <class U> friend class Cache; | |
688 | ||
689 | odd_list( OddListDummyY ) | |
690 | : second( Cache<T>::XBAD() ) { } | |
691 | ||
692 | void init( const T& x ) { | |
693 | new (static_cast<void*>(&fst)) T(x); | |
694 | } | |
695 | ||
696 | bool fst_is_valid() const { | |
697 | if( second.rep != Cache<T>::XNIL() ) | |
698 | if( second.rep != Cache<T>::XBAD() ) | |
699 | return true; | |
700 | return false; | |
701 | } | |
702 | ||
703 | bool priv_isEmpty() const { return second.rep == Cache<T>::XNIL(); } | |
704 | T priv_head() const { | |
705 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
706 | if( priv_isEmpty() ) | |
707 | throw lazy_exception("Tried to take head() of empty odd_list"); | |
708 | #endif | |
709 | return first(); | |
710 | } | |
711 | ||
712 | list<T> priv_tail() const { | |
713 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
714 | if( priv_isEmpty() ) | |
715 | throw lazy_exception("Tried to take tail() of empty odd_list"); | |
716 | #endif | |
717 | return second; | |
718 | } | |
719 | ||
720 | public: | |
721 | static const bool is_lazy = true; | |
722 | ||
723 | typedef T value_type; | |
724 | typedef list<T> tail_result_type; | |
725 | typedef odd_list<T> force_result_type; | |
726 | typedef list<T> delay_result_type; | |
727 | template <class UU> struct cons_rebind { | |
728 | typedef odd_list<UU> type; | |
729 | typedef list<UU> delay_type; | |
730 | }; | |
731 | ||
732 | odd_list() : second( Cache<T>::XNIL() ) { } | |
733 | odd_list( a_unique_type_for_nil ) : second( Cache<T>::XNIL() ) { } | |
734 | odd_list( const T& x, const list<T>& y ) : second(y) { init(x); } | |
735 | odd_list( const T& x, a_unique_type_for_nil ) : second(NIL) { init(x); } | |
736 | ||
737 | odd_list( const odd_list<T>& x ) : second(x.second) { | |
738 | if( fst_is_valid() ) { | |
739 | init( x.first() ); | |
740 | } | |
741 | } | |
742 | ||
743 | template <class It> | |
744 | odd_list( It begin, const It& end ) | |
745 | : second( begin==end ? Cache<T>::XNIL() : | |
746 | ( init(*begin++), list<T>( begin, end ) ) ) {} | |
747 | ||
748 | odd_list<T>& operator=( const odd_list<T>& x ) { | |
749 | if( this == &x ) return *this; | |
750 | if( fst_is_valid() ) { | |
751 | if( x.fst_is_valid() ) | |
752 | first() = x.first(); | |
753 | else | |
754 | first().~T(); | |
755 | } | |
756 | else { | |
757 | if( x.fst_is_valid() ) | |
758 | init( x.first() ); | |
759 | } | |
760 | second = x.second; | |
761 | return *this; | |
762 | } | |
763 | ||
764 | ~odd_list() { | |
765 | if( fst_is_valid() ) { | |
766 | first().~T(); | |
767 | } | |
768 | } | |
769 | ||
770 | operator bool() const { return !priv_isEmpty(); } | |
771 | const force_result_type& force() const { return *this; } | |
772 | delay_result_type delay() const { return list<T>(*this); } | |
773 | ||
774 | T head() const { return priv_head(); } | |
775 | tail_result_type tail() const { return priv_tail(); } | |
776 | ||
777 | // The following helps makes odd_list almost an STL "container" | |
778 | typedef list_iterator<T> const_iterator; | |
779 | typedef const_iterator iterator; // odd_list is immutable | |
780 | iterator begin() const { return list_iterator<T>( this->delay() ); } | |
781 | iterator end() const { return list_iterator<T>(); } | |
782 | ||
783 | // end of odd_list<T> | |
784 | }; | |
785 | ||
786 | ////////////////////////////////////////////////////////////////////// | |
787 | // struct cvt | |
788 | ////////////////////////////////////////////////////////////////////// | |
789 | ||
790 | // This converts ()->list<T> to ()->odd_list<T>. | |
791 | // In other words, here is the 'extra work' done when using the | |
792 | // unoptimized interface. | |
793 | template <class U,class F> | |
794 | struct cvt /*: public c_fun_type<odd_list<U> >*/ { | |
795 | typedef odd_list<U> return_type; | |
796 | F f; | |
797 | cvt( const F& ff ) : f(ff) {} | |
798 | odd_list<U> operator()() const { | |
799 | list<U> l = f(); | |
800 | return l.force(); | |
801 | } | |
802 | }; | |
803 | ||
804 | ||
805 | ////////////////////////////////////////////////////////////////////// | |
806 | // Cache<T> and associated functions. | |
807 | ////////////////////////////////////////////////////////////////////// | |
808 | ||
809 | // I malloc a RefCountType to hold the refCount and init it to 1 to ensure the | |
810 | // refCount will never get to 0, so the destructor-of-global-object | |
811 | // order at the end of the program is a non-issue. In other words, the | |
812 | // memory allocated here is only reclaimed by the operating system. | |
813 | template <class T> | |
814 | Cache<T>* xnil_helper() { | |
815 | void *p = std::malloc( sizeof(RefCountType) ); | |
816 | *((RefCountType*)p) = 1; | |
817 | return static_cast<Cache<T>*>( p ); | |
818 | } | |
819 | ||
820 | template <class T> | |
821 | Cache<T>* xnil_helper_nil() { | |
822 | Cache<T>* p = xnil_helper<T>(); | |
823 | return p; | |
824 | } | |
825 | ||
826 | template <class T> | |
827 | Cache<T>* xnil_helper_bad() { | |
828 | Cache<T>* p = xnil_helper<T>(); | |
829 | return p; | |
830 | } | |
831 | ||
832 | template <class T> | |
833 | Cache<T>* xempty_helper() { | |
834 | Cache<T>* p = new Cache<T>( CacheEmpty() ); | |
835 | return p; | |
836 | } | |
837 | ||
838 | // This makes a boost phoenix function type with return type | |
839 | // odd_list<T> | |
840 | template <class T> | |
841 | struct fun0_type_helper{ | |
842 | typedef boost::function0<odd_list<T> > fun_type; | |
843 | typedef boost::phoenix::function<fun_type> phx_type; | |
844 | }; | |
845 | ||
846 | ||
847 | template <class T> | |
848 | struct make_fun0_odd_list { | |
849 | ||
850 | typedef typename fun0_type_helper<T>::fun_type fun_type; | |
851 | typedef typename fun0_type_helper<T>::phx_type phx_type; | |
852 | typedef phx_type result_type; | |
853 | ||
854 | template <class F> | |
855 | result_type operator()(const F& f) const | |
856 | { | |
857 | fun_type ff(f); | |
858 | phx_type g(ff); | |
859 | return g; | |
860 | } | |
861 | ||
862 | // Overload for the case where it is a boost phoenix function already. | |
863 | template <class F> | |
864 | typename boost::phoenix::function<F> operator() | |
865 | (const boost::phoenix::function<F>& f) const | |
866 | { | |
867 | return f; | |
868 | } | |
869 | ||
870 | }; | |
871 | ||
872 | template <class T> | |
873 | class Cache : boost::noncopyable { | |
874 | mutable RefCountType refC; | |
875 | // This is the boost::function type | |
876 | typedef typename fun0_type_helper<T>::fun_type fun_odd_list_T; | |
877 | // This is the boost::phoenix::function type; | |
878 | typedef typename fun0_type_helper<T>::phx_type fun0_odd_list_T; | |
879 | mutable fun0_odd_list_T fxn; | |
880 | mutable odd_list<T> val; | |
881 | // val.second.rep can be XBAD, XNIL, or a valid ptr | |
882 | // - XBAD: val is invalid (fxn is valid) | |
883 | // - XNIL: this is the empty list | |
884 | // - anything else: val.first() is head, val.second is tail() | |
885 | ||
886 | // This functoid should never be called; it represents a | |
887 | // self-referent Cache, which should be impossible under the current | |
888 | // implementation. Nonetheless, we need a 'dummy' function object to | |
889 | // represent invalid 'fxn's (val.second.rep!=XBAD), and this | |
890 | // implementation seems to be among the most reasonable. | |
891 | struct blackhole_helper /*: c_fun_type< odd_list<T> >*/ { | |
892 | typedef odd_list<T> return_type; | |
893 | odd_list<T> operator()() const { | |
894 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
895 | throw lazy_exception("You have entered a black hole."); | |
896 | #else | |
897 | return odd_list<T>(); | |
898 | #endif | |
899 | } | |
900 | }; | |
901 | ||
902 | // Don't get rid of these XFOO() functions; they impose no overhead, | |
903 | // and provide a useful place to add debugging code for tracking down | |
904 | // before-main()-order-of-initialization problems. | |
905 | static const boost::intrusive_ptr<Cache<T> >& XEMPTY() { | |
906 | static boost::intrusive_ptr<Cache<T> > xempty( xempty_helper<T>() ); | |
907 | return xempty; | |
908 | } | |
909 | static const boost::intrusive_ptr<Cache<T> >& XNIL() { | |
910 | // this list is nil | |
911 | static boost::intrusive_ptr<Cache<T> > xnil( xnil_helper_nil<T>() ); | |
912 | return xnil; | |
913 | } | |
914 | ||
915 | static const boost::intrusive_ptr<Cache<T> >& XBAD() { | |
916 | // the pair is invalid; use fxn | |
917 | static boost::intrusive_ptr<Cache<T> > xbad( xnil_helper_bad<T>() ); | |
918 | return xbad; | |
919 | } | |
920 | ||
921 | static fun0_odd_list_T /*<odd_list<T> >*/ the_blackhole; | |
922 | static fun0_odd_list_T& blackhole() { | |
923 | static fun0_odd_list_T the_blackhole; | |
924 | //( make_fun0_odd_list<T>()( blackhole_helper() ) ); | |
925 | return the_blackhole; | |
926 | } | |
927 | ||
928 | odd_list<T>& cache() const { | |
929 | if( val.second.rep == XBAD() ) { | |
930 | val = fxn()(); | |
931 | fxn = blackhole(); | |
932 | } | |
933 | return val; | |
934 | } | |
935 | ||
936 | template <class U> friend class list; | |
937 | template <class U> friend class odd_list; | |
938 | template <class TT, class F, class L, bool b> friend struct ConsHelp2; | |
939 | template <class U,class F> friend struct cvt; | |
940 | template <class U, class F, class R> friend struct ListHelp; | |
941 | template <class U> friend Cache<U>* xempty_helper(); | |
942 | ||
943 | Cache( CacheEmpty ) : refC(0), fxn(blackhole()), val() {} | |
944 | Cache( const odd_list<T>& x ) : refC(0), fxn(blackhole()), val(x) {} | |
945 | Cache( const T& x, const list<T>& l ) : refC(0),fxn(blackhole()),val(x,l) | |
946 | {} | |
947 | ||
948 | Cache( const fun0_odd_list_T& f ) | |
949 | : refC(0), fxn(f), val( OddListDummyY() ) {} | |
950 | ||
951 | // f must be a boost phoenix function object? | |
952 | template <class F> | |
953 | Cache( const F& f ) // ()->odd_list | |
954 | : refC(0), fxn(make_fun0_odd_list<T>()(f)), val( OddListDummyY() ) {} | |
955 | ||
956 | // This is for ()->list<T> to ()->odd_list<T> | |
957 | struct CvtFxn {}; | |
958 | template <class F> | |
959 | Cache( CvtFxn, const F& f ) // ()->list | |
960 | : refC(0), fxn(make_fun0_odd_list<T>()(cvt<T,F>(f))), val( OddListDummyY() ) {} | |
961 | ||
962 | template <class X> | |
963 | friend void intrusive_ptr_add_ref( const Cache<X>* p ); | |
964 | template <class X> | |
965 | friend void intrusive_ptr_release( const Cache<X>* p ); | |
966 | }; | |
967 | ||
968 | template <class T> | |
969 | void intrusive_ptr_add_ref( const Cache<T>* p ) { | |
970 | ++ (p->refC); | |
971 | } | |
972 | template <class T> | |
973 | void intrusive_ptr_release( const Cache<T>* p ) { | |
974 | if( !--(p->refC) ) delete p; | |
975 | } | |
976 | ||
977 | ////////////////////////////////////////////////////////////////////// | |
978 | // Rest of list's stuff | |
979 | ////////////////////////////////////////////////////////////////////// | |
980 | ||
981 | template <class T, class F> struct ListHelp<T,F,list<T> > { | |
982 | boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const { | |
983 | return boost::intrusive_ptr<Cache<T> > | |
984 | (new Cache<T>(typename Cache<T>::CvtFxn(),f)); | |
985 | } | |
986 | }; | |
987 | template <class T, class F> struct ListHelp<T,F,odd_list<T> > { | |
988 | boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const { | |
989 | return boost::intrusive_ptr<Cache<T> >(new Cache<T>(f)); | |
990 | } | |
991 | }; | |
992 | ||
993 | template <class T> | |
994 | class list_iterator | |
995 | : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> { | |
996 | list<T> l; | |
997 | bool is_nil; | |
998 | void advance() { | |
999 | l = l.tail(); | |
1000 | if( !l ) | |
1001 | is_nil = true; | |
1002 | } | |
1003 | class Proxy { // needed for operator-> | |
1004 | const T x; | |
1005 | friend class list_iterator; | |
1006 | Proxy( const T& xx ) : x(xx) {} | |
1007 | public: | |
1008 | const T* operator->() const { return &x; } | |
1009 | }; | |
1010 | public: | |
1011 | list_iterator() : l(), is_nil(true) {} | |
1012 | explicit list_iterator( const list<T>& ll ) : l(ll), is_nil(!ll) {} | |
1013 | ||
1014 | const T operator*() const { return l.head(); } | |
1015 | const Proxy operator->() const { return Proxy(l.head()); } | |
1016 | list_iterator<T>& operator++() { | |
1017 | advance(); | |
1018 | return *this; | |
1019 | } | |
1020 | const list_iterator<T> operator++(int) { | |
1021 | list_iterator<T> i( *this ); | |
1022 | advance(); | |
1023 | return i; | |
1024 | } | |
1025 | bool operator==( const list_iterator<T>& i ) const { | |
1026 | return is_nil && i.is_nil; | |
1027 | } | |
1028 | bool operator!=( const list_iterator<T>& i ) const { | |
1029 | return ! this->operator==(i); | |
1030 | } | |
1031 | }; | |
1032 | ||
1033 | ||
1034 | } // namespace impl | |
1035 | ||
1036 | using impl::list; | |
1037 | using impl::odd_list; | |
1038 | using impl::list_iterator; | |
1039 | ||
1040 | ////////////////////////////////////////////////////////////////////// | |
1041 | // op== and op<, overloaded for all combos of list, odd_list, and NIL | |
1042 | ////////////////////////////////////////////////////////////////////// | |
1043 | // All of these null head and tail are now non lazy using e.g. null(a)(). | |
1044 | // They need an extra () e.g. null(a)(). | |
1045 | ||
1046 | // FIX THIS comparison operators can be implemented simpler with enable_if | |
1047 | template <class T> | |
1048 | bool operator==( const odd_list<T>& a, a_unique_type_for_nil ) { | |
1049 | return null(a)(); | |
1050 | } | |
1051 | template <class T> | |
1052 | bool operator==( const list<T>& a, a_unique_type_for_nil ) { | |
1053 | return null(a)(); | |
1054 | } | |
1055 | template <class T> | |
1056 | bool operator==( a_unique_type_for_nil, const odd_list<T>& a ) { | |
1057 | return null(a)(); | |
1058 | } | |
1059 | template <class T> | |
1060 | bool operator==( a_unique_type_for_nil, const list<T>& a ) { | |
1061 | return null(a)(); | |
1062 | } | |
1063 | template <class T> | |
1064 | bool operator==( const list<T>& a, const list<T>& b ) { | |
1065 | if( null(a)() && null(b)() ) | |
1066 | return true; | |
1067 | if( null(a)() || null(b)() ) | |
1068 | return false; | |
1069 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1070 | } | |
1071 | template <class T> | |
1072 | bool operator==( const odd_list<T>& a, const odd_list<T>& b ) { | |
1073 | if( null(a)() && null(b)() ) | |
1074 | return true; | |
1075 | if( null(a)() || null(b)() ) | |
1076 | return false; | |
1077 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1078 | } | |
1079 | template <class T> | |
1080 | bool operator==( const list<T>& a, const odd_list<T>& b ) { | |
1081 | if( null(a)() && null(b)() ) | |
1082 | return true; | |
1083 | if( null(a)() || null(b)() ) | |
1084 | return false; | |
1085 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1086 | } | |
1087 | template <class T> | |
1088 | bool operator==( const odd_list<T>& a, const list<T>& b ) { | |
1089 | if( null(a)() && null(b)() ) | |
1090 | return true; | |
1091 | if( null(a)() || null(b)() ) | |
1092 | return false; | |
1093 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1094 | } | |
1095 | ||
1096 | template <class T> | |
1097 | bool operator<( const list<T>& a, const list<T>& b ) { | |
1098 | if( null(a)() && !null(b)() ) return true; | |
1099 | if( null(b)() ) return false; | |
1100 | if( head(b)() < head(a)() ) return false; | |
1101 | if( head(a)() < head(b)() ) return true; | |
1102 | return (tail(a)() < tail(b)()); | |
1103 | } | |
1104 | template <class T> | |
1105 | bool operator<( const odd_list<T>& a, const list<T>& b ) { | |
1106 | if( null(a)() && !null(b)() ) return true; | |
1107 | if( null(b)() ) return false; | |
1108 | if( head(b)() < head(a)() ) return false; | |
1109 | if( head(a)() < head(b)() ) return true; | |
1110 | return (tail(a)() < tail(b)()); | |
1111 | } | |
1112 | template <class T> | |
1113 | bool operator<( const list<T>& a, const odd_list<T>& b ) { | |
1114 | if( null(a) && !null(b) ) return true; | |
1115 | if( null(b) ) return false; | |
1116 | if( head(b) < head(a) ) return false; | |
1117 | if( head(a) < head(b) ) return true; | |
1118 | return (tail(a) < tail(b)); | |
1119 | } | |
1120 | template <class T> | |
1121 | bool operator<( const odd_list<T>& a, const odd_list<T>& b ) { | |
1122 | if( null(a)() && !null(b)() ) return true; | |
1123 | if( null(b)() ) return false; | |
1124 | if( head(b)() < head(a)() ) return false; | |
1125 | if( head(a)() < head(b)() ) return true; | |
1126 | return (tail(a)() < tail(b)()); | |
1127 | } | |
1128 | template <class T> | |
1129 | bool operator<( const odd_list<T>&, a_unique_type_for_nil ) { | |
1130 | return false; | |
1131 | } | |
1132 | template <class T> | |
1133 | bool operator<( const list<T>&, a_unique_type_for_nil ) { | |
1134 | return false; | |
1135 | } | |
1136 | template <class T> | |
1137 | bool operator<( a_unique_type_for_nil, const odd_list<T>& b ) { | |
1138 | return !null(b)(); | |
1139 | } | |
1140 | template <class T> | |
1141 | bool operator<( a_unique_type_for_nil, const list<T>& b ) { | |
1142 | return !null(b)(); | |
1143 | } | |
1144 | ||
1145 | ////////////////////////////////////////////////////////////////////// | |
1146 | // Implement cat and cons after the list types are defined. | |
1147 | ////////////////////////////////////////////////////////////////////// | |
1148 | namespace impl { | |
1149 | using listlike::ListLike; | |
1150 | ||
1151 | template <class T, class F, class L> | |
1152 | struct ConsHelp2<T,F,L,true> | |
1153 | { | |
1154 | typedef typename boost::remove_reference<T>::type TT; | |
1155 | typedef typename L::force_result_type type; | |
1156 | static type go( const TT& x, const F& f ) { | |
1157 | return type( x, f ); | |
1158 | } | |
1159 | }; | |
1160 | template <class T, class F> | |
1161 | struct ConsHelp2<T,F,list<T>,true> | |
1162 | { | |
1163 | typedef typename boost::remove_reference<T>::type TT; | |
1164 | typedef list<TT> L; | |
1165 | typedef typename L::force_result_type type; | |
1166 | static type go( const TT& x, const F& f ) { | |
1167 | return odd_list<TT>(x, list<TT>( | |
1168 | boost::intrusive_ptr<Cache<TT> >(new Cache<T>( | |
1169 | typename Cache<TT>::CvtFxn(),f)))); | |
1170 | } | |
1171 | }; | |
1172 | template <class T, class F> | |
1173 | struct ConsHelp2<T,F,odd_list<T>,true> | |
1174 | { | |
1175 | typedef typename boost::remove_reference<T>::type TT; | |
1176 | typedef odd_list<TT> L; | |
1177 | typedef typename L::force_result_type type; | |
1178 | static type go( const TT& x, const F& f ) { | |
1179 | return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) )); | |
1180 | } | |
1181 | }; | |
1182 | template <class T, class F> | |
1183 | struct ConsHelp2<T,F,a_unique_type_for_nil,false> | |
1184 | { | |
1185 | typedef typename boost::remove_reference<T>::type TT; | |
1186 | typedef odd_list<TT> type; | |
1187 | static type go( const TT& x, const F& f ) { | |
1188 | return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) )); | |
1189 | } | |
1190 | }; | |
1191 | ||
1192 | template <class T, class L, bool b> struct ConsHelp1 { | |
1193 | typedef typename boost::remove_reference<T>::type TT; | |
1194 | typedef typename L::force_result_type type; | |
1195 | static type go( const TT& x, const L& l ) { | |
1196 | return type(x,l); | |
1197 | } | |
1198 | }; | |
1199 | template <class T> struct ConsHelp1<T,a_unique_type_for_nil,false> { | |
1200 | typedef typename boost::remove_reference<T>::type TT; | |
1201 | typedef odd_list<TT> type; | |
1202 | static type go( const TT& x, const a_unique_type_for_nil& n ) { | |
1203 | return type(x,n); | |
1204 | } | |
1205 | }; | |
1206 | template <class T, class F> struct ConsHelp1<T,F,false> { | |
1207 | // It's a function returning a list | |
1208 | // This is the one I have not fixed yet.... | |
1209 | // typedef typename F::result_type L; | |
1210 | // typedef typename result_of::template ListType<F>::result_type L; | |
1211 | typedef odd_list<T> L; | |
1212 | typedef ConsHelp2<T,F,L,boost::is_base_and_derived<ListLike,L>::value> help; | |
1213 | typedef typename help::type type; | |
1214 | static type go( const T& x, const F& f ) { | |
1215 | return help::go(x,f); | |
1216 | } | |
1217 | }; | |
1218 | ||
1219 | template <class T, class L, bool b> | |
1220 | struct ConsHelp0; | |
1221 | ||
1222 | template <class T> | |
1223 | struct ConsHelp0<T,a_unique_type_for_nil,true> { | |
1224 | typedef typename boost::remove_reference<T>::type TT; | |
1225 | typedef odd_list<T> type; | |
1226 | }; | |
1227 | ||
1228 | template <class T> | |
1229 | struct ConsHelp0<const T &,const a_unique_type_for_nil &,true> { | |
1230 | typedef typename boost::remove_reference<T>::type TT; | |
1231 | typedef odd_list<TT> type; | |
1232 | }; | |
1233 | ||
1234 | template <class T> | |
1235 | struct ConsHelp0<T &,a_unique_type_for_nil &,true> { | |
1236 | typedef typename boost::remove_reference<T>::type TT; | |
1237 | typedef odd_list<TT> type; | |
1238 | }; | |
1239 | ||
1240 | template <class T, class L> | |
1241 | struct ConsHelp0<T,L,false> { | |
1242 | // This removes any references from L for correct return type | |
1243 | // identification. | |
1244 | typedef typename boost::remove_reference<L>::type LType; | |
1245 | typedef typename ConsHelp1<T,LType, | |
1246 | boost::is_base_and_derived<ListLike,LType>::value>::type type; | |
1247 | }; | |
1248 | ||
1249 | ///////////////////////////////////////////////////////////////////// | |
1250 | // cons (t,l) - cons a value to the front of a list. | |
1251 | // Note: The first arg, t, must be a value. | |
1252 | // The second arg, l, can be a list or NIL | |
1253 | // or a function that returns a list. | |
1254 | ///////////////////////////////////////////////////////////////////// | |
1255 | struct Cons | |
1256 | { | |
1257 | /* template <class T, class L> struct sig : public fun_type< | |
1258 | typename ConsHelp1<T,L, | |
1259 | boost::is_base_and_derived<ListLike,L>::value>::type> {}; | |
1260 | */ | |
1261 | template <typename Sig> struct result; | |
1262 | ||
1263 | template <typename This, typename T, typename L> | |
1264 | struct result<This(T, L)> | |
1265 | { | |
1266 | typedef typename ConsHelp0<T,L, | |
1267 | listlike::detect_nil<L>::is_nil>::type type; | |
1268 | }; | |
1269 | ||
1270 | template <typename This, typename T> | |
1271 | struct result<This(T,a_unique_type_for_nil)> | |
1272 | { | |
1273 | typedef typename boost::remove_reference<T>::type TT; | |
1274 | typedef odd_list<TT> type; | |
1275 | }; | |
1276 | ||
1277 | template <typename T, typename L> | |
1278 | typename result<Cons(T,L)>::type | |
1279 | operator()( const T& x, const L& l ) const { | |
1280 | typedef typename result_of::ListType<L>::LType LType; | |
1281 | typedef ConsHelp1<T,LType, | |
1282 | boost::is_base_and_derived<ListLike,LType>::value> help; | |
1283 | return help::go(x,l); | |
1284 | } | |
1285 | ||
1286 | template <typename T> | |
1287 | typename result<Cons(T,a_unique_type_for_nil)>::type | |
1288 | operator()( const T& x, const a_unique_type_for_nil &n ) const { | |
1289 | typedef typename result<Cons(T,a_unique_type_for_nil)>::type LL; | |
1290 | typedef ConsHelp1<T,LL, | |
1291 | boost::is_base_and_derived<ListLike,LL>::value> help; | |
1292 | return help::go(x,n); | |
1293 | } | |
1294 | ||
1295 | }; | |
1296 | } | |
1297 | ||
1298 | typedef boost::phoenix::function<impl::Cons> Cons; | |
1299 | Cons cons; | |
1300 | ||
1301 | namespace impl { | |
1302 | ||
1303 | template <class L, class M, bool b> | |
1304 | struct CatHelp0; | |
1305 | ||
1306 | template <class LL> | |
1307 | struct CatHelp0<LL,a_unique_type_for_nil,true> { | |
1308 | typedef typename result_of::template ListType<LL>::LType type; | |
1309 | }; | |
1310 | ||
1311 | template <class LL> | |
1312 | struct CatHelp0<const LL &,const a_unique_type_for_nil &,true> { | |
1313 | typedef typename result_of::template ListType<LL>::LType type; | |
1314 | //typedef L type; | |
1315 | }; | |
1316 | ||
1317 | template <class LL> | |
1318 | struct CatHelp0<LL &,a_unique_type_for_nil &,true> { | |
1319 | typedef typename result_of::template ListType<LL>::LType type; | |
1320 | //typedef L type; | |
1321 | }; | |
1322 | ||
1323 | template <class LL, class MM> | |
1324 | struct CatHelp0<LL,MM,false> { | |
1325 | // This removes any references from L for correct return type | |
1326 | // identification. | |
1327 | typedef typename result_of::template ListType<LL>::LType type; | |
1328 | // typedef typename ConsHelp1<T,LType, | |
1329 | // boost::is_base_and_derived<ListLike,LType>::value>::type type; | |
1330 | }; | |
1331 | ||
1332 | ///////////////////////////////////////////////////////////////////// | |
1333 | // cat (l,m) - concatenate lists. | |
1334 | // Note: The first arg, l, must be a list or NIL. | |
1335 | // The second arg, m, can be a list or NIL | |
1336 | // or a function that returns a list. | |
1337 | ///////////////////////////////////////////////////////////////////// | |
1338 | struct Cat | |
1339 | { | |
1340 | template <class L, class M, bool b, class R> | |
1341 | struct Helper /*: public c_fun_type<L,M,R>*/ { | |
1342 | template <typename Sig> struct result; | |
1343 | ||
1344 | template <typename This> | |
1345 | struct result<This(L,M)> | |
1346 | { | |
1347 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1348 | }; | |
1349 | ||
1350 | typedef R return_type; | |
1351 | R operator()( const L& l, const M& m, | |
1352 | reuser2<INV,VAR,INV,Helper, | |
1353 | typename result_of::template ListType<L>::tail_result_type,M> | |
1354 | r = NIL ) const { | |
1355 | if( null(l)() ) | |
1356 | return m().force(); | |
1357 | else | |
1358 | return cons( head(l)(), r( Helper<L,M,b,R>(), tail(l), m )() ); | |
1359 | } | |
1360 | }; | |
1361 | template <class L, class M, class R> | |
1362 | struct Helper<L,M,true,R> /*: public c_fun_type<L,M,R>*/ { | |
1363 | template <typename Sig> struct result; | |
1364 | ||
1365 | template <typename This> | |
1366 | struct result<This(L,M)> | |
1367 | { | |
1368 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1369 | }; | |
1370 | typedef R return_type; | |
1371 | R operator()( const L& l, const M& m, | |
1372 | reuser2<INV,VAR,INV,Helper, | |
1373 | typename result_of::template ListType<L>::tail_result_type,M> | |
1374 | r = NIL ) const { | |
1375 | if( null(l)() ) | |
1376 | return m.force(); | |
1377 | else | |
1378 | return cons( head(l)(), r(Helper<L,M,true,R>(), tail(l), m )()); | |
1379 | } | |
1380 | }; | |
1381 | template <class L, class R> | |
1382 | struct Helper<L,a_unique_type_for_nil,false,R> | |
1383 | /*: public c_fun_type<L, | |
1384 | a_unique_type_for_nil,odd_list<typename L::value_type> > */ | |
1385 | { | |
1386 | typedef odd_list<typename result_of::template ListType<L>::value_type> type; | |
1387 | odd_list<typename result_of::template ListType<L>::value_type> | |
1388 | operator()( const L& l, const a_unique_type_for_nil& ) const { | |
1389 | return l; | |
1390 | } | |
1391 | }; | |
1392 | public: | |
1393 | /*template <class L, class M> struct sig : public fun_type< | |
1394 | typename RT<cons_type,typename L::value_type,M>::result_type> | |
1395 | {}; */ | |
1396 | // Need to work out the return type here. | |
1397 | template <typename Sig> struct result; | |
1398 | ||
1399 | template <typename This, typename L, typename M> | |
1400 | struct result<This(L,M)> | |
1401 | { | |
1402 | typedef typename CatHelp0<L,M, | |
1403 | listlike::detect_nil<M>::is_nil>::type type; | |
1404 | // typedef typename result_of::ListType<L>::tail_result_type type; | |
1405 | }; | |
1406 | ||
1407 | template <typename This, typename L> | |
1408 | struct result<This(L,a_unique_type_for_nil)> | |
1409 | { | |
1410 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1411 | }; | |
1412 | template <class L, class M> | |
1413 | typename result<Cat(L,M)>::type operator()( const L& l, const M& m ) const | |
1414 | { | |
1415 | listlike::EnsureListLike<L>(); | |
1416 | return Helper<L,M, | |
1417 | boost::is_base_and_derived<typename listlike::ListLike,M>::value, | |
1418 | typename result<Cat(L,M)>::type>()(l,m); | |
1419 | } | |
1420 | ||
1421 | template <class L> | |
1422 | typename result<Cat(L,a_unique_type_for_nil)>::type operator()( const L& l, const a_unique_type_for_nil& /* n */ ) const | |
1423 | { | |
1424 | listlike::EnsureListLike<L>(); | |
1425 | return l; | |
1426 | } | |
1427 | ||
1428 | }; | |
1429 | ||
1430 | ||
1431 | } | |
1432 | ||
1433 | typedef boost::phoenix::function<impl::Cat> Cat; | |
1434 | Cat cat; | |
1435 | ||
1436 | ||
1437 | ////////////////////////////////////////////////////////////////////// | |
1438 | // Handy functions for making list literals | |
1439 | ////////////////////////////////////////////////////////////////////// | |
1440 | // Yes, these aren't functoids, they're just template functions. I'm | |
1441 | // lazy and created these mostly to make it easily to make little lists | |
1442 | // in the sample code snippets that appear in papers. | |
1443 | ||
1444 | struct UseList { | |
1445 | template <class T> struct List { typedef list<T> type; }; | |
1446 | }; | |
1447 | struct UseOddList { | |
1448 | template <class T> struct List { typedef odd_list<T> type; }; | |
1449 | }; | |
1450 | struct UseStrictList { | |
1451 | template <class T> struct List { typedef strict_list<T> type; }; | |
1452 | }; | |
1453 | ||
1454 | template <class Kind = UseList> | |
1455 | struct list_with { | |
1456 | template <class T> | |
1457 | typename Kind::template List<T>::type | |
1458 | operator()( const T& a ) const { | |
1459 | typename Kind::template List<T>::type l; | |
1460 | l = cons( a, l ); | |
1461 | return l; | |
1462 | } | |
1463 | ||
1464 | template <class T> | |
1465 | typename Kind::template List<T>::type | |
1466 | operator()( const T& a, const T& b ) const { | |
1467 | typename Kind::template List<T>::type l; | |
1468 | l = cons( b, l ); | |
1469 | l = cons( a, l ); | |
1470 | return l; | |
1471 | } | |
1472 | ||
1473 | template <class T> | |
1474 | typename Kind::template List<T>::type | |
1475 | operator()( const T& a, const T& b, const T& c ) const { | |
1476 | typename Kind::template List<T>::type l; | |
1477 | l = cons( c, l ); | |
1478 | l = cons( b, l ); | |
1479 | l = cons( a, l ); | |
1480 | return l; | |
1481 | } | |
1482 | ||
1483 | template <class T> | |
1484 | typename Kind::template List<T>::type | |
1485 | operator()( const T& a, const T& b, const T& c, const T& d ) const { | |
1486 | typename Kind::template List<T>::type l; | |
1487 | l = cons( d, l ); | |
1488 | l = cons( c, l ); | |
1489 | l = cons( b, l ); | |
1490 | l = cons( a, l ); | |
1491 | return l; | |
1492 | } | |
1493 | ||
1494 | template <class T> | |
1495 | typename Kind::template List<T>::type | |
1496 | operator()( const T& a, const T& b, const T& c, const T& d, | |
1497 | const T& e ) const { | |
1498 | typename Kind::template List<T>::type l; | |
1499 | l = cons( e, l ); | |
1500 | l = cons( d, l ); | |
1501 | l = cons( c, l ); | |
1502 | l = cons( b, l ); | |
1503 | l = cons( a, l ); | |
1504 | return l; | |
1505 | } | |
1506 | }; | |
1507 | ////////////////////////////////////////////////////////////////////// | |
1508 | ||
1509 | } | |
1510 | ||
1511 | } | |
1512 | ||
1513 | #endif |