/*******************************************************************************
+
+  LEDA 3.5
+
+  param_types.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_PARAM_TYPE_H
#define LEDA_PARAM_TYPE_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350090
#include <LEDA/REDEFINE_NAMES.h>
#endif


//----------------------------------------------------------------------------
//
// Parameterized data types store copies of values of arbitrary types T
// in a single data field of type void* (GenPtr). There are two cases
// which have to be treated differently here.
//
// If T is a "big type" (sizeof(T) > sizeof(GenPtr)) we make a copy in the 
// dynamic memory using the new operator and store a pointer to this copy. 
// If T is a "small type" (sizeof(T) <= sizeof(GenPtr)) we avoid the 
// overhead of an extra level of indirection by copying the value directly 
// into the void* data field. This is done by using the "in-place" variant 
// of the new operator. A good description of this feature can be found 
// in  R.B. Murray: "C++ Strategies and Tactics" (chapter 9.5). We would
// like to thank all people contributing to this solution by sending us
// problem reports and helpful suggestions (see LEDA/ACKNOWLEDGEMENTS).
//
// Both cases are handled by the "leda_copy" function template defined in this 
// file. Similarly, the two cases (small or big type) have to be treated 
// differently,  when creating ("leda_create"), destroying ("leda_clear"),
// and accessing ("leda_access") data of a parameterized type. Note that 
// destruction of small types uses an an explicit destructor call which is 
// not supported by some compilers.
//
// More details on the implementation of parameterized data types in LEDA
// will be given in the text book "LEDA: A Platform ..."  by K. Mehlhorn
// and S. Naeher (to appear in 1996)
//
//
// S. Naeher (1995)
//
//
// MODIFICATIONS
//
// Mai  1996 : leda_const_access  (S. Naeher)
// July 1996 : removed default compare definition (S . Naeher)
//
//----------------------------------------------------------------------------


#if defined(__NO_VOLATILE__) || defined(__MICROSOFTC__)
#define __volatile
#else
#define __volatile volatile
#endif



// type id's

enum { UNKNOWN_TYPE_ID,
       CHAR_TYPE_ID, 
       SHORT_TYPE_ID, 
       INT_TYPE_ID, 
       LONG_TYPE_ID, 
       FLOAT_TYPE_ID, 
       DOUBLE_TYPE_ID, 
       PTR_TYPE_ID };


// default input operator for pointers

inline istream& operator>>(istream& in, GenPtr) { return in; }

/*
template <class T>
inline istream& operator>>(istream& I, T) { return I; }

template <class T>
inline ostream& operator<<(ostream& O, T) { return O; }
*/



// Most c++ implementations provide an in-place new operator in <new.h>.
// However, it is not always declared inline. So, for efficiency reasons,
// we define our own (inline) version. We use a third dummy argument to 
// avoid conflicts with user defined variants.
// For compilers not supporting explicit destructor calls or in-place new
// we use the old method based on casting and assignment. Then 0 must be
// legal value on the right side of assignments for all one-word types.


#if defined(__NO_INPLACE_NEW__)

#define COPY_INTO_WORD(T,x,p) *(T*)(&p) = x;
#define CONSTRUCT_WORD(T,p)   { T x; COPY_INTO_WORD(T,x,p); }

#else

inline void Avoid_Unused_Warning(GenPtr) {}
inline void* operator new(size_t, void* where, int) { return where; }
/*
#define COPY_INTO_WORD(T,x,p) Avoid_Unused_Warning(new((T*)&p,0) T(x))
#define CONSTRUCT_WORD(T,p)   Avoid_Unused_Warning(new((T*)&p,0) T)
*/
#define COPY_INTO_WORD(T,x,p) Avoid_Unused_Warning(new((void*)(&p),0) T(x))
#define CONSTRUCT_WORD(T,p)   Avoid_Unused_Warning(new((void*)(&p),0) T)

#endif



#if defined(__NO_EXPLICIT_DESTRUCTION__)

inline void leda_explicit_destruction(GenPtr) {}
#define DESTROY_WORD(T,p)  leda_explicit_destruction((T*)p)

#else

#if defined(__lucid)
#define DESTROY_WORD(T,p)  p->T::~T();
#else
#define DESTROY_WORD(T,p)  p->~T();
#endif

#endif




//----------------------------------------------------------------------------
// Function templates for leda_copy, leda_create, leda_clear, leda_cast, 
// leda_access, etc.  
// When using a compiler that does not support function templates
// these functions have to be created for class types by a call of the
// LEDA_TYPE_PARAMETER macro defined at end of this file. Most of the 
// templates distinguish the two cases that the actual type has size 
// greater than the size of a pointer or not, i.e., is a big or small 
// type. Note that this does not cause any overhead at run time since 
// the right case can be determined at compile time. 
//----------------------------------------------------------------------------


template<class T>
inline GenPtr leda_copy(const T& x)
{ __volatile GenPtr p=0;
  if (sizeof(T) <= sizeof(GenPtr)) COPY_INTO_WORD(T,x,p);
  if (sizeof(T) >  sizeof(GenPtr)) p = (GenPtr) new T(x);
  return p;
 }

template <class T>
inline GenPtr leda_create(const T*) 
{ __volatile GenPtr p=0;
  if (sizeof(T) <= sizeof(GenPtr)) CONSTRUCT_WORD(T,p);
  if (sizeof(T) >  sizeof(GenPtr)) p = (GenPtr) new T;
  return p;
 }

template <class T>
inline void leda_clear(T& x) 
{ T* p = &x;
  if (sizeof(T) <= sizeof(GenPtr)) DESTROY_WORD(T,p);
  if (sizeof(T) >  sizeof(GenPtr)) delete p;
}


template <class T>
inline GenPtr leda_cast(const T& x) 
{ __volatile GenPtr p=0;
  if (sizeof(T) == sizeof(GenPtr)) p = *(GenPtr*)&x;
  if (sizeof(T) <  sizeof(GenPtr)) *(T*)(&p) = x;
  if (sizeof(T) >  sizeof(GenPtr)) p = (GenPtr)&x;
  return p;
 }


#if !defined(__MICROSOFTC__)

template <class T>
inline T& leda_access(const T*, const GenPtr& p)
{ if (sizeof(T) <= sizeof(GenPtr))
     return *(T*)(&p);
  else
     return *(T*)p;
 }

template <class T>
inline const T& leda_const_access(const T*, const GenPtr& p)
{ if (sizeof(T) <= sizeof(GenPtr))
     return *(const T*)(&p);
  else
     return *(const T*)p;
 }

#else

// Since Microsoft C++ cannot convert a GenPtr to a const GenPtr& in this 
// situation  we use a pointer instead of a reference as second argument in
// the leda_access template and a dummy function for converting the
// reference into a pointer (see also the definition of LEDA_ACCESS at the end
// of this file).

inline GenPtr* msc_hack(const GenPtr& p) { return (GenPtr*)&p; }

template <class T>
inline T& leda_access(const T*, GenPtr* p) 
{ if (sizeof(T) <= sizeof(GenPtr))
     return *(T*)p;
  else
     return *(T*)*p;
 }

template <class T>
inline const T& leda_const_access(const T*, GenPtr* p) 
{ if (sizeof(T) <= sizeof(GenPtr))
     return *(const T*)p;
  else
     return *(const T*)*p;
 }

#endif




template <class T> 
inline int   leda_type_id(const T*)   { return UNKNOWN_TYPE_ID; }

template <class T>
inline char* leda_tname(const T*) { return "unknown"; }


//---------------------------------------------------------------------------
// default definitions for Print and Read
//---------------------------------------------------------------------------

#if defined(LEDA_PRINT_AND_READ)

template <class T> 
inline void Print(const T& x, ostream& out) { out << x; }

template <class T>
inline void Read(T& x, istream& in) { in >> x; }

#endif


//---------------------------------------------------------------------------
// template declaration for compare
//---------------------------------------------------------------------------


#if defined(LEDA_COMPARE_TEMPLATE)
template <class T> int compare(const T&, const T&);
//template <class T> 
//inline int compare(const T& x, const T& y) { return default_compare(&x,&y); }
#endif



#if defined(LEDA_STREAM_TEMPLATE)
template <class T> ostream& operator<<(ostream&, const T&);
template <class T> istream& operator>>(istream&, T&);
#endif




//----------------------------------------------------------------------------
// Specializations for some built-in types (to be extended as needed) for
// compilers not supporting function templates at all or having particular 
// problems with function templates (watcomc, lucid) (g++ seems not to be
// able to instantiate function templates inline).
//----------------------------------------------------------------------------

#if defined(__WATCOMC__) || defined(__lucid) || defined(__GNUC__)

inline GenPtr leda_copy(const char& x) 
{ __volatile GenPtr p=0; *(char*)&p = x;  return p;}

inline GenPtr leda_copy(const short& x)
{ __volatile GenPtr p=0; *(short*)&p = x; return p;}

inline GenPtr leda_copy(const int& x)  
{ __volatile GenPtr p=0; *(int*)&p = x;   return p;}

inline GenPtr leda_copy(const long& x) 
{ __volatile GenPtr p=0; *(long*)&p = x;  return p;}

inline GenPtr leda_copy(const float& x)
{ __volatile GenPtr p=0; *(float*)&p = x; return p;}
 

inline GenPtr leda_cast(const char& x)  { return leda_copy(x); }
inline GenPtr leda_cast(const short& x) { return leda_copy(x); }
inline GenPtr leda_cast(const int& x)   { return leda_copy(x); }
inline GenPtr leda_cast(const long& x)  { return leda_copy(x); }
inline GenPtr leda_cast(const float& x) { return leda_copy(x); }
 
inline GenPtr leda_create(const char*)  { return 0; }
inline GenPtr leda_create(const short*) { return 0; }
inline GenPtr leda_create(const int*)   { return 0; }
inline GenPtr leda_create(const long*)  { return 0; }
inline GenPtr leda_create(const float*) { return 0; }
 
inline void   leda_clear(char&)  {}
inline void   leda_clear(short&) {}
inline void   leda_clear(int&)   {}
inline void   leda_clear(long&)  {}
inline void   leda_clear(float&) {}
 
inline char&  leda_access(const char*, const GenPtr& p) { return *(char*)&p;  }
inline short& leda_access(const short*,const GenPtr& p) { return *(short*)&p; }
inline int&   leda_access(const int*,  const GenPtr& p) { return *(int*)&p;   }
inline long&  leda_access(const long*, const GenPtr& p) { return *(long*)&p;  }
inline float& leda_access(const float*,const GenPtr& p) { return *(float*)&p; }

inline const char&  leda_const_access(const char*, const GenPtr& p) 
{ return *(char*)&p;  }
inline const short& leda_const_access(const short*,const GenPtr& p) 
{ return *(short*)&p; }
inline const int&   leda_const_access(const int*,  const GenPtr& p) 
{ return *(int*)&p;   }
inline const long&  leda_const_access(const long*, const GenPtr& p) 
{ return *(long*)&p;  }
inline const float& leda_const_access(const float*,const GenPtr& p) 
{ return *(float*)&p; }
 
#endif



//----------------------------------------------------------------------------
// A "special" specialization for "double" using the LEDA memory management 
// if sizeof(double) > sizeof(GenPtr). 
//----------------------------------------------------------------------------

inline GenPtr leda_copy(const double& x)
{ GenPtr p;
  if (sizeof(double) > sizeof(GenPtr))
    { p = std_memory.allocate_bytes(sizeof(double));
      *(double*)p = x; }
  else 
      *(double*)&p = x;
  return p;
 }

inline GenPtr leda_create(const double*)
{ GenPtr p;
  if (sizeof(double) > sizeof(GenPtr))
    { p = std_memory.allocate_bytes(sizeof(double));
      *(double*)p = 0; }
  else 
      *(double*)&p = 0;
  return p;
 }

inline void leda_clear(double& x) 
{ if (sizeof(double) > sizeof(GenPtr)) 
     std_memory.deallocate_bytes(&x,sizeof(double)); 
 }

inline GenPtr leda_cast(const double& x) 
{ return (sizeof(double) <= sizeof(GenPtr)) ? *(GenPtr*)&x : GenPtr(&x); }


inline double& leda_access(const double*, const GenPtr& p) 
{ return (sizeof(double) <= sizeof(GenPtr)) ? *(double*)&p : *(double*)p; }

inline const double& leda_const_access(const double*, const GenPtr& p) 
{ return (sizeof(double) <= sizeof(GenPtr)) ? *(double*)&p : *(double*)p; }




//----------------------------------------------------------------------------
// type id's
//----------------------------------------------------------------------------

inline int leda_type_id(const char*)   { return CHAR_TYPE_ID; }
inline int leda_type_id(const short*)  { return SHORT_TYPE_ID; }
inline int leda_type_id(const int*)    { return INT_TYPE_ID; }
inline int leda_type_id(const long*)   { return LONG_TYPE_ID; }
inline int leda_type_id(const float*)  { return FLOAT_TYPE_ID; }
inline int leda_type_id(const double*) { return DOUBLE_TYPE_ID; }


//----------------------------------------------------------------------------
// type names
//----------------------------------------------------------------------------

inline char* leda_tname(const char*  ) { return "char";   }
inline char* leda_tname(const short* ) { return "short";  }
inline char* leda_tname(const int*   ) { return "int";    }
inline char* leda_tname(const long*  ) { return "long";   }
inline char* leda_tname(const float* ) { return "float";  }
inline char* leda_tname(const double*) { return "double"; }



//----------------------------------------------------------------------------
// id numbers
//----------------------------------------------------------------------------

inline unsigned long ID_Number(GenPtr x) { return (unsigned long)x; }
inline unsigned long ID_Number(char   x) { return (unsigned long)x; }
inline unsigned long ID_Number(short  x) { return (unsigned long)x; }
inline unsigned long ID_Number(int    x) { return (unsigned long)x; }
inline unsigned long ID_Number(long   x) { return (unsigned long)x; }
inline unsigned long ID_Number(unsigned int  x) { return (unsigned long)x; }
inline unsigned long ID_Number(unsigned long x) { return (unsigned long)x; }




//----------------------------------------------------------------------------
// pre-defined linear orders and hash functions
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// compare
//----------------------------------------------------------------------------

template <class T> class decl_compare_func { 
#if defined(__GNUC__)
  friend inline int compare(const T&, const T&);
#else
  friend int compare(const T&, const T&);
#endif
};



/*
template <class T>
inline int default_compare(const T&, const T&)
{ error_handler(1,"no default compare"); }

#define DEFINE_DEFAULT_COMPARE(T)          \
inline int default_compare(const T& x, const T& y) \
{ if (x < y) return -1;                    \
  else if (x > y) return  1;               \
  else return 0;                           \
}

DEFINE_DEFAULT_COMPARE(char)
DEFINE_DEFAULT_COMPARE(int)
DEFINE_DEFAULT_COMPARE(unsigned int)
DEFINE_DEFAULT_COMPARE(long)
DEFINE_DEFAULT_COMPARE(unsigned long)
DEFINE_DEFAULT_COMPARE(float)
DEFINE_DEFAULT_COMPARE(double)

#if defined(__HAS_BUILTIN_BOOL__)
DEFINE_DEFAULT_COMPARE(bool)
#endif
*/


#define DEFINE_COMPARE(T)                 \
inline int compare(const T& x, const T& y)\
{ if (x < y) return -1;                   \
  else if (x > y) return  1;              \
  else return 0;                          \
}

DEFINE_COMPARE(char)
DEFINE_COMPARE(int)
DEFINE_COMPARE(unsigned int)
DEFINE_COMPARE(long)
DEFINE_COMPARE(unsigned long)
DEFINE_COMPARE(float)
DEFINE_COMPARE(double)

#if defined(__HAS_BUILTIN_BOOL__) && !defined(__MICROSOFTC__)
DEFINE_COMPARE(bool)
#endif


//----------------------------------------------------------------------------
// hashing
//----------------------------------------------------------------------------

inline int Hash(const GenPtr& x) { return int(long(x)); }
inline int Hash(const char&   x) { return int(x); } 
inline int Hash(const short&  x) { return int(x); }
inline int Hash(const int&    x) { return int(x); }
inline int Hash(const long&   x) { return int(x); }
inline int Hash(const float&  x) { return int(x); }
inline int Hash(const double& x) { return int(x); }
#if defined(__HAS_BUILTIN_BOOL__)
inline int Hash(const bool&   x) { return int(x); }
#endif



//----------------------------------------------------------------------------
// some useful macros 
// (used in data type templates)
//----------------------------------------------------------------------------

#if defined(__WATCOMC__) && __WATCOMC__ < 1050
#define MKNULLPTR(T) (const T*)0
#define ACCESSPTR(p) (const GenPtr&)p
#else
#if defined(__MICROSOFTC__)
#define MKNULLPTR(T) (T*)0
#define ACCESSPTR(p) msc_hack(p)
#else
#define MKNULLPTR(T) (T*)0
#define ACCESSPTR(p) p
#endif
#endif


#if defined(__ATTCFRONT__)
#define LEDA_ACCESS(T,p)       (T&)(leda_access(MKNULLPTR(T),p))
#define LEDA_CONST_ACCESS(T,p) (const T&)(leda_access(MKNULLPTR(T),p))
#else
#define LEDA_ACCESS(T,p)       leda_access(MKNULLPTR(T),ACCESSPTR(p))
#define LEDA_CONST_ACCESS(T,p) leda_const_access(MKNULLPTR(T),ACCESSPTR(p))
#endif

#define LEDA_CREATE(T,x)    x=leda_create(MKNULLPTR(T))
#define LEDA_COPY(T,x)      x=leda_copy(LEDA_CONST_ACCESS(T,x))
#define LEDA_TYPE_ID(T)     leda_type_id(MKNULLPTR(T))
#define LEDA_TYPE_NAME(T)   leda_tname(MKNULLPTR(T))
#define LEDA_CAST(x)        leda_cast(x)
#define LEDA_CLEAR(T,x)     leda_clear(LEDA_ACCESS(T,x))
#define LEDA_COMPARE(T,x,y) compare(LEDA_CONST_ACCESS(T,x),LEDA_CONST_ACCESS(T,y))
#define LEDA_HASH(T,x)      Hash(LEDA_CONST_ACCESS(T,x))
#define LEDA_EQUAL(T,x,y)   (LEDA_CONST_ACCESS(T,x) == LEDA_CONST_ACCESS(T,y))


#if defined(LEDA_PRINT_AND_READ)
#define LEDA_PRINT(T,x,out) Print(LEDA_CONST_ACCESS(T,x),(ostream&)out)
#define LEDA_READ(T,x,in)   LEDA_CREATE(T,x);Read(LEDA_ACCESS(T,x),(istream&)in)
#else
#define LEDA_PRINT(T,x,out) out << LEDA_CONST_ACCESS(T,x)
#define LEDA_READ(T,x,in)  LEDA_CREATE(T,x); in >> LEDA_ACCESS(T,x)
#endif



#if LEDA_ROOT_INCL_ID == 350090
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
