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