/* Copyright (c) 1997-2007
   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 7563 2007-01-16 12:07:34Z gawrilow $"

#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, typename Category=typename container_traits<Vector>::category>
class ListMatrixCols;

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)>());
   }

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

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

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)
   {
      const int add_rows=M.rows();
      if (add_rows) {
	 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+=add_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)
   {
      const int add_cols=M.cols();
      if (add_cols) {
	 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+=add_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>;
   template <typename,typename> friend class ListMatrixCols;

   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> >,
				  list( Container< std::list<Vector> >,
					MasqueradedTop ) > {
   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, int _is_rev> class comb_iterator;
template <typename Vector, int _is_rev> class CombVector;
template <typename Vector, int _is_rev, bool _is_sparse=check_container_ref_feature<Vector,sparse>::value>
class CombVector_helper;

template <typename Vector>
class CombVector_helper<Vector,2,false> {	// !reversed, !sparse
protected:
   typedef Array<typename container_traits<Vector>::iterator> it_container;

   template <typename Iterator>
   void init_begin(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 *it=src->begin();
   }
   template <typename Iterator>
   void init_end(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 *it=src->end();
   }
};

template <typename Vector>
class CombVector_helper<Vector,3,false> {	// reversed, !sparse
protected:
   typedef Array<typename container_traits<Vector>::reverse_iterator> it_container;

   template <typename Iterator>
   void init_begin(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 *it=src->rbegin();
   }
   template <typename Iterator>
   void init_end(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 *it=src->rend();
   }
};

template <typename Vector, int _is_rev>
class CombVector_helper<Vector, _is_rev, false>
   : public CombVector_helper<Vector, _is_rev+2, false> {
protected:
   typedef typename CombVector_helper<Vector, _is_rev+2, false>::it_container it_container;

   void incr(it_container& itc, int& index)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it)
	 ++(*it);
      !_is_rev ? ++index : --index;
   }
public:
   typedef cons< Container< it_container >,
		 Operation< BuildUnary<operations::extra_deref> > >
      manip_traits;

   it_container& get_container() { return static_cast<CombVector<Vector,_is_rev>*>(this)->it_array; }
   const it_container& get_container() const { return static_cast<const CombVector<Vector,_is_rev>*>(this)->it_array; }
};

template <typename Vector>
class CombVector_helper<Vector,2,true> {	// !reversed, sparse
protected:
   typedef Array< std::pair<typename container_traits<Vector>::iterator, Vector*> > it_container;

   template <typename Iterator>
   void init_begin(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 it->first=(it->second=&*src)->begin();
   }
   template <typename Iterator>
   void init_end(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 it->first=(it->second=&*src)->end();
   }
};

template <typename Vector>
class CombVector_helper<Vector,3,true> {	// reversed, sparse
protected:
   typedef Array< std::pair<typename container_traits<Vector>::reverse_iterator, Vector*> > it_container;

   template <typename Iterator>
   void init_begin(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 it->first=(it->second=&*src)->rbegin();
   }
   template <typename Iterator>
   void init_end(it_container& itc, Iterator& src)
   {
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it, ++src)
	 it->first=(it->second=&*src)->rend();
   }
};

template <typename Vector, int _is_rev>
class CombVector_helper<Vector, _is_rev, true>
   : public CombVector_helper<Vector, _is_rev+2, true> {
protected:
   typedef typename CombVector_helper<Vector, _is_rev+2, true>::it_container it_container;

   class it_filter {
   public:
      typedef typename it_container::value_type::first_type argument_type;
      typedef bool result_type;

      it_filter(int index_arg=0) : index(index_arg) {}

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

   static it_container& get_c(CombVector<Vector,_is_rev>& cv) { return cv.it_array; }
   static const it_container& get_c(const CombVector<Vector,_is_rev>& cv) { return cv.it_array; }
   static int get_i(const CombVector<Vector,_is_rev>& cv) { return cv.index; }

   class intermediate
      : public modified_container_impl< intermediate,
					list( Container< it_container >,
					      Operation< operations::composed11<BuildUnary<operations::take_first>,
					                                        it_filter> >,
					      IteratorConstructor< unary_predicate_selector_constructor >,
					      ExpectedFeatures< indexed >,
					      Hidden< CombVector<Vector,_is_rev> > ) > {
      typedef modified_container_impl<intermediate> _super;
   public:
      it_container& get_container() { return get_c(this->hidden()); }
      const it_container& get_container() const { return get_c(this->hidden()); }
      typename _super::operation get_operation() const { return it_filter(get_i(this->hidden())); }
   };

   void incr(it_container& itc, int& index)
   {
      const it_filter cf(index);
      for (typename Entire<it_container>::iterator it=entire(itc); !it.at_end(); ++it)
	 if (cf(it->first)) ++it->first;
      !_is_rev ? ++index : --index;
   }

public:
   typedef cons< Container< intermediate >,
		 Operation< operations::composed11<BuildUnary<operations::take_first>, 
			                           BuildUnary<operations::extra_deref> > > >
      manip_traits;

   intermediate& get_container() { return reinterpret_cast<intermediate&>(*this); }
   const intermediate& get_container() const { return reinterpret_cast<const intermediate&>(*this); }

   template <typename Iterator>
   void insert(const Iterator&, int i, const typename Vector::element_type& d)
   {
      this->hidden().it_array[i].second->insert(this->hidden().it_array[i].first, this->hidden().index, d);
   }
   template <typename Iterator>
   void erase(const Iterator& pos)
   {
      int i=pos.index();
      this->hidden().it_array[i].second->erase(this->hidden().it_array[i].first);
   }
};

template <typename Vector, int _is_rev>
class CombVector
   : public CombVector_helper<Vector,_is_rev>,
     public modified_container_impl< CombVector<Vector,_is_rev>,
				     typename CombVector_helper<Vector,_is_rev>::manip_traits >,
     public GenericVector< CombVector<Vector,_is_rev>, typename Vector::element_type > {

   typedef modified_container_impl<CombVector> _super;
   typedef CombVector_helper<Vector,_is_rev> _helper;
   friend class comb_iterator<Vector,_is_rev>;
   template <typename, int> friend class CombVector;
   friend class CombVector_helper<Vector,_is_rev>;
protected:
   typename _helper::it_container it_array;
   int index;

   typedef typename inherit_const<CombVector<typename deref<Vector>::type,_is_rev>, Vector>::type nonconst_arg;
public:
   CombVector() {}

   CombVector(const CombVector& cv)
      : it_array(cv.it_array),
	index(cv.index) {}

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

   CombVector& operator= (const CombVector& cv)
   {
      return CombVector::generic_type::operator=(cv);
   }
   using CombVector::generic_type::operator=;

   template <typename Iterator>
   CombVector(int n, Iterator src)
      : it_array(n), index(!_is_rev ? 0 : n-1)
   {
      this->init_begin(it_array, src);
   }

   template <typename Iterator>
   CombVector(int n, maximal<int>, Iterator src)
      : it_array(n), index(!_is_rev ? n : -1)
   {
      this->init_end(it_array, src);
   }

   template <typename Iterator>
   CombVector(int n, int index_arg, Iterator src)
      : it_array(n), index(index_arg)
   {
      for (typename Entire<typename _helper::it_container>::iterator it=entire(it_array); !it.at_end(); ++it, ++src)
	 *it=src->begin()+index;
   }

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

protected:
   void copy(const CombVector& cv)
   {
      it_array=cv.it_array;
      index=cv.index;
   }
   void copy(nonconst_arg& cv)
   {
      it_array=reinterpret_cast<const typename _helper::it_container&>(cv.it_array);
      index=cv.index;
   }
   void incr()
   {
      _helper::incr(it_array, index);
   }
};

template <typename Vector, int _is_rev>
class comb_iterator {
public:
   typedef CombVector<Vector,_is_rev> 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, _is_rev> iterator;
   typedef comb_iterator<const typename deref<Vector>::type, _is_rev> const_iterator;

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

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

   comb_iterator& operator= (typename assign_const<iterator, !identical<iterator,comb_iterator>::value>::type& it)
   {
      cv.copy(it.cv);
      return *this;
   }

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

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

   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>(cv);
   }
   pointer operator-> () const
   {
      return const_cast<pointer>(&cv);
   }

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

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

   bool at_end() const { return index()==_last; }
   int index() const { return cv.index; }
protected:
   value_type cv;
   int _last;
};

template <typename Vector, int _is_rev>
struct check_iterator_feature<comb_iterator<Vector, _is_rev>, end_sensitive> : True {};
template <typename Vector, int _is_rev>
struct check_iterator_feature<comb_iterator<Vector, _is_rev>, indexed> : True {};

template <typename Vector, int _is_rev>
struct check_container_feature<CombVector<Vector, _is_rev>, sparse>
   : check_container_ref_feature<Vector, sparse> {};

template <typename Vector, int _is_rev>
struct check_container_feature<CombVector<Vector, _is_rev>, pure_sparse>
   : check_container_ref_feature<Vector, pure_sparse> {};

template <typename Vector, typename Category>
class ListMatrixCols {
protected:
   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,0> iterator;
   typedef comb_iterator<const Vector,0> const_iterator;
   typedef CombVector<Vector,0> value_type;
   typedef value_type reference;
   typedef CombVector<const Vector,0> const_reference;
   typedef Category container_category;

   iterator begin()
   {
      return iterator(hidden().dimr, hidden().dimc, hidden().R.begin());
   }
   iterator end()
   {
      return iterator(hidden().dimr, hidden().dimc, maximal<int>(), hidden().R.begin());
   }
   const_iterator begin() const
   {
      return const_iterator(hidden().dimr, hidden().dimc, hidden().R.begin());
   }
   const_iterator end() const
   {
      return const_iterator(hidden().dimr, hidden().dimc, maximal<int>(), hidden().R.begin());
   }

   reference front()
   {
      return reference(hidden().dimr, hidden().R.begin());
   }
   const_reference front() const
   {
      return const_reference(hidden().dimr, hidden().R.begin());
   }

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

template <typename Vector>
class ListMatrixCols<Vector, bidirectional_iterator_tag>
   : public ListMatrixCols<Vector, forward_iterator_tag> {
public:
   typedef comb_iterator<Vector,1> reverse_iterator;
   typedef comb_iterator<const Vector,1> const_reverse_iterator;
   typedef bidirectional_iterator_tag container_category;

   reverse_iterator rbegin()
   {
      return reverse_iterator(this->hidden().dimr, this->hidden().dimc, this->hidden().R.begin());
   }
   reverse_iterator rend()
   {
      return reverse_iterator(this->hidden().dimr, this->hidden().dimc, maximal<int>(), this->hidden().R.begin());
   }
   const_reverse_iterator rbegin() const
   {
      return const_reverse_iterator(this->hidden().dimr, this->hidden().dimc, this->hidden().R.begin());
   }
   const_reverse_iterator rend() const
   {
      return reverse_iterator(this->hidden().dimr, this->hidden().dimc, maximal<int>(), this->hidden().R.begin());
   }

   CombVector<Vector,1> back()
   {
      return CombVector<Vector,1>(this->hidden().dimr, this->hidden().R.begin());
   }
   CombVector<const Vector,1> back() const
   {
      return CombVector<const Vector,1>(this->hidden().dimr, this->hidden().R.begin());
   }
};

template <typename Vector>
class ListMatrixCols<Vector, random_access_iterator_tag>
   : public ListMatrixCols<Vector, bidirectional_iterator_tag> {
public:
   typedef random_access_iterator_tag container_category;

   CombVector<Vector,0> operator[] (int c)
   {
      return CombVector<Vector,0>(this->hidden().dimr, c, this->hidden().R.begin());
   }
   CombVector<const Vector,0> operator[] (int c) const
   {
      return CombVector<const Vector,0>(this->hidden().dimr, c, this->hidden().R.begin());
   }
};

template <typename Vector>
class Cols< ListMatrix<Vector> >
   : public ListMatrixCols<Vector> {
protected:
   Cols();
   ~Cols();
};

} // end namespace pm

namespace polymake {
   using pm::ListMatrix;
}

#endif // _POLYMAKE_LIST_MATRIX_H

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