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> {
requires_lazy_list_to_prevent_infinite_recursionboost::phoenix::lazy::ensure_lazy_helper128 static void requires_lazy_list_to_prevent_infinite_recursion() {}
129 };
130 template <class L>
ensure_lazy()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> {
requires_lazy_list_to_prevent_infinite_recursionboost::phoenix::listlike::ensure_lazy_helper184 static void requires_lazy_list_to_prevent_infinite_recursion() {}
185 };
186 template <class L>
ensure_lazy()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 {
trying_to_call_a_list_function_on_a_non_listboost::phoenix::listlike::EnsureListLikeHelp194 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>
EnsureListLike()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>
is_a_unique_type_for_nil(const L & l)205 bool is_a_unique_type_for_nil(const L& l) {
206 return false;
207 }
208
209 template <>
is_a_unique_type_for_nil(const a_unique_type_for_nil &)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
operator ()boost::phoenix::impl::Head260 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
operator ()boost::phoenix::impl::Tail281 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
operator ()boost::phoenix::impl::Null303 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
operator ()boost::phoenix::impl::Delay323 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
operator ()boost::phoenix::impl::Force343 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;
strict_consboost::phoenix::impl::strict_cons378 strict_cons( const T& h, const tail_type& t ) : refC(0), head(h), tail(t) {}
379
380 };
381 template <class T>
intrusive_ptr_add_ref(const strict_cons<T> * p)382 void intrusive_ptr_add_ref( const strict_cons<T>* p ) {
383 ++ (p->refC);
384 }
385 template <class T>
intrusive_ptr_release(const strict_cons<T> * p)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;
advance()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;
Proxy(const T & xx)404 Proxy( const T& xx ) : x(xx) {}
405 public:
operator ->() const406 const T* operator->() const { return &x; }
407 };
408 public:
strict_list_iterator()409 strict_list_iterator() : l(), is_nil(true) {}
strict_list_iterator(const rep_type & ll)410 explicit strict_list_iterator( const rep_type& ll ) : l(ll), is_nil(!ll) {}
411
operator *() const412 const T operator*() const { return l->head; }
operator ->() const413 const Proxy operator->() const { return Proxy(l->head); }
operator ++()414 strict_list_iterator<T>& operator++() {
415 advance();
416 return *this;
417 }
operator ++(int)418 const strict_list_iterator<T> operator++(int) {
419 strict_list_iterator<T> i( *this );
420 advance();
421 return i;
422 }
operator ==(const strict_list_iterator<T> & i) const423 bool operator==( const strict_list_iterator<T>& i ) const {
424 return is_nil && i.is_nil;
425 }
operator !=(const strict_list_iterator<T> & i) const426 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>
help(Iter a,const Iter & b)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
strict_list(Make,const rep_type & r)466 strict_list( Make, const rep_type& r ) : rep(r) {}
467
strict_list()468 strict_list() : rep() {}
469
strict_list(a_unique_type_for_nil)470 strict_list( a_unique_type_for_nil ) : rep() {}
471
472 template <class F>
strict_list(const F & 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
strict_list(const T & x,const strict_list & y)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>
strict_list(const T & x,const F & f)482 strict_list( const T& x, const F& f )
483 : rep( new impl::strict_cons<T>(x,f().rep) ) {}
484
operator bool() const485 operator bool() const { return (bool)rep; }
force() const486 force_result_type force() const { return *this; }
delay() const487 delay_result_type delay() const { return *this; }
head() const488 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 }
tail() const495 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>
strict_list(const Iter & a,const Iter & b)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.
~strict_list()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
begin() const519 iterator begin() const { return impl::strict_list_iterator<T>( rep ); }
end() const520 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>
operator ==(const strict_list<T> & a,a_unique_type_for_nil)527 bool operator==( const strict_list<T>& a, a_unique_type_for_nil ) {
528 return null(a)();
529 }
530 template <class T>
operator ==(a_unique_type_for_nil,const strict_list<T> & a)531 bool operator==( a_unique_type_for_nil, const strict_list<T>& a ) {
532 return null(a)();
533 }
534 template <class T>
operator ==(const strict_list<T> & a,const strict_list<T> & b)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>
operator <(const strict_list<T> & a,const strict_list<T> & b)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>
operator <(const strict_list<T> &,a_unique_type_for_nil)553 bool operator<( const strict_list<T>&, a_unique_type_for_nil ) {
554 return false;
555 }
556 template <class T>
operator <(a_unique_type_for_nil,const strict_list<T> & b)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
list(const boost::intrusive_ptr<Cache<T>> & p)599 list( const boost::intrusive_ptr<Cache<T> >& p ) : rep(p) { }
list(ListRaw,Cache<T> * p)600 list( ListRaw, Cache<T>* p ) : rep(p) { }
601
priv_isEmpty() const602 bool priv_isEmpty() const {
603 return rep->cache().second.rep == Cache<T>::XNIL();
604 }
priv_head() const605 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 }
priv_tail() const612 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
list(a_unique_type_for_nil)633 list( a_unique_type_for_nil ) : rep( Cache<T>::XEMPTY() ) { }
list()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.
list(const F & f)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
operator bool() const643 operator bool() const { return !priv_isEmpty(); }
force() const644 const force_result_type& force() const { return rep->cache(); }
delay() const645 const delay_result_type& delay() const { return *this; }
646 // Note: force returns a reference;
647 // implicit conversion now returns a copy.
operator odd_list<T>() const648 operator odd_list<T>() const { return force(); }
649
head() const650 T head() const { return priv_head(); }
tail() const651 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
begin() const656 iterator begin() const { return list_iterator<T>( *this ); }
end() const657 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
first() const678 const T& first() const {
679 return *static_cast<const T*>(static_cast<const void*>(&fst));
680 }
first()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
odd_list(OddListDummyY)689 odd_list( OddListDummyY )
690 : second( Cache<T>::XBAD() ) { }
691
init(const T & x)692 void init( const T& x ) {
693 new (static_cast<void*>(&fst)) T(x);
694 }
695
fst_is_valid() const696 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
priv_isEmpty() const703 bool priv_isEmpty() const { return second.rep == Cache<T>::XNIL(); }
priv_head() const704 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
priv_tail() const712 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
odd_list()732 odd_list() : second( Cache<T>::XNIL() ) { }
odd_list(a_unique_type_for_nil)733 odd_list( a_unique_type_for_nil ) : second( Cache<T>::XNIL() ) { }
odd_list(const T & x,const list<T> & y)734 odd_list( const T& x, const list<T>& y ) : second(y) { init(x); }
odd_list(const T & x,a_unique_type_for_nil)735 odd_list( const T& x, a_unique_type_for_nil ) : second(NIL) { init(x); }
736
odd_list(const odd_list<T> & x)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>
odd_list(It begin,const It & end)744 odd_list( It begin, const It& end )
745 : second( begin==end ? Cache<T>::XNIL() :
746 ( init(*begin++), list<T>( begin, end ) ) ) {}
747
operator =(const odd_list<T> & x)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
~odd_list()764 ~odd_list() {
765 if( fst_is_valid() ) {
766 first().~T();
767 }
768 }
769
operator bool() const770 operator bool() const { return !priv_isEmpty(); }
force() const771 const force_result_type& force() const { return *this; }
delay() const772 delay_result_type delay() const { return list<T>(*this); }
773
head() const774 T head() const { return priv_head(); }
tail() const775 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
begin() const780 iterator begin() const { return list_iterator<T>( this->delay() ); }
end() const781 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;
cvtboost::phoenix::impl::cvt797 cvt( const F& ff ) : f(ff) {}
operator ()boost::phoenix::impl::cvt798 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>
xnil_helper()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>
xnil_helper_nil()821 Cache<T>* xnil_helper_nil() {
822 Cache<T>* p = xnil_helper<T>();
823 return p;
824 }
825
826 template <class T>
xnil_helper_bad()827 Cache<T>* xnil_helper_bad() {
828 Cache<T>* p = xnil_helper<T>();
829 return p;
830 }
831
832 template <class T>
xempty_helper()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>
operator ()boost::phoenix::impl::make_fun0_odd_list855 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>
operator ()boost::phoenix::impl::make_fun0_odd_list864 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;
operator ()boost::phoenix::impl::Cache::blackhole_helper893 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.
XEMPTY()905 static const boost::intrusive_ptr<Cache<T> >& XEMPTY() {
906 static boost::intrusive_ptr<Cache<T> > xempty( xempty_helper<T>() );
907 return xempty;
908 }
XNIL()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
XBAD()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;
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
cache() const928 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
Cache(CacheEmpty)943 Cache( CacheEmpty ) : refC(0), fxn(blackhole()), val() {}
Cache(const odd_list<T> & x)944 Cache( const odd_list<T>& x ) : refC(0), fxn(blackhole()), val(x) {}
Cache(const T & x,const list<T> & l)945 Cache( const T& x, const list<T>& l ) : refC(0),fxn(blackhole()),val(x,l)
946 {}
947
Cache(const fun0_odd_list_T & f)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>
Cache(const F & 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>
Cache(CvtFxn,const F & 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>
intrusive_ptr_add_ref(const Cache<T> * p)969 void intrusive_ptr_add_ref( const Cache<T>* p ) {
970 ++ (p->refC);
971 }
972 template <class T>
intrusive_ptr_release(const Cache<T> * p)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> > {
operator ()boost::phoenix::impl::ListHelp982 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> > {
operator ()boost::phoenix::impl::ListHelp988 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;
advance()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;
Proxy(const T & xx)1006 Proxy( const T& xx ) : x(xx) {}
1007 public:
operator ->() const1008 const T* operator->() const { return &x; }
1009 };
1010 public:
list_iterator()1011 list_iterator() : l(), is_nil(true) {}
list_iterator(const list<T> & ll)1012 explicit list_iterator( const list<T>& ll ) : l(ll), is_nil(!ll) {}
1013
operator *() const1014 const T operator*() const { return l.head(); }
operator ->() const1015 const Proxy operator->() const { return Proxy(l.head()); }
operator ++()1016 list_iterator<T>& operator++() {
1017 advance();
1018 return *this;
1019 }
operator ++(int)1020 const list_iterator<T> operator++(int) {
1021 list_iterator<T> i( *this );
1022 advance();
1023 return i;
1024 }
operator ==(const list_iterator<T> & i) const1025 bool operator==( const list_iterator<T>& i ) const {
1026 return is_nil && i.is_nil;
1027 }
operator !=(const list_iterator<T> & i) const1028 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>
operator ==(const odd_list<T> & a,a_unique_type_for_nil)1048 bool operator==( const odd_list<T>& a, a_unique_type_for_nil ) {
1049 return null(a)();
1050 }
1051 template <class T>
operator ==(const list<T> & a,a_unique_type_for_nil)1052 bool operator==( const list<T>& a, a_unique_type_for_nil ) {
1053 return null(a)();
1054 }
1055 template <class T>
operator ==(a_unique_type_for_nil,const odd_list<T> & a)1056 bool operator==( a_unique_type_for_nil, const odd_list<T>& a ) {
1057 return null(a)();
1058 }
1059 template <class T>
operator ==(a_unique_type_for_nil,const list<T> & a)1060 bool operator==( a_unique_type_for_nil, const list<T>& a ) {
1061 return null(a)();
1062 }
1063 template <class T>
operator ==(const list<T> & a,const list<T> & b)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>
operator ==(const odd_list<T> & a,const odd_list<T> & b)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>
operator ==(const list<T> & a,const odd_list<T> & b)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>
operator ==(const odd_list<T> & a,const list<T> & b)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>
operator <(const list<T> & a,const list<T> & b)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>
operator <(const odd_list<T> & a,const list<T> & b)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>
operator <(const list<T> & a,const odd_list<T> & b)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>
operator <(const odd_list<T> & a,const odd_list<T> & b)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>
operator <(const odd_list<T> &,a_unique_type_for_nil)1129 bool operator<( const odd_list<T>&, a_unique_type_for_nil ) {
1130 return false;
1131 }
1132 template <class T>
operator <(const list<T> &,a_unique_type_for_nil)1133 bool operator<( const list<T>&, a_unique_type_for_nil ) {
1134 return false;
1135 }
1136 template <class T>
operator <(a_unique_type_for_nil,const odd_list<T> & b)1137 bool operator<( a_unique_type_for_nil, const odd_list<T>& b ) {
1138 return !null(b)();
1139 }
1140 template <class T>
operator <(a_unique_type_for_nil,const list<T> & b)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;
goboost::phoenix::impl::ConsHelp21156 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;
goboost::phoenix::impl::ConsHelp21166 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;
goboost::phoenix::impl::ConsHelp21178 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;
goboost::phoenix::impl::ConsHelp21187 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;
goboost::phoenix::impl::ConsHelp11195 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;
goboost::phoenix::impl::ConsHelp11202 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;
goboost::phoenix::impl::ConsHelp11214 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
operator ()boost::phoenix::impl::Cons1279 operator()( const T& x, const L& l ) const {
1280 typedef typename result<Cons(T,L)>::type LL;
1281 typedef typename result_of::ListType<L>::LType LType;
1282 typedef ConsHelp1<T,LType,
1283 boost::is_base_and_derived<ListLike,LType>::value> help;
1284 return help::go(x,l);
1285 }
1286
1287 template <typename T>
1288 typename result<Cons(T,a_unique_type_for_nil)>::type
operator ()boost::phoenix::impl::Cons1289 operator()( const T& x, const a_unique_type_for_nil &n ) const {
1290 typedef typename result<Cons(T,a_unique_type_for_nil)>::type LL;
1291 typedef ConsHelp1<T,LL,
1292 boost::is_base_and_derived<ListLike,LL>::value> help;
1293 return help::go(x,n);
1294 }
1295
1296 };
1297 }
1298
1299 typedef boost::phoenix::function<impl::Cons> Cons;
1300 Cons cons;
1301
1302 namespace impl {
1303
1304 template <class L, class M, bool b>
1305 struct CatHelp0;
1306
1307 template <class L>
1308 struct CatHelp0<L,a_unique_type_for_nil,true> {
1309 typedef typename result_of::template ListType<L>::LType type;
1310 };
1311
1312 template <class L>
1313 struct CatHelp0<const L &,const a_unique_type_for_nil &,true> {
1314 typedef typename result_of::template ListType<L>::LType type;
1315 //typedef L type;
1316 };
1317
1318 template <class L>
1319 struct CatHelp0<L &,a_unique_type_for_nil &,true> {
1320 typedef typename result_of::template ListType<L>::LType type;
1321 //typedef L type;
1322 };
1323
1324 template <class L, class M>
1325 struct CatHelp0<L,M,false> {
1326 // This removes any references from L for correct return type
1327 // identification.
1328 typedef typename result_of::template ListType<L>::LType type;
1329 // typedef typename ConsHelp1<T,LType,
1330 // boost::is_base_and_derived<ListLike,LType>::value>::type type;
1331 };
1332
1333 /////////////////////////////////////////////////////////////////////
1334 // cat (l,m) - concatenate lists.
1335 // Note: The first arg, l, must be a list or NIL.
1336 // The second arg, m, can be a list or NIL
1337 // or a function that returns a list.
1338 /////////////////////////////////////////////////////////////////////
1339 struct Cat
1340 {
1341 template <class L, class M, bool b, class R>
1342 struct Helper /*: public c_fun_type<L,M,R>*/ {
1343 template <typename Sig> struct result;
1344
1345 template <typename This>
1346 struct result<This(L,M)>
1347 {
1348 typedef typename result_of::ListType<L>::tail_result_type type;
1349 };
1350
1351 typedef R return_type;
operator ()boost::phoenix::impl::Cat::Helper1352 R operator()( const L& l, const M& m,
1353 reuser2<INV,VAR,INV,Helper,
1354 typename result_of::template ListType<L>::tail_result_type,M>
1355 r = NIL ) const {
1356 if( null(l)() )
1357 return m().force();
1358 else
1359 return cons( head(l)(), r( Helper<L,M,b,R>(), tail(l), m )() );
1360 }
1361 };
1362 template <class L, class M, class R>
1363 struct Helper<L,M,true,R> /*: public c_fun_type<L,M,R>*/ {
1364 template <typename Sig> struct result;
1365
1366 template <typename This>
1367 struct result<This(L,M)>
1368 {
1369 typedef typename result_of::ListType<L>::tail_result_type type;
1370 };
1371 typedef R return_type;
operator ()boost::phoenix::impl::Cat::Helper1372 R operator()( const L& l, const M& m,
1373 reuser2<INV,VAR,INV,Helper,
1374 typename result_of::template ListType<L>::tail_result_type,M>
1375 r = NIL ) const {
1376 if( null(l)() )
1377 return m.force();
1378 else
1379 return cons( head(l)(), r(Helper<L,M,true,R>(), tail(l), m )());
1380 }
1381 };
1382 template <class L, class R>
1383 struct Helper<L,a_unique_type_for_nil,false,R>
1384 /*: public c_fun_type<L,
1385 a_unique_type_for_nil,odd_list<typename L::value_type> > */
1386 {
1387 typedef odd_list<typename result_of::template ListType<L>::value_type> type;
1388 odd_list<typename result_of::template ListType<L>::value_type>
operator ()boost::phoenix::impl::Cat::Helper1389 operator()( const L& l, const a_unique_type_for_nil& ) const {
1390 return l;
1391 }
1392 };
1393 public:
1394 /*template <class L, class M> struct sig : public fun_type<
1395 typename RT<cons_type,typename L::value_type,M>::result_type>
1396 {}; */
1397 // Need to work out the return type here.
1398 template <typename Sig> struct result;
1399
1400 template <typename This, typename L, typename M>
1401 struct result<This(L,M)>
1402 {
1403 typedef typename CatHelp0<L,M,
1404 listlike::detect_nil<M>::is_nil>::type type;
1405 // typedef typename result_of::ListType<L>::tail_result_type type;
1406 };
1407
1408 template <typename This, typename L>
1409 struct result<This(L,a_unique_type_for_nil)>
1410 {
1411 typedef typename result_of::ListType<L>::tail_result_type type;
1412 };
1413 template <class L, class M>
operator ()boost::phoenix::impl::Cat1414 typename result<Cat(L,M)>::type operator()( const L& l, const M& m ) const
1415 {
1416 listlike::EnsureListLike<L>();
1417 return Helper<L,M,
1418 boost::is_base_and_derived<typename listlike::ListLike,M>::value,
1419 typename result<Cat(L,M)>::type>()(l,m);
1420 }
1421
1422 template <class L>
operator ()boost::phoenix::impl::Cat1423 typename result<Cat(L,a_unique_type_for_nil)>::type operator()( const L& l, const a_unique_type_for_nil& /* n */ ) const
1424 {
1425 listlike::EnsureListLike<L>();
1426 return l;
1427 }
1428
1429 };
1430
1431
1432 }
1433
1434 typedef boost::phoenix::function<impl::Cat> Cat;
1435 Cat cat;
1436
1437
1438 //////////////////////////////////////////////////////////////////////
1439 // Handy functions for making list literals
1440 //////////////////////////////////////////////////////////////////////
1441 // Yes, these aren't functoids, they're just template functions. I'm
1442 // lazy and created these mostly to make it easily to make little lists
1443 // in the sample code snippets that appear in papers.
1444
1445 struct UseList {
1446 template <class T> struct List { typedef list<T> type; };
1447 };
1448 struct UseOddList {
1449 template <class T> struct List { typedef odd_list<T> type; };
1450 };
1451 struct UseStrictList {
1452 template <class T> struct List { typedef strict_list<T> type; };
1453 };
1454
1455 template <class Kind = UseList>
1456 struct list_with {
1457 template <class T>
1458 typename Kind::template List<T>::type
operator ()boost::phoenix::list_with1459 operator()( const T& a ) const {
1460 typename Kind::template List<T>::type l;
1461 l = cons( a, l );
1462 return l;
1463 }
1464
1465 template <class T>
1466 typename Kind::template List<T>::type
operator ()boost::phoenix::list_with1467 operator()( const T& a, const T& b ) const {
1468 typename Kind::template List<T>::type l;
1469 l = cons( b, l );
1470 l = cons( a, l );
1471 return l;
1472 }
1473
1474 template <class T>
1475 typename Kind::template List<T>::type
operator ()boost::phoenix::list_with1476 operator()( const T& a, const T& b, const T& c ) const {
1477 typename Kind::template List<T>::type l;
1478 l = cons( c, l );
1479 l = cons( b, l );
1480 l = cons( a, l );
1481 return l;
1482 }
1483
1484 template <class T>
1485 typename Kind::template List<T>::type
operator ()boost::phoenix::list_with1486 operator()( const T& a, const T& b, const T& c, const T& d ) const {
1487 typename Kind::template List<T>::type l;
1488 l = cons( d, l );
1489 l = cons( c, l );
1490 l = cons( b, l );
1491 l = cons( a, l );
1492 return l;
1493 }
1494
1495 template <class T>
1496 typename Kind::template List<T>::type
operator ()boost::phoenix::list_with1497 operator()( const T& a, const T& b, const T& c, const T& d,
1498 const T& e ) const {
1499 typename Kind::template List<T>::type l;
1500 l = cons( e, l );
1501 l = cons( d, l );
1502 l = cons( c, l );
1503 l = cons( b, l );
1504 l = cons( a, l );
1505 return l;
1506 }
1507 };
1508 //////////////////////////////////////////////////////////////////////
1509
1510 }
1511
1512 }
1513
1514 #endif
1515