]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
11fdf7f2 | 391 | class strict_list_iterator { |
7c673cae FG |
392 | typedef boost::intrusive_ptr<strict_cons<T> > rep_type; |
393 | rep_type l; | |
394 | bool is_nil; | |
395 | void advance() { | |
396 | l = l->tail; | |
397 | if( !l ) | |
398 | is_nil = true; | |
399 | } | |
400 | class Proxy { // needed for operator-> | |
401 | const T x; | |
402 | friend class strict_list_iterator; | |
403 | Proxy( const T& xx ) : x(xx) {} | |
404 | public: | |
405 | const T* operator->() const { return &x; } | |
406 | }; | |
407 | public: | |
11fdf7f2 TL |
408 | typedef std::input_iterator_tag iterator_category; |
409 | typedef T value_type; | |
410 | typedef ptrdiff_t difference_type; | |
411 | typedef T* pointer; | |
412 | typedef T& reference; | |
413 | ||
7c673cae FG |
414 | strict_list_iterator() : l(), is_nil(true) {} |
415 | explicit strict_list_iterator( const rep_type& ll ) : l(ll), is_nil(!ll) {} | |
416 | ||
417 | const T operator*() const { return l->head; } | |
418 | const Proxy operator->() const { return Proxy(l->head); } | |
419 | strict_list_iterator<T>& operator++() { | |
420 | advance(); | |
421 | return *this; | |
422 | } | |
423 | const strict_list_iterator<T> operator++(int) { | |
424 | strict_list_iterator<T> i( *this ); | |
425 | advance(); | |
426 | return i; | |
427 | } | |
428 | bool operator==( const strict_list_iterator<T>& i ) const { | |
429 | return is_nil && i.is_nil; | |
430 | } | |
431 | bool operator!=( const strict_list_iterator<T>& i ) const { | |
432 | return ! this->operator==(i); | |
433 | } | |
434 | }; | |
435 | } | |
436 | ||
437 | ////////////////////////////////////////////////////////////////////// | |
438 | ////////////////////////////////////////////////////////////////////// | |
439 | ||
440 | template <class T> | |
441 | class strict_list : public listlike::ListLike | |
442 | { | |
443 | typedef boost::intrusive_ptr<impl::strict_cons<T> > rep_type; | |
444 | rep_type rep; | |
445 | struct Make {}; | |
446 | ||
447 | template <class Iter> | |
448 | static rep_type help( Iter a, const Iter& b ) { | |
449 | rep_type r; | |
450 | while( a != b ) { | |
451 | T x( *a ); | |
452 | r = rep_type( new impl::strict_cons<T>( x, r ) ); | |
453 | ++a; | |
454 | } | |
455 | return r; | |
456 | } | |
457 | ||
458 | public: | |
459 | static const bool is_lazy = false; | |
460 | ||
461 | typedef T value_type; | |
462 | typedef strict_list force_result_type; | |
463 | typedef strict_list delay_result_type; | |
464 | typedef strict_list tail_result_type; | |
465 | template <class UU> struct cons_rebind { | |
466 | typedef strict_list<UU> type; | |
467 | typedef strict_list<UU> delay_type; | |
468 | }; | |
469 | ||
470 | ||
471 | strict_list( Make, const rep_type& r ) : rep(r) {} | |
472 | ||
473 | strict_list() : rep() {} | |
474 | ||
475 | strict_list( a_unique_type_for_nil ) : rep() {} | |
476 | ||
477 | template <class F> | |
478 | strict_list( const F& f ) : rep( f().rep ) { | |
479 | // I cannot do this yet. | |
480 | //functoid_traits<F>::template ensure_accepts<0>::args(); | |
481 | } | |
482 | ||
483 | strict_list( const T& x, const strict_list& y ) | |
484 | : rep( new impl::strict_cons<T>(x,y.rep) ) {} | |
485 | ||
486 | template <class F> | |
487 | strict_list( const T& x, const F& f ) | |
488 | : rep( new impl::strict_cons<T>(x,f().rep) ) {} | |
489 | ||
490 | operator bool() const { return (bool)rep; } | |
491 | force_result_type force() const { return *this; } | |
492 | delay_result_type delay() const { return *this; } | |
493 | T head() const { | |
494 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
495 | if( !*this ) | |
496 | throw lazy_exception("Tried to take head() of empty strict_list"); | |
497 | #endif | |
498 | return rep->head; | |
499 | } | |
500 | tail_result_type tail() const { | |
501 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
502 | if( !*this ) | |
503 | throw lazy_exception("Tried to take tail() of empty strict_list"); | |
504 | #endif | |
505 | return strict_list(Make(),rep->tail); | |
506 | } | |
507 | ||
508 | template <class Iter> | |
509 | strict_list( const Iter& a, const Iter& b ) : rep( rep_type() ) { | |
510 | // How ironic. We need to reverse the iterator range in order to | |
511 | // non-recursively build this! | |
512 | std::vector<T> tmp(a,b); | |
513 | rep = help( tmp.rbegin(), tmp.rend() ); | |
514 | } | |
515 | ||
516 | // Since the strict_cons destructor can't call the strict_list | |
517 | // destructor, the "simple" iterative destructor is correct and | |
518 | // efficient. Hurray. | |
519 | ~strict_list() { while(rep && (rep->refC == 1)) rep = rep->tail; } | |
520 | ||
521 | // The following helps makes strict_list almost an STL "container" | |
522 | typedef impl::strict_list_iterator<T> const_iterator; | |
523 | typedef const_iterator iterator; // strict_list is immutable | |
524 | iterator begin() const { return impl::strict_list_iterator<T>( rep ); } | |
525 | iterator end() const { return impl::strict_list_iterator<T>(); } | |
526 | ||
527 | }; | |
528 | ||
529 | // All of these null head and tail are now non lazy using e.g. null(a)(). | |
530 | // They need an extra () e.g. null(a)(). | |
531 | template <class T> | |
532 | bool operator==( const strict_list<T>& a, a_unique_type_for_nil ) { | |
533 | return null(a)(); | |
534 | } | |
535 | template <class T> | |
536 | bool operator==( a_unique_type_for_nil, const strict_list<T>& a ) { | |
537 | return null(a)(); | |
538 | } | |
539 | template <class T> | |
540 | bool operator==( const strict_list<T>& a, const strict_list<T>& b ) { | |
541 | if( null(a)() && null(b)() ) | |
542 | return true; | |
543 | if( null(a)() || null(b)() ) | |
544 | return false; | |
545 | return (head(a)()==head(b)()) && | |
546 | (tail(a)()==tail(b)()); | |
547 | } | |
548 | ||
549 | template <class T> | |
550 | bool operator<( const strict_list<T>& a, const strict_list<T>& b ) { | |
551 | if( null(a)() && !null(b)() ) return true; | |
552 | if( null(b)() ) return false; | |
553 | if( head(b)() < head(a)() ) return false; | |
554 | if( head(a)() < head(b)() ) return true; | |
555 | return (tail(a)() < tail(b)()); | |
556 | } | |
557 | template <class T> | |
558 | bool operator<( const strict_list<T>&, a_unique_type_for_nil ) { | |
559 | return false; | |
560 | } | |
561 | template <class T> | |
562 | bool operator<( a_unique_type_for_nil, const strict_list<T>& b ) { | |
563 | return !(null(b)()); | |
564 | } | |
565 | ||
566 | ////////////////////////////////////////////////////////////////////// | |
567 | // Class list<T> is the primary interface to the user for lazy lists. | |
568 | //////////////////////////////////////////////////////////////////////{ | |
569 | namespace impl { | |
570 | using fcpp::INV; | |
571 | using fcpp::VAR; | |
572 | using fcpp::reuser2; | |
573 | ||
574 | struct CacheEmpty {}; | |
575 | ||
576 | template <class T> class Cache; | |
577 | template <class T> class odd_list; | |
578 | template <class T> class list_iterator; | |
579 | template <class It, class T> | |
580 | struct ListItHelp2 /*: public c_fun_type<It,It,odd_list<T> >*/ { | |
581 | // This will need a return type. | |
582 | typedef odd_list<T> return_type; | |
583 | odd_list<T> operator()( It begin, const It& end, | |
584 | reuser2<INV,VAR,INV,ListItHelp2<It,T>,It,It> r = NIL ) const; | |
585 | }; | |
586 | template <class U,class F> struct cvt; | |
587 | template <class T, class F, class R> struct ListHelp; | |
588 | template <class T> Cache<T>* xempty_helper(); | |
589 | template <class T, class F, class L, bool b> struct ConsHelp2; | |
590 | ||
591 | struct ListRaw {}; | |
592 | ||
593 | template <class T> | |
594 | class list : public listlike::ListLike | |
595 | { | |
596 | // never NIL, unless an empty odd_list | |
597 | boost::intrusive_ptr<Cache<T> > rep; | |
598 | ||
599 | template <class U> friend class Cache; | |
600 | template <class U> friend class odd_list; | |
601 | template <class TT, class F, class L, bool b> friend struct ConsHelp2; | |
602 | template <class U,class F> friend struct cvt; | |
603 | ||
604 | list( const boost::intrusive_ptr<Cache<T> >& p ) : rep(p) { } | |
605 | list( ListRaw, Cache<T>* p ) : rep(p) { } | |
606 | ||
607 | bool priv_isEmpty() const { | |
608 | return rep->cache().second.rep == Cache<T>::XNIL(); | |
609 | } | |
610 | T priv_head() const { | |
611 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
612 | if( priv_isEmpty() ) | |
613 | throw lazy_exception("Tried to take head() of empty list"); | |
614 | #endif | |
615 | return rep->cache().first(); | |
616 | } | |
617 | list<T> priv_tail() const { | |
618 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
619 | if( priv_isEmpty() ) | |
620 | throw lazy_exception("Tried to take tail() of empty list"); | |
621 | #endif | |
622 | return rep->cache().second; | |
623 | } | |
624 | ||
625 | ||
626 | public: | |
627 | static const bool is_lazy = true; | |
628 | ||
629 | typedef T value_type; | |
630 | typedef list tail_result_type; | |
631 | typedef odd_list<T> force_result_type; | |
632 | typedef list delay_result_type; | |
633 | template <class UU> struct cons_rebind { | |
634 | typedef odd_list<UU> type; | |
635 | typedef list<UU> delay_type; | |
636 | }; | |
637 | ||
638 | list( a_unique_type_for_nil ) : rep( Cache<T>::XEMPTY() ) { } | |
639 | list() : rep( Cache<T>::XEMPTY() ) { } | |
640 | ||
641 | template <class F> // works on both ()->odd_list and ()->list | |
642 | // At the moment this is fixed for odd_list<T>. | |
643 | // I need to do more work to get the general result. | |
644 | list( const F& f ) | |
645 | : rep( ListHelp<T,F,odd_list<T> >()(f) ) { } | |
646 | //: rep( ListHelp<T,F,typename F::result_type>()(f) ) { } | |
647 | ||
648 | operator bool() const { return !priv_isEmpty(); } | |
649 | const force_result_type& force() const { return rep->cache(); } | |
650 | const delay_result_type& delay() const { return *this; } | |
651 | // Note: force returns a reference; | |
652 | // implicit conversion now returns a copy. | |
653 | operator odd_list<T>() const { return force(); } | |
654 | ||
655 | T head() const { return priv_head(); } | |
656 | tail_result_type tail() const { return priv_tail(); } | |
657 | ||
658 | // The following helps makes list almost an STL "container" | |
659 | typedef list_iterator<T> const_iterator; | |
660 | typedef const_iterator iterator; // list is immutable | |
661 | iterator begin() const { return list_iterator<T>( *this ); } | |
662 | iterator end() const { return list_iterator<T>(); } | |
663 | ||
664 | // end of list<T> | |
665 | }; | |
666 | ||
667 | ////////////////////////////////////////////////////////////////////// | |
668 | // Class odd_list<T> is not normally accessed by the user. | |
669 | ////////////////////////////////////////////////////////////////////// | |
670 | ||
671 | struct OddListDummyY {}; | |
672 | ||
673 | template <class T> | |
674 | class odd_list : public listlike::ListLike | |
675 | { | |
676 | public: | |
677 | typedef | |
678 | typename boost::type_with_alignment<boost::alignment_of<T>::value>::type | |
679 | xfst_type; | |
680 | private: | |
681 | union { xfst_type fst; unsigned char dummy[sizeof(T)]; }; | |
682 | ||
683 | const T& first() const { | |
684 | return *static_cast<const T*>(static_cast<const void*>(&fst)); | |
685 | } | |
686 | T& first() { | |
687 | return *static_cast<T*>(static_cast<void*>(&fst)); | |
688 | } | |
689 | list<T> second; // If XNIL, then this odd_list is NIL | |
690 | ||
691 | template <class U> friend class list; | |
692 | template <class U> friend class Cache; | |
693 | ||
694 | odd_list( OddListDummyY ) | |
695 | : second( Cache<T>::XBAD() ) { } | |
696 | ||
697 | void init( const T& x ) { | |
698 | new (static_cast<void*>(&fst)) T(x); | |
699 | } | |
700 | ||
701 | bool fst_is_valid() const { | |
702 | if( second.rep != Cache<T>::XNIL() ) | |
703 | if( second.rep != Cache<T>::XBAD() ) | |
704 | return true; | |
705 | return false; | |
706 | } | |
707 | ||
708 | bool priv_isEmpty() const { return second.rep == Cache<T>::XNIL(); } | |
709 | T priv_head() const { | |
710 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
711 | if( priv_isEmpty() ) | |
712 | throw lazy_exception("Tried to take head() of empty odd_list"); | |
713 | #endif | |
714 | return first(); | |
715 | } | |
716 | ||
717 | list<T> priv_tail() const { | |
718 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
719 | if( priv_isEmpty() ) | |
720 | throw lazy_exception("Tried to take tail() of empty odd_list"); | |
721 | #endif | |
722 | return second; | |
723 | } | |
724 | ||
725 | public: | |
726 | static const bool is_lazy = true; | |
727 | ||
728 | typedef T value_type; | |
729 | typedef list<T> tail_result_type; | |
730 | typedef odd_list<T> force_result_type; | |
731 | typedef list<T> delay_result_type; | |
732 | template <class UU> struct cons_rebind { | |
733 | typedef odd_list<UU> type; | |
734 | typedef list<UU> delay_type; | |
735 | }; | |
736 | ||
737 | odd_list() : second( Cache<T>::XNIL() ) { } | |
738 | odd_list( a_unique_type_for_nil ) : second( Cache<T>::XNIL() ) { } | |
739 | odd_list( const T& x, const list<T>& y ) : second(y) { init(x); } | |
740 | odd_list( const T& x, a_unique_type_for_nil ) : second(NIL) { init(x); } | |
741 | ||
742 | odd_list( const odd_list<T>& x ) : second(x.second) { | |
743 | if( fst_is_valid() ) { | |
744 | init( x.first() ); | |
745 | } | |
746 | } | |
747 | ||
748 | template <class It> | |
749 | odd_list( It begin, const It& end ) | |
750 | : second( begin==end ? Cache<T>::XNIL() : | |
751 | ( init(*begin++), list<T>( begin, end ) ) ) {} | |
752 | ||
753 | odd_list<T>& operator=( const odd_list<T>& x ) { | |
754 | if( this == &x ) return *this; | |
755 | if( fst_is_valid() ) { | |
756 | if( x.fst_is_valid() ) | |
757 | first() = x.first(); | |
758 | else | |
759 | first().~T(); | |
760 | } | |
761 | else { | |
762 | if( x.fst_is_valid() ) | |
763 | init( x.first() ); | |
764 | } | |
765 | second = x.second; | |
766 | return *this; | |
767 | } | |
768 | ||
769 | ~odd_list() { | |
770 | if( fst_is_valid() ) { | |
771 | first().~T(); | |
772 | } | |
773 | } | |
774 | ||
775 | operator bool() const { return !priv_isEmpty(); } | |
776 | const force_result_type& force() const { return *this; } | |
777 | delay_result_type delay() const { return list<T>(*this); } | |
778 | ||
779 | T head() const { return priv_head(); } | |
780 | tail_result_type tail() const { return priv_tail(); } | |
781 | ||
782 | // The following helps makes odd_list almost an STL "container" | |
783 | typedef list_iterator<T> const_iterator; | |
784 | typedef const_iterator iterator; // odd_list is immutable | |
785 | iterator begin() const { return list_iterator<T>( this->delay() ); } | |
786 | iterator end() const { return list_iterator<T>(); } | |
787 | ||
788 | // end of odd_list<T> | |
789 | }; | |
790 | ||
791 | ////////////////////////////////////////////////////////////////////// | |
792 | // struct cvt | |
793 | ////////////////////////////////////////////////////////////////////// | |
794 | ||
795 | // This converts ()->list<T> to ()->odd_list<T>. | |
796 | // In other words, here is the 'extra work' done when using the | |
797 | // unoptimized interface. | |
798 | template <class U,class F> | |
799 | struct cvt /*: public c_fun_type<odd_list<U> >*/ { | |
800 | typedef odd_list<U> return_type; | |
801 | F f; | |
802 | cvt( const F& ff ) : f(ff) {} | |
803 | odd_list<U> operator()() const { | |
804 | list<U> l = f(); | |
805 | return l.force(); | |
806 | } | |
807 | }; | |
808 | ||
809 | ||
810 | ////////////////////////////////////////////////////////////////////// | |
811 | // Cache<T> and associated functions. | |
812 | ////////////////////////////////////////////////////////////////////// | |
813 | ||
814 | // I malloc a RefCountType to hold the refCount and init it to 1 to ensure the | |
815 | // refCount will never get to 0, so the destructor-of-global-object | |
816 | // order at the end of the program is a non-issue. In other words, the | |
817 | // memory allocated here is only reclaimed by the operating system. | |
818 | template <class T> | |
819 | Cache<T>* xnil_helper() { | |
820 | void *p = std::malloc( sizeof(RefCountType) ); | |
821 | *((RefCountType*)p) = 1; | |
822 | return static_cast<Cache<T>*>( p ); | |
823 | } | |
824 | ||
825 | template <class T> | |
826 | Cache<T>* xnil_helper_nil() { | |
827 | Cache<T>* p = xnil_helper<T>(); | |
828 | return p; | |
829 | } | |
830 | ||
831 | template <class T> | |
832 | Cache<T>* xnil_helper_bad() { | |
833 | Cache<T>* p = xnil_helper<T>(); | |
834 | return p; | |
835 | } | |
836 | ||
837 | template <class T> | |
838 | Cache<T>* xempty_helper() { | |
839 | Cache<T>* p = new Cache<T>( CacheEmpty() ); | |
840 | return p; | |
841 | } | |
842 | ||
843 | // This makes a boost phoenix function type with return type | |
844 | // odd_list<T> | |
845 | template <class T> | |
846 | struct fun0_type_helper{ | |
847 | typedef boost::function0<odd_list<T> > fun_type; | |
848 | typedef boost::phoenix::function<fun_type> phx_type; | |
849 | }; | |
850 | ||
851 | ||
852 | template <class T> | |
853 | struct make_fun0_odd_list { | |
854 | ||
855 | typedef typename fun0_type_helper<T>::fun_type fun_type; | |
856 | typedef typename fun0_type_helper<T>::phx_type phx_type; | |
857 | typedef phx_type result_type; | |
858 | ||
859 | template <class F> | |
860 | result_type operator()(const F& f) const | |
861 | { | |
862 | fun_type ff(f); | |
863 | phx_type g(ff); | |
864 | return g; | |
865 | } | |
866 | ||
867 | // Overload for the case where it is a boost phoenix function already. | |
868 | template <class F> | |
869 | typename boost::phoenix::function<F> operator() | |
870 | (const boost::phoenix::function<F>& f) const | |
871 | { | |
872 | return f; | |
873 | } | |
874 | ||
875 | }; | |
876 | ||
877 | template <class T> | |
878 | class Cache : boost::noncopyable { | |
879 | mutable RefCountType refC; | |
880 | // This is the boost::function type | |
881 | typedef typename fun0_type_helper<T>::fun_type fun_odd_list_T; | |
882 | // This is the boost::phoenix::function type; | |
883 | typedef typename fun0_type_helper<T>::phx_type fun0_odd_list_T; | |
884 | mutable fun0_odd_list_T fxn; | |
885 | mutable odd_list<T> val; | |
886 | // val.second.rep can be XBAD, XNIL, or a valid ptr | |
887 | // - XBAD: val is invalid (fxn is valid) | |
888 | // - XNIL: this is the empty list | |
889 | // - anything else: val.first() is head, val.second is tail() | |
890 | ||
891 | // This functoid should never be called; it represents a | |
892 | // self-referent Cache, which should be impossible under the current | |
893 | // implementation. Nonetheless, we need a 'dummy' function object to | |
894 | // represent invalid 'fxn's (val.second.rep!=XBAD), and this | |
895 | // implementation seems to be among the most reasonable. | |
896 | struct blackhole_helper /*: c_fun_type< odd_list<T> >*/ { | |
897 | typedef odd_list<T> return_type; | |
898 | odd_list<T> operator()() const { | |
899 | #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS | |
900 | throw lazy_exception("You have entered a black hole."); | |
901 | #else | |
902 | return odd_list<T>(); | |
903 | #endif | |
904 | } | |
905 | }; | |
906 | ||
907 | // Don't get rid of these XFOO() functions; they impose no overhead, | |
908 | // and provide a useful place to add debugging code for tracking down | |
909 | // before-main()-order-of-initialization problems. | |
910 | static const boost::intrusive_ptr<Cache<T> >& XEMPTY() { | |
911 | static boost::intrusive_ptr<Cache<T> > xempty( xempty_helper<T>() ); | |
912 | return xempty; | |
913 | } | |
914 | static const boost::intrusive_ptr<Cache<T> >& XNIL() { | |
915 | // this list is nil | |
916 | static boost::intrusive_ptr<Cache<T> > xnil( xnil_helper_nil<T>() ); | |
917 | return xnil; | |
918 | } | |
919 | ||
920 | static const boost::intrusive_ptr<Cache<T> >& XBAD() { | |
921 | // the pair is invalid; use fxn | |
922 | static boost::intrusive_ptr<Cache<T> > xbad( xnil_helper_bad<T>() ); | |
923 | return xbad; | |
924 | } | |
925 | ||
926 | static fun0_odd_list_T /*<odd_list<T> >*/ the_blackhole; | |
927 | static fun0_odd_list_T& blackhole() { | |
928 | static fun0_odd_list_T the_blackhole; | |
929 | //( make_fun0_odd_list<T>()( blackhole_helper() ) ); | |
930 | return the_blackhole; | |
931 | } | |
932 | ||
933 | odd_list<T>& cache() const { | |
934 | if( val.second.rep == XBAD() ) { | |
935 | val = fxn()(); | |
936 | fxn = blackhole(); | |
937 | } | |
938 | return val; | |
939 | } | |
940 | ||
941 | template <class U> friend class list; | |
942 | template <class U> friend class odd_list; | |
943 | template <class TT, class F, class L, bool b> friend struct ConsHelp2; | |
944 | template <class U,class F> friend struct cvt; | |
945 | template <class U, class F, class R> friend struct ListHelp; | |
946 | template <class U> friend Cache<U>* xempty_helper(); | |
947 | ||
948 | Cache( CacheEmpty ) : refC(0), fxn(blackhole()), val() {} | |
949 | Cache( const odd_list<T>& x ) : refC(0), fxn(blackhole()), val(x) {} | |
950 | Cache( const T& x, const list<T>& l ) : refC(0),fxn(blackhole()),val(x,l) | |
951 | {} | |
952 | ||
953 | Cache( const fun0_odd_list_T& f ) | |
954 | : refC(0), fxn(f), val( OddListDummyY() ) {} | |
955 | ||
956 | // f must be a boost phoenix function object? | |
957 | template <class F> | |
958 | Cache( const F& f ) // ()->odd_list | |
959 | : refC(0), fxn(make_fun0_odd_list<T>()(f)), val( OddListDummyY() ) {} | |
960 | ||
961 | // This is for ()->list<T> to ()->odd_list<T> | |
962 | struct CvtFxn {}; | |
963 | template <class F> | |
964 | Cache( CvtFxn, const F& f ) // ()->list | |
965 | : refC(0), fxn(make_fun0_odd_list<T>()(cvt<T,F>(f))), val( OddListDummyY() ) {} | |
966 | ||
967 | template <class X> | |
968 | friend void intrusive_ptr_add_ref( const Cache<X>* p ); | |
969 | template <class X> | |
970 | friend void intrusive_ptr_release( const Cache<X>* p ); | |
971 | }; | |
972 | ||
973 | template <class T> | |
974 | void intrusive_ptr_add_ref( const Cache<T>* p ) { | |
975 | ++ (p->refC); | |
976 | } | |
977 | template <class T> | |
978 | void intrusive_ptr_release( const Cache<T>* p ) { | |
979 | if( !--(p->refC) ) delete p; | |
980 | } | |
981 | ||
982 | ////////////////////////////////////////////////////////////////////// | |
983 | // Rest of list's stuff | |
984 | ////////////////////////////////////////////////////////////////////// | |
985 | ||
986 | template <class T, class F> struct ListHelp<T,F,list<T> > { | |
987 | boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const { | |
988 | return boost::intrusive_ptr<Cache<T> > | |
989 | (new Cache<T>(typename Cache<T>::CvtFxn(),f)); | |
990 | } | |
991 | }; | |
992 | template <class T, class F> struct ListHelp<T,F,odd_list<T> > { | |
993 | boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const { | |
994 | return boost::intrusive_ptr<Cache<T> >(new Cache<T>(f)); | |
995 | } | |
996 | }; | |
997 | ||
998 | template <class T> | |
11fdf7f2 | 999 | class list_iterator { |
7c673cae FG |
1000 | list<T> l; |
1001 | bool is_nil; | |
1002 | void advance() { | |
1003 | l = l.tail(); | |
1004 | if( !l ) | |
1005 | is_nil = true; | |
1006 | } | |
1007 | class Proxy { // needed for operator-> | |
1008 | const T x; | |
1009 | friend class list_iterator; | |
1010 | Proxy( const T& xx ) : x(xx) {} | |
1011 | public: | |
1012 | const T* operator->() const { return &x; } | |
1013 | }; | |
1014 | public: | |
11fdf7f2 TL |
1015 | typedef std::input_iterator_tag iterator_category; |
1016 | typedef T value_type; | |
1017 | typedef ptrdiff_t difference_type; | |
1018 | typedef T* pointer; | |
1019 | typedef T& reference; | |
1020 | ||
7c673cae FG |
1021 | list_iterator() : l(), is_nil(true) {} |
1022 | explicit list_iterator( const list<T>& ll ) : l(ll), is_nil(!ll) {} | |
1023 | ||
1024 | const T operator*() const { return l.head(); } | |
1025 | const Proxy operator->() const { return Proxy(l.head()); } | |
1026 | list_iterator<T>& operator++() { | |
1027 | advance(); | |
1028 | return *this; | |
1029 | } | |
1030 | const list_iterator<T> operator++(int) { | |
1031 | list_iterator<T> i( *this ); | |
1032 | advance(); | |
1033 | return i; | |
1034 | } | |
1035 | bool operator==( const list_iterator<T>& i ) const { | |
1036 | return is_nil && i.is_nil; | |
1037 | } | |
1038 | bool operator!=( const list_iterator<T>& i ) const { | |
1039 | return ! this->operator==(i); | |
1040 | } | |
1041 | }; | |
1042 | ||
1043 | ||
1044 | } // namespace impl | |
1045 | ||
1046 | using impl::list; | |
1047 | using impl::odd_list; | |
1048 | using impl::list_iterator; | |
1049 | ||
1050 | ////////////////////////////////////////////////////////////////////// | |
1051 | // op== and op<, overloaded for all combos of list, odd_list, and NIL | |
1052 | ////////////////////////////////////////////////////////////////////// | |
1053 | // All of these null head and tail are now non lazy using e.g. null(a)(). | |
1054 | // They need an extra () e.g. null(a)(). | |
1055 | ||
1056 | // FIX THIS comparison operators can be implemented simpler with enable_if | |
1057 | template <class T> | |
1058 | bool operator==( const odd_list<T>& a, a_unique_type_for_nil ) { | |
1059 | return null(a)(); | |
1060 | } | |
1061 | template <class T> | |
1062 | bool operator==( const list<T>& a, a_unique_type_for_nil ) { | |
1063 | return null(a)(); | |
1064 | } | |
1065 | template <class T> | |
1066 | bool operator==( a_unique_type_for_nil, const odd_list<T>& a ) { | |
1067 | return null(a)(); | |
1068 | } | |
1069 | template <class T> | |
1070 | bool operator==( a_unique_type_for_nil, const list<T>& a ) { | |
1071 | return null(a)(); | |
1072 | } | |
1073 | template <class T> | |
1074 | bool operator==( const list<T>& a, const list<T>& b ) { | |
1075 | if( null(a)() && null(b)() ) | |
1076 | return true; | |
1077 | if( null(a)() || null(b)() ) | |
1078 | return false; | |
1079 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1080 | } | |
1081 | template <class T> | |
1082 | bool operator==( const odd_list<T>& a, const odd_list<T>& b ) { | |
1083 | if( null(a)() && null(b)() ) | |
1084 | return true; | |
1085 | if( null(a)() || null(b)() ) | |
1086 | return false; | |
1087 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1088 | } | |
1089 | template <class T> | |
1090 | bool operator==( const list<T>& a, const odd_list<T>& b ) { | |
1091 | if( null(a)() && null(b)() ) | |
1092 | return true; | |
1093 | if( null(a)() || null(b)() ) | |
1094 | return false; | |
1095 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1096 | } | |
1097 | template <class T> | |
1098 | bool operator==( const odd_list<T>& a, const list<T>& b ) { | |
1099 | if( null(a)() && null(b)() ) | |
1100 | return true; | |
1101 | if( null(a)() || null(b)() ) | |
1102 | return false; | |
1103 | return (head(a)()==head(b)()) && (tail(a)()==tail(b)()); | |
1104 | } | |
1105 | ||
1106 | template <class T> | |
1107 | bool operator<( const list<T>& a, const list<T>& b ) { | |
1108 | if( null(a)() && !null(b)() ) return true; | |
1109 | if( null(b)() ) return false; | |
1110 | if( head(b)() < head(a)() ) return false; | |
1111 | if( head(a)() < head(b)() ) return true; | |
1112 | return (tail(a)() < tail(b)()); | |
1113 | } | |
1114 | template <class T> | |
1115 | bool operator<( const odd_list<T>& a, const list<T>& b ) { | |
1116 | if( null(a)() && !null(b)() ) return true; | |
1117 | if( null(b)() ) return false; | |
1118 | if( head(b)() < head(a)() ) return false; | |
1119 | if( head(a)() < head(b)() ) return true; | |
1120 | return (tail(a)() < tail(b)()); | |
1121 | } | |
1122 | template <class T> | |
1123 | bool operator<( const list<T>& a, const odd_list<T>& b ) { | |
1124 | if( null(a) && !null(b) ) return true; | |
1125 | if( null(b) ) return false; | |
1126 | if( head(b) < head(a) ) return false; | |
1127 | if( head(a) < head(b) ) return true; | |
1128 | return (tail(a) < tail(b)); | |
1129 | } | |
1130 | template <class T> | |
1131 | bool operator<( const odd_list<T>& a, const odd_list<T>& b ) { | |
1132 | if( null(a)() && !null(b)() ) return true; | |
1133 | if( null(b)() ) return false; | |
1134 | if( head(b)() < head(a)() ) return false; | |
1135 | if( head(a)() < head(b)() ) return true; | |
1136 | return (tail(a)() < tail(b)()); | |
1137 | } | |
1138 | template <class T> | |
1139 | bool operator<( const odd_list<T>&, a_unique_type_for_nil ) { | |
1140 | return false; | |
1141 | } | |
1142 | template <class T> | |
1143 | bool operator<( const list<T>&, a_unique_type_for_nil ) { | |
1144 | return false; | |
1145 | } | |
1146 | template <class T> | |
1147 | bool operator<( a_unique_type_for_nil, const odd_list<T>& b ) { | |
1148 | return !null(b)(); | |
1149 | } | |
1150 | template <class T> | |
1151 | bool operator<( a_unique_type_for_nil, const list<T>& b ) { | |
1152 | return !null(b)(); | |
1153 | } | |
1154 | ||
1155 | ////////////////////////////////////////////////////////////////////// | |
1156 | // Implement cat and cons after the list types are defined. | |
1157 | ////////////////////////////////////////////////////////////////////// | |
1158 | namespace impl { | |
1159 | using listlike::ListLike; | |
1160 | ||
1161 | template <class T, class F, class L> | |
1162 | struct ConsHelp2<T,F,L,true> | |
1163 | { | |
1164 | typedef typename boost::remove_reference<T>::type TT; | |
1165 | typedef typename L::force_result_type type; | |
1166 | static type go( const TT& x, const F& f ) { | |
1167 | return type( x, f ); | |
1168 | } | |
1169 | }; | |
1170 | template <class T, class F> | |
1171 | struct ConsHelp2<T,F,list<T>,true> | |
1172 | { | |
1173 | typedef typename boost::remove_reference<T>::type TT; | |
1174 | typedef list<TT> L; | |
1175 | typedef typename L::force_result_type type; | |
1176 | static type go( const TT& x, const F& f ) { | |
1177 | return odd_list<TT>(x, list<TT>( | |
1178 | boost::intrusive_ptr<Cache<TT> >(new Cache<T>( | |
1179 | typename Cache<TT>::CvtFxn(),f)))); | |
1180 | } | |
1181 | }; | |
1182 | template <class T, class F> | |
1183 | struct ConsHelp2<T,F,odd_list<T>,true> | |
1184 | { | |
1185 | typedef typename boost::remove_reference<T>::type TT; | |
1186 | typedef odd_list<TT> L; | |
1187 | typedef typename L::force_result_type type; | |
1188 | static type go( const TT& x, const F& f ) { | |
1189 | return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) )); | |
1190 | } | |
1191 | }; | |
1192 | template <class T, class F> | |
1193 | struct ConsHelp2<T,F,a_unique_type_for_nil,false> | |
1194 | { | |
1195 | typedef typename boost::remove_reference<T>::type TT; | |
1196 | typedef odd_list<TT> type; | |
1197 | static type go( const TT& x, const F& f ) { | |
1198 | return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) )); | |
1199 | } | |
1200 | }; | |
1201 | ||
1202 | template <class T, class L, bool b> struct ConsHelp1 { | |
1203 | typedef typename boost::remove_reference<T>::type TT; | |
1204 | typedef typename L::force_result_type type; | |
1205 | static type go( const TT& x, const L& l ) { | |
1206 | return type(x,l); | |
1207 | } | |
1208 | }; | |
1209 | template <class T> struct ConsHelp1<T,a_unique_type_for_nil,false> { | |
1210 | typedef typename boost::remove_reference<T>::type TT; | |
1211 | typedef odd_list<TT> type; | |
1212 | static type go( const TT& x, const a_unique_type_for_nil& n ) { | |
1213 | return type(x,n); | |
1214 | } | |
1215 | }; | |
1216 | template <class T, class F> struct ConsHelp1<T,F,false> { | |
1217 | // It's a function returning a list | |
1218 | // This is the one I have not fixed yet.... | |
1219 | // typedef typename F::result_type L; | |
1220 | // typedef typename result_of::template ListType<F>::result_type L; | |
1221 | typedef odd_list<T> L; | |
1222 | typedef ConsHelp2<T,F,L,boost::is_base_and_derived<ListLike,L>::value> help; | |
1223 | typedef typename help::type type; | |
1224 | static type go( const T& x, const F& f ) { | |
1225 | return help::go(x,f); | |
1226 | } | |
1227 | }; | |
1228 | ||
1229 | template <class T, class L, bool b> | |
1230 | struct ConsHelp0; | |
1231 | ||
1232 | template <class T> | |
1233 | struct ConsHelp0<T,a_unique_type_for_nil,true> { | |
1234 | typedef typename boost::remove_reference<T>::type TT; | |
1235 | typedef odd_list<T> type; | |
1236 | }; | |
1237 | ||
1238 | template <class T> | |
1239 | struct ConsHelp0<const T &,const a_unique_type_for_nil &,true> { | |
1240 | typedef typename boost::remove_reference<T>::type TT; | |
1241 | typedef odd_list<TT> type; | |
1242 | }; | |
1243 | ||
1244 | template <class T> | |
1245 | struct ConsHelp0<T &,a_unique_type_for_nil &,true> { | |
1246 | typedef typename boost::remove_reference<T>::type TT; | |
1247 | typedef odd_list<TT> type; | |
1248 | }; | |
1249 | ||
1250 | template <class T, class L> | |
1251 | struct ConsHelp0<T,L,false> { | |
1252 | // This removes any references from L for correct return type | |
1253 | // identification. | |
1254 | typedef typename boost::remove_reference<L>::type LType; | |
1255 | typedef typename ConsHelp1<T,LType, | |
1256 | boost::is_base_and_derived<ListLike,LType>::value>::type type; | |
1257 | }; | |
1258 | ||
1259 | ///////////////////////////////////////////////////////////////////// | |
1260 | // cons (t,l) - cons a value to the front of a list. | |
1261 | // Note: The first arg, t, must be a value. | |
1262 | // The second arg, l, can be a list or NIL | |
1263 | // or a function that returns a list. | |
1264 | ///////////////////////////////////////////////////////////////////// | |
1265 | struct Cons | |
1266 | { | |
1267 | /* template <class T, class L> struct sig : public fun_type< | |
1268 | typename ConsHelp1<T,L, | |
1269 | boost::is_base_and_derived<ListLike,L>::value>::type> {}; | |
1270 | */ | |
1271 | template <typename Sig> struct result; | |
1272 | ||
1273 | template <typename This, typename T, typename L> | |
1274 | struct result<This(T, L)> | |
1275 | { | |
1276 | typedef typename ConsHelp0<T,L, | |
1277 | listlike::detect_nil<L>::is_nil>::type type; | |
1278 | }; | |
1279 | ||
1280 | template <typename This, typename T> | |
1281 | struct result<This(T,a_unique_type_for_nil)> | |
1282 | { | |
1283 | typedef typename boost::remove_reference<T>::type TT; | |
1284 | typedef odd_list<TT> type; | |
1285 | }; | |
1286 | ||
1287 | template <typename T, typename L> | |
1288 | typename result<Cons(T,L)>::type | |
1289 | operator()( const T& x, const L& l ) const { | |
1290 | typedef typename result_of::ListType<L>::LType LType; | |
1291 | typedef ConsHelp1<T,LType, | |
1292 | boost::is_base_and_derived<ListLike,LType>::value> help; | |
1293 | return help::go(x,l); | |
1294 | } | |
1295 | ||
1296 | template <typename T> | |
1297 | typename result<Cons(T,a_unique_type_for_nil)>::type | |
1298 | operator()( const T& x, const a_unique_type_for_nil &n ) const { | |
1299 | typedef typename result<Cons(T,a_unique_type_for_nil)>::type LL; | |
1300 | typedef ConsHelp1<T,LL, | |
1301 | boost::is_base_and_derived<ListLike,LL>::value> help; | |
1302 | return help::go(x,n); | |
1303 | } | |
1304 | ||
1305 | }; | |
1306 | } | |
1307 | ||
1308 | typedef boost::phoenix::function<impl::Cons> Cons; | |
1309 | Cons cons; | |
1310 | ||
1311 | namespace impl { | |
1312 | ||
1313 | template <class L, class M, bool b> | |
1314 | struct CatHelp0; | |
1315 | ||
1316 | template <class LL> | |
1317 | struct CatHelp0<LL,a_unique_type_for_nil,true> { | |
1318 | typedef typename result_of::template ListType<LL>::LType type; | |
1319 | }; | |
1320 | ||
1321 | template <class LL> | |
1322 | struct CatHelp0<const LL &,const a_unique_type_for_nil &,true> { | |
1323 | typedef typename result_of::template ListType<LL>::LType type; | |
1324 | //typedef L type; | |
1325 | }; | |
1326 | ||
1327 | template <class LL> | |
1328 | struct CatHelp0<LL &,a_unique_type_for_nil &,true> { | |
1329 | typedef typename result_of::template ListType<LL>::LType type; | |
1330 | //typedef L type; | |
1331 | }; | |
1332 | ||
1333 | template <class LL, class MM> | |
1334 | struct CatHelp0<LL,MM,false> { | |
1335 | // This removes any references from L for correct return type | |
1336 | // identification. | |
1337 | typedef typename result_of::template ListType<LL>::LType type; | |
1338 | // typedef typename ConsHelp1<T,LType, | |
1339 | // boost::is_base_and_derived<ListLike,LType>::value>::type type; | |
1340 | }; | |
1341 | ||
1342 | ///////////////////////////////////////////////////////////////////// | |
1343 | // cat (l,m) - concatenate lists. | |
1344 | // Note: The first arg, l, must be a list or NIL. | |
1345 | // The second arg, m, can be a list or NIL | |
1346 | // or a function that returns a list. | |
1347 | ///////////////////////////////////////////////////////////////////// | |
1348 | struct Cat | |
1349 | { | |
1350 | template <class L, class M, bool b, class R> | |
1351 | struct Helper /*: public c_fun_type<L,M,R>*/ { | |
1352 | template <typename Sig> struct result; | |
1353 | ||
1354 | template <typename This> | |
1355 | struct result<This(L,M)> | |
1356 | { | |
1357 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1358 | }; | |
1359 | ||
1360 | typedef R return_type; | |
1361 | R operator()( const L& l, const M& m, | |
1362 | reuser2<INV,VAR,INV,Helper, | |
1363 | typename result_of::template ListType<L>::tail_result_type,M> | |
1364 | r = NIL ) const { | |
1365 | if( null(l)() ) | |
1366 | return m().force(); | |
1367 | else | |
1368 | return cons( head(l)(), r( Helper<L,M,b,R>(), tail(l), m )() ); | |
1369 | } | |
1370 | }; | |
1371 | template <class L, class M, class R> | |
1372 | struct Helper<L,M,true,R> /*: public c_fun_type<L,M,R>*/ { | |
1373 | template <typename Sig> struct result; | |
1374 | ||
1375 | template <typename This> | |
1376 | struct result<This(L,M)> | |
1377 | { | |
1378 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1379 | }; | |
1380 | typedef R return_type; | |
1381 | R operator()( const L& l, const M& m, | |
1382 | reuser2<INV,VAR,INV,Helper, | |
1383 | typename result_of::template ListType<L>::tail_result_type,M> | |
1384 | r = NIL ) const { | |
1385 | if( null(l)() ) | |
1386 | return m.force(); | |
1387 | else | |
1388 | return cons( head(l)(), r(Helper<L,M,true,R>(), tail(l), m )()); | |
1389 | } | |
1390 | }; | |
1391 | template <class L, class R> | |
1392 | struct Helper<L,a_unique_type_for_nil,false,R> | |
1393 | /*: public c_fun_type<L, | |
1394 | a_unique_type_for_nil,odd_list<typename L::value_type> > */ | |
1395 | { | |
1396 | typedef odd_list<typename result_of::template ListType<L>::value_type> type; | |
1397 | odd_list<typename result_of::template ListType<L>::value_type> | |
1398 | operator()( const L& l, const a_unique_type_for_nil& ) const { | |
1399 | return l; | |
1400 | } | |
1401 | }; | |
1402 | public: | |
1403 | /*template <class L, class M> struct sig : public fun_type< | |
1404 | typename RT<cons_type,typename L::value_type,M>::result_type> | |
1405 | {}; */ | |
1406 | // Need to work out the return type here. | |
1407 | template <typename Sig> struct result; | |
1408 | ||
1409 | template <typename This, typename L, typename M> | |
1410 | struct result<This(L,M)> | |
1411 | { | |
1412 | typedef typename CatHelp0<L,M, | |
1413 | listlike::detect_nil<M>::is_nil>::type type; | |
1414 | // typedef typename result_of::ListType<L>::tail_result_type type; | |
1415 | }; | |
1416 | ||
1417 | template <typename This, typename L> | |
1418 | struct result<This(L,a_unique_type_for_nil)> | |
1419 | { | |
1420 | typedef typename result_of::ListType<L>::tail_result_type type; | |
1421 | }; | |
1422 | template <class L, class M> | |
1423 | typename result<Cat(L,M)>::type operator()( const L& l, const M& m ) const | |
1424 | { | |
1425 | listlike::EnsureListLike<L>(); | |
1426 | return Helper<L,M, | |
1427 | boost::is_base_and_derived<typename listlike::ListLike,M>::value, | |
1428 | typename result<Cat(L,M)>::type>()(l,m); | |
1429 | } | |
1430 | ||
1431 | template <class L> | |
1432 | typename result<Cat(L,a_unique_type_for_nil)>::type operator()( const L& l, const a_unique_type_for_nil& /* n */ ) const | |
1433 | { | |
1434 | listlike::EnsureListLike<L>(); | |
1435 | return l; | |
1436 | } | |
1437 | ||
1438 | }; | |
1439 | ||
1440 | ||
1441 | } | |
1442 | ||
1443 | typedef boost::phoenix::function<impl::Cat> Cat; | |
1444 | Cat cat; | |
1445 | ||
1446 | ||
1447 | ////////////////////////////////////////////////////////////////////// | |
1448 | // Handy functions for making list literals | |
1449 | ////////////////////////////////////////////////////////////////////// | |
1450 | // Yes, these aren't functoids, they're just template functions. I'm | |
1451 | // lazy and created these mostly to make it easily to make little lists | |
1452 | // in the sample code snippets that appear in papers. | |
1453 | ||
1454 | struct UseList { | |
1455 | template <class T> struct List { typedef list<T> type; }; | |
1456 | }; | |
1457 | struct UseOddList { | |
1458 | template <class T> struct List { typedef odd_list<T> type; }; | |
1459 | }; | |
1460 | struct UseStrictList { | |
1461 | template <class T> struct List { typedef strict_list<T> type; }; | |
1462 | }; | |
1463 | ||
1464 | template <class Kind = UseList> | |
1465 | struct list_with { | |
1466 | template <class T> | |
1467 | typename Kind::template List<T>::type | |
1468 | operator()( const T& a ) const { | |
1469 | typename Kind::template List<T>::type l; | |
1470 | l = cons( a, l ); | |
1471 | return l; | |
1472 | } | |
1473 | ||
1474 | template <class T> | |
1475 | typename Kind::template List<T>::type | |
1476 | operator()( const T& a, const T& b ) const { | |
1477 | typename Kind::template List<T>::type 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 { | |
1486 | typename Kind::template List<T>::type l; | |
1487 | l = cons( c, l ); | |
1488 | l = cons( b, l ); | |
1489 | l = cons( a, l ); | |
1490 | return l; | |
1491 | } | |
1492 | ||
1493 | template <class T> | |
1494 | typename Kind::template List<T>::type | |
1495 | operator()( const T& a, const T& b, const T& c, const T& d ) const { | |
1496 | typename Kind::template List<T>::type l; | |
1497 | l = cons( d, l ); | |
1498 | l = cons( c, l ); | |
1499 | l = cons( b, l ); | |
1500 | l = cons( a, l ); | |
1501 | return l; | |
1502 | } | |
1503 | ||
1504 | template <class T> | |
1505 | typename Kind::template List<T>::type | |
1506 | operator()( const T& a, const T& b, const T& c, const T& d, | |
1507 | const T& e ) const { | |
1508 | typename Kind::template List<T>::type l; | |
1509 | l = cons( e, l ); | |
1510 | l = cons( d, l ); | |
1511 | l = cons( c, l ); | |
1512 | l = cons( b, l ); | |
1513 | l = cons( a, l ); | |
1514 | return l; | |
1515 | } | |
1516 | }; | |
1517 | ////////////////////////////////////////////////////////////////////// | |
1518 | ||
1519 | } | |
1520 | ||
1521 | } | |
1522 | ||
1523 | #endif |