Chris@102: ////////////////////////////////////////////////////////////////////////////
Chris@102: // lazy_list.hpp
Chris@102: //
Chris@102: // Build lazy operations for Phoenix equivalents for FC++
Chris@102: //
Chris@102: // These are equivalents of the Boost FC++ functoids in list.hpp
Chris@102: //
Chris@102: // Implemented so far:
Chris@102: //
Chris@102: // head tail null
Chris@102: //
Chris@102: // strict_list<T> and associated iterator.
Chris@102: //
Chris@102: // list<T> and odd_list<T>
Chris@102: //
Chris@102: // cons cat
Chris@102: //
Chris@102: // Comparisons between list and odd_list types and separately for strict_list.
Chris@102: //
Chris@102: // NOTES: There is a fix at the moment as I have not yet sorted out
Chris@102: //        how to get back the return type of a functor returning a list type.
Chris@102: //        For the moment I have fixed this as odd_list<T> at two locations,
Chris@102: //        one in list<T> and one in Cons. I am going to leave it like this
Chris@102: //        for now as reading the code, odd_list<T> seems to be correct.
Chris@102: //
Chris@102: //        I am also not happy at the details needed to detect types in Cons.
Chris@102: //
Chris@102: // I think the structure of this file is now complete.
Chris@102: // John Fletcher  February 2015.
Chris@102: //
Chris@102: ////////////////////////////////////////////////////////////////////////////
Chris@102: /*=============================================================================
Chris@102:     Copyright (c) 2000-2003 Brian McNamara and Yannis Smaragdakis
Chris@102:     Copyright (c) 2001-2007 Joel de Guzman
Chris@102:     Copyright (c) 2015 John Fletcher
Chris@102: 
Chris@102:     Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@102:     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@102: ==============================================================================*/
Chris@102: 
Chris@102: ///////////////////////////////////////////////////////////////////////
Chris@102: // This is from Boost FC++ list.hpp reimplemented without Fun0 or Full0
Chris@102: ///////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: /*
Chris@102: concept ListLike: Given a list representation type L
Chris@102: 
Chris@102: L<T> inherits ListLike and has
Chris@102:    // typedefs just show typical values
Chris@102:    typedef T value_type
Chris@102:    typedef L<T> force_result_type
Chris@102:    typedef L<T> delay_result_type
Chris@102:    typedef L<T> tail_result_type
Chris@102:    template <class UU> struct cons_rebind {
Chris@102:       typedef L<UU> type;        // force type
Chris@102:       typedef L<UU> delay_type;  // delay type
Chris@102:    };
Chris@102: 
Chris@102:    L()
Chris@102:    L( a_unique_type_for_nil )
Chris@102:    template <class F> L(F)       // F :: ()->L
Chris@102: 
Chris@102:    constructor: force_result_type( T, L<T> )
Chris@102:    template <class F>
Chris@102:    constructor: force_result_type( T, F )  // F :: ()->L
Chris@102: 
Chris@102:    template <class It>
Chris@102:    L( It, It )
Chris@102: 
Chris@102:    // FIX THIS instead of operator bool(), does Boost have something better?
Chris@102:    operator bool() const
Chris@102:    force_result_type force() const
Chris@102:    delay_result_type delay() const
Chris@102:    T head() const
Chris@102:    tail_result_type tail() const
Chris@102: 
Chris@102:    static const bool is_lazy;   // true if can represent infinite lists
Chris@102: 
Chris@102:    typedef const_iterator;
Chris@102:    typedef const_iterator iterator;  // ListLikes are immutable
Chris@102:    iterator begin() const
Chris@102:    iterator end() const
Chris@102: */
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // End of section from Boost FC++ list.hpp
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: #ifndef BOOST_PHOENIX_FUNCTION_LAZY_LIST
Chris@102: #define BOOST_PHOENIX_FUNCTION_LAZY_LIST
Chris@102: 
Chris@102: #include <boost/phoenix/core.hpp>
Chris@102: #include <boost/phoenix/function.hpp>
Chris@102: #include <boost/intrusive_ptr.hpp>
Chris@102: #include <boost/function.hpp>
Chris@102: #include <boost/type_traits/type_with_alignment.hpp>
Chris@102: //#include "lazy_reuse.hpp"
Chris@102: 
Chris@102: namespace boost {
Chris@102: 
Chris@102:   namespace phoenix {
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // These are the list types being declared.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:    template <class T> class strict_list;
Chris@102:     namespace impl {
Chris@102:    template <class T> class list;
Chris@102:    template <class T> class odd_list;
Chris@102:     }
Chris@102:    // in ref_count.hpp in BoostFC++ now in lazy_operator.hpp
Chris@102:    //typedef unsigned int RefCountType;
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // a_unique_type_for_nil moved to lazy_operator.hpp.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Distinguish lazy lists (list and odd_list) from strict_list.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:     namespace lazy {
Chris@102:       // Copied from Boost FC++ list.hpp
Chris@102:       template <class L, bool is_lazy> struct ensure_lazy_helper {};
Chris@102:       template <class L> struct ensure_lazy_helper<L,true> {
Chris@102:          static void requires_lazy_list_to_prevent_infinite_recursion() {}
Chris@102:       };
Chris@102:       template <class L>
Chris@102:       void ensure_lazy() {
Chris@102:         ensure_lazy_helper<L,L::is_lazy>::
Chris@102:         requires_lazy_list_to_prevent_infinite_recursion();
Chris@102:       }
Chris@102: 
Chris@102:     }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Provide remove reference for types defined for list types.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:     namespace result_of {
Chris@102: 
Chris@102:       template < typename L >
Chris@102:       class ListType
Chris@102:       {
Chris@102:       public:
Chris@102:         typedef typename boost::remove_reference<L>::type LType;
Chris@102:         typedef typename LType::value_type value_type;
Chris@102:         typedef typename LType::tail_result_type tail_result_type;
Chris@102:         typedef typename LType::force_result_type force_result_type;
Chris@102:         typedef typename LType::delay_result_type delay_result_type;
Chris@102:       };
Chris@102: 
Chris@102:       template <>
Chris@102:       class ListType<a_unique_type_for_nil>
Chris@102:       {
Chris@102:       public:
Chris@102:         typedef a_unique_type_for_nil LType;
Chris@102:         //typedef a_unique_type_for_nil value_type;
Chris@102:       };
Chris@102: 
Chris@102:       template <typename F, typename T>
Chris@102:       struct ResultType {
Chris@102:         typedef typename impl::odd_list<T> type;
Chris@102:       };
Chris@102:   
Chris@102:     }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // ListLike is a property inherited by any list type to enable it to
Chris@102: // work with the functions being implemented in this file.
Chris@102: // It provides the check for the structure described above.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:    namespace listlike {
Chris@102: 
Chris@102:        struct ListLike {};   // This lets us use is_base_and_derived() to see
Chris@102:        // (at compile-time) what classes are user-defined lists.
Chris@102: 
Chris@102:  
Chris@102:        template <class L, bool is_lazy> struct ensure_lazy_helper {};
Chris@102:        template <class L> struct ensure_lazy_helper<L,true> {
Chris@102:            static void requires_lazy_list_to_prevent_infinite_recursion() {}
Chris@102:        };
Chris@102:        template <class L>
Chris@102:        void ensure_lazy() {
Chris@102:          ensure_lazy_helper<L,L::is_lazy>::
Chris@102:          requires_lazy_list_to_prevent_infinite_recursion();
Chris@102:        }
Chris@102: 
Chris@102:        template <class L, bool b>
Chris@102:        struct EnsureListLikeHelp {
Chris@102:            static void trying_to_call_a_list_function_on_a_non_list() {}
Chris@102:        };
Chris@102:        template <class L> struct EnsureListLikeHelp<L,false> { };
Chris@102:        template <class L>
Chris@102:        void EnsureListLike() {
Chris@102:           typedef typename result_of::ListType<L>::LType LType;
Chris@102:           EnsureListLikeHelp<L,boost::is_base_and_derived<ListLike,LType>::value>::
Chris@102:              trying_to_call_a_list_function_on_a_non_list();
Chris@102:        }
Chris@102: 
Chris@102:       template <class L>
Chris@102:       bool is_a_unique_type_for_nil(const L& l) {
Chris@102:          return false;
Chris@102:       }
Chris@102:   
Chris@102:       template <>
Chris@102:       bool is_a_unique_type_for_nil<a_unique_type_for_nil>
Chris@102:       (const a_unique_type_for_nil& /* n */) {
Chris@102:          return true;
Chris@102:       }
Chris@102: 
Chris@102:       template <class L>
Chris@102:       struct detect_nil {
Chris@102:         static const bool is_nil = false;
Chris@102:       };
Chris@102: 
Chris@102:       template <>
Chris@102:       struct detect_nil<a_unique_type_for_nil> {
Chris@102:        static const bool is_nil = true;
Chris@102:       };
Chris@102: 
Chris@102:       template <>
Chris@102:       struct detect_nil<a_unique_type_for_nil&> {
Chris@102:        static const bool is_nil = true;
Chris@102:       };
Chris@102: 
Chris@102:       template <>
Chris@102:       struct detect_nil<const a_unique_type_for_nil&> {
Chris@102:        static const bool is_nil = true;
Chris@102:       };
Chris@102:           
Chris@102:     }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Implement lazy functions for list types. cat and cons come later.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: #ifndef BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH
Chris@102: #define BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH 1000
Chris@102: #endif
Chris@102: 
Chris@102:     namespace impl {
Chris@102: 
Chris@102:       struct Head
Chris@102:       {
Chris@102:         template <typename Sig>
Chris@102:         struct result;
Chris@102: 
Chris@102:         template <typename This, typename L>
Chris@102:         struct result<This(L)>
Chris@102:         {
Chris@102:           typedef typename result_of::ListType<L>::value_type type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename L>
Chris@102:         typename result<Head(L)>::type
Chris@102:         operator()(const L & l) const
Chris@102:         {
Chris@102:           listlike::EnsureListLike<L>();
Chris@102:           return l.head();
Chris@102:         }
Chris@102: 
Chris@102:       };
Chris@102: 
Chris@102:       struct Tail
Chris@102:       {
Chris@102:         template <typename Sig>
Chris@102:         struct result;
Chris@102: 
Chris@102:         template <typename This, typename L>
Chris@102:         struct result<This(L)>
Chris@102:         {
Chris@102:           typedef typename result_of::ListType<L>::tail_result_type type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename L>
Chris@102:         typename result<Tail(L)>::type
Chris@102:         operator()(const L & l) const
Chris@102:         {
Chris@102:           listlike::EnsureListLike<L>();
Chris@102:           return l.tail();
Chris@102:         }
Chris@102: 
Chris@102:       };
Chris@102: 
Chris@102:       struct Null
Chris@102:       {
Chris@102:         template <typename Sig>
Chris@102:         struct result;
Chris@102: 
Chris@102:         template <typename This, typename L>
Chris@102:         struct result<This(L)>
Chris@102:         {
Chris@102:             typedef bool type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename L>
Chris@102:         typename result<Null(L)>::type
Chris@102:         //bool
Chris@102:         operator()(const L& l) const
Chris@102:         {
Chris@102:           listlike::EnsureListLike<L>();
Chris@102:           return !l;
Chris@102:         }
Chris@102: 
Chris@102:       };
Chris@102: 
Chris@102:       struct Delay {
Chris@102:         template <typename Sig>
Chris@102:         struct result;
Chris@102: 
Chris@102:         template <typename This, typename L>
Chris@102:         struct result<This(L)>
Chris@102:         {
Chris@102:           typedef typename result_of::ListType<L>::delay_result_type type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename L>
Chris@102:         typename result<Delay(L)>::type
Chris@102:         operator()(const L & l) const
Chris@102:         {
Chris@102:           listlike::EnsureListLike<L>();
Chris@102:           return l.delay();
Chris@102:         }
Chris@102: 
Chris@102:       };
Chris@102: 
Chris@102:       struct Force {
Chris@102:         template <typename Sig>
Chris@102:         struct result;
Chris@102: 
Chris@102:         template <typename This, typename L>
Chris@102:         struct result<This(L)>
Chris@102:         {
Chris@102:           typedef typename result_of::ListType<L>::force_result_type type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename L>
Chris@102:         typename result<Force(L)>::type
Chris@102:         operator()(const L & l) const
Chris@102:         {
Chris@102:           listlike::EnsureListLike<L>();
Chris@102:           return l.force();
Chris@102:         }
Chris@102: 
Chris@102:       };
Chris@102: 
Chris@102:     }
Chris@102:     //BOOST_PHOENIX_ADAPT_CALLABLE(head, impl::head, 1)
Chris@102:     //BOOST_PHOENIX_ADAPT_CALLABLE(tail, impl::tail, 1)
Chris@102:     //BOOST_PHOENIX_ADAPT_CALLABLE(null, impl::null, 1)
Chris@102:     typedef boost::phoenix::function<impl::Head> Head;
Chris@102:     typedef boost::phoenix::function<impl::Tail> Tail;
Chris@102:     typedef boost::phoenix::function<impl::Null> Null;
Chris@102:     typedef boost::phoenix::function<impl::Delay> Delay;
Chris@102:     typedef boost::phoenix::function<impl::Force> Force;
Chris@102:     Head head;
Chris@102:     Tail tail;
Chris@102:     Null null;
Chris@102:     Delay delay;
Chris@102:     Force force;
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // These definitions used for strict_list are imported from BoostFC++
Chris@102: // unchanged.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: namespace impl {
Chris@102: template <class T>
Chris@102: struct strict_cons : public boost::noncopyable {
Chris@102:    mutable RefCountType refC;
Chris@102:    T head;
Chris@102:    typedef boost::intrusive_ptr<strict_cons> tail_type;
Chris@102:    tail_type tail;
Chris@102:    strict_cons( const T& h, const tail_type& t ) : refC(0), head(h), tail(t) {}
Chris@102: 
Chris@102: };
Chris@102: template <class T>
Chris@102: void intrusive_ptr_add_ref( const strict_cons<T>* p ) {
Chris@102:    ++ (p->refC);
Chris@102: }
Chris@102: template <class T>
Chris@102: void intrusive_ptr_release( const strict_cons<T>* p ) {
Chris@102:    if( !--(p->refC) ) delete p;
Chris@102: }
Chris@102: 
Chris@102: template <class T>
Chris@102: class strict_list_iterator
Chris@102: : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> {
Chris@102:    typedef boost::intrusive_ptr<strict_cons<T> > rep_type;
Chris@102:    rep_type l;
Chris@102:    bool is_nil;
Chris@102:    void advance() {
Chris@102:       l = l->tail;
Chris@102:       if( !l )
Chris@102:          is_nil = true;
Chris@102:    }
Chris@102:    class Proxy {  // needed for operator->
Chris@102:       const T x;
Chris@102:       friend class strict_list_iterator;
Chris@102:       Proxy( const T& xx ) : x(xx) {}
Chris@102:    public:
Chris@102:       const T* operator->() const { return &x; }
Chris@102:    };
Chris@102: public:
Chris@102:    strict_list_iterator() : l(), is_nil(true) {}
Chris@102:    explicit strict_list_iterator( const rep_type& ll ) : l(ll), is_nil(!ll) {}
Chris@102:    
Chris@102:    const T operator*() const { return l->head; }
Chris@102:    const Proxy operator->() const { return Proxy(l->head); }
Chris@102:    strict_list_iterator<T>& operator++() {
Chris@102:       advance();
Chris@102:       return *this;
Chris@102:    }
Chris@102:    const strict_list_iterator<T> operator++(int) {
Chris@102:       strict_list_iterator<T> i( *this );
Chris@102:       advance();
Chris@102:       return i;
Chris@102:    }
Chris@102:    bool operator==( const strict_list_iterator<T>& i ) const {
Chris@102:       return is_nil && i.is_nil;
Chris@102:    }
Chris@102:    bool operator!=( const strict_list_iterator<T>& i ) const {
Chris@102:       return ! this->operator==(i);
Chris@102:    }
Chris@102: };
Chris@102: }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:    template <class T>
Chris@102:    class strict_list : public listlike::ListLike
Chris@102:    {
Chris@102:        typedef boost::intrusive_ptr<impl::strict_cons<T> > rep_type;
Chris@102:        rep_type rep;
Chris@102:        struct Make {};
Chris@102: 
Chris@102:        template <class Iter>
Chris@102:        static rep_type help( Iter a, const Iter& b ) {
Chris@102:            rep_type r;
Chris@102:            while( a != b ) {
Chris@102:               T x( *a );
Chris@102:               r = rep_type( new impl::strict_cons<T>( x, r ) );
Chris@102:               ++a;
Chris@102:            }
Chris@102:            return r;
Chris@102:        }
Chris@102: 
Chris@102:    public:
Chris@102:        static const bool is_lazy = false;
Chris@102: 
Chris@102:        typedef T value_type;
Chris@102:        typedef strict_list force_result_type;
Chris@102:        typedef strict_list delay_result_type;
Chris@102:        typedef strict_list tail_result_type;
Chris@102:        template <class UU> struct cons_rebind {
Chris@102:            typedef strict_list<UU> type;
Chris@102:            typedef strict_list<UU> delay_type;
Chris@102:        };
Chris@102:  
Chris@102: 
Chris@102:    strict_list( Make, const rep_type& r ) : rep(r) {}
Chris@102: 
Chris@102:    strict_list() : rep() {}
Chris@102: 
Chris@102:    strict_list( a_unique_type_for_nil ) : rep() {}
Chris@102: 
Chris@102:    template <class F>
Chris@102:    strict_list( const F& f ) : rep( f().rep ) {
Chris@102:      // I cannot do this yet.
Chris@102:      //functoid_traits<F>::template ensure_accepts<0>::args();
Chris@102:    }
Chris@102: 
Chris@102:    strict_list( const T& x, const strict_list& y )
Chris@102:       : rep( new impl::strict_cons<T>(x,y.rep) ) {}
Chris@102: 
Chris@102:    template <class F>
Chris@102:    strict_list( const T& x, const F& f )
Chris@102:       : rep( new impl::strict_cons<T>(x,f().rep) ) {}
Chris@102:    
Chris@102:      operator bool() const { return (bool)rep; }
Chris@102:    force_result_type force() const { return *this; }
Chris@102:    delay_result_type delay() const { return *this; }
Chris@102:    T head() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:       if( !*this )
Chris@102:          throw lazy_exception("Tried to take head() of empty strict_list");
Chris@102: #endif
Chris@102:       return rep->head;
Chris@102:    }
Chris@102:    tail_result_type tail() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:       if( !*this )
Chris@102:          throw lazy_exception("Tried to take tail() of empty strict_list");
Chris@102: #endif
Chris@102:       return strict_list(Make(),rep->tail);
Chris@102:    }
Chris@102: 
Chris@102:    template <class Iter>
Chris@102:    strict_list( const Iter& a, const Iter& b ) : rep( rep_type() ) {
Chris@102:       // How ironic.  We need to reverse the iterator range in order to
Chris@102:       // non-recursively build this!
Chris@102:       std::vector<T> tmp(a,b);
Chris@102:       rep = help( tmp.rbegin(), tmp.rend() );
Chris@102:    }
Chris@102: 
Chris@102:    // Since the strict_cons destructor can't call the strict_list
Chris@102:    // destructor, the "simple" iterative destructor is correct and
Chris@102:    // efficient.  Hurray.
Chris@102:    ~strict_list() { while(rep && (rep->refC == 1)) rep = rep->tail; }
Chris@102: 
Chris@102:    // The following helps makes strict_list almost an STL "container"
Chris@102:    typedef impl::strict_list_iterator<T> const_iterator;
Chris@102:    typedef const_iterator iterator;         // strict_list is immutable
Chris@102:    iterator begin() const { return impl::strict_list_iterator<T>( rep ); }
Chris@102:    iterator end() const   { return impl::strict_list_iterator<T>(); }
Chris@102: 
Chris@102:    };
Chris@102: 
Chris@102:     // All of these null head and tail are now non lazy using e.g. null(a)().
Chris@102:     // They need an extra () e.g. null(a)().
Chris@102:     template <class T>
Chris@102:     bool operator==( const strict_list<T>& a, a_unique_type_for_nil ) {
Chris@102:       return null(a)();
Chris@102:     }
Chris@102:     template <class T>
Chris@102:     bool operator==( a_unique_type_for_nil, const strict_list<T>& a ) {
Chris@102:       return null(a)();
Chris@102:     }
Chris@102:     template <class T>
Chris@102:     bool operator==( const strict_list<T>& a, const strict_list<T>& b ) {
Chris@102:         if( null(a)() && null(b)() )
Chris@102:             return true;
Chris@102:         if( null(a)() || null(b)() )
Chris@102:             return false;
Chris@102:         return (head(a)()==head(b)()) &&
Chris@102:             (tail(a)()==tail(b)());
Chris@102:     }
Chris@102: 
Chris@102:     template <class T>
Chris@102:     bool operator<( const strict_list<T>& a, const strict_list<T>& b ) {
Chris@102:       if( null(a)() && !null(b)() )  return true;
Chris@102:         if( null(b)() )                      return false;
Chris@102:         if( head(b)() < head(a)() )    return false;
Chris@102:         if( head(a)() < head(b)() )    return true;
Chris@102:         return (tail(a)() < tail(b)());
Chris@102:     }
Chris@102:     template <class T>
Chris@102:     bool operator<( const strict_list<T>&, a_unique_type_for_nil ) {
Chris@102:         return false;
Chris@102:     }
Chris@102:     template <class T>
Chris@102:     bool operator<( a_unique_type_for_nil, const strict_list<T>& b ) {
Chris@102:       return !(null(b)());
Chris@102:     }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Class list<T> is the primary interface to the user for lazy lists.
Chris@102: //////////////////////////////////////////////////////////////////////{
Chris@102:     namespace impl {
Chris@102:       using fcpp::INV;
Chris@102:       using fcpp::VAR;
Chris@102:       using fcpp::reuser2;
Chris@102: 
Chris@102:       struct CacheEmpty {};
Chris@102: 
Chris@102:       template <class T> class Cache;
Chris@102:       template <class T> class odd_list;
Chris@102:       template <class T> class list_iterator;
Chris@102:       template <class It, class T>
Chris@102:       struct ListItHelp2 /*: public c_fun_type<It,It,odd_list<T> >*/ {
Chris@102:         // This will need a return type.
Chris@102:         typedef odd_list<T> return_type;
Chris@102:         odd_list<T> operator()( It begin, const It& end,
Chris@102:           reuser2<INV,VAR,INV,ListItHelp2<It,T>,It,It> r = NIL ) const;
Chris@102:       };
Chris@102:       template <class U,class F> struct cvt;
Chris@102:       template <class T, class F, class R> struct ListHelp;
Chris@102:       template <class T> Cache<T>* xempty_helper();
Chris@102:       template <class T, class F, class L, bool b> struct ConsHelp2;
Chris@102: 
Chris@102:       struct ListRaw {};
Chris@102: 
Chris@102:       template <class T>
Chris@102:       class list : public listlike::ListLike
Chris@102:       {
Chris@102:         // never NIL, unless an empty odd_list
Chris@102:         boost::intrusive_ptr<Cache<T> > rep;
Chris@102: 
Chris@102:         template <class U> friend class Cache;
Chris@102:         template <class U> friend class odd_list;
Chris@102:         template <class TT, class F, class L, bool b> friend struct ConsHelp2;
Chris@102:         template <class U,class F> friend struct cvt;
Chris@102: 
Chris@102:         list( const boost::intrusive_ptr<Cache<T> >& p ) : rep(p) { }
Chris@102:         list( ListRaw, Cache<T>* p ) : rep(p) { }
Chris@102: 
Chris@102:         bool priv_isEmpty() const {
Chris@102:           return rep->cache().second.rep == Cache<T>::XNIL();
Chris@102:         }
Chris@102:         T priv_head() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:           if( priv_isEmpty() )
Chris@102:              throw lazy_exception("Tried to take head() of empty list");
Chris@102: #endif
Chris@102:           return rep->cache().first();
Chris@102:         }
Chris@102:         list<T> priv_tail() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:           if( priv_isEmpty() )
Chris@102:             throw lazy_exception("Tried to take tail() of empty list");
Chris@102: #endif
Chris@102:           return rep->cache().second;
Chris@102:         }
Chris@102: 
Chris@102: 
Chris@102:       public:
Chris@102:         static const bool is_lazy = true;
Chris@102: 
Chris@102:         typedef T value_type;
Chris@102:         typedef list tail_result_type;
Chris@102:         typedef odd_list<T> force_result_type;
Chris@102:         typedef list delay_result_type;
Chris@102:         template <class UU> struct cons_rebind {
Chris@102:            typedef odd_list<UU> type;
Chris@102:            typedef list<UU> delay_type;
Chris@102:         };
Chris@102: 
Chris@102:         list( a_unique_type_for_nil ) : rep( Cache<T>::XEMPTY() ) { }
Chris@102:         list() : rep( Cache<T>::XEMPTY() ) { }
Chris@102: 
Chris@102:         template <class F>  // works on both ()->odd_list and ()->list
Chris@102:         // At the moment this is fixed for odd_list<T>.
Chris@102:         // I need to do more work to get the general result.
Chris@102:         list( const F& f )
Chris@102:           : rep( ListHelp<T,F,odd_list<T> >()(f) ) { }
Chris@102:         //: rep( ListHelp<T,F,typename F::result_type>()(f) ) { }
Chris@102: 
Chris@102:         operator bool() const { return !priv_isEmpty(); }
Chris@102:         const force_result_type& force() const { return rep->cache(); }
Chris@102:         const delay_result_type& delay() const { return *this; }
Chris@102:         // Note: force returns a reference;
Chris@102:         // implicit conversion now returns a copy.
Chris@102:         operator odd_list<T>() const { return force(); }
Chris@102: 
Chris@102:         T head() const { return priv_head(); }
Chris@102:         tail_result_type tail() const { return priv_tail(); }
Chris@102: 
Chris@102:         // The following helps makes list almost an STL "container"
Chris@102:         typedef list_iterator<T> const_iterator;
Chris@102:         typedef const_iterator iterator;         // list is immutable
Chris@102:         iterator begin() const { return list_iterator<T>( *this ); }
Chris@102:         iterator end() const   { return list_iterator<T>(); }
Chris@102: 
Chris@102:         // end of list<T>
Chris@102:       };
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Class odd_list<T> is not normally accessed by the user.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:       struct OddListDummyY {};
Chris@102: 
Chris@102:       template <class T>
Chris@102:       class odd_list : public listlike::ListLike
Chris@102:       {
Chris@102:       public:
Chris@102:         typedef
Chris@102:         typename boost::type_with_alignment<boost::alignment_of<T>::value>::type
Chris@102:         xfst_type;
Chris@102:       private:
Chris@102:         union { xfst_type fst; unsigned char dummy[sizeof(T)]; };
Chris@102: 
Chris@102:         const T& first() const {
Chris@102:            return *static_cast<const T*>(static_cast<const void*>(&fst));
Chris@102:         }
Chris@102:         T& first() {
Chris@102:            return *static_cast<T*>(static_cast<void*>(&fst));
Chris@102:         }
Chris@102:         list<T>  second;   // If XNIL, then this odd_list is NIL
Chris@102: 
Chris@102:         template <class U> friend class list;
Chris@102:         template <class U> friend class Cache;
Chris@102: 
Chris@102:         odd_list( OddListDummyY )
Chris@102:           : second( Cache<T>::XBAD() ) { }
Chris@102: 
Chris@102:         void init( const T& x ) {
Chris@102:            new (static_cast<void*>(&fst)) T(x);
Chris@102:         }
Chris@102: 
Chris@102:         bool fst_is_valid() const {
Chris@102:            if( second.rep != Cache<T>::XNIL() )
Chris@102:               if( second.rep != Cache<T>::XBAD() )
Chris@102:                  return true;
Chris@102:            return false;
Chris@102:         }
Chris@102: 
Chris@102:         bool priv_isEmpty() const { return second.rep == Cache<T>::XNIL(); }
Chris@102:         T priv_head() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:            if( priv_isEmpty() )
Chris@102:              throw lazy_exception("Tried to take head() of empty odd_list");
Chris@102: #endif
Chris@102:            return first();
Chris@102:         }
Chris@102: 
Chris@102:         list<T> priv_tail() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:            if( priv_isEmpty() )
Chris@102:              throw lazy_exception("Tried to take tail() of empty odd_list");
Chris@102: #endif
Chris@102:            return second;
Chris@102:         }
Chris@102: 
Chris@102:       public:
Chris@102:         static const bool is_lazy = true;
Chris@102: 
Chris@102:         typedef T value_type;
Chris@102:         typedef list<T> tail_result_type;
Chris@102:         typedef odd_list<T> force_result_type;
Chris@102:         typedef list<T> delay_result_type;
Chris@102:         template <class UU> struct cons_rebind {
Chris@102:           typedef odd_list<UU> type;
Chris@102:           typedef list<UU> delay_type;
Chris@102:         };
Chris@102: 
Chris@102:         odd_list() : second( Cache<T>::XNIL() ) { }
Chris@102:         odd_list( a_unique_type_for_nil ) : second( Cache<T>::XNIL() ) { }
Chris@102:         odd_list( const T& x, const list<T>& y ) : second(y) { init(x); }
Chris@102:         odd_list( const T& x, a_unique_type_for_nil ) : second(NIL) { init(x); }
Chris@102: 
Chris@102:         odd_list( const odd_list<T>& x ) : second(x.second) {
Chris@102:            if( fst_is_valid() ) {
Chris@102:               init( x.first() );
Chris@102:            }
Chris@102:         }
Chris@102: 
Chris@102:         template <class It>
Chris@102:         odd_list( It begin, const It& end )
Chris@102:           : second( begin==end ? Cache<T>::XNIL() :
Chris@102:              ( init(*begin++), list<T>( begin, end ) ) ) {}
Chris@102: 
Chris@102:         odd_list<T>& operator=( const odd_list<T>& x ) {
Chris@102:            if( this == &x ) return *this;
Chris@102:            if( fst_is_valid() ) {
Chris@102:              if( x.fst_is_valid() )
Chris@102:                first() = x.first();
Chris@102:              else
Chris@102:                first().~T();
Chris@102:            }
Chris@102:            else {
Chris@102:               if( x.fst_is_valid() )
Chris@102:                  init( x.first() );
Chris@102:            }
Chris@102:            second = x.second;
Chris@102:            return *this;
Chris@102:         }
Chris@102:       
Chris@102:        ~odd_list() {
Chris@102:           if( fst_is_valid() ) {
Chris@102:             first().~T();
Chris@102:           }
Chris@102:         }
Chris@102: 
Chris@102:         operator bool() const { return !priv_isEmpty(); }
Chris@102:         const force_result_type& force() const { return *this; }
Chris@102:         delay_result_type delay() const { return list<T>(*this); }
Chris@102: 
Chris@102:         T head() const { return priv_head(); }
Chris@102:         tail_result_type tail() const { return priv_tail(); }
Chris@102: 
Chris@102:         // The following helps makes odd_list almost an STL "container"
Chris@102:         typedef list_iterator<T> const_iterator;
Chris@102:         typedef const_iterator iterator;         // odd_list is immutable
Chris@102:         iterator begin() const { return list_iterator<T>( this->delay() ); }
Chris@102:         iterator end() const   { return list_iterator<T>(); }
Chris@102: 
Chris@102:         // end of odd_list<T>
Chris@102:       };
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // struct cvt
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:       // This converts ()->list<T> to ()->odd_list<T>.
Chris@102:       // In other words, here is the 'extra work' done when using the
Chris@102:       // unoptimized interface.
Chris@102:       template <class U,class F>
Chris@102:       struct cvt /*: public c_fun_type<odd_list<U> >*/ {
Chris@102:         typedef odd_list<U> return_type;
Chris@102:         F f;
Chris@102:         cvt( const F& ff ) : f(ff) {}
Chris@102:         odd_list<U> operator()() const {
Chris@102:            list<U> l = f();
Chris@102:            return l.force();
Chris@102:         }
Chris@102:       };
Chris@102: 
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Cache<T> and associated functions.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: // I malloc a RefCountType to hold the refCount and init it to 1 to ensure the
Chris@102: // refCount will never get to 0, so the destructor-of-global-object
Chris@102: // order at the end of the program is a non-issue.  In other words, the
Chris@102: // memory allocated here is only reclaimed by the operating system.
Chris@102:     template <class T>
Chris@102:     Cache<T>* xnil_helper() {
Chris@102:        void *p = std::malloc( sizeof(RefCountType) );
Chris@102:        *((RefCountType*)p) = 1;
Chris@102:        return static_cast<Cache<T>*>( p );
Chris@102:     }
Chris@102: 
Chris@102:     template <class T>
Chris@102:     Cache<T>* xnil_helper_nil() {
Chris@102:        Cache<T>* p = xnil_helper<T>();
Chris@102:        return p;
Chris@102:     }
Chris@102: 
Chris@102:     template <class T>
Chris@102:     Cache<T>* xnil_helper_bad() {
Chris@102:        Cache<T>* p = xnil_helper<T>();
Chris@102:        return p;
Chris@102:     }
Chris@102: 
Chris@102:     template <class T>
Chris@102:     Cache<T>* xempty_helper() {
Chris@102:        Cache<T>* p = new Cache<T>( CacheEmpty() );
Chris@102:        return p;
Chris@102:     }
Chris@102: 
Chris@102:     // This makes a boost phoenix function type with return type
Chris@102:     // odd_list<T>
Chris@102:     template <class T>
Chris@102:     struct fun0_type_helper{
Chris@102:        typedef boost::function0<odd_list<T> > fun_type;
Chris@102:        typedef boost::phoenix::function<fun_type> phx_type;
Chris@102:     };
Chris@102: 
Chris@102: 
Chris@102:       template <class T>
Chris@102:       struct make_fun0_odd_list {
Chris@102: 
Chris@102:         typedef typename fun0_type_helper<T>::fun_type fun_type;
Chris@102:         typedef typename fun0_type_helper<T>::phx_type phx_type;
Chris@102:         typedef phx_type result_type;
Chris@102: 
Chris@102:         template <class F>
Chris@102:         result_type operator()(const F& f) const
Chris@102:         {
Chris@102:             fun_type ff(f);
Chris@102:             phx_type g(ff);
Chris@102:             return g;
Chris@102:         }
Chris@102: 
Chris@102:         // Overload for the case where it is a boost phoenix function already.
Chris@102:         template <class F>
Chris@102:         typename boost::phoenix::function<F> operator()
Chris@102:           (const boost::phoenix::function<F>& f) const
Chris@102:         {
Chris@102:             return f;
Chris@102:         }
Chris@102: 
Chris@102:     };
Chris@102: 
Chris@102:     template <class T>
Chris@102:     class Cache : boost::noncopyable {
Chris@102:        mutable RefCountType refC;
Chris@102:        // This is the boost::function type
Chris@102:        typedef typename fun0_type_helper<T>::fun_type fun_odd_list_T;
Chris@102:        // This is the boost::phoenix::function type;
Chris@102:        typedef typename fun0_type_helper<T>::phx_type fun0_odd_list_T;
Chris@102:        mutable fun0_odd_list_T fxn;
Chris@102:        mutable odd_list<T>     val;
Chris@102:        // val.second.rep can be XBAD, XNIL, or a valid ptr
Chris@102:        //  - XBAD: val is invalid (fxn is valid)
Chris@102:        //  - XNIL: this is the empty list
Chris@102:        //  - anything else: val.first() is head, val.second is tail()
Chris@102: 
Chris@102:        // This functoid should never be called; it represents a
Chris@102:        // self-referent Cache, which should be impossible under the current
Chris@102:        // implementation.  Nonetheless, we need a 'dummy' function object to
Chris@102:        // represent invalid 'fxn's (val.second.rep!=XBAD), and this
Chris@102:        // implementation seems to be among the most reasonable.
Chris@102:        struct blackhole_helper /*: c_fun_type< odd_list<T> >*/ {
Chris@102:           typedef odd_list<T> return_type;
Chris@102:           odd_list<T> operator()() const {
Chris@102: #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
Chris@102:             throw lazy_exception("You have entered a black hole.");
Chris@102: #else
Chris@102:             return odd_list<T>();
Chris@102: #endif
Chris@102:           }
Chris@102:        };
Chris@102: 
Chris@102:        // Don't get rid of these XFOO() functions; they impose no overhead,
Chris@102:        // and provide a useful place to add debugging code for tracking down
Chris@102:        // before-main()-order-of-initialization problems.
Chris@102:        static const boost::intrusive_ptr<Cache<T> >& XEMPTY() {
Chris@102:           static boost::intrusive_ptr<Cache<T> > xempty( xempty_helper<T>() );
Chris@102:           return xempty;
Chris@102:        }
Chris@102:        static const boost::intrusive_ptr<Cache<T> >& XNIL() {
Chris@102:        // this list is nil
Chris@102:           static boost::intrusive_ptr<Cache<T> > xnil( xnil_helper_nil<T>() );
Chris@102:           return xnil;
Chris@102:        }
Chris@102: 
Chris@102:        static const boost::intrusive_ptr<Cache<T> >& XBAD() {
Chris@102:        // the pair is invalid; use fxn
Chris@102:           static boost::intrusive_ptr<Cache<T> > xbad( xnil_helper_bad<T>() );
Chris@102:           return xbad;
Chris@102:        }
Chris@102: 
Chris@102:        static fun0_odd_list_T /*<odd_list<T> >*/ the_blackhole;
Chris@102:        static fun0_odd_list_T& blackhole() {
Chris@102:          static fun0_odd_list_T the_blackhole;
Chris@102:          //( make_fun0_odd_list<T>()( blackhole_helper() ) );
Chris@102:          return the_blackhole;
Chris@102:        }
Chris@102: 
Chris@102:        odd_list<T>& cache() const {
Chris@102:          if( val.second.rep == XBAD() ) {
Chris@102:             val = fxn()();
Chris@102:             fxn = blackhole();
Chris@102:          }
Chris@102:          return val;
Chris@102:        }
Chris@102: 
Chris@102:        template <class U> friend class list;
Chris@102:        template <class U> friend class odd_list;
Chris@102:        template <class TT, class F, class L, bool b> friend struct ConsHelp2;
Chris@102:        template <class U,class F> friend struct cvt;
Chris@102:        template <class U, class F, class R> friend struct ListHelp;
Chris@102:        template <class U> friend Cache<U>* xempty_helper();
Chris@102: 
Chris@102:        Cache( CacheEmpty ) : refC(0), fxn(blackhole()), val() {}
Chris@102:        Cache( const odd_list<T>& x ) : refC(0), fxn(blackhole()), val(x) {}
Chris@102:        Cache( const T& x, const list<T>& l ) : refC(0),fxn(blackhole()),val(x,l)
Chris@102:           {}
Chris@102: 
Chris@102:        Cache( const fun0_odd_list_T& f )
Chris@102:          : refC(0), fxn(f), val( OddListDummyY() ) {}
Chris@102: 
Chris@102:        // f must be a boost phoenix function object?
Chris@102:        template <class F>
Chris@102:        Cache( const F& f )    // ()->odd_list
Chris@102:          : refC(0), fxn(make_fun0_odd_list<T>()(f)), val( OddListDummyY() ) {}
Chris@102: 
Chris@102:        // This is for ()->list<T> to ()->odd_list<T>
Chris@102:        struct CvtFxn {};
Chris@102:        template <class F>
Chris@102:        Cache( CvtFxn, const F& f )    // ()->list
Chris@102:          :  refC(0), fxn(make_fun0_odd_list<T>()(cvt<T,F>(f))), val( OddListDummyY() ) {}
Chris@102: 
Chris@102:        template <class X>
Chris@102:        friend void intrusive_ptr_add_ref( const Cache<X>* p );
Chris@102:        template <class X>
Chris@102:        friend void intrusive_ptr_release( const Cache<X>* p );
Chris@102:     };
Chris@102: 
Chris@102:     template <class T>
Chris@102:     void intrusive_ptr_add_ref( const Cache<T>* p ) {
Chris@102:         ++ (p->refC);
Chris@102:     }
Chris@102:     template <class T>
Chris@102:     void intrusive_ptr_release( const Cache<T>* p ) {
Chris@102:         if( !--(p->refC) ) delete p;
Chris@102:     }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Rest of list's stuff
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: template <class T, class F> struct ListHelp<T,F,list<T> > {
Chris@102:    boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const {
Chris@102:       return boost::intrusive_ptr<Cache<T> >
Chris@102:          (new Cache<T>(typename Cache<T>::CvtFxn(),f));
Chris@102:    }
Chris@102: };
Chris@102: template <class T, class F> struct ListHelp<T,F,odd_list<T> > {
Chris@102:    boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const {
Chris@102:       return boost::intrusive_ptr<Cache<T> >(new Cache<T>(f));
Chris@102:    }
Chris@102: };
Chris@102: 
Chris@102: template <class T>
Chris@102: class list_iterator
Chris@102: : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> {
Chris@102:    list<T> l;
Chris@102:    bool is_nil;
Chris@102:    void advance() {
Chris@102:       l = l.tail();
Chris@102:       if( !l )
Chris@102:          is_nil = true;
Chris@102:    }
Chris@102:    class Proxy {  // needed for operator->
Chris@102:       const T x;
Chris@102:       friend class list_iterator;
Chris@102:       Proxy( const T& xx ) : x(xx) {}
Chris@102:    public:
Chris@102:       const T* operator->() const { return &x; }
Chris@102:    };
Chris@102: public:
Chris@102:    list_iterator() : l(), is_nil(true) {}
Chris@102:    explicit list_iterator( const list<T>& ll ) : l(ll), is_nil(!ll) {}
Chris@102:    
Chris@102:    const T operator*() const { return l.head(); }
Chris@102:    const Proxy operator->() const { return Proxy(l.head()); }
Chris@102:    list_iterator<T>& operator++() {
Chris@102:       advance();
Chris@102:       return *this;
Chris@102:    }
Chris@102:    const list_iterator<T> operator++(int) {
Chris@102:       list_iterator<T> i( *this );
Chris@102:       advance();
Chris@102:       return i;
Chris@102:    }
Chris@102:    bool operator==( const list_iterator<T>& i ) const {
Chris@102:       return is_nil && i.is_nil;
Chris@102:    }
Chris@102:    bool operator!=( const list_iterator<T>& i ) const {
Chris@102:       return ! this->operator==(i);
Chris@102:    }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102:     } // namespace impl
Chris@102: 
Chris@102:   using impl::list;
Chris@102:   using impl::odd_list;
Chris@102:   using impl::list_iterator;
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // op== and op<, overloaded for all combos of list, odd_list, and NIL
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // All of these null head and tail are now non lazy using e.g. null(a)().
Chris@102: // They need an extra () e.g. null(a)().
Chris@102: 
Chris@102: // FIX THIS comparison operators can be implemented simpler with enable_if
Chris@102: template <class T>
Chris@102: bool operator==( const odd_list<T>& a, a_unique_type_for_nil ) {
Chris@102:   return null(a)();
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( const list<T>& a, a_unique_type_for_nil ) {
Chris@102:   return null(a)();
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( a_unique_type_for_nil, const odd_list<T>& a ) {
Chris@102:   return null(a)();
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( a_unique_type_for_nil, const list<T>& a ) {
Chris@102:   return null(a)();
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( const list<T>& a, const list<T>& b ) {
Chris@102:   if( null(a)() && null(b)() )
Chris@102:       return true;
Chris@102:   if( null(a)() || null(b)() )
Chris@102:       return false;
Chris@102:   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( const odd_list<T>& a, const odd_list<T>& b ) {
Chris@102:   if( null(a)() && null(b)() )
Chris@102:       return true;
Chris@102:   if( null(a)() || null(b)() )
Chris@102:       return false;
Chris@102:   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( const list<T>& a, const odd_list<T>& b ) {
Chris@102:   if( null(a)() && null(b)() )
Chris@102:       return true;
Chris@102:   if( null(a)() || null(b)() )
Chris@102:       return false;
Chris@102:   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator==( const odd_list<T>& a, const list<T>& b ) {
Chris@102:   if( null(a)() && null(b)() )
Chris@102:       return true;
Chris@102:   if( null(a)() || null(b)() )
Chris@102:       return false;
Chris@102:   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
Chris@102: }
Chris@102: 
Chris@102: template <class T>
Chris@102: bool operator<( const list<T>& a, const list<T>& b ) {
Chris@102:   if( null(a)() && !null(b)() )  return true;
Chris@102:   if( null(b)() )              return false;
Chris@102:   if( head(b)() < head(a)() )    return false;
Chris@102:   if( head(a)() < head(b)() )    return true;
Chris@102:   return (tail(a)() < tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( const odd_list<T>& a, const list<T>& b ) {
Chris@102:   if( null(a)() && !null(b)() )  return true;
Chris@102:   if( null(b)() )              return false;
Chris@102:   if( head(b)() < head(a)() )    return false;
Chris@102:   if( head(a)() < head(b)() )    return true;
Chris@102:   return (tail(a)() < tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( const list<T>& a, const odd_list<T>& b ) {
Chris@102:    if( null(a) && !null(b) )  return true;
Chris@102:    if( null(b) )              return false;
Chris@102:    if( head(b) < head(a) )    return false;
Chris@102:    if( head(a) < head(b) )    return true;
Chris@102:    return (tail(a) < tail(b));
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( const odd_list<T>& a, const odd_list<T>& b ) {
Chris@102:   if( null(a)() && !null(b)() )  return true;
Chris@102:   if( null(b)() )              return false;
Chris@102:   if( head(b)() < head(a)() )    return false;
Chris@102:   if( head(a)() < head(b)() )    return true;
Chris@102:   return (tail(a)() < tail(b)());
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( const odd_list<T>&, a_unique_type_for_nil ) {
Chris@102:    return false;
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( const list<T>&, a_unique_type_for_nil ) {
Chris@102:    return false;
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( a_unique_type_for_nil, const odd_list<T>& b ) {
Chris@102:   return !null(b)();
Chris@102: }
Chris@102: template <class T>
Chris@102: bool operator<( a_unique_type_for_nil, const list<T>& b ) {
Chris@102:   return !null(b)();
Chris@102: }
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Implement cat and cons after the list types are defined.
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102:     namespace impl {
Chris@102:       using listlike::ListLike;
Chris@102: 
Chris@102:       template <class T, class F, class L>
Chris@102:       struct ConsHelp2<T,F,L,true>
Chris@102:       {
Chris@102:          typedef typename boost::remove_reference<T>::type TT;
Chris@102:          typedef typename L::force_result_type type;
Chris@102:          static type go( const TT& x, const F& f ) {
Chris@102:             return type( x, f );
Chris@102:          }
Chris@102:       };
Chris@102:       template <class T, class F>
Chris@102:       struct ConsHelp2<T,F,list<T>,true>
Chris@102:       {
Chris@102:          typedef typename boost::remove_reference<T>::type TT;
Chris@102:          typedef list<TT> L;
Chris@102:          typedef typename L::force_result_type type;
Chris@102:          static type go( const TT& x, const F& f ) {
Chris@102:             return odd_list<TT>(x, list<TT>(
Chris@102:             boost::intrusive_ptr<Cache<TT> >(new Cache<T>(
Chris@102:             typename Cache<TT>::CvtFxn(),f))));
Chris@102:          }
Chris@102:        };
Chris@102:        template <class T, class F>
Chris@102:        struct ConsHelp2<T,F,odd_list<T>,true>
Chris@102:        {
Chris@102:           typedef typename boost::remove_reference<T>::type TT;
Chris@102:           typedef odd_list<TT> L;
Chris@102:           typedef typename L::force_result_type type;
Chris@102:           static type go( const TT& x, const F& f ) {
Chris@102:               return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) ));
Chris@102:           }
Chris@102:        };
Chris@102:        template <class T, class F>
Chris@102:        struct ConsHelp2<T,F,a_unique_type_for_nil,false>
Chris@102:        {
Chris@102:           typedef typename boost::remove_reference<T>::type TT;
Chris@102:           typedef odd_list<TT> type;
Chris@102:           static type go( const TT& x, const F& f ) {
Chris@102:              return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) ));
Chris@102:           }
Chris@102:        };
Chris@102: 
Chris@102:        template <class T, class L, bool b> struct ConsHelp1 {
Chris@102:           typedef typename boost::remove_reference<T>::type TT;
Chris@102:           typedef typename L::force_result_type type;
Chris@102:           static type go( const TT& x, const L& l ) {
Chris@102:              return type(x,l);
Chris@102:           }
Chris@102:        };
Chris@102:       template <class T> struct ConsHelp1<T,a_unique_type_for_nil,false> {
Chris@102:         typedef typename boost::remove_reference<T>::type TT;
Chris@102:         typedef odd_list<TT> type;
Chris@102:         static type go( const TT& x, const a_unique_type_for_nil& n ) {
Chris@102:         return type(x,n);
Chris@102:         }
Chris@102:       };
Chris@102:       template <class T, class F> struct ConsHelp1<T,F,false> {
Chris@102:         // It's a function returning a list
Chris@102:         // This is the one I have not fixed yet....
Chris@102:         // typedef typename F::result_type L;
Chris@102:         // typedef typename result_of::template ListType<F>::result_type L;
Chris@102:         typedef odd_list<T> L;
Chris@102:         typedef ConsHelp2<T,F,L,boost::is_base_and_derived<ListLike,L>::value> help;
Chris@102:         typedef typename help::type type;
Chris@102:         static type go( const T& x, const F& f ) {
Chris@102:            return help::go(x,f);
Chris@102:         }
Chris@102:       };
Chris@102: 
Chris@102:       template <class T, class L, bool b>
Chris@102:       struct ConsHelp0;
Chris@102: 
Chris@102:       template <class T>
Chris@102:       struct ConsHelp0<T,a_unique_type_for_nil,true> {
Chris@102:         typedef typename boost::remove_reference<T>::type TT;
Chris@102:         typedef odd_list<T> type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class T>
Chris@102:       struct ConsHelp0<const T &,const a_unique_type_for_nil &,true> {
Chris@102:         typedef typename boost::remove_reference<T>::type TT;
Chris@102:         typedef odd_list<TT> type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class T>
Chris@102:       struct ConsHelp0<T &,a_unique_type_for_nil &,true> {
Chris@102:         typedef typename boost::remove_reference<T>::type TT;
Chris@102:         typedef odd_list<TT> type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class T, class L>
Chris@102:       struct ConsHelp0<T,L,false> {
Chris@102:           // This removes any references from L for correct return type
Chris@102:           // identification.
Chris@102:            typedef typename boost::remove_reference<L>::type LType;
Chris@102:            typedef typename ConsHelp1<T,LType,
Chris@102:            boost::is_base_and_derived<ListLike,LType>::value>::type type;
Chris@102:       };
Chris@102: 
Chris@102:       /////////////////////////////////////////////////////////////////////
Chris@102:       // cons (t,l) - cons a value to the front of a list.
Chris@102:       // Note: The first arg,  t, must be a value.
Chris@102:       //       The second arg, l, can be a list or NIL
Chris@102:       //       or a function that returns a list.
Chris@102:       /////////////////////////////////////////////////////////////////////
Chris@102:       struct Cons
Chris@102:       {
Chris@102:         /* template <class T, class L> struct sig : public fun_type<
Chris@102:         typename ConsHelp1<T,L,
Chris@102:       boost::is_base_and_derived<ListLike,L>::value>::type> {};
Chris@102:         */
Chris@102:         template <typename Sig> struct result;
Chris@102: 
Chris@102:         template <typename This, typename T, typename L>
Chris@102:         struct result<This(T, L)>
Chris@102:         {
Chris@102:           typedef typename ConsHelp0<T,L,
Chris@102:           listlike::detect_nil<L>::is_nil>::type type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename This, typename T>
Chris@102:         struct result<This(T,a_unique_type_for_nil)>
Chris@102:         {
Chris@102:           typedef typename boost::remove_reference<T>::type TT;
Chris@102:           typedef odd_list<TT> type;
Chris@102:         };
Chris@102: 
Chris@102:         template <typename T, typename L>
Chris@102:         typename result<Cons(T,L)>::type
Chris@102:         operator()( const T& x, const L& l ) const {
Chris@102:            typedef typename result<Cons(T,L)>::type LL;
Chris@102:            typedef typename result_of::ListType<L>::LType LType;
Chris@102:            typedef ConsHelp1<T,LType,
Chris@102:            boost::is_base_and_derived<ListLike,LType>::value> help;
Chris@102:            return help::go(x,l);
Chris@102:           }
Chris@102:       
Chris@102:         template <typename T>
Chris@102:         typename result<Cons(T,a_unique_type_for_nil)>::type
Chris@102:         operator()( const T& x, const a_unique_type_for_nil &n ) const {
Chris@102:            typedef typename result<Cons(T,a_unique_type_for_nil)>::type LL;
Chris@102:            typedef ConsHelp1<T,LL,
Chris@102:            boost::is_base_and_derived<ListLike,LL>::value> help;
Chris@102:            return help::go(x,n);
Chris@102:           }
Chris@102: 
Chris@102:       };
Chris@102:     }
Chris@102: 
Chris@102:     typedef boost::phoenix::function<impl::Cons> Cons;
Chris@102:     Cons cons;
Chris@102: 
Chris@102:     namespace impl {
Chris@102: 
Chris@102:       template <class L, class M, bool b>
Chris@102:       struct CatHelp0;
Chris@102: 
Chris@102:       template <class L>
Chris@102:       struct CatHelp0<L,a_unique_type_for_nil,true> {
Chris@102:         typedef typename result_of::template ListType<L>::LType type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class L>
Chris@102:       struct CatHelp0<const L &,const a_unique_type_for_nil &,true> {
Chris@102:         typedef typename result_of::template ListType<L>::LType type;
Chris@102:         //typedef L type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class L>
Chris@102:       struct CatHelp0<L &,a_unique_type_for_nil &,true> {
Chris@102:         typedef typename result_of::template ListType<L>::LType type;
Chris@102:         //typedef L type;
Chris@102:       };
Chris@102: 
Chris@102:       template <class L, class M>
Chris@102:       struct CatHelp0<L,M,false> {
Chris@102:           // This removes any references from L for correct return type
Chris@102:           // identification.
Chris@102:         typedef typename result_of::template ListType<L>::LType type;
Chris@102:         //    typedef typename ConsHelp1<T,LType,
Chris@102:         //   boost::is_base_and_derived<ListLike,LType>::value>::type type;
Chris@102:       };
Chris@102: 
Chris@102:       /////////////////////////////////////////////////////////////////////
Chris@102:       // cat (l,m) - concatenate lists.
Chris@102:       // Note: The first arg,  l, must be a list or NIL.
Chris@102:       //       The second arg, m, can be a list or NIL
Chris@102:       //       or a function that returns a list.
Chris@102:       /////////////////////////////////////////////////////////////////////
Chris@102:       struct Cat
Chris@102:       {
Chris@102:          template <class L, class M, bool b, class R>
Chris@102:          struct Helper /*: public c_fun_type<L,M,R>*/ {
Chris@102:            template <typename Sig> struct result;
Chris@102:            
Chris@102:            template <typename This>
Chris@102:            struct result<This(L,M)>
Chris@102:           {
Chris@102:              typedef typename result_of::ListType<L>::tail_result_type type;
Chris@102:           };
Chris@102: 
Chris@102:            typedef R return_type;
Chris@102:            R operator()( const L& l, const M& m,
Chris@102:              reuser2<INV,VAR,INV,Helper,
Chris@102:              typename result_of::template ListType<L>::tail_result_type,M>
Chris@102:              r = NIL ) const {
Chris@102:              if( null(l)() )
Chris@102:                 return m().force();
Chris@102:              else
Chris@102:                 return cons( head(l)(), r( Helper<L,M,b,R>(), tail(l), m )() );
Chris@102:          }
Chris@102:       };
Chris@102:           template <class L, class M, class R>
Chris@102:           struct Helper<L,M,true,R> /*: public c_fun_type<L,M,R>*/ {
Chris@102:            template <typename Sig> struct result;
Chris@102:            
Chris@102:            template <typename This>
Chris@102:            struct result<This(L,M)>
Chris@102:           {
Chris@102:              typedef typename result_of::ListType<L>::tail_result_type type;
Chris@102:           };
Chris@102:           typedef R return_type;
Chris@102:           R operator()( const L& l, const M& m,
Chris@102:              reuser2<INV,VAR,INV,Helper,
Chris@102:              typename result_of::template ListType<L>::tail_result_type,M>
Chris@102:              r = NIL ) const {
Chris@102:              if( null(l)() )
Chris@102:                 return m.force();
Chris@102:              else
Chris@102:                 return cons( head(l)(), r(Helper<L,M,true,R>(), tail(l), m )());
Chris@102:          }
Chris@102:       };
Chris@102:       template <class L, class R>
Chris@102:       struct Helper<L,a_unique_type_for_nil,false,R>
Chris@102:       /*: public c_fun_type<L,
Chris@102:         a_unique_type_for_nil,odd_list<typename L::value_type> > */
Chris@102:       {
Chris@102:         typedef odd_list<typename result_of::template ListType<L>::value_type> type;
Chris@102:         odd_list<typename result_of::template ListType<L>::value_type>
Chris@102:         operator()( const L& l, const a_unique_type_for_nil& ) const {
Chris@102:          return l;
Chris@102:         }
Chris@102:       };
Chris@102:    public:
Chris@102:         /*template <class L, class M> struct sig : public fun_type<
Chris@102:         typename RT<cons_type,typename L::value_type,M>::result_type>
Chris@102:       {}; */
Chris@102:    // Need to work out the return type here.
Chris@102:       template <typename Sig> struct result;
Chris@102: 
Chris@102:       template <typename This, typename L, typename M>
Chris@102:       struct result<This(L,M)>
Chris@102:       {
Chris@102:         typedef typename CatHelp0<L,M,
Chris@102:           listlike::detect_nil<M>::is_nil>::type type;
Chris@102:         // typedef typename result_of::ListType<L>::tail_result_type type;
Chris@102:       };
Chris@102:       
Chris@102:       template <typename This, typename L>
Chris@102:       struct result<This(L,a_unique_type_for_nil)>
Chris@102:       {
Chris@102:          typedef typename result_of::ListType<L>::tail_result_type type;
Chris@102:       };
Chris@102:       template <class L, class M>
Chris@102:       typename result<Cat(L,M)>::type operator()( const L& l, const M& m ) const
Chris@102:       {
Chris@102:          listlike::EnsureListLike<L>();
Chris@102:          return Helper<L,M,
Chris@102:          boost::is_base_and_derived<typename listlike::ListLike,M>::value,
Chris@102:                 typename result<Cat(L,M)>::type>()(l,m);
Chris@102:       }
Chris@102: 
Chris@102:       template <class L>
Chris@102:       typename result<Cat(L,a_unique_type_for_nil)>::type operator()( const L& l, const a_unique_type_for_nil& /* n */ ) const
Chris@102:       {
Chris@102:          listlike::EnsureListLike<L>();
Chris@102:          return l;
Chris@102:       }
Chris@102:        
Chris@102:       };
Chris@102: 
Chris@102: 
Chris@102:     }
Chris@102: 
Chris@102:     typedef boost::phoenix::function<impl::Cat> Cat;
Chris@102:     Cat cat;
Chris@102: 
Chris@102: 
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Handy functions for making list literals
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: // Yes, these aren't functoids, they're just template functions.  I'm
Chris@102: // lazy and created these mostly to make it easily to make little lists
Chris@102: // in the sample code snippets that appear in papers.
Chris@102: 
Chris@102: struct UseList {
Chris@102:    template <class T> struct List { typedef list<T> type; };
Chris@102: };
Chris@102: struct UseOddList {
Chris@102:    template <class T> struct List { typedef odd_list<T> type; };
Chris@102: };
Chris@102: struct UseStrictList {
Chris@102:    template <class T> struct List { typedef strict_list<T> type; };
Chris@102: };
Chris@102: 
Chris@102: template <class Kind = UseList>
Chris@102: struct list_with {
Chris@102:    template <class T>
Chris@102:    typename Kind::template List<T>::type
Chris@102:    operator()( const T& a ) const {
Chris@102:       typename Kind::template List<T>::type l;
Chris@102:       l = cons( a, l );
Chris@102:       return l;
Chris@102:    }
Chris@102:    
Chris@102:    template <class T>
Chris@102:    typename Kind::template List<T>::type
Chris@102:    operator()( const T& a, const T& b ) const {
Chris@102:       typename Kind::template List<T>::type l;
Chris@102:       l = cons( b, l );
Chris@102:       l = cons( a, l );
Chris@102:       return l;
Chris@102:    }
Chris@102:    
Chris@102:    template <class T>
Chris@102:    typename Kind::template List<T>::type
Chris@102:    operator()( const T& a, const T& b, const T& c ) const {
Chris@102:       typename Kind::template List<T>::type l;
Chris@102:       l = cons( c, l );
Chris@102:       l = cons( b, l );
Chris@102:       l = cons( a, l );
Chris@102:       return l;
Chris@102:    }
Chris@102:    
Chris@102:    template <class T>
Chris@102:    typename Kind::template List<T>::type
Chris@102:    operator()( const T& a, const T& b, const T& c, const T& d ) const {
Chris@102:       typename Kind::template List<T>::type l;
Chris@102:       l = cons( d, l );
Chris@102:       l = cons( c, l );
Chris@102:       l = cons( b, l );
Chris@102:       l = cons( a, l );
Chris@102:       return l;
Chris@102:    }
Chris@102:    
Chris@102:    template <class T>
Chris@102:    typename Kind::template List<T>::type
Chris@102:    operator()( const T& a, const T& b, const T& c, const T& d,
Chris@102:                const T& e ) const {
Chris@102:       typename Kind::template List<T>::type l;
Chris@102:       l = cons( e, l );
Chris@102:       l = cons( d, l );
Chris@102:       l = cons( c, l );
Chris@102:       l = cons( b, l );
Chris@102:       l = cons( a, l );
Chris@102:       return l;
Chris@102:    }
Chris@102: };
Chris@102: //////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102:   }
Chris@102: 
Chris@102: }
Chris@102: 
Chris@102: #endif