/* Copyright (c) 1997-2005
   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_GENERIC_IO_H
#define _POLYMAKE_GENERIC_IO_H "$Project: polymake $$Id: GenericIO.h,v 1.14 2006/03/09 16:21:35 gawrilow Exp $"

#ifndef _POLYMAKE_SPARSE_H
#  include <sparse.h>
#endif

namespace pm {

template <typename Data, typename Input> struct make_list_reader;

#if 0
template <typename T, int min_occurs, int max_occurs> struct repeat_item {};
template <typename T> struct zero_or_one : repeat_item<T,0,1> {};
template <typename T> struct zero_or_many : repeat_item<T,0,-1> {};
template <typename T> struct one_or_many : repeat_item<T,1,-1> {};
#endif

template <typename> class CheckEOF;
template <typename> class SparseRepresentation;
template <typename> class HideDimension;
template <typename> class LookForward;

template <typename T>
struct ignore_in_composite : False { };

template <>
struct ignore_in_composite<nothing> : True { };

template <typename T, typename Expected>
struct ignore_in_composite< ignore<T,Expected> > : identical<Expected,nothing> { };

template <typename T>
struct ignore_in_composite<const T> : ignore_in_composite<T> { };

template <typename T>
struct ignore_in_composite<T&> : ignore_in_composite<T> { };

template <typename Top, typename Options, int subst_pos=0>
class GenericIOoptions {
public:
   template <typename OptionInst>
   struct get_option : extract_param<Options, OptionInst>::result { };

   template <typename OptionInst>
   typename subst_template_type_param<Top, typename replace_params<Options, OptionInst>::result, subst_pos>::type&
   set_option(OptionInst*)
   {
      return reinterpret_cast<typename subst_template_type_param<Top, typename replace_params<Options, OptionInst>::result, subst_pos>::type&>(static_cast<Top&>(*this));
   }
};

template <typename Input>
class GenericInput {
public:
   Input& top() { return static_cast<Input&>(*this); }
   Input& top() const { return static_cast<Input&>(const_cast<GenericInput&>(*this)); }
};

namespace io_test {

struct fallback {
   template <typename Any>
   fallback(const Any&);
};

nothing& operator>> (const fallback&, const fallback&);

template <typename Input, typename Data>
struct has_generic_input_operator {
   static GenericInput<Input>& input();
   static Data& data();
   struct helper {
      derivation::yes Test(Input&);
      derivation::no Test(nothing&);
   };
   static const bool answer= sizeof(helper().Test( input() >> data() )) == sizeof(derivation::yes);
};

} // end namespace io_test

template <typename Input>
class GenericInputImpl : public GenericInput<Input> {
   template <typename> friend class GenericInputImpl;
public:
   typedef GenericInputImpl generic_type;

   template <typename Data>
   Input& operator>> (Data& data)
   {
      typedef typename Concrete<Data>::type data_type;
      dispatch_retrieve(Concrete<Data>::get(data),
			(bool2type< io_test::has_generic_input_operator<Input,data_type>::answer >*)0);
      return this->top();
   }

protected:
   template <typename Data>
   void dispatch_retrieve(Data& data, False*)
   {
      // no generic output operator found
      dispatch_retrieve(data,
			(typename object_traits<Data>::model*)0,
			(function_argument<typename object_traits<Data>::serialized>*)0);
   }

   template <typename Data>
   void dispatch_retrieve(Data& data, True*)
   {
      static_cast<GenericInput<Input>&>(*this) >> data;
   }

   template <typename Data>
   void dispatch_retrieve(Data& data, is_scalar*, function_argument<void>*)
   {
      this->top().fallback(data);
   }

   template <typename Data, typename Serialized>
   void dispatch_retrieve(Data& data, is_scalar*, function_argument<Serialized>*)
   {
      this->top() >> object_traits<Data>::serialize(data);
   }

   template <typename Data, typename Serialized>
   void dispatch_retrieve(Data& data, is_container*, function_argument<Serialized>*)
   {
      retrieve_container(data,
			(int2type<object_traits<Data>::dimension>*)0);
   }

   template <typename Data, typename Serialized>
   void dispatch_retrieve(Data& data, is_composite*, function_argument<Serialized>*)
   {
      retrieve_composite(data);
   }

   template <typename Data>
   void retrieve_container(Data& data, int2type<1>*)
   {
      retrieve_container(data,
			 (typename container_traits<Data>::category*)0,
			 (bool2type<check_container_feature<Data, sparse>::answer>*)0
			);
   }

   template <typename Data>
   void retrieve_container(Data& data, int2type<2>*)
   {
      retrieve_matrix(data, object_traits<Data>::serialize(data),
		      (int2type<object_traits<Data>::is_resizeable>*)0);
   }

   template <typename Data>
   void retrieve_container(Data& data, forward_iterator_tag*, False*)
   {
      retrieve_container(data,
			 (bool2type<object_traits<Data>::is_ordered>*)0,
			 (bool2type<is_mutable<typename Data::reference>::answer>*)0
			);
   }

   template <typename Data>
   void retrieve_container(Data& data, True*, True*)
   {
      retrieve_list(data);
   }

   template <typename Data>
   void retrieve_container(Data& data, True*, False*)
   {
      retrieve_set(data);
   }

   template <typename Data, bool _is_mutable>
   void retrieve_container(Data& data, False*, bool2type<_is_mutable>*)
   {
      retrieve_insertable(data);
   }

   template <typename Data>
   void retrieve_container(Data& data, random_access_iterator_tag*, False*)
   {
      this->top().begin_list(&data).retrieve_array(data,
						   (int2type<object_traits<Data>::is_resizeable>*)0,
						   (bool2type<object_traits<Data>::allow_sparse>*)0);
   }

   template <typename Data, typename Category>
   void retrieve_container(Data& data, Category*, True*)
   {
      const int discr= object_traits<Data>::IO_hide_dim ? -1 : object_traits<Data>::is_resizeable;
      this->top().begin_list(&data).retrieve_sparse(data, (int2type<discr>*)0);
   }

   template <typename Data> inline
   void retrieve_array(Data& data, int2type<0>*, False*);

   template <typename Data> inline
   void retrieve_array(Data& data, int2type<0>*, True*);

   template <typename Data> inline
   void retrieve_array(Data& data, int2type<1>*, False*);

   template <typename Data> inline
   void retrieve_array(Data& data, int2type<1>*, True*);

   template <typename Data> inline
   void retrieve_sparse(Data& data, int2type<-1>*);

   template <typename Data> inline
   void retrieve_sparse(Data& data, int2type<0>*);

   template <typename Data> inline
   void retrieve_sparse(Data& data, int2type<1>*);

   template <typename Data, typename Serialized> inline
   void retrieve_matrix(Data& data, Serialized& serialized, int2type<0>*);

   template <typename Data, typename Serialized> inline
   void retrieve_matrix(Data& data, Serialized& serialized, int2type<1>*);

   template <typename Data, typename Serialized> inline
   void retrieve_matrix(Data& data, Serialized& serialized, int2type<2>*);

public:
   template <typename Data>
   void retrieve_list(Data& data)
   {
      this->template retrieve_list_as<Data>(data);
   }

   template <typename Masquerade, typename Data>
   void retrieve_list_as(Data& data);

   template <typename Data>
   void retrieve_set(Data& data);

   template <typename Data>
   void retrieve_insertable(Data& data);

   template <typename Data>
   void retrieve_composite(Data& data);

   template <typename Data>
   typename make_list_reader<Data, Input>::type
   create_list_input_iterator(Data* x)
   {
      return typename make_list_reader<Data, Input>::type (this->top().begin_list(x));
   }
};

template <typename Input>
template <typename Masquerade, typename Data>
void GenericInputImpl<Input>::retrieve_list_as(Data& data)
{
   typename Input::template list_cursor<Masquerade>::type c=this->top().begin_list(reinterpret_cast<Masquerade*>(&data));
   typename Data::iterator dst=data.begin(), end=data.end();
   while (dst != end && !c.at_end()) {
      c >> *dst;
      ++dst;
   }

   if (c.at_end()) {
      data.erase(dst, end);
   } else {
      do
	 c >> *data.insert(end, typename Data::value_type());
      while (!c.at_end());
   }
}

template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_set(Data& data)
{
   data.clear();
   typename Input::template list_cursor<Data>::type c=this->top().begin_list(&data);
   typename Data::value_type item;
   typename Data::iterator end=data.end();
   while (!c.at_end()) {
      c >> item;
      data.insert(end, item);
   }
}

template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_insertable(Data& data)
{
   data.clear();
   typename Input::template list_cursor<Data>::type c=this->top().begin_list(&data);
   typename Data::value_type item;
   while (!c.at_end()) {
      c >> item;
      data.insert(item);
   }
}

template <typename Value, typename CursorRef>
class list_reader {
protected:
   alias<CursorRef> cursor;
   typedef typename deref<CursorRef>::type cursor_type;
   Value item;
   bool _end;

   void load()
   {
      typename attrib<cursor_type>::plus_ref c=cursor;
      if (c.at_end())
	 _end=true;
      else
	 c >> item;
   }
public:
   list_reader(typename alias<CursorRef>::arg_type cursor_arg)
      : cursor(cursor_arg), _end(false) { load(); }

   typedef input_iterator_tag iterator_category;
   typedef Value value_type;
   typedef const Value& reference;
   typedef const Value* pointer;
   typedef ptrdiff_t difference_type;

   reference operator* () const { return item; }
   pointer operator-> () const { return &item; }

   bool at_end() const { return _end; }

   list_reader& operator++ () { load(); return *this; }
private:
   list_reader& operator++ (int);
};

template <typename Data, typename Input>
struct make_list_reader {
   typedef list_reader<typename Data::value_type, typename Input::template list_cursor<Data>::type> type;
};

template <typename Input, typename Data> inline
void fill_dense_from_dense(Input& src, Data& data)
{
   for (typename Entire<Data>::iterator dst=entire(data); !dst.at_end(); ++dst) {
      typename Entire<Data>::iterator::reference dst_item=*dst;
      src >> dst_item;
   }
   src.finish();
}

template <typename Input, typename Data>
void fill_dense_from_sparse(Input& src, Data& data, int d)
{
   operations::clear<typename Data::value_type> zero;
   typename Data::iterator dst=data.begin();
   int i=0;
   while (!src.at_end()) {
      const int pos=src.index();
      while (i<pos) {
	 zero.assign(*dst);
	 ++dst; ++i;
      }
      src >> *dst;
      ++dst; ++i;
   }
   while (i<d) {
      zero.assign(*dst);
      ++dst; ++i;
   }
}

template <typename Input, typename Data>
void fill_sparse_from_dense(Input& src, Data& data)
{
   typename Entire<Data>::iterator dst=entire(data);
   typename Data::value_type v;
   conv<typename Data::value_type, bool> non_zero;
   int i=-1;
   if (!dst.at_end()) {
      for (;;) {
	 ++i; src >> v;
	 if (non_zero(v)) {
	    if (dst.index() > i) {
	       data.insert(dst, i, v);
	    } else {
	       *dst=v; ++dst;
	       if (dst.at_end()) break;
	    }
	 } else if (dst.index() == i) {
	    data.erase(dst++);
	    if (dst.at_end()) break;
	 }
	 
      }
   }
   while (!src.at_end()) {
      ++i; src >> v;
      if (non_zero(v))
	 data.insert(dst, i, v);
   }
}

template <typename Input, typename Data, typename LimitDim>
void fill_sparse_from_sparse(Input& src, Data& data, const LimitDim& limit_dim)
{
   typename Entire<Data>::iterator dst=entire(data);
   if (!dst.at_end()) {
      while (!src.at_end()) {
	 const int index=src.index();
	 if (index > dst.index()) {
	    do
	       data.erase(dst++);
	    while (!dst.at_end() && index > dst.index());
	    if (dst.at_end()) {
	       src >> *data.insert(dst,index);
	       break;
	    }
	 }
	 if (index < dst.index()) {
	    src >> *data.insert(dst,index);
	 } else {
	    src >> *dst;
	    ++dst;
	    if (dst.at_end()) break;
	 }
      }
   }
   if (src.at_end()) {
      while (!dst.at_end())
	 data.erase(dst++);
   } else {
      do {
	 const int index=src.index();
	 if (index > limit_dim) {
	    if (!ignore_in_composite<typename Input::value_type>::answer)
	       src.skip_item();
	    src.skip_rest(); src.finish();
	    break;
	 }
	 src >> *data.insert(index);
      } while (!src.at_end());
   }
}

template <typename Input, typename Data> inline
void resize_and_fill_dense_from_dense(Input& src, Data& data)
{
   data.resize(src.size());
   fill_dense_from_dense(src, data);
}

template <typename Input, typename Data> inline
void check_and_fill_dense_from_dense(Input& src, Data& data)
{
   if (src.size() != data.size())
      throw std::runtime_error("array input - dimension mismatch");
   fill_dense_from_dense(src, data);
}

template <typename Input, typename Data> inline
void resize_and_fill_dense_from_sparse(Input& src, Data& data)
{
   const int d=src.dim();
   data.resize(d);
   fill_dense_from_sparse(src, data, d);
}

template <typename Input, typename Data> inline
void check_and_fill_dense_from_sparse(Input& src, Data& data)
{
   const int d=src.dim();
   if (d != data.size())
      throw std::runtime_error("sparse input - dimension mismatch");
   fill_dense_from_sparse(src, data, d);
}

template <typename Input, typename Data> inline
void resize_and_fill_sparse_from_dense(Input& src, Data& data)
{
   data.resize(src.size());
   fill_sparse_from_dense(src, data);
}

template <typename Input, typename Data> inline
void check_and_fill_sparse_from_dense(Input& src, Data& data)
{
   if (src.size() != data.dim())
      throw std::runtime_error("array input - dimension mismatch");
   fill_sparse_from_dense(src, data);
}

template <typename Input, typename Data> inline
void resize_and_fill_sparse_from_sparse(Input& src, Data& data)
{
   data.resize(src.dim());
   fill_sparse_from_sparse(src, data, maximal<int>());
}

template <typename Input, typename Data> inline
void check_and_fill_sparse_from_sparse(Input& src, Data& data)
{
   if (!Input::template get_option< HideDimension<False> >::value && src.dim() != data.dim())
      throw std::runtime_error("sparse input - dimension mismatch");
   fill_sparse_from_sparse(src, data, maximal<int>());
}

// resizeable, allow sparse
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_array(Data& data, int2type<1>*, True*)
{
   if (this->top().sparse_representation())
      resize_and_fill_dense_from_sparse(this->top().set_option((SparseRepresentation<True>*)0), data);
   else
      resize_and_fill_dense_from_dense(this->top().set_option((SparseRepresentation<False>*)0), data);
}

// resizeable, only dense
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_array(Data& data, int2type<1>*, False*)
{
   resize_and_fill_dense_from_dense(this->top().set_option((SparseRepresentation<False>*)0), data);
}

// non-resizeable, allow sparse
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_array(Data& data, int2type<0>*, True*)
{
   if (this->top().sparse_representation())
      check_and_fill_dense_from_sparse(this->top().set_option((SparseRepresentation<True>*)0), data);
   else
      check_and_fill_dense_from_dense(this->top().set_option((cons< SparseRepresentation<False>, CheckEOF<True> >*)0), data);
}

// non-resizeable, only dense
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_array(Data& data, int2type<0>*, False*)
{
   check_and_fill_dense_from_dense(this->top().set_option((cons< SparseRepresentation<False>, CheckEOF<True> >*)0), data);
}

// resizeable
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_sparse(Data& data, int2type<1>*)
{
   if (this->top().sparse_representation())
      resize_and_fill_sparse_from_sparse(this->top().set_option((SparseRepresentation<True>*)0), data);
   else
      resize_and_fill_sparse_from_dense(this->top().set_option((SparseRepresentation<False>*)0), data);
}

// non-resizeable
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_sparse(Data& data, int2type<0>*)
{
   if (this->top().sparse_representation())
      check_and_fill_sparse_from_sparse(this->top().set_option((SparseRepresentation<True>*)0), data);
   else
      check_and_fill_sparse_from_dense(this->top().set_option((cons< SparseRepresentation<False>, CheckEOF<True> >*)0), data);
}

// non-resizeable, hidden dimension
template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_sparse(Data& data, int2type<-1>*)
{
   fill_sparse_from_sparse(this->top().set_option((SparseRepresentation<True>*)0), data, data.max_input_dim());
}

template <typename Input, typename Data, typename Serialized> inline
void resize_and_fill_matrix(Input& src, Data& data, Serialized& serialized)
{
   const int r=src.size();
   if (r) {
      const int c=src.set_option((LookForward<True>*)0)->begin_list((typename Serialized::value_type*)0).dim();
      data.clear(r,c);
      fill_dense_from_dense(src,serialized);
   } else {
      data.clear();
      src.finish();
   }
}

// fully resizeable
template <typename Input>
template <typename Data, typename Serialized>
void GenericInputImpl<Input>::retrieve_matrix(Data& data, Serialized& serialized, int2type<2>*)
{
   resize_and_fill_matrix(this->top().begin_list(&serialized).set_option((void*)0), data, serialized);
}

// resizable via serialized
template <typename Input>
template <typename Data, typename Serialized>
void GenericInputImpl<Input>::retrieve_matrix(Data&, Serialized& serialized, int2type<1>*)
{
   resize_and_fill_dense_from_dense(this->top().begin_list(&serialized).set_option((void*)0), serialized);
}

// non-resizeable
template <typename Input>
template <typename Data, typename Serialized>
void GenericInputImpl<Input>::retrieve_matrix(Data&, Serialized& serialized, int2type<0>*)
{
   check_and_fill_dense_from_dense(this->top().begin_list(&serialized).set_option((void*)0), serialized);
}

template <typename T, typename CursorRef>
class composite_reader {
protected:
   alias<CursorRef> cursor;
   typedef typename deref<CursorRef>::type cursor_type;

public:
   typedef typename deref<T>::type value_type;

   composite_reader(typename alias<CursorRef>::arg_type cursor_arg) : cursor(cursor_arg) { }

   composite_reader<void,void>& operator<< (typename attrib<T>::plus_ref elem)
   {
      typename attrib<cursor_type>::plus_ref c=cursor;
      if (c.at_end()) {
	 operations::clear<value_type> clear;
	 clear.assign(const_cast<value_type&>(elem));
      } else {
	 c >> const_cast<value_type&>(elem);
	 c.finish();
      }
      return reinterpret_cast<composite_reader<void,void>&>(*this);
   }
};

template <>
class composite_reader<void,void> { };

template <typename Car, typename Cdr, typename CursorRef>
class composite_reader< cons<Car,Cdr>, CursorRef> {
protected:
   alias<CursorRef> cursor;
   typedef typename deref<CursorRef>::type cursor_type;
public:
   typedef typename deref<Car>::type value_type;

   composite_reader(typename alias<CursorRef>::arg_type cursor_arg) : cursor(cursor_arg) { }

   composite_reader<Cdr, CursorRef>& operator<< (typename attrib<Car>::plus_ref elem)
   {
      typename attrib<cursor_type>::plus_ref c=cursor;
      if (c.at_end()) {
	 operations::clear<value_type> clear;
	 clear.assign(const_cast<value_type&>(elem));
      } else {
	 c >> const_cast<value_type&>(elem);
      }
      return reinterpret_cast<composite_reader<Cdr, CursorRef>&>(*this);
   }
};

template <typename Input>
template <typename Data>
void GenericInputImpl<Input>::retrieve_composite(Data& data)
{
   typedef typename Input::template composite_cursor<Data>::type cursor_type;
   cursor_type c=this->top().begin_composite(&data);
   composite_reader<typename object_traits<Data>::elements, typename attrib<cursor_type>::plus_ref> r(c);
   object_traits<Data>::visit_elements(data, r);
}

template <typename Output>
class GenericOutput {
public:
   Output& top() { return static_cast<Output&>(*this); }
   Output& top() const { return static_cast<Output&>(const_cast<GenericOutput&>(*this)); }
};

namespace io_test {

nothing& operator<< (const fallback&, const fallback&);

template <typename Output, typename Data>
struct has_generic_output_operator {
   static GenericOutput<Output>& output();
   static const Data& data();
   struct helper {
      derivation::yes Test(Output&);
      derivation::no Test(nothing&);
   };
   static const bool answer= sizeof(helper().Test( output() << data() )) == sizeof(derivation::yes);
};

} // end namespace io_test

template <typename Output>
class GenericOutputImpl : public GenericOutput<Output> {
public:
   typedef GenericOutputImpl generic_type;

   template <typename Data>
   Output& operator<< (const Data& data)
   {
      typedef typename Concrete<Data>::type data_type;
      dispatch_store(Concrete<Data>::get(data),
		     (bool2type< io_test::has_generic_output_operator<Output,data_type>::answer >*)0,
		     (function_argument<typename object_traits<data_type>::serialized>*)0);
      return this->top();
   }

protected:
   template <typename Data>
   void dispatch_store(const Data& data, False*, function_argument<void>*)
   {
      // no generic output operator found, no special serialization
      dispatch_store(data,
		     (typename object_traits<Data>::model*)0);
   }

   template <typename Data, typename Serialized>
   void dispatch_store(const Data& data, False*, function_argument<Serialized>*)
   {
      this->top() << object_traits<Data>::serialize(data);
   }

   template <typename Data, typename Serialized>
   void dispatch_store(const Data& data, True*, function_argument<Serialized>*)
   {
      static_cast<GenericOutput<Output>&>(*this) << data;
   }

   template <typename Data>
   void dispatch_store(const Data& data, is_scalar*)
   {
      this->top().fallback(data);
   }

   template <typename Data>
   void dispatch_store(const Data& data, is_container*)
   {
      dispatch_store(data,
		     (int2type<object_traits<Data>::dimension>*)0);
   }

   template <typename Data>
   void dispatch_store(const Data& data, int2type<1>*)
   {
      store_container(data,
		      (bool2type<check_container_feature<Data, sparse>::answer>*)0
		     );
   }

   template <typename Data>
   void store_container(const Data& data, False*)
   {
      store_list(data);
   }

   template <typename Data>
   void store_container(const Data& data, True*)
   {
      if (this->top().prefer_sparse_representation(data))
	 store_sparse(data);
      else
	 store_list(data);
   }

   template <typename Data>
   void dispatch_store(const Data& data, is_composite*)
   {
      store_composite(data);
   }

   template <typename Data>
   bool prefer_sparse_representation(const Data& data) const
   {
      return object_traits<Data>::IO_hide_dim || data.size()*2 < data.dim();
   }

public:
   template <typename Data>
   void store_list(const Data& data)
   {
      this->template store_list_as<Data>(data);
   }

   template <typename Data>
   void store_sparse(const Data& data)
   {
      this->template store_sparse_as<Data>(data);
   }

   template <typename Data>
   void store_composite(const Data& data);

   template <typename Masquerade, typename Data>
   void store_list_as(const Data& data);

   template <typename Masquerade, typename Data>
   void store_sparse_as(const Data& data);
};

template <typename Output>
template <typename Masquerade, typename Data>
void GenericOutputImpl<Output>::store_list_as(const Data& data)
{
   typedef typename Output::template list_cursor<Masquerade>::type cursor_type;
   cursor_type c=this->top().begin_list(reinterpret_cast<const Masquerade*>(&data));
   for (typename ensure_features<Data, cons<dense, end_sensitive> >::const_iterator
	   src=ensure(data, (cons<dense, end_sensitive>*)0).begin();
	!src.at_end(); ++src)
      c << *src;
   c.finish();
}

template <typename Iterator>
class indexed_pair : public Iterator {
protected:
   indexed_pair();
   ~indexed_pair();
};

template <typename Iterator>
struct spec_object_traits< indexed_pair<Iterator> >
   : spec_object_traits<is_composite> {
   typedef cons<int, typename iterator_traits<Iterator>::reference> elements;
   template <typename Visitor>
   static void visit_elements(const indexed_pair<Iterator>& it, Visitor& v)
   {
      v << it.index() << *it;
   }
};

template <typename Output>
template <typename Masquerade, typename Data>
void GenericOutputImpl<Output>::store_sparse_as(const Data& data)
{
   typedef typename Output::template sparse_cursor<Masquerade>::type cursor_type;
   cursor_type c=this->top().begin_sparse(reinterpret_cast<const Masquerade*>(&data));
   for (typename Data::const_iterator src=data.begin();  !src.at_end(); ++src)
      c << src;
   c.finish();
}

template <typename T, typename CursorRef>
class composite_writer {
protected:
   alias<CursorRef> cursor;
   typedef typename deref<CursorRef>::type cursor_type;
public:
   composite_writer(typename alias<CursorRef>::arg_type cursor_arg) : cursor(cursor_arg) { }

   composite_writer<void,void>& operator<< (typename attrib<T>::plus_const_ref elem)
   {
      typename attrib<cursor_type>::plus_ref c=cursor;
      c << elem;
      c.finish();
      return reinterpret_cast<composite_writer<void,void>&>(*this);
   }
};

template <>
class composite_writer<void,void> { };

template <typename Car, typename Cdr, typename CursorRef>
class composite_writer< cons<Car,Cdr>, CursorRef> {
protected:
   alias<CursorRef> cursor;
   typedef typename deref<CursorRef>::type cursor_type;
public:
   composite_writer(typename alias<CursorRef>::arg_type cursor_arg) : cursor(cursor_arg) { }

   composite_writer<Cdr, CursorRef>& operator<< (typename attrib<Car>::plus_const_ref elem)
   {
      typename attrib<cursor_type>::plus_ref c=cursor;
      c << elem;
      return reinterpret_cast<composite_writer<Cdr, CursorRef>&>(*this);
   }
};

template <typename Output>
template <typename Data>
void GenericOutputImpl<Output>::store_composite(const Data& data)
{
   typedef typename Output::template composite_cursor<Data>::type cursor_type;
   cursor_type c=this->top().begin_composite(&data);
   composite_writer<typename object_traits<Data>::elements, typename attrib<cursor_type>::plus_ref> w(c);
   object_traits<Data>::visit_elements(data, w);
}

template <typename Output>
Output& operator<< (GenericOutput<Output>& os, const nothing&)
{
   return os.top();
}

template <typename Output, typename Data> inline
Output& operator<< (GenericOutput<Output>& os, const ignore<Data,nothing>&)
{
   return os.top();
}

template <typename Output, typename Data, typename Expected> inline
Output& operator<< (GenericOutput<Output>& os, const ignore<Data,Expected>&)
{
   operations::clear<Expected> dummy;
   return os.top() << dummy();
}

template <typename Input>
Input& operator>> (GenericInput<Input>& is, const nothing&)
{
   return is.top();
}

template <typename Input, typename Data, typename Expected> inline
Input& operator>> (GenericInput<Input>& is, ignore<Data,Expected>&)
{
   return is.top();
}

template <typename Container>
class IO_Array : public Container {
protected:
   IO_Array();
   ~IO_Array();

   template <typename Output>
   void output(Output& os) const
   {
      os.template store_list_as<IO_Array>(static_cast<const Container&>(*this));
   }
public:
   template <typename Output> friend
   Output& operator<< (GenericOutput<Output>& os, const IO_Array& x)
   {
      x.output(os.top());
      return os.top();
   }
};

template <typename Container>
struct redirect_object_traits< IO_Array<Container> > : object_traits<Container> {
   static const IO_separator_kind IO_separator=IO_sep_containers;
};

template <typename Container>
class IO_List : public Container {
protected:
   IO_List();
   ~IO_List();

   template <typename Output>
   void output(Output& os) const
   {
      os.template store_list_as<IO_List>(static_cast<const Container&>(*this));
   }
public:
   template <typename Output> friend
   Output& operator<< (GenericOutput<Output>& os, const IO_List& x)
   {
      x.output(os.top());
      return os.top();
   }
};

template <typename Container>
struct redirect_object_traits< IO_List<Container> > : object_traits<Container> {
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};

template <typename Container>
class IO_Sparse : public ensure_features<Container, pure_sparse>::container {
protected:
   IO_Sparse();
   ~IO_Sparse();

   template <typename Output>
   void output(Output& os) const
   {
      os.template store_sparse_as<IO_Sparse>(static_cast<const typename ensure_features<Container, pure_sparse>::container&>(*this));
   }
public:
   template <typename Output> friend
   Output& operator<< (GenericOutput<Output>& os, const IO_Sparse& x)
   {
      x.output(os.top());
      return os.top();
   }
};

template <typename Container>
struct redirect_object_traits< IO_Sparse<Container> > : object_traits<Container> { };

template <typename Container>
struct check_container_feature<IO_Sparse<Container>, pure_sparse> : True { };

template <typename Container> inline
const IO_Array<Container>& as_array(const Container& c)
{
   return reinterpret_cast<const IO_Array<Container>&>(c);
}

template <typename Container> inline
const IO_List<Container>& as_list(const Container& c)
{
   return reinterpret_cast<const IO_List<Container>&>(c);
}

template <typename Container> inline
const IO_Sparse<Container>& as_sparse(const Container& c)
{
   return reinterpret_cast<const IO_Sparse<Container>&>(c);
}

} // end namespace pm

namespace polymake {
   using pm::GenericInput;
   using pm::GenericOutput;
   using pm::as_array;
   using pm::as_list;
   using pm::as_sparse;
}

#ifndef _POLYMAKE_OSTREAM_WRAPPER_H
#  include <ostream_wrapper.h>
#endif

#endif // _POLYMAKE_GENERIC_IO_H

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