/* Copyright (c) 1997-2004
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_TYPE_MANIP_H
#define _POLYMAKE_TYPE_MANIP_H "$Project: polymake $$Id: type_manip.h,v 1.36 2004/06/22 16:22:42 gawrilow Exp $"

#if defined(__COMO__)
# include <type_traits.h>
#else
# include <bits/type_traits.h>
#endif
#include <ext/defines.h>

#if defined(__GNUC__) || defined(__COMO__)
#  define _POLYMAKE_ALIGN(what,n) what __attribute__ ((aligned (n)))
#elif defined(__INTEL_COMPILER)
# if __INTEL_COMPILER<=700
#  define _POLYMAKE_ALIGN(what,n) __declspec(align(16)) what
# else
#  define _POLYMAKE_ALIGN(what,n) __declspec(align(n)) what
# endif
#endif

namespace pm {

/** A piece of METALISP - binary choice
    @tmplparam Cond boolean value the choice depends on
    @tmplparam Then result type chosen in the @c true case
    @tmplparam Else result type chosen in the @c false case
*/
template <bool Cond, typename Then, typename Else>
struct if_else {
   typedef Then result;
};

template <typename Then, typename Else>
struct if_else<false,Then,Else> {
   typedef Else result;
};

template <typename Case>
struct choice {
   typedef Case result;
};

template <typename Then, typename Else>
struct choice< if_else<true, Then, Else> > {
   typedef Then result;
};

template <typename Then, typename Else>
struct choice< if_else<false, Then, Else> > : choice<Else> { };

template <typename X, typename Y>
struct project_first {
   typedef X result;
};

template <typename X, typename Y>
struct project_second {
   typedef Y result;
};

template <bool x> struct bool2type {
   static const bool value=x, answer=x;
};
template <int x> struct int2type {
   static const int value=x;
};
typedef bool2type<true> True;
typedef bool2type<false> False;

template <typename T1, typename T2>
struct identical_raw : False {
   typedef void type;
};

template <typename T>
struct identical_raw<T,T> : True {
   typedef T type;
};

/** Definition of the input argument type

    For a given type, a suitable type of the function input argument is defined.
    Objects of user-defined classes should be passed as a const reference, while
    built-in types are more efficiently passed per value.
*/
template <typename T>
struct function_argument {
   typedef typename if_else<(identical_raw<typename __type_traits<T>::is_POD_type, __true_type>::answer &&
			     sizeof(T)<=sizeof(double)), const T, const T&>::result type;
   typedef type ref;
   typedef const T& plus_ref;
   typedef T& lvalue;
};

template <typename T>
struct function_argument<T&> {
   typedef T& type;
   typedef T& ref;
   typedef T& plus_ref;
   typedef T& lvalue;
};

template <typename T>
struct function_argument<const T&> : function_argument<T> {
   typedef const T& ref;
   typedef T& lvalue;
};

template <>
struct function_argument<void> {
   typedef void* type;
   typedef void* ref;
   typedef void* plus_ref;
   typedef void* lvalue;
};

template <typename T>
struct type_traits {
   static const bool
      is_default_constructible=identical_raw<typename __type_traits<T>::has_trivial_default_constructor, __true_type>::answer,
      is_copy_constructible=identical_raw<typename __type_traits<T>::has_trivial_copy_constructor, __true_type>::answer,
      is_assignable=identical_raw<typename __type_traits<T>::has_trivial_assignment_operator, __true_type>::answer;
};

/** Removal of the pointer/reference modifier

    For a given pointer/reference type, the data type being referred to is revealed.
    For the sake of completeness, non-reference types yield themselves as result.
*/
template <typename C> struct attrib {
   typedef C type;
   typedef C result;	// for deref<.>
   typedef const C plus_const;
   typedef C minus_const;
   typedef C& plus_ref;
   typedef C minus_ref;
   typedef const C& plus_const_ref;
   typedef C alias;
   typedef const C const_alias;
   static const bool is_reference=false, is_const=false;
};
template <>
struct attrib<void> {
   typedef void type;
   typedef void result;
   typedef void plus_const;
   typedef void minus_const;
   typedef void plus_ref;
   typedef void minus_ref;
   typedef void plus_const_ref;
   typedef void alias;
   typedef void const_alias;
   static const bool is_reference=false, is_const=false;
};
template <typename C>
struct attrib<const C> : attrib<C> {
   typedef const C& plus_ref;
   typedef const C minus_ref;
   typedef const C alias;
   static const bool is_const=true;
};
#if defined(__INTEL_COMPILER) || defined(__COMO__)
template <typename C, int size>
struct attrib<const C[size]> {
   typedef C type[size];
   typedef type result;
   typedef const C plus_const[size];
   typedef type minus_const;
   typedef const C (&plus_ref)[size];
   typedef plus_const minus_ref;
   typedef plus_ref plus_const_ref;
   typedef type alias;
   typedef plus_const const_alias;
   static const bool is_reference=false, is_const=true;
};
#endif
template <typename C>
struct attrib<C&> : attrib<C> {
   typedef typename attrib<C>::plus_const& plus_const;
   typedef typename attrib<C>::minus_const& minus_const;
   typedef typename attrib<C>::type* alias;
   typedef typename attrib<C>::plus_const* const_alias;
   static const bool is_reference=true;
};

template <typename C>
struct is_pointer : False { };

template <typename C>
struct is_pointer<C*> : True { };

/// Synonym
template <typename C>
struct deref : attrib<C> { };

template <typename C>
struct deref_ptr : attrib<C> { };

template <typename C>
struct deref_ptr<C*> : attrib<C> {
   typedef typename attrib<C>::type type;
   typedef const type* plus_const;
   typedef type* minus_const;
   typedef type& minus_const_ref;
};

/** Const attribute assignment

    For a given type T and some other type From, a new data type is defined,
    which has the same const qualification as From.
*/
template <typename T, typename From>
struct inherit_const {
   typedef typename if_else<deref<From>::is_const, typename attrib<T>::plus_const, T>::result type;
};

template <typename T, typename From>
struct inherit_ref {
   typedef typename inherit_const<typename deref<T>::minus_ref, From>::type QT;
   typedef typename if_else<(deref<T>::is_reference || deref<From>::is_reference), QT&, QT>::result type;
};

template <typename T, bool is_const>
struct assign_const {
   typedef typename if_else<is_const, typename attrib<T>::plus_const, typename attrib<T>::minus_const>::result type;
};

template <typename T1, typename T2>
struct identical {
   static const bool answer=identical_raw<typename attrib<T1>::plus_const, typename attrib<T2>::plus_const>::answer;
   typedef typename if_else<answer, typename assign_const<T1, attrib<T1>::is_const || attrib<T2>::is_const>::type,
			    void>::result type;
};

template <typename T1, typename T2>
struct identical_without_ref
   : identical_raw<typename attrib<T1>::type, typename attrib<T2>::type> { };

template <typename T1, typename T2>
struct cons {
   typedef T1 car;
   typedef T2 cdr;
};

template <typename List>
struct list_length {
   static const int answer=!identical_raw<List,void>::answer;
};

template <typename Car, typename Cdr>
struct list_length< cons<Car,Cdr> > {
   static const int answer= list_length<Car>::answer + list_length<Cdr>::answer;
};

template <typename List, int n> struct n_th;

template <typename T>
struct n_th<T,0> {
   typedef T car;
   typedef void cdr;
   typedef T list;
};

template <typename Car, typename Cdr, int n>
struct n_th<cons<Car, Cdr>, n> : n_th<Cdr, n-1> { };

template <typename Car, typename Cdr>
struct n_th<cons<Car, Cdr>, 0> {
   typedef Car car;
   typedef Cdr cdr;
   typedef cons<Car, Cdr> list;
};

template <typename List, int n, typename New> struct subst_n_th;

template <typename T, typename New>
struct subst_n_th<T, 0, New> {
   typedef New type;
};

template <typename Car, typename Cdr, int n, typename New>
struct subst_n_th<cons<Car, Cdr>, n, New> {
   typedef cons<Car, typename subst_n_th<Cdr, n-1, New>::type> type;
};

template <typename Car, typename Cdr, typename New>
struct subst_n_th<cons<Car, Cdr>, 0, New> {
   typedef cons<New, Cdr> type;
};

template <typename Top>
class Generic {
protected:
   Generic() { }
   Generic(const Generic&) { }
public:
   typedef Top top_type;
   typedef void generic_type;
   typedef Top persistent_type;

   const Top& top() const
   {
      return *static_cast<const Top*>(this);
   }
   Top& top()
   {
      return *static_cast<Top*>(this);
   }
};

/// due to Andrei Alexandrescu

struct yes_no_helper {
   typedef char no[1];
   typedef char yes[2];
   static no* Test(...);
};

template <typename Child, typename Base>
class derived_from {
   struct helper : yes_no_helper {
      static yes* Test(const Base*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer= sizeof(*helper::Test((Child*)0)) == sizeof(typename helper::yes);
};

template <typename T>
class derived_from<T, void> : public False { };

template <typename T> struct least_derived { typedef T type; };
template <typename T> struct most_derived  { typedef T type; };

template <typename Car, typename Cdr>
struct least_derived< cons<Car,Cdr> > {
   typedef typename least_derived<Cdr>::type C2;
   typedef typename if_else<derived_from<C2,Car>::answer, Car,
			    typename if_else<derived_from<Car,C2>::answer, C2, void>::result
                           >::result
      type;
};

template <typename Car, typename Cdr>
struct most_derived< cons<Car,Cdr> > {
   typedef typename most_derived<Cdr>::type C2;
   typedef typename if_else<derived_from<C2,Car>::answer, C2,
			    typename if_else<derived_from<Car,C2>::answer, Car, void>::result
                           >::result
      type;
};

template <typename Concrete, template <typename> class Template>
class derived_from_instance {
   struct helper : yes_no_helper {
      template <typename T>
      static yes* Test(const Template<T>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer= sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename> class Template>
class derived_from_instance2 {
   struct helper : yes_no_helper {
      template <typename T1, typename T2>
      static yes* Test(const Template<T1,T2>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename,typename> class Template>
class derived_from_instance3 {
   struct helper : yes_no_helper {
      template <typename T1, typename T2, typename T3>
      static yes* Test(const Template<T1,T2,T3>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename,typename,typename> class Template>
class derived_from_instance4 {
   struct helper : yes_no_helper {
      template <typename T1, typename T2, typename T3, typename T4>
      static yes* Test(const Template<T1,T2,T3,T4>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename T1, typename T2,
	  typename common_base=typename least_derived< cons<typename deref<T1>::type, typename deref<T2>::type> >::type>
struct compatible_helper : True {
   typedef typename assign_const<common_base, attrib<T1>::is_const || attrib<T2>::is_const>::type value_type;
   typedef typename if_else<attrib<T1>::is_reference && attrib<T2>::is_reference, value_type&, value_type>::result type;
};

template <typename T1, typename T2>
struct compatible_helper<T1,T2,void> : False {
   typedef void type;
};

template <typename T1, typename T2>
struct compatible : compatible_helper<T1, T2> { };

template <typename T1, typename T2>
struct compatible<T1*, T2*> : compatible<T1, T2> {
   typedef typename compatible<T1,T2>::type *type;
};

template <typename Concrete, template <typename> class Template>
class is_instance_of {
   struct helper : yes_no_helper {
      template <typename T>
      static typename if_else<identical<Concrete, Template<T> >::answer, yes, no>::result*
      Test(const Template<T>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer= sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename> class Template>
class is_instance2_of {
   struct helper : yes_no_helper {
      template <typename T1, typename T2>
      static typename if_else<identical<Concrete, Template<T1,T2> >::answer, yes, no>::result*
      Test(const Template<T1,T2>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename,typename> class Template>
class is_instance3_of {
   struct helper : yes_no_helper {
      template <typename T1, typename T2, typename T3>
      static typename if_else<identical<Concrete, Template<T1,T2,T3> >::answer, yes, no>::result*
      Test(const Template<T1,T2,T3>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

template <typename Concrete, template <typename,typename,typename,typename> class Template>
class is_instance4_of {
   struct helper : yes_no_helper {
      template <typename T1, typename T2, typename T3, typename T4>
      static typename if_else<identical<Concrete, Template<T1,T2,T3,T4> >::answer, yes, no>::result*
      Test(const Template<T1,T2,T3,T4>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((Concrete*)0)) == sizeof(typename helper::yes);
};

/* g++ and como have different rules for matching template template parameters
   in partial specializations.

   Given
     template <typename X, typename Y=Default> class FOO;
   and following specializations:
     template <template <typename> class Template, typename X> class BAR< Template<X> >;
     template <template <typename,typename> class Template, typename X, typename Y> class BAR< Template<X,Y> >;

   g++ would match both (and complain about ambiguity), while como would consider only the second.

   I don't know, who is right; at any rate, this complicated stuff helps to circumvent these problems.
*/

template <typename T>
struct has_1_template_type_param_helper {
   struct helper : yes_no_helper {
      template <template <typename> class Template, typename X>
      static yes* Test(const Template<X>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((T*)0)) == sizeof(typename helper::yes);
};

template <typename T, bool _answer=has_1_template_type_param_helper<T>::answer>
struct has_1_template_type_param : int2type<(int(_answer))> { };

template <typename T>
struct has_2_template_type_params_helper {
   struct helper : yes_no_helper {
      template <template <typename,typename> class Template, typename X, typename Y>
      static yes* Test(const Template<X,Y>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((T*)0)) == sizeof(typename helper::yes);
};

template <typename T, bool _answer=has_2_template_type_params_helper<T>::answer>
struct has_2_template_type_params : int2type<2> { };
template <typename T>
struct has_2_template_type_params<T,false> : has_1_template_type_param<T> { };

template <typename T>
struct has_3_template_type_params_helper {
   struct helper : yes_no_helper {
      template <template <typename,typename,typename> class Template, typename X, typename Y, typename Z>
      static yes* Test(const Template<X,Y,Z>*);
      using yes_no_helper::Test;
   };
public:
   static const bool answer = sizeof(*helper::Test((T*)0)) == sizeof(typename helper::yes);
};

template <typename T, bool _answer=has_3_template_type_params_helper<T>::answer>
struct has_3_template_type_params : int2type<3> { };
template <typename T>
struct has_3_template_type_params<T,false> : has_2_template_type_params<T> { };

template <typename T>
struct n_of_template_type_params : has_3_template_type_params<T> { };

template <typename T, int n, int i> struct extract_template_type_param_helper;
template <typename T, typename New, int n, int i> struct subst_template_type_param_helper;

template <template <typename> class Template, typename T>
struct extract_template_type_param_helper<Template<T>, 1, 0> {
   typedef T type;
};
template <template <typename> class Template, typename T, typename New>
struct subst_template_type_param_helper<Template<T>, New, 1, 0> {
   typedef Template<New> type;
};

template <template <typename,typename> class Template, typename T1, typename T2>
struct extract_template_type_param_helper<Template<T1,T2>, 2, 0> {
   typedef T1 type;
};
template <template <typename,typename> class Template, typename T1, typename T2>
struct extract_template_type_param_helper<Template<T1,T2>, 2, 1> {
   typedef T2 type;
};
template <template <typename,typename> class Template, typename T1, typename T2, typename New1>
struct subst_template_type_param_helper<Template<T1,T2>, New1, 2, 0> {
   typedef Template<New1,T2> type;
};
template <template <typename,typename> class Template, typename T1, typename T2, typename New2>
struct subst_template_type_param_helper<Template<T1,T2>, New2, 2, 1> {
   typedef Template<T1,New2> type;
};

template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3>
struct extract_template_type_param_helper<Template<T1,T2,T3>, 3, 0> {
   typedef T1 type;
};
template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3>
struct extract_template_type_param_helper<Template<T1,T2,T3>, 3, 1> {
   typedef T2 type;
};
template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3>
struct extract_template_type_param_helper<Template<T1,T2,T3>, 3, 2> {
   typedef T3 type;
};

template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3, typename New1>
struct subst_template_type_param_helper<Template<T1,T2,T3>, New1, 3, 0> {
   typedef Template<New1,T2,T3> type;
};
template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3, typename New2>
struct subst_template_type_param_helper<Template<T1,T2,T3>, New2, 3, 1> {
   typedef Template<T1,New2,T3> type;
};
template <template <typename,typename,typename> class Template, typename T1, typename T2, typename T3, typename New3>
struct subst_template_type_param_helper<Template<T1,T2,T3>, New3, 3, 2> {
   typedef Template<T1,T2,New3> type;
};

template <typename T, int i=0>
struct extract_template_type_param
   : extract_template_type_param_helper<T, n_of_template_type_params<T>::value, i> { };

template <typename T, typename New, int i=0>
struct subst_template_type_param
   : subst_template_type_param_helper<T, New, n_of_template_type_params<T>::value, i> { };

/* ---------------------------------------------
 *  Building blocks for flexible traits classes
 * --------------------------------------------- */

template <typename T1, typename T2>
struct concat_list {
   typedef typename if_else<identical_raw<T1,void>::answer, T2,
			    typename if_else<identical_raw<T2,void>::answer, T1, cons<T1, T2> >::result>::result
      result;
};

template <typename Car, typename Cdr, typename T>
struct concat_list<cons<Car,Cdr>, T>
   : concat_list<Car, typename concat_list<Cdr, T>::result> { };

template <typename Car, typename Cdr>
struct concat_list<cons<Car,Cdr>, void> {
   typedef cons<Car, Cdr> result;
};

template <typename ParamList, template <typename> class Tag, typename Default=void>
struct extract_type_param {
   typedef Default result;
   static const bool specified=false;
};

template <typename Value, template <typename> class Tag, typename Default>
struct extract_type_param<Tag<Value>, Tag, Default> {
   typedef Value result;
   static const bool specified=true;
};

template <typename Car, typename Cdr, template <typename> class Tag, typename Default>
struct extract_type_param<cons<Car,Cdr>, Tag, Default>
   : extract_type_param<Cdr, Tag, Default> { };

template <typename Value, typename Cdr, template <typename> class Tag, typename Default>
struct extract_type_param<cons<Tag<Value>, Cdr>, Tag, Default> {
   typedef Value result;
   static const bool specified=true;
};

template <typename ParamList, template <typename> class Tag, int Default=0>
struct extract_int_param {
   typedef extract_type_param<ParamList, Tag, int2type<Default> > extractor;
   typedef typename extractor::result wrapped;
   static const int result=wrapped::value;
   static const bool specified=extractor::specified;
};

template <typename ParamList, template <typename> class Tag, bool Default=false>
struct extract_bool_param {
   typedef extract_type_param<ParamList, Tag, bool2type<Default> > extractor;
   typedef typename extractor::result wrapped;
   static const bool result=wrapped::value;
   static const bool specified=extractor::specified;
};

template <typename ParamList, template <typename> class Tag, template <typename,typename> class Operation, typename Second>
struct modify_type_param
   : concat_list< Tag<typename Operation<void,Second>::result>, ParamList > { };

template <typename Value, template <typename> class Tag, template <typename,typename> class Operation, typename Second>
struct modify_type_param<Tag<Value>, Tag, Operation, Second> {
   typedef Tag<typename Operation<Value,Second>::result> result;
};

template <typename Car, typename Cdr, template <typename> class Tag, template <typename,typename> class Operation, typename Second>
struct modify_type_param<cons<Car,Cdr>, Tag, Operation, Second>
   : concat_list< Car, typename modify_type_param<Cdr,Tag,Operation,Second>::result > { };

template <typename Value, typename Cdr, template <typename> class Tag, template <typename,typename> class Operation, typename Second>
struct modify_type_param<cons<Tag<Value>, Cdr>, Tag, Operation, Second>
   : concat_list< Tag<typename Operation<Value,Second>::result>, Cdr > { };

template <typename ParamList, template <typename> class Tag, typename NewValue>
struct replace_type_param : modify_type_param<ParamList, Tag, project_second, NewValue> { };

template <typename ParamList, template <typename> class Tag, int NewValue>
struct replace_int_param : replace_type_param<ParamList, Tag, int2type<NewValue> > { };

template <typename ParamList, template <typename> class Tag, bool NewValue>
struct replace_bool_param : replace_type_param<ParamList, Tag, bool2type<NewValue> > { };

template <typename ParamList, template <typename> class Tag>
struct remove_type_param {
   typedef ParamList result;
};

template <typename Value, template <typename> class Tag>
struct remove_type_param<Tag<Value>, Tag> {
   typedef void result;
};

template <typename Car, typename Cdr, template <typename> class Tag>
struct remove_type_param<cons<Car,Cdr>, Tag>
   : concat_list<Car, typename remove_type_param<Cdr,Tag>::result> { };

template <typename Value, typename Cdr, template <typename> class Tag>
struct remove_type_param<cons<Tag<Value>, Cdr>, Tag> {
   typedef Cdr result;
};

template <typename ParamList, template <typename> class Tag>
struct remove_int_param : remove_type_param<ParamList, Tag> { };

template <typename ParamList, template <typename> class Tag>
struct remove_bool_param : remove_type_param<ParamList, Tag> { };

template <typename ParamList, typename ParamInstance, typename Default=void>
struct extract_by_instance {
   typedef void result;
};

template <typename ParamList, template <typename> class Tag, typename dummy, typename Default>
struct extract_by_instance<ParamList, Tag<dummy>, Default>
   : extract_type_param<ParamList, Tag, Default> { };

template <typename ParamList, typename ParamInstance>
struct replace_by_instance {
   typedef ParamList result;
};

template <typename ParamList, template <typename> class Tag, typename Value>
struct replace_by_instance<ParamList, Tag<Value> >
   : replace_type_param<ParamList, Tag, Value> { };


/** Determine element pairs yielding Predicate::answer==true
    The primary template handles the case of $First$ and $Second$ being scalars,
    while the general case of $First$ being a list is handled in specializations.

    list_search is a simplified function, it terminates as soon as one matching
    pair is found.
 */
template <typename First, typename Second, template <typename,typename> class Predicate>
struct list_search {
   /// whether at least one pair found
   static const bool answer=Predicate<First,Second>::answer;
   /// where it was found
   static const int pos= answer ? 0 : -1;
   /// elements from First matching the predicate
   typedef typename if_else<answer, First, void>::result positive;
   /// complement
   typedef typename if_else<answer, void, First>::result negative;
   /// $Second$ if there is at least one matching pair
   typedef typename if_else<answer, Second, void>::result positive2;
   /// complement
   typedef typename if_else<answer, void, Second>::result negative2;
};

template <typename Second, template <typename,typename> class Predicate>
struct list_search<void, Second, Predicate> : False {
   static const int pos=-1;
   typedef void positive;
   typedef void negative;
   typedef void positive2;
   typedef Second negative2;
};

template <typename First, template <typename,typename> class Predicate>
struct list_search<First, void, Predicate> : False {
   static const int pos=-1;
   typedef void positive;
   typedef First negative;
   typedef void positive2;
   typedef void negative2;
};

// to avoid ambiguity
template <template <typename,typename> class Predicate>
struct list_search<void, void, Predicate> : False {
   static const int pos=-1;
   typedef void positive;
   typedef void negative;
   typedef void positive2;
   typedef void negative2;
};

#if __GNUC__ == 3 && __GNUC_MINOR__ == 1 && __GNUC_PATCHLEVEL__ == 0
template <typename First, typename Second, template <typename,typename> class Predicate>
struct _eval {
   static const bool answer=Predicate<First,Second>::answer;
};
#  define _Eval(First,Second,Predicate) _eval<First,Second,Predicate>::answer
#else
#  define _Eval(First,Second,Predicate) Predicate<First,Second>::answer
#endif

template <typename Car, typename Cdr, typename Second, template <typename,typename> class Predicate,
          bool _car_matches=_Eval(Car,Second,Predicate)>
struct list_search_helper {
   static const bool answer=_car_matches; // true
   static const int pos=0;
   typedef Car positive;
   typedef Cdr negative;
};
#undef _Eval

template <typename Car, typename Cdr, typename Second, template <typename,typename> class Predicate>
struct list_search_helper<Car, Cdr, Second, Predicate, false>
   : list_search<Cdr, Second, Predicate> {
   typedef list_search<Cdr, Second, Predicate> _super;
   static const int pos= _super::answer ? _super::pos+1 : -1;
   typedef typename concat_list<Car, typename _super::negative>::result negative;
};

template <typename Car, typename Cdr, typename Second, template <typename,typename> class Predicate>
struct list_search<cons<Car,Cdr>, Second, Predicate>
   : list_search_helper<Car, Cdr, Second, Predicate> { };

// to avoid ambiguity
template <typename Car, typename Cdr, template <typename,typename> class Predicate>
struct list_search<cons<Car,Cdr>, void, Predicate> : False {
   static const int pos=-1;
   typedef void positive;
   typedef cons<Car,Cdr> negative;
   typedef void positive2;
   typedef void negative2;
};

/** More powerful than list_search: find all pairs from $First$ and $Second$
    (both may be lists or scalars.) */
template <typename First, typename Second, template <typename,typename> class Predicate>
struct list_search_all : list_search<First, Second, Predicate> { };

template <typename Car, typename Cdr, typename Second, template <typename,typename> class Predicate>
struct list_search_all_first_helper {
   typedef list_search_all<Car,Second,Predicate> head;
   typedef list_search_all<Cdr,Second,Predicate> tail;
   static const bool answer=head::answer || tail::answer;
   typedef typename concat_list<typename head::positive, typename tail::positive>::result positive;
   typedef typename concat_list<typename head::negative, typename tail::negative>::result negative;
   typedef typename if_else<answer, Second, void>::result positive2;
   typedef typename if_else<answer, void, Second>::result negative2;
};

template <typename First, typename Car, typename Cdr, template <typename,typename> class Predicate>
struct list_search_all_second_helper {
   typedef list_search_all<First,Car,Predicate> head;
   typedef list_search_all<First,Cdr,Predicate> tail;
   static const bool answer=head::answer || tail::answer;
   typedef typename if_else<answer,First,void>::result positive;
   typedef typename if_else<answer,void,First>::result negative;
   typedef typename concat_list<typename head::positive2, typename tail::positive2>::result positive2;
   typedef typename concat_list<typename head::negative2, typename tail::negative2>::result negative2;
};

template <typename Car, typename Cdr, typename Second, template <typename,typename> class Predicate>
struct list_search_all<cons<Car,Cdr>, Second, Predicate>
   : list_search_all_first_helper<Car, Cdr, Second, Predicate> { };

template <typename First, typename Car, typename Cdr, template <typename,typename> class Predicate>
struct list_search_all<First, cons<Car, Cdr>, Predicate>
   : list_search_all_second_helper<First, Car, Cdr, Predicate> { };

template <typename Car, typename Cdr, typename Car2, typename Cdr2, template <typename,typename> class Predicate>
struct list_search_all<cons<Car,Cdr>, cons<Car2, Cdr2>, Predicate>
   : list_search_all_first_helper<Car, Cdr, cons<Car2, Cdr2>, Predicate> {
   typedef list_search_all_second_helper<cons<Car,Cdr>, Car2, Cdr2, Predicate> h2;
   typedef typename h2::positive2 positive2;
   typedef typename h2::negative2 negative2;
};

template <typename List, typename Item>
struct list_contains : list_search<List, Item, identical_raw> { };

/// Eliminate the elements of Second that evaluate Predicate::answer==TRUE
///  when combined with some element(s) from First.
template <typename First, typename Second, template <typename,typename> class Predicate>
struct merge_list
   : concat_list<First, typename list_search_all<First, Second, Predicate>::negative2> { };

template <template <typename> class Operation, typename T>
struct list_apply_unary : Operation<T> { };

template <template <typename> class Operation, typename Car, typename Cdr>
struct list_apply_unary<Operation, cons<Car,Cdr> >
   : concat_list<typename Operation<Car>::result,
		 typename list_apply_unary<Operation, Cdr>::result> { };

template <template <typename> class Operation, typename T>
struct list_and_unary : Operation<T> { };

template <template <typename> class Operation, typename Car, typename Cdr>
struct list_and_unary<Operation, cons<Car,Cdr> > {
   static const bool answer= Operation<Car>::answer && list_and_unary<Operation, Cdr>::answer;
};

template <template <typename> class Operation, typename T>
struct list_or_unary : Operation<T> { };

template <template <typename> class Operation, typename Car, typename Cdr>
struct list_or_unary<Operation, cons<Car,Cdr> > {
   static const bool answer= Operation<Car>::answer || list_or_unary<Operation, Cdr>::answer;
};

template <template <typename> class Operation, typename T>
struct list_count_unary {
   static const int answer= Operation<T>::answer ? 1 : 0;
};

template <template <typename> class Operation, typename Car, typename Cdr>
struct list_count_unary<Operation, cons<Car,Cdr> > {
   static const int answer= list_count_unary<Operation, Car>::answer + list_count_unary<Operation, Cdr>::answer;
};

template <typename> struct same { };

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_apply_binary : Operation<T1,T2> { };

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_apply_binary<Operation, T1, same<T2> > : Operation<T1,T2> { };

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_apply_binary<Operation, same<T1>, T2> : Operation<T1,T2> { };

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_apply_binary<Operation, same<T1>, same<T2> > : Operation<T1,T2> { };

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename Car2, typename Cdr2>
struct list_apply_binary<Operation, cons<Car1,Cdr1>, cons<Car2,Cdr2> >
   : concat_list<typename Operation<Car1,Car2>::result,
		 typename list_apply_binary<Operation, Cdr1, Cdr2>::result> { };

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename T2>
struct list_apply_binary<Operation, cons<Car1,Cdr1>, same<T2> >
   : concat_list<typename Operation<Car1,T2>::result,
		 typename list_apply_binary<Operation, Cdr1, same<T2> >::result> { };

template <template <typename,typename> class Operation, typename T1, typename Car2, typename Cdr2>
struct list_apply_binary<Operation, same<T1>, cons<Car2,Cdr2> >
   : concat_list<typename Operation<T1,Car2>::result,
		 typename list_apply_binary<Operation, same<T1>, Cdr2>::result> { };

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_and_binary : list_apply_binary<Operation, T1, T2> { };

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename Car2, typename Cdr2>
struct list_and_binary<Operation, cons<Car1,Cdr1>, cons<Car2,Cdr2> > {
   static const bool answer= Operation<Car1,Car2>::answer && list_and_binary<Operation, Cdr1, Cdr2>::answer;
};

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename T2>
struct list_and_binary<Operation, cons<Car1,Cdr1>, same<T2> > {
   static const bool answer= Operation<Car1,T2>::answer && list_and_binary<Operation, Cdr1, same<T2> >::answer;
};

template <template <typename,typename> class Operation, typename T1, typename Car2, typename Cdr2>
struct list_and_binary<Operation, same<T1>, cons<Car2,Cdr2> > {
   static const bool answer= Operation<T1,Car2>::answer && list_and_binary<Operation, same<T1>, Cdr2>::answer;
};

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_or_binary : list_apply_binary<Operation, T1, T2> { };

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename Car2, typename Cdr2>
struct list_or_binary<Operation, cons<Car1,Cdr1>, cons<Car2,Cdr2> > {
   static const bool answer= Operation<Car1,Car2>::answer || list_or_binary<Operation, Cdr1,Cdr2>::answer;
};

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename T2>
struct list_or_binary<Operation, cons<Car1,Cdr1>, same<T2> > {
   static const bool answer= Operation<Car1,T2>::answer || list_or_binary<Operation, Cdr1, same<T2> >::answer;
};

template <template <typename,typename> class Operation, typename T1, typename Car2, typename Cdr2>
struct list_or_binary<Operation, same<T1>, cons<Car2,Cdr2> > {
   static const bool answer= Operation<T1,Car2>::answer || list_or_binary<Operation, same<T1>, Cdr2>::answer;
};

template <template <typename,typename> class Operation, typename T1, typename T2>
struct list_count_binary {
   static const int answer= list_apply_binary<Operation, T1, T2>::answer ? 1 : 0;
};

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename Car2, typename Cdr2>
struct list_count_binary<Operation, cons<Car1,Cdr1>, cons<Car2,Cdr2> > {
   static const int answer= list_count_binary<Operation, Car1, Car2>::answer + list_count_binary<Operation, Cdr1, Cdr2>::answer;
};

template <template <typename,typename> class Operation, typename Car1, typename Cdr1, typename T2>
struct list_count_binary<Operation, cons<Car1,Cdr1>, same<T2> > {
   static const bool answer= list_count_binary<Operation, Car1, T2>::answer + list_count_binary<Operation, Cdr1, same<T2> >::answer;
};

template <template <typename,typename> class Operation, typename T1, typename Car2, typename Cdr2>
struct list_count_binary<Operation, same<T1>, cons<Car2,Cdr2> > {
   static const bool answer= list_count_binary<Operation, T1, Car2>::answer + list_count_binary<Operation, same<T1>, Cdr2>::answer;
};

template <typename First, typename Second, template <typename, typename> class Predicate=identical_raw>
struct list_mapping {
   typedef int2type< list_search<Second, First, Predicate>::pos > result;
   static const bool mismatch= list_search<Second, First, Predicate>::pos < 0;
};

template <typename Car, typename Cdr, typename Second, template <typename, typename> class Predicate>
struct list_mapping< cons<Car, Cdr>, Second, Predicate> {
   typedef list_mapping<Car, Second, Predicate> first;
   typedef list_mapping<Cdr, Second, Predicate> second;
   typedef cons< typename first::result, typename second::result > result;
   static const bool mismatch= first::mismatch || second::mismatch;
};

#if 0
template <typename T>
struct value_holder {
   T value;

   value_holder(typename function_argument<T>::type x) : value(x) { }

   template <typename T2>
   value_holder(const value_holder<T2>& x) : value(x.value) { }

   typename attrib<T>::plus_ref get(int2type<0>*) {
      return value;
   }
   typename attrib<T>::plus_const_ref get(int2type<0>*) const {
      return value;
   }
};

template <typename Car, typename Cdr>
struct value_holder< cons<Car, Cdr> > : value_holder<Cdr> {
   typedef Car head;
   typedef typename n_th<Cdr, list_length<Cdr>::answer-1>::car tail;

   head value;

   value_holder(typename function_argument<head>::type x, typename function_argument<tail>::type y)
      : value_holder<Cdr>(y), value(x) { }

   template <typename List2>
   value_holder(typename function_argument<head>::type x, const value_holder<List2>& y)
      : value_holder<Cdr>(y), value(x) { }

   template <typename Car2, typename Cdr2>
   value_holder(const value_holder< cons<Car2, Cdr2> >& x, typename function_argument<tail>::type y)
      : value_holder<Cdr>(static_cast<const value_holder<Cdr2>&>(x), y), value(x.value) { }

   template <typename Car2, typename Cdr2>
   value_holder(const value_holder< cons<Car2, Cdr2> >& x)
      : value_holder<Cdr>(static_cast<const value_holder<Cdr2>&>(x)), value(x.value) { }

   template <typename Car2, typename List2>
   value_holder(const value_holder<Car2>& x, const value_holder<List2>& y)
      : value_holder<Cdr>(y), value(x.value) { }

   template <typename Car2, typename Cdr2, typename List2>
   value_holder(const value_holder< cons<Car2, Cdr2> >& x, const value_holder<List2>& y)
      : value_holder<Cdr>(static_cast<const value_holder<Cdr2>&>(x), y), value(x.value) { }

   template <int i>
   typename attrib<typename n_th<cons<Car, Cdr>, i>::car>::plus_ref
   get(int2type<i>*) {
      typedef value_holder<typename n_th<cons<Car, Cdr>, i>::list> link;
      return link::value;
   }
   template <int i>
   typename attrib<typename n_th<cons<Car, Cdr>, i>::car>::plus_const_ref
   get(int2type<i>*) const {
      typedef value_holder<typename n_th<cons<Car, Cdr>, i>::list> link;
      return link::value;
   }
};
#endif

/* -----------------------------------
 *  Structural description of objects
 * ----------------------------------- */

struct is_scalar;
struct is_container;
struct is_composite;

namespace object_classifier {
   enum { unspecified=1 };
   typedef char (&_unspecified)[unspecified];

   _unspecified analyzer_f(...);

   template <typename T>
   struct kind_of {
      static const int answer=sizeof(analyzer_f((const T*)0));
   };

   template <typename T, int kind=kind_of<T>::answer>
   struct what_is {
      static const int answer=kind;
   };
} // end namespace object_classifier

template <typename T>
struct spec_object_traits
   : spec_object_traits< int2type<object_classifier::what_is<T>::answer> > { };

template <>
struct spec_object_traits< int2type<object_classifier::unspecified> > {
   typedef is_scalar model;
   static const bool is_lazy=false, is_temporary=false, is_always_const=false;
   // FIXME: until XML serialization implemented!
   static const bool IO_ends_with_eol=false;
};

template <>
struct spec_object_traits<is_composite> {
   typedef is_composite model;
   static const bool is_lazy=false, is_temporary=false, is_always_const=false;
};

template <typename T, typename Model,
	  bool _fulfilled=derived_from< spec_object_traits<T>, spec_object_traits<Model> >::answer>
struct spec_or_model_traits : spec_object_traits<T> { };

template <typename T, typename Model>
struct spec_or_model_traits<T, Model, false> : spec_object_traits<Model> { };

template <typename T>
struct has_generic_type : derived_from_instance<T,Generic> { };

template <typename T,
	  bool _has_generic=has_generic_type<T>::answer>
struct generic_object_traits
   : spec_object_traits<T> {
   typedef T persistent_type;
   typedef void generic_type;
   typedef typename spec_object_traits<T>::model generic_tag;
};

template <typename T>
struct insert_spec_traits_before_generic {
   static const bool
      is_top=identical<T, typename T::generic_type::top_type>::answer,
      is_specialized=derived_from< spec_object_traits<T>,
				   spec_object_traits<typename T::generic_type> >::answer,
      answer=!is_top && is_specialized;
};

template <typename T,
	  bool _use_spec=insert_spec_traits_before_generic<T>::answer>
struct generic_object_traits_helper
   : spec_object_traits<typename T::generic_type> {
   typedef typename T::persistent_type persistent_type;
   typedef typename T::generic_type generic_type;
   typedef typename T::generic_tag generic_tag;
};

template <typename T>
struct generic_object_traits_helper<T, true>
   : spec_object_traits<T> { };

template <typename T>
struct generic_object_traits<T,true>
   : generic_object_traits_helper<T> { };

template <typename T, typename Model=typename generic_object_traits<T>::model>
struct object_traits : generic_object_traits<T> {
   static const int total_dimension=0, nesting_level=0;
};

enum IO_separator_kind { IO_sep_inherit, IO_sep_containers, IO_sep_enforce };

template <typename T>
struct object_traits<T,is_container> : generic_object_traits<T> {
   static const int
      total_dimension = object_traits<typename T::value_type>::total_dimension + object_traits<T>::dimension,
      nesting_level = object_traits<typename T::value_type>::nesting_level + 1;
   // FIXME: until XML serialization implemented!
   static const bool
      IO_separate_elements_with_eol=
         object_traits<T>::IO_separator==IO_sep_inherit &&
            object_traits<typename T::value_type>::IO_ends_with_eol
      || object_traits<T>::IO_separator==IO_sep_containers &&
            object_traits<typename T::value_type>::total_dimension >= 1
      || object_traits<T>::IO_separator==IO_sep_enforce,
      IO_ends_with_eol=
         IO_separate_elements_with_eol
      || object_traits<typename T::value_type>::IO_ends_with_eol
      || object_traits<T>::dimension>1;
};

template <>
struct spec_object_traits<is_container> {
   typedef is_container model;
   static const int dimension=1;
   static const bool is_lazy=false, is_temporary=false, is_always_const=false, is_ordered=true, allow_sparse=false;
   // FIXME: until XML serialization implemented!
   static const IO_separator_kind IO_separator=IO_sep_containers;
};

template <typename T>
struct max_dimension {
   static const int answer=object_traits<typename deref<T>::type>::total_dimension;
   // FIXME: until XML serialization implemented!
   static const bool IO_ends_with_eol=object_traits<typename deref<T>::type>::IO_ends_with_eol;
};

#if defined (__COMO__) || defined(__INTEL_COMPILER)
   template <int X, int Y, bool _ge=(X>=Y)>
   struct const_compare {
      static const int max=X, min=Y;
   };
   template <int X, int Y>
   struct const_compare<X,Y,false> {
      static const int max=Y, min=X;
   };
#else
   template <int X, int Y>
   struct const_compare {
      static const int max=X >? Y, min=X <? Y;
   };
#endif
template <int X, int Y, bool _ge=(X>=0)>
struct const_first_nonnegative {
   static const int answer=X;
};
template <int X, int Y>
struct const_first_nonnegative<X,Y,false> {
   static const int answer=Y;
};

template <typename Car, typename Cdr>
struct max_dimension< cons<Car, Cdr> > {
   static const int answer=const_compare<max_dimension<Car>::answer, max_dimension<Cdr>::answer>::max;
   // FIXME: until XML serialization implemented!
   static const bool IO_ends_with_eol=max_dimension<Car>::IO_ends_with_eol || max_dimension<Cdr>::IO_ends_with_eol;
};

template <typename Object>
struct object_traits<Object,is_composite> : generic_object_traits<Object> {
   static const int total_dimension=max_dimension<typename object_traits::elements>::answer,
                    nesting_level=0;
   // FIXME: until XML serialization implemented!
   static const bool IO_ends_with_eol=max_dimension<typename object_traits::elements>::IO_ends_with_eol;
};

template <typename ObjectRef, typename Model=typename object_traits<typename attrib<ObjectRef>::type>::model>
struct is_mutable_helper {
   static const bool answer=!attrib<ObjectRef>::is_const;
};

template <typename ObjectRef>
struct is_mutable : is_mutable_helper<ObjectRef> { };

template <typename ObjectRef>
struct is_mutable_helper<ObjectRef, is_composite>
   : list_and_unary<is_mutable, typename object_traits<typename attrib<ObjectRef>::type>::elements> { };

// common case: everything is bad
template <typename T1, typename T2,
          typename Model1=typename object_traits<T1>::model, typename Model2=typename object_traits<T2>::model>
struct isomorphic {
   static const bool answer=false;
   typedef void discriminant;
};

template <typename T1, typename T2, typename Model>
struct isomorphic<T1, T2, Model, Model> {
   static const bool answer=true;
   typedef cons<typename object_traits<T1>::generic_tag, typename object_traits<T2>::generic_tag> discriminant;
};

template <typename T1, typename T2>
struct isomorphic<T1, T2, is_container, is_container> {
   typedef typename T1::value_type V1;
   typedef typename T2::value_type V2;
   static const bool answer=isomorphic<V1,V2>::answer;
   typedef typename choice< if_else< answer, cons<typename object_traits<T1>::generic_tag, typename object_traits<T2>::generic_tag>,
			    if_else< isomorphic<T1,V2>::answer, cons<is_scalar, typename object_traits<T2>::generic_tag>,
			    if_else< isomorphic<V1,T2>::answer, cons<typename object_traits<T1>::generic_tag, is_scalar>,
				     void > > > >::result
      discriminant;
};

template <typename T1, typename T2, typename Model1>
struct isomorphic<T1, T2, Model1, is_container> {
   static const bool answer=false;
   typedef typename if_else< isomorphic<T1, typename T2::value_type>::answer,
			     cons<is_scalar, typename object_traits<T2>::generic_tag>, void>::result
      discriminant;
};

template <typename T1, typename T2, typename Model2>
struct isomorphic<T1, T2, is_container, Model2> {
   static const bool answer=false;
   typedef typename if_else< isomorphic<typename T1::value_type, T2>::answer,
			     cons<typename object_traits<T1>::generic_tag, is_scalar>, void>::result
      discriminant;
};

template <typename T1, typename T2>
struct isomorphic_helper : isomorphic<typename deref<T1>::type, typename deref<T2>::type> { };

template <typename T1, typename T2>
struct isomorphic<T1, T2, is_composite, is_composite> {
   static const bool answer=
      list_and_binary<isomorphic_helper, typename object_traits<T1>::elements, typename object_traits<T2>::elements>::answer;
   typedef typename if_else<answer, cons<typename object_traits<T1>::generic_tag, typename object_traits<T2>::generic_tag>, void>::result
      discriminant;
};


/* -----------------------------------------------
 *  conversion between generic and concrete types
 * ----------------------------------------------- */

template <typename T, bool _has_generic=has_generic_type<T>::answer,
		      bool _itself_generic=false>
struct Concrete : True {
   typedef typename deref<T>::type type;
   static type& get(type& x) { return x; }
   static const type& get(const type& x) { return x; }
};

template <typename T>
struct Concrete<T,true,false>
   : Concrete<T, false, identical<typename deref<T>::type, typename deref<T>::type::generic_type>::answer> { };

template <typename T>
struct Concrete<T,false,true> : False {
   typedef typename T::top_type type;
   static type& get(typename deref<T>::type& x) { return x.top(); }
   static const type& get(const typename deref<T>::type& x) { return x.top(); }
};

template <typename ObjectRef,
	  bool _is_lazy=object_traits<typename Concrete<typename deref<ObjectRef>::type>::type>::is_lazy>
struct prevent_lazy {
   typedef typename attrib<ObjectRef>::plus_const type;
   typedef typename attrib<ObjectRef>::plus_const_ref result_type;
   static result_type get(result_type x) { return x; }
};

template <typename ObjectRef>
struct prevent_lazy<ObjectRef,true> {
   typedef const typename object_traits<typename Concrete<typename deref<ObjectRef>::type>::type>::persistent_type type;
   typedef type result_type;
   static result_type get(typename attrib<ObjectRef>::plus_const_ref x) { return result_type(x); }
};

template <typename Result, typename Source, typename _Generic>
struct inherit_generic_helper {
   typedef typename Source::template construct_generic<Result>::type type;
};

template <typename Top>
class generic_anything {
protected:
   // undefined
   generic_anything& operator= (const generic_anything&);
   void swap(generic_anything&);
   typedef generic_anything generic_type;
};

template <typename Result, typename Source>
struct inherit_generic_helper<Result, Source, void> {
   typedef generic_anything<Result> type;
};

template <typename Result, typename Source>
struct inherit_generic
   : inherit_generic_helper<Result, Source, typename object_traits<Source>::generic_type> { };

template <typename T>
struct inherit_generic_helper2 {
   typedef typename object_traits<T>::generic_tag tag;
   typedef typename object_traits<T>::generic_type generic_type;
};

template <typename Car, typename Cdr>
struct inherit_generic_helper2< cons<Car,Cdr> > {
   typedef typename object_traits<Car>::generic_tag tag1;
   typedef typename inherit_generic_helper2<Cdr>::tag tag2;
   typedef typename identical<tag1,tag2>::type tag;
   typedef typename if_else<identical<tag1,tag2>::answer, typename object_traits<Car>::generic_type, void>::result generic_type;
};

template <typename Result, typename Car, typename Cdr>
struct inherit_generic<Result, cons<Car, Cdr> >
   : inherit_generic_helper<Result, Car, typename inherit_generic_helper2< cons<Car,Cdr> >::generic_type> { };

/* ----------------------------------------
 *  tools for alias and masquerade objects 
 * ---------------------------------------- */

template <typename ObjectRef>
struct effectively_const {
   typedef typename deref<ObjectRef>::type Object;
   static const bool answer= object_traits<Object>::is_temporary
                             ? object_traits<Object>::is_always_const
                             : attrib<ObjectRef>::is_const;
};

template <typename T>
struct non_const_helper : assign_const<T, effectively_const<const T>::answer> { };

template <typename T> inline
typename non_const_helper<T>::type& non_const(const T& x)
{
   return const_cast<typename non_const_helper<T>::type&>(x);
}

template <typename T> inline
T& non_const(T& x) { return x; }

template <template <typename> class Masquerade, typename OrigRef>
struct masquerade {
   typedef OrigRef orig_ref;
   typedef typename inherit_ref<Masquerade<typename deref<OrigRef>::type>, OrigRef>::type type;
};

template <template <typename,typename> class Masquerade, typename OrigRef, typename Second>
struct masquerade2 {
   typedef OrigRef orig_ref;
   typedef typename inherit_ref<Masquerade<typename deref<OrigRef>::type, Second>, OrigRef>::type type;
};

template <template <typename> class Masquerade, typename OrigRef>
struct deref< masquerade<Masquerade, OrigRef> >
   : deref< typename masquerade<Masquerade, OrigRef>::type > { };

template <template <typename> class Masquerade, typename OrigRef>
struct deref< const masquerade<Masquerade, OrigRef> >
   : deref< typename masquerade<Masquerade, typename attrib<OrigRef>::plus_const>::type > { };

template <template <typename,typename> class Masquerade, typename OrigRef, typename Second>
struct deref< masquerade2<Masquerade, OrigRef, Second> >
   : deref< typename masquerade2<Masquerade, OrigRef, Second>::type > { };

template <template <typename,typename> class Masquerade, typename OrigRef, typename Second>
struct deref< const masquerade2<Masquerade, OrigRef, Second> >
   : deref< typename masquerade2<Masquerade, typename attrib<OrigRef>::plus_const, Second>::type > { };

template <typename Object>
class alias_ptr {
protected:
   const Object* ptr;
public:
   alias_ptr(const Object* ptr_arg) : ptr(ptr_arg) { }
};

template <typename ObjectRef,
	  bool _is_ref=attrib<ObjectRef>::is_reference && !object_traits<typename deref<ObjectRef>::type>::is_temporary,
	  bool _is_masqueraded=!identical<typename attrib<ObjectRef>::type, typename deref<ObjectRef>::type>::answer>
class alias : private alias_ptr<typename deref<ObjectRef>::type> {
private:
   typedef typename deref<ObjectRef>::minus_ref Object;
public:
   typedef ObjectRef arg_type;
   alias(arg_type ref) : alias_ptr<typename deref<ObjectRef>::type>(&ref) { }

   typedef ObjectRef reference;
   typedef typename attrib<ObjectRef>::plus_const const_reference;
   typedef typename if_else<identical_raw<reference, const_reference>::answer,
			    function_argument<ObjectRef>, 	// something that will be surely never asked for
			    reference>::result
      reference_op;
   operator reference_op () { return *const_cast<Object*>(this->ptr); }
   operator const_reference () const { return *this->ptr; }
};

template <typename ObjectRef>
class alias<ObjectRef, false, false> {
private:
   typedef typename deref<ObjectRef>::type Object;
   Object member;
public:
   typedef typename attrib<ObjectRef>::plus_const_ref arg_type;
   alias(arg_type m) : member(m) { }

   typedef typename assign_const<Object, effectively_const<ObjectRef>::answer>::type& reference;
   typedef const Object& const_reference;
   typedef typename if_else<identical_raw<reference, const_reference>::answer,
			    function_argument<ObjectRef>, 	// something that will be surely never asked for
			    reference>::result
      reference_op;
   operator reference_op () { return member; }
   operator const_reference () const { return member; }
};

template <typename Masquerade>
class alias<Masquerade, false, true> : public alias<typename Masquerade::orig_ref> {
   typedef alias<typename Masquerade::orig_ref> super;
   typedef typename deref<Masquerade>::minus_ref ApparentObject;
public:
   alias(typename super::arg_type x) : super(x) { }

   typedef typename assign_const<ApparentObject, effectively_const<typename Masquerade::orig_ref>::answer>::type& reference;
   typedef const ApparentObject& const_reference;
   typedef typename if_else<identical_raw<reference, const_reference>::answer,
			    function_argument<Masquerade>, 	// something that will be surely never asked for
			    reference>::result
      reference_op;
   operator reference_op ()
   {
      return reinterpret_cast<reference>(static_cast<typename super::reference>(*this));
   }
   operator const_reference () const
   {
      return reinterpret_cast<const_reference>(static_cast<typename super::const_reference>(*this));
   }
};

template <typename ObjectRef, bool _is_ref, bool _is_masqueraded>
struct function_argument< alias<ObjectRef, _is_ref, _is_masqueraded> > {
   typedef typename alias<ObjectRef,_is_ref,_is_masqueraded>::arg_type type;
};

/* ----------------------
 *  memory layout tricks
 * ---------------------- */

template <typename T> inline
void relocate(T* from, T* to, __true_type)
{
   *to=*from;
}

template <typename T> inline
void relocate(T* from, T* to, __false_type)
{
   new(to) T(*from);
   from->~T();
}

template <typename T> inline
void relocate(T* from, T* to)
{
   relocate(from, to, typename __type_traits<T>::is_POD_type());
}

/** Move a pointer from a data member of a class to the containing class object.
    data_member may also point to some Member's parent class.  */
template <typename Class, typename Member, typename Source> inline
Class* reverse_cast(Source* data_member, Member Class::* member_ptr)
{
   const int fict_addr=8,
      offset=reinterpret_cast<char*>(&(reinterpret_cast<Class*>(fict_addr)->*member_ptr))
            -reinterpret_cast<char*>(fict_addr);
   return reinterpret_cast<Class*>( reinterpret_cast<char*>(static_cast<Member*>(data_member)) - offset );
}

template <typename Class, typename Member, typename Source> inline
const Class* reverse_cast(const Source* data_member, Member Class::* member_ptr)
{
   const int fict_addr=8,
      offset=reinterpret_cast<const char*>(&(reinterpret_cast<const Class*>(fict_addr)->*member_ptr))
            -reinterpret_cast<const char*>(fict_addr);
   return reinterpret_cast<const Class*>( reinterpret_cast<const char*>(static_cast<const Member*>(data_member)) - offset );
}

template <typename Class, typename Member, typename Source> inline
const Class* reverse_cast(const Source* data_member, const Member Class::* member_ptr)
{
   const int fict_addr=8,
      offset=reinterpret_cast<const char*>(&(reinterpret_cast<const Class*>(fict_addr)->*member_ptr))
            -reinterpret_cast<const char*>(fict_addr);
   return reinterpret_cast<const Class*>( reinterpret_cast<const char*>(static_cast<const Member*>(data_member)) - offset );
}

template <typename Class, typename Member, typename Source, int _size> inline
Class* reverse_cast(Source* data_member, int i, Member (Class::* member_ptr)[_size])
{
   const int fict_addr=8,
      offset=reinterpret_cast<char*>((reinterpret_cast<Class*>(fict_addr)->*member_ptr)+0)
            -reinterpret_cast<char*>(fict_addr);
   return reinterpret_cast<Class*>( reinterpret_cast<char*>(static_cast<Member*>(data_member)-i) - offset );
}

template <typename Class, typename Member, typename Source, int _size> inline
const Class* reverse_cast(const Source* data_member, int i, Member (Class::* member_ptr)[_size])
{
   const int fict_addr=8,
      offset=reinterpret_cast<const char*>((reinterpret_cast<const Class*>(fict_addr)->*member_ptr)+0)
            -reinterpret_cast<const char*>(fict_addr);
   return reinterpret_cast<const Class*>( reinterpret_cast<const char*>(static_cast<const Member*>(data_member)-i) - offset );
}

template <typename Class, typename Member, typename Source, int _size> inline
const Class* reverse_cast(const Source* data_member, int i, const Member (Class::* member_ptr)[_size])
{
   const int fict_addr=8,
      offset=reinterpret_cast<const char*>((reinterpret_cast<const Class*>(fict_addr)->*member_ptr)+0)
            -reinterpret_cast<const char*>(fict_addr);
   return reinterpret_cast<const Class*>( reinterpret_cast<const char*>(static_cast<const Member*>(data_member)-i) - offset );
}

} // end namespace pm

namespace polymake {
   using pm::non_const;
   using pm::reverse_cast;
}

#endif // _POLYMAKE_TYPE_MANIP_H

// Local Variables:
// mode:C++
// End:
