/* 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_LIST_MATRIX_H
#define _POLYMAKE_LIST_MATRIX_H "$Project: polymake $$Id: ListMatrix.h,v 1.18 2006/03/09 16:21:35 gawrilow Exp $"

#include <list>

#ifndef _POLYMAKE_SELECTED_SUBSET_H
#  include <SelectedSubset.h>
#endif
#ifndef _POLYMAKE_GENERIC_MATRIX_H
#  include <GenericMatrix.h>
#endif
#ifndef _POLYMAKE_ARRAY_H
#  include <Array.h>
#endif

namespace pm {

template <typename _Vector>
class ListMatrix : public GenericMatrix< ListMatrix<_Vector>, typename _Vector::element_type> {
protected:
   typedef std::list<_Vector> row_list;
   row_list R;
   int dimr, dimc;

   template <typename Iterator>
   void _copy(Iterator src, False*)
   {
      for (int i=0; i<dimr; ++i) {
	 Iterator src_next=src;
	 std::advance(src_next,dimc);
	 R.push_back(_Vector(dimc, make_iterator_range(src,src_next)));
	 src=src_next;
      }
   }

   template <typename Iterator>
   void _copy(Iterator src, True*)
   {
      for (int i=0; i<dimr; ++i, ++src)
	 R.push_back(_Vector(*src));
   }

public:
   typedef typename _Vector::value_type value_type;
   typedef typename _Vector::reference reference;
   typedef typename _Vector::const_reference const_reference;
   typedef typename _Vector::element_type element_type;

   typedef ListMatrix persistent_type;

   ListMatrix() : dimr(0), dimc(0) { }

   ListMatrix(int m, int n)
      : R(m, zero_vector<element_type>(n)), dimr(m), dimc(n) { }

   ListMatrix(int m, int n, typename function_argument<element_type>::type init)
      : R(m, same_element_vector(init,n)), dimr(m), dimc(n) { }

   template <typename Iterator>
   ListMatrix(int m, int n, Iterator src)
      : dimr(m), dimc(n)
   {
      _copy(src, (bool2type<object_traits<_Vector>::total_dimension ==
		            object_traits<typename iterator_traits<Iterator>::value_type>::total_dimension>*)0);
   }

   template <typename Matrix2>
   ListMatrix(const GenericMatrix<Matrix2,element_type>& M)
      : dimr(M.rows()), dimc(M.cols())
   {
      _copy(pm::rows(M).begin(), (True*)0);
   }

   template <typename Matrix2, typename E2>
   explicit ListMatrix(const GenericMatrix<Matrix2,E2>& M)
      : dimr(M.rows()), dimc(M.cols())
   {
      _copy(pm::rows(M).begin(), (True*)0);
   }

private:
   template <typename Input>
   void input(Input& is)
   {
      is.template retrieve_list_as< array_traits<_Vector> >(R);
      if ((dimr=R.size())) dimc=R.front().dim();
   }

public:
   template <typename Input> friend
   Input& operator>> (GenericInput<Input>& is, ListMatrix& M)
   {
      M.input(is.top());
      return is.top();
   }

   ListMatrix& operator= (const ListMatrix& M)
   {
      assign(M);
      return *this;
   }

   using GenericMatrix<ListMatrix>::operator=;

   void swap(ListMatrix& M)
   {
      R.swap(M.R);
      std::swap(dimr,M.dimr);
      std::swap(dimc,M.dimc);
   }

   friend void relocate(ListMatrix* from, ListMatrix* to)
   {
      pm::relocate(&from->R, &to->R);
      to->dimr=from->dimr;
      to->dimc=from->dimc;
   }

   void resize(int m, int n)
   {
      for (; dimr>m; --dimr) R.pop_back();

      if (dimc != n) {
	 for (typename Entire<row_list>::iterator r=entire(R); !r.at_end(); ++r)
	    r->resize(n);
	 dimc=n;
      }

      for (; dimr<m; ++dimr) R.push_back(zero_vector<element_type>(dimc));
   }

   void clear() { dimr=dimc=0; R.clear(); }

   int rows() const { return dimr; }
   int cols() const { return dimc; }

   template <typename Matrix2>
   ListMatrix& operator/= (const GenericMatrix<Matrix2,element_type>& M)
   {
      if (!this->rows())
	 dimc=M.cols();
      else
	 DIMENSION_CHECK((this->cols() != M.cols()), "append_rows - column dimensions mismatch");
      for (typename Entire< Rows<Matrix2> >::const_iterator r=entire(pm::rows(M)); !r.at_end(); ++r)
	 R.push_back(*r);
      dimr+=M.rows();
      return *this;
   }

   template <typename Vector2>
   ListMatrix& operator/= (const GenericVector<Vector2,element_type>& v)
   {
      if (!this->rows())
	 dimc=v.dim();
      else
	 DIMENSION_CHECK((this->cols() != v.dim()), "append_row - column dimensions mismatch");
      R.push_back(v.top());
      ++dimr;
      return *this;
   }

   template <typename Matrix2>
   ListMatrix& operator|= (const GenericMatrix<Matrix2,element_type>& M)
   {
      DIMENSION_CHECK((this->rows() != M.rows()), "append_cols - row dimensions mismatch");
      typename Rows<Matrix2>::const_iterator r=pm::rows(M).begin();
      for (typename Entire<row_list>::iterator myr=entire(R); !myr.at_end(); ++myr, ++r)
	 *myr |= *r;
      dimc+=M.cols();
      return *this;
   }

   template <typename Vector2>
   ListMatrix& operator|= (const GenericVector<Vector2,element_type>& v)
   {
      DIMENSION_CHECK((this->rows() != v.dim()), "append_col - column dimensions mismatch");
      typename Vector2::const_iterator e=v.top().begin();
      for (typename Entire<row_list>::iterator myr=entire(R); !myr.at_end(); ++myr, ++e)
	 *myr |= *e;
      ++dimc;
      return *this;
   }

   template <typename Vector2>
   typename row_list::iterator
   insert_row(const typename row_list::iterator& where, const GenericVector<Vector2>& v)
   {
      if (!this->rows())
	 dimc=v.dim();
      else
	 DIMENSION_CHECK((this->cols() != v.dim()), "insert_row - column dimensions mismatch");
      ++dimr;
      return R.insert(where,v.top());
   }

   void delete_row(const typename row_list::iterator& where)
   {
      --dimr;
      R.erase(where);
   }
protected:
   friend class GenericMatrix<ListMatrix>;
   friend class Rows<ListMatrix>;
   friend class Cols<ListMatrix>;

   void assign(const GenericMatrix<ListMatrix>& M)
   {
      dimr=M.top().dimr;  dimc=M.top().dimc;  R=M.top().R;
   }

   template <typename Matrix2>
   void assign(const GenericMatrix<Matrix2>& M)
   {
      int m=M.rows(); dimc=M.cols();
      for (; dimr>m; --dimr) R.pop_back();

      typename Rows<Matrix2>::const_iterator r=pm::rows(M).begin();
      for (typename Entire<row_list>::iterator myr=entire(R); !myr.at_end(); ++myr, ++r)
	 *myr=*r;

      for (; dimr<m; ++dimr, ++r) R.push_back(*r);
   }
};

template <typename _Vector>
struct check_container_feature<ListMatrix<_Vector>, sparse>
   : check_container_feature<_Vector, sparse> { };

template <typename _Vector>
struct check_container_feature<ListMatrix<_Vector>, pure_sparse>
   : check_container_feature<_Vector, pure_sparse> { };

template <typename _Vector>
class Rows< ListMatrix<_Vector> >
   : public redirected_container< Rows< ListMatrix<_Vector> >,
               cons< Container< std::list<_Vector> >,
		     Hidden< ListMatrix<_Vector> > >
            > {
   typedef redirected_container<Rows> _super;
protected:
   Rows();
   ~Rows();
public:
   typename _super::container& get_container() { return this->hidden().R; }
   const typename _super::container& get_container() const { return this->hidden().R; }
   int size() const { return this->hidden().dimr; }
   void resize(int n) { this->hidden().resize(n, this->hidden().dimc); }
};

template <typename _Vector> class comb_iterator;

template <typename _Vector, bool _is_sparse=check_container_ref_feature<_Vector,sparse>::answer>
class CombVectorBase
   : public modified_container_impl< CombVectorBase<_Vector,_is_sparse>,
	       cons< Container< Array<typename container_traits<_Vector>::iterator> >,
		     Accessor< BuildUnary<operations::extra_deref> > >
            > {
   typedef modified_container_impl<CombVectorBase> _super;
   friend class comb_iterator<_Vector>;
   template <typename, bool> friend class CombVectorBase;
protected:
   typename _super::container it_array;
   int index;

   typedef typename inherit_const<CombVectorBase<typename deref<_Vector>::type, _is_sparse>, _Vector>::type nonconst_arg;
public:
   typename _super::container& get_container() { return it_array; }
   const typename _super::container& get_container() const { return it_array; }

   CombVectorBase() { }

   CombVectorBase(nonconst_arg& cv)
      : it_array(reinterpret_cast<const typename _super::container&>(cv.it_array)),
	index(cv.index) { }

   CombVectorBase& operator= (nonconst_arg& cv)
   {
      it_array=reinterpret_cast<const typename _super::container&>(cv.it_array);
      index=cv.index;
      return *this;
   }

   template <typename Iterator>
   CombVectorBase(int n, int index_arg, Iterator src)
      : it_array(n), index(index_arg)
   {
      if (index==0)
	 for (typename Entire<typename _super::container>::iterator it=entire(it_array); !it.at_end(); ++it, ++src)
	    *it=src->begin();
      else
	 for (typename Entire<typename _super::container>::iterator it=entire(it_array); !it.at_end(); ++it, ++src)
	    *it=src->end();
   }

protected:
   void incr()
   {
      for (typename Entire<typename _super::container>::iterator it=entire(it_array); !it.at_end(); ++it)
	 ++(*it);
      ++index;
   }
};

template <typename Iterator>
class sparse_comb_filter {
public:
   typedef Iterator argument_type;
   typedef bool result_type;

   sparse_comb_filter(int index_arg) : index(index_arg) { }

   bool operator() (const Iterator& it) const
   {
      return !it.at_end() && it.index()==index;
   }
protected:
   int index;
};

template <typename _Vector>
class CombVector_helper
   : public modified_container_impl< CombVector_helper<_Vector>,
	       cons< Container< Array< std::pair<typename container_traits<_Vector>::iterator, _Vector*> > >,
	       cons< Accessor< operations::composed11<BuildUnary<operations::take_first>,
						      sparse_comb_filter<typename container_traits<_Vector>::iterator> > >,
	       cons< Modifier< unary_predicate_selector_modifier >,
	       cons< ExpectedFeatures< indexed >,
		     Hidden< CombVectorBase<_Vector> > > > > >
            > {
   typedef modified_container_impl<CombVector_helper> _super;
public:
   typename _super::container& get_container() { return this->hidden().it_array; }
   const typename _super::container& get_container() const { return this->hidden().it_array; }
   typename _super::accessor get_accessor() const
   {
      return sparse_comb_filter<typename container_traits<_Vector>::iterator>(this->hidden().index);
   }
};

template <typename _Vector>
class CombVectorBase<_Vector, true>
   : public modified_container_impl< CombVectorBase<_Vector, true>,
	       cons< Container< CombVector_helper<_Vector> >,
		     Accessor< operations::composed11<BuildUnary<operations::take_first>, BuildUnary<operations::extra_deref> > > >
            > {
   typedef modified_container_impl<CombVectorBase> _super;
protected:
   typedef typename _super::container::container it_container;
   it_container it_array;
   int index;

   typedef typename inherit_const<CombVectorBase<typename deref<_Vector>::type, true>, _Vector>::type nonconst_arg;

   friend class CombVector_helper<_Vector>;
   friend class comb_iterator<_Vector>;
   template <typename,bool> friend class CombVectorBase;
public:
   typename _super::container& get_container()
   {
      return reinterpret_cast<typename _super::container&>(*this);
   }
   const typename _super::container& get_container() const
   {
      return reinterpret_cast<const typename _super::container&>(*this);
   }

   CombVectorBase() { }

   CombVectorBase(nonconst_arg& cv)
      : it_array(reinterpret_cast<const it_container&>(cv.it_array)),
	index(cv.index) { }

   CombVectorBase& operator= (nonconst_arg& cv)
   {
      it_array=reinterpret_cast<const it_container&>(cv.it_array);
      index=cv.index;
      return *this;
   }

   template <typename Iterator>
   CombVectorBase(int n, int index_arg, Iterator src)
      : it_array(n), index(index_arg)
   {
      if (index==0)
	 for (typename Entire<it_container>::iterator it=entire(it_array); !it.at_end(); ++it, ++src)
	    it->first=(it->second=&*src)->begin();
      else
	 for (typename Entire<it_container>::iterator it=entire(it_array); !it.at_end(); ++it, ++src)
	    it->first=(it->second=&*src)->end();
   }

   void insert(const typename _super::iterator&, int i, const typename _Vector::element_type& d)
   {
      it_array[i].second->insert(it_array[i].first, index, d);
   }

   void erase(const typename _super::iterator& pos)
   {
      int i=pos.index();
      it_array[i].second->erase(it_array[i].first);
   }
protected:
   void incr()
   {
      for (typename Entire<typename _super::container>::iterator it=entire(get_container()); !it.at_end(); ++it)
	 ++it->first;
      ++index;
   }
};

template <typename _Vector>
class CombVector
   : public CombVectorBase<_Vector>,
     public GenericVector< CombVector<_Vector>, typename _Vector::element_type> {
protected:
   CombVector();
   ~CombVector();
public:
   CombVector& operator= (const CombVector& v)
   {
      return CombVector::generic_type::operator=(v);
   }
   using CombVector::generic_type::operator=;

   int dim() const { return this->it_array.size(); }
};

template <typename _Vector>
class comb_iterator {
public:
   typedef CombVector<_Vector> value_type;
   typedef typename inherit_const<value_type, _Vector>::type& reference;
   typedef typename inherit_const<value_type, _Vector>::type* pointer;
   typedef forward_iterator_tag iterator_category;
   typedef ptrdiff_t difference_type;
   typedef comb_iterator<typename deref<_Vector>::type> iterator;
   typedef comb_iterator<const typename deref<_Vector>::type> const_iterator;

   comb_iterator() { }
   comb_iterator(const iterator& it)
      : cv(it.value) { }

   comb_iterator& operator= (const iterator& it)
   {
      cv=it.cv;
      return *this;
   }

   template <typename Iterator>
   comb_iterator(int m, int n, int index_arg, Iterator src)
      : cv(m,index_arg,src), _last(n) { }

   reference operator* () const
   {
      return const_cast<reference>(static_cast<const value_type&>(cv));
   }
   pointer operator-> () const
   {
      return const_cast<pointer>(&static_cast<const value_type&>(cv));
   }

   comb_iterator& operator++ () { cv.incr(); return *this; }
   const comb_iterator operator++ (int) { comb_iterator copy=*this; operator++(); return copy; }

   bool operator== (const iterator& it) const { return index()==it.index(); }
   bool operator== (typename assign_const<const_iterator, !identical<iterator,const_iterator>::answer>::type& it) { return index()==it.index(); }
   bool operator!= (const iterator& it) const { return !operator==(it); }

   bool at_end() const { return index()==_last; }
   int index() const { return cv.index; }
protected:
   CombVectorBase<_Vector> cv;
   int _last;
};

template <typename _Vector>
struct check_iterator_feature<comb_iterator<_Vector>, end_sensitive> : True { };
template <typename _Vector>
struct check_iterator_feature<comb_iterator<_Vector>, indexed> : True { };

template <typename _Vector>
struct check_container_feature<CombVector<_Vector>, sparse>
   : check_container_ref_feature<_Vector, sparse> { };

template <typename _Vector>
struct check_container_feature<CombVector<_Vector>, pure_sparse>
   : check_container_ref_feature<_Vector, pure_sparse> { };

template <typename _Vector>
class Cols< ListMatrix<_Vector> > {
protected:
   Cols();
   ~Cols();

   typedef ListMatrix<_Vector> hidden_type;
   hidden_type& hidden() { return reinterpret_cast<hidden_type&>(*this); }
   const hidden_type& hidden() const { return reinterpret_cast<const hidden_type&>(*this); }
public:
   typedef comb_iterator<_Vector> iterator;
   typedef comb_iterator<const _Vector> const_iterator;
   typedef CombVector<_Vector> value_type;
   typedef typename iterator::reference reference;
   typedef typename const_iterator::reference const_reference;

   iterator begin()
   {
      return iterator(hidden().dimr, hidden().dimc, 0, hidden().R.begin());
   }
   iterator end()
   {
      return iterator(hidden().dimr, hidden().dimc, hidden().dimc, hidden().R.begin());
   }
   const_iterator begin() const
   {
      return const_iterator(hidden().dimr, hidden().dimc, 0, hidden().R.begin());
   }
   const_iterator end() const
   {
      return const_iterator(hidden().dimr, hidden().dimc, hidden().dimc, hidden().R.begin());
   }

   typename iterator::value_type front()
   {
      return typename iterator::value_type(hidden().dimr, 0, hidden().R.begin());
   }
   typename const_iterator::value_type front() const
   {
      return typename const_iterator::value_type(hidden().dimr, 0, hidden().R.begin());
   }

   int size() const { return hidden().dimc; }
   bool empty() const { return size()==0; }
   void resize(int n) { hidden().resize(hidden().dimr, n); }
};

} // end namespace pm

namespace polymake {
   using pm::ListMatrix;
}

#endif // _POLYMAKE_LIST_MATRIX_H

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