/* 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_SPARSE2D_H
#define _POLYMAKE_SPARSE2D_H "$Project: polymake $$Id: sparse2d.h,v 1.49 2004/06/22 16:22:42 gawrilow Exp $"

#if defined(__GNUC__) && __GNUC_MINOR__<3 && !defined(__APPLE__) && !defined(__COMO__)
#pragma interface
#endif

#ifdef POLY_DEBUG
#  include <sstream>
#endif

#ifndef _POLYMAKE_PLAUSIBLE_CHECKS_H
#  include <plausible_checks.h>
#endif
#ifndef _POLYMAKE_AVL_H
#  include <AVL.h>
#endif
#ifndef _POLYMAKE_TREE_CONTAINERS_H
#  include <tree_containers.h>
#endif
#ifndef _POLYMAKE_SPARSE2D_RULER_H
#  include <sparse2d_ruler.h>
#endif

namespace pm {

namespace sparse2d {

template <typename E>
struct cell {
   typedef E data_type;

   int key;		/// sum of row and column indices
   AVL::Ptr<cell> links[6];
   E data;

   explicit cell(int i) : key(i), data() { }
   template <typename Data>
   cell(int i_arg, const Data& data_arg) : key(i_arg), data(data_arg) { }

   /// don't copy the tree links
   cell(const cell& o) : key(o.key), data(o.data) { }

   data_type& get_data() { return data; }
   const data_type& get_data() const { return data; }

   void* operator new(size_t s) { return raw_alloc::allocate(s); }
   void operator delete(void* p) { if (p) raw_alloc::deallocate(p,sizeof(cell)); }
};

template <>
struct cell<nothing> {
   typedef nothing data_type;

   int key;			/// sum of row and column indices
   AVL::Ptr<cell> links[6];

   explicit cell(int i) : key(i) { }

   /// don't copy the tree links
   cell(const cell& o) : key(o.key) { }

   nothing& get_data()
   {
      return pair<int,nothing>::second;
   }
   const nothing& get_data() const
   {
      return pair<int,nothing>::second;
   }

   void* operator new(size_t s) { return raw_alloc::allocate(s); }
   void operator delete(void* p) { if (p) raw_alloc::deallocate(p,sizeof(cell)); }
};

enum restriction_kind { full, dying, only_rows, only_cols };

template <typename E, bool symmetric=false, restriction_kind restriction=full> class Table;
template <typename Base, bool symmetric, restriction_kind restriction=full> class traits;

template <typename E, bool _row_oriented, bool _symmetric>
class it_traits {
protected:
   int line_index;
public:
   static const bool row_oriented=_row_oriented, symmetric=_symmetric;
   typedef cell<E> Node;
   typedef it_traits<E,(!symmetric && !row_oriented),symmetric> cross_traits;

   AVL::Ptr<Node>& link(Node *n, AVL::link_index X) const {
      const int in_row= symmetric ? n->key > 2*line_index : row_oriented;
      return n->links[X-AVL::L + in_row*3];
   }

   it_traits(int index_arg=0) : line_index(index_arg) { }

   int get_line_index() const { return line_index; }
   const it_traits& get_it_traits() const { return *this; }
};

template <typename E, bool _row_oriented, bool _symmetric, restriction_kind restriction=full>
class traits_base : public it_traits<E,_row_oriented,_symmetric> {
public:
   typedef it_traits<E,_row_oriented,_symmetric> traits_for_iterator;
   typedef typename traits_for_iterator::Node Node;
protected:
   mutable AVL::Ptr<Node> root_links[3];

public:
   static const bool
      symmetric=_symmetric,
      row_oriented=_row_oriented,
      cross_oriented= restriction!=only_rows && restriction!=only_cols ? !symmetric && !row_oriented : row_oriented;

   typedef E data_type;
   typedef AVL::tree< traits<traits_base, symmetric, restriction> > own_tree;
   typedef AVL::tree< traits<traits_base<E,cross_oriented,symmetric,restriction>, symmetric, restriction> > cross_tree;
protected:
   typedef ruler<own_tree, void*> own_ruler;
   typedef ruler<cross_tree, void*> cross_ruler;

   Node* head_node() const
   {
      return reinterpret_cast<Node*>(reinterpret_cast<char*>(const_cast<traits_base*>(this))
				     - (!symmetric & row_oriented)*sizeof(root_links));
   }

   const own_ruler& get_cross_ruler(True*) const
   {
      return own_ruler::reverse_cast(static_cast<const own_tree*>(this), this->line_index);
   }
   own_ruler& get_cross_ruler(True*)
   {
      return own_ruler::reverse_cast(static_cast<own_tree*>(this), this->line_index);
   }
   const cross_ruler& get_cross_ruler(False*) const
   {
      return *reinterpret_cast<const cross_ruler*>(get_cross_ruler((True*)0).prefix());
   }
   cross_ruler& get_cross_ruler(False*)
   {
      return *reinterpret_cast<cross_ruler*>(get_cross_ruler((True*)0).prefix());
   }
   const cross_ruler& get_cross_ruler() const
   {
      return get_cross_ruler((bool2type<symmetric>*)0);
   }
   cross_ruler& get_cross_ruler()
   {
      return get_cross_ruler((bool2type<symmetric>*)0);
   }

   /** @retval <0 first visit of two
                0 first and only visit
	       >0 second visit of two */
   int visit_by_copy(Node* n) const
   {
      if (symmetric)
	 return 2*this->line_index - n->key;
      else
	 return row_oriented ? -1 : 1;
   }
public:
   typedef int arg_type;
   traits_base(int index_arg) : traits_for_iterator(index_arg) { }

   const cross_tree& get_cross_tree(int i) const
   {
      return get_cross_ruler()[i];
   }
   cross_tree& get_cross_tree(int i)
   {
      return get_cross_ruler()[i];
   }
};

template <typename Base, bool symmetric, restriction_kind restriction>
class traits : public Base {
public:
   typedef int key_type;
   typedef BuildBinary<operations::cmp> key_comparator;
   typedef typename Base::Node Node;
protected:
   static key_comparator key_cmp;

   int key(const Node& n) const { return n.key - this->get_line_index(); }

   static void assign(Node&, int) { }

   template <typename Data>
   static void assign(Node& n, const pair<int, Data>& p)
   {
      n.data=p.second;
   }

   template <typename Data>
   static void assign(Node& n, int, const Data& d)
   {
      n.data=d;
   }

   void insert_node_cross(Node *n, int i, True*)
   {
      this->get_cross_tree(i).insert_node(n);
   }
   void insert_node_cross(Node *, int i, False*)
   {
      long& max_cross=reinterpret_cast<long&>(this->get_cross_ruler((True*)0).prefix());
      if (i>=max_cross) max_cross=i+1;
   }

   Node* create_node(int i)
   {
      Node *n=new Node(i + this->get_line_index());
      insert_node_cross(n, i, (bool2type<restriction==full>*)0);
      return n;
   }

   template <typename Data>
   Node* create_node(int i, const Data& data)
   {
      Node *n=new Node(i + this->get_line_index(), data);
      insert_node_cross(n, i, (bool2type<restriction==full>*)0);
      return n;
   }

   template <typename Data>
   Node* create_node(const pair<int, Data>& p)
   {
      return create_node(p.first, p.second);
   }

   Node* create_node(const pair<int, nothing>& p)
   {
      return create_node(p.first);
   }

   void remove_node_cross(Node* n, True*)
   {
      get_cross_tree(n->key - this->get_line_index()).remove_node(n);
   }
   void remove_node_cross(Node*, False*) { }

   void destroy_node(Node* n) {
      remove_node_cross(n, (bool2type<restriction==full>*)0);
      delete n;
   }

   Node* clone_node(Node* n) {
      const int visit=visit_by_copy(n);
      Node *clone=visit<=0 ? new Node(*n) : n->links[1];
      if (visit<0) {
	 clone->links[1]=n->links[1];
	 n->links[1]=clone;
      } else if (visit>0) {
	 n->links[1]=clone->links[1];
      }
      return clone;
   }

   static bool own_node(Node*)
   {
      return restriction != dying || Base::row_oriented;
   }

   int max_size(True*) const
   {
      return this->get_cross_ruler().size();
   }
   int max_size(False*) const
   {
      return reinterpret_cast<const long&>(this->get_cross_ruler((True*)0).prefix());
   }

public:
   traits() { }
   traits(typename Base::arg_type init_arg) : Base(init_arg) { }

   int max_size() const {
      return max_size((bool2type<(restriction!=only_rows && restriction!=only_cols)>*)0);
   }
   const key_comparator& get_comparator() const {
      return key_cmp;
   }

   friend class Table<typename Base::data_type,true,restriction>;
   friend class Table<typename Base::data_type,false,restriction>;
};

template <typename Base, bool symmetric, restriction_kind restriction>
BuildBinary<operations::cmp> traits<Base,symmetric,restriction>::key_cmp;

template <typename Base, restriction_kind restriction>
class traits<Base,true,restriction> : public traits<Base,false,restriction> {
public:
   typedef typename traits<Base,false,restriction>::Node Node;
protected:
   Node* insert_node(Node *n, int i)
   {
      if (i != this->get_line_index())
	 this->get_cross_tree(i).insert_node(n);
      return n;
   }

   Node* create_node(int i)
   {
      return insert_node(new Node(i + this->get_line_index()), i);
   }

   template <typename Data>
   Node* create_node(int i, const Data& data)
   {
      return insert_node(new Node(i + this->get_line_index(), data), i);
   }

   template <typename Data>
   Node* create_node(const pair<int, Data>& p)
   {
      return create_node(p.first, p.second);
   }

   Node* create_node(const pair<int, nothing>& p)
   {
      return create_node(p.first);
   }

   void remove_node_cross(Node* n, True*)
   {
      const int l=this->get_line_index(), i=n->key - l;
      if (i != l) this->get_cross_tree(i).remove_node(n);
   }
   void remove_node_cross(Node*, False*) { }

   void destroy_node(Node* n)
   {
      remove_node_cross(n, (bool2type<restriction==full>*)0);
      delete n;
   }

   bool own_node(Node *n) const
   {
      return restriction==full || n->key >= 2*this->get_line_index();
   }
public:
   traits() { }
   traits(typename Base::arg_type init_arg) : traits<Base,false,restriction>(init_arg) { }
};

template <typename CellRef>
struct cell_accessor {
   typedef typename attrib<CellRef>::plus_ref argument_type;
   typedef typename inherit_ref<typename deref<CellRef>::type::data_type, argument_type>::type result_type;

   result_type operator() (argument_type c) const { return c.get_data(); }
};

template <typename IteratorRef>
struct cell_index_accessor {
   typedef IteratorRef argument_type;
   typedef const int result_type;

   result_type operator() (argument_type it) const {
      return it->key - it.get_line_index();
   }
};

template <typename Iterator> struct cross_direction_helper;

template <typename Traits, AVL::link_index Dir>
struct cross_direction_helper< AVL::tree_iterator<Traits,Dir> > {
   typedef AVL::tree_iterator<typename inherit_const<typename Traits::cross_traits, Traits>::type, Dir> iterator;
};

template <typename Iterator, bool _relaxed> inline
unary_transform_iterator<typename cross_direction_helper<Iterator>::iterator,
			 pair< BuildUnary<cell_accessor>, BuildUnaryIt<cell_index_accessor> >, _relaxed>
cross_direction(const unary_transform_iterator<Iterator, pair< BuildUnary<cell_accessor>, BuildUnaryIt<cell_index_accessor> >,
		                   _relaxed>& it) {
   return typename cross_direction_helper<Iterator>::iterator(it.index(), it.Iterator::operator->());
}

template <typename E, bool symmetric, restriction_kind restriction, template <typename> class MasqueradeLine> class Rows;
template <typename E, bool symmetric, restriction_kind restriction, template <typename> class MasqueradeLine> class Cols;

template <typename E, bool symmetric, restriction_kind restriction>
class Table {
protected:
   static const bool restricted= restriction != full;
   typedef traits<traits_base<E,true,symmetric,restriction>, symmetric,restriction> row_tree_traits;
   typedef traits<traits_base<E,false,symmetric,restriction>, symmetric,restriction> col_tree_traits;
   typedef AVL::tree<row_tree_traits> row_tree_type;
   typedef AVL::tree<col_tree_traits> col_tree_type;
public:
   typedef ruler<row_tree_type, void*> row_ruler;
   typedef ruler<col_tree_type, void*> col_ruler;
protected:
   typedef Table<E,symmetric,dying> restricted_Table;

   row_ruler *R;
   col_ruler *C;

   void _copy(const Table& t)
   {
      R= restriction != only_cols ? row_ruler::construct(*t.R) : 0;
      C= restriction != only_rows ? col_ruler::construct(*t.C) : 0;
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      } else if (restriction == only_rows) {
	 R->prefix()=t.R->prefix();
      } else if (restriction == only_cols) {
	 C->prefix()=t.C->prefix();
      }
   }
public:
   Table()
      : R(row_ruler::construct(0)),
	C(col_ruler::construct(0))
   {
      R->prefix()=C;
      C->prefix()=R;
   }

   Table(const nothing&)
   {
      DIMENSION_CHECK(!restricted, "sparse2d::Table - both dimensions required in unrestricted mode");
      R=0; C=0;
   }

   explicit Table(int n)
      : R(restriction != only_cols ? row_ruler::construct(n) : 0),
	C(restriction != only_rows ? col_ruler::construct(n) : 0)
   {
      DIMENSION_CHECK(!restricted, "sparse2d::Table - both dimensions required in unrestricted mode");
      if (restriction == only_rows)
	 R->prefix()=0;
      else
	 C->prefix()=0;
   }

   Table(int r, int c)
      : R(row_ruler::construct(r)), C(col_ruler::construct(c))
   {
      DIMENSION_CHECK(restricted, "sparse2d::Table - exactly one non-zero dimension allowed in restricted mode");
      R->prefix()=C;
      C->prefix()=R;
   }

   Table(const Table& t)
   {
      _copy(t);
   }
private:
   template <typename _row_ruler, typename _col_ruler>
   static _col_ruler* _take_over(_row_ruler* R, _col_ruler* C)
   {
      C=_col_ruler::construct(reinterpret_cast<const long&>(R->prefix()));
      for (typename Entire<_row_ruler>::iterator t=entire(*R);  !t.at_end();  ++t)
	 for (typename _row_ruler::value_type::iterator e=t->begin(); !e.at_end(); ++e)
	    (*C)[e->key - t->get_line_index()].push_back_node(e.operator->());
      R->prefix()=C;
      C->prefix()=R;
      return C;
   }
public:
   Table(Table<E,symmetric,only_rows>& t)
   {
      if (restriction==only_rows) {
	 _copy(reinterpret_cast<const Table&>(t));
      } else {
	 DIMENSION_CHECK(restricted, "sparse2d::Table - conversion between two restricted modes");
	 R=reinterpret_cast<row_ruler*>(t.R); t.R=0;
	 C=_take_over(R, C);
      }
   }

   Table(Table<E,symmetric,only_cols>& t)
   {
      if (restriction==only_cols) {
	 _copy(reinterpret_cast<const Table&>(t));
      } else {
	 DIMENSION_CHECK(restricted, "sparse2d::Table - conversion between two restricted modes");
	 C=reinterpret_cast<col_ruler*>(t.C); t.C=0;
	 R=_take_over(C,R);
      }
   }

   ~Table()
   {
      if (restriction==full) {
	 reinterpret_cast<restricted_Table*>(this)->~restricted_Table();
      } else {
	 if (restriction==only_cols && C || restriction==dying) col_ruler::destroy(C);
	 if (restriction==only_rows && R || restriction==dying) row_ruler::destroy(R);
      }
   }

   Table& operator= (const Table& t)
   {
      this->~Table();
      new(this) Table(t);
      return *this;
   }

   Table& operator= (Table<E,symmetric,only_rows>& t)
   {
      this->~Table();
      new(this) Table(t);
      return *this;
   }

   Table& operator= (Table<E,symmetric,only_cols>& t)
   {
      this->~Table();
      new(this) Table(t);
      return *this;
   }

   void swap(Table& t)
   {
      std::swap(R,t.R);
      std::swap(C,t.C);
   }

   int rows() const
   {
      return restriction != only_cols ? R->size() : reinterpret_cast<const long&>(C->prefix());
   }
   int cols() const
   {
      return restriction != only_rows ? C->size() : reinterpret_cast<const long&>(R->prefix());
   }

   void clear(int r=0, int c=0)
   {
      if (restriction==full) {
	 reinterpret_cast<restricted_Table*>(this)->clear(r,c);
      } else if (restriction==only_rows) {
	 R=row_ruler::resize_and_clear(R,r);
	 R->prefix()=0;
      } else if (restriction==only_cols) {
	 C=col_ruler::resize_and_clear(C,r);	// not a typo: the second argument must be omitted in this case
	 C->prefix()=0;
      } else {
	 R=row_ruler::resize_and_clear(R,r);
	 C=col_ruler::resize_and_clear(C,c);
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   void resize_rows(int r)
   {
      if (restriction == only_rows && !R) {
	 R=row_ruler::construct(r);
	 R->prefix()=0;
      } else if (restriction == only_cols) {
	 reinterpret_cast<long&>(C->prefix())=r;
      } else {
	 R=row_ruler::resize(R,r);
      }
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   void resize_cols(int c)
   {
      if (restriction == only_cols && !C) {
	 C=col_ruler::construct(c);
	 C->prefix()=0;
      } else if (restriction == only_rows) {
	 reinterpret_cast<long&>(R->prefix())=c;
      } else {
	 C=col_ruler::resize(C,c);
      }
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   void resize(int r, int c) {
      if (!restricted) {
	 R=row_ruler::resize(R,r);
	 C=col_ruler::resize(C,c);
	 R->prefix()=C;
	 C->prefix()=R;
      } else {
	 DIMENSION_CHECK(restricted, "sparse2d::Table::resize - exactly one non-zero dimension allowed in restricted mode");
      }
   }

   /** Remove the empty rows and columns.
       The remaining rows and columns are renumbered without gaps.
   */
   template <typename row_number_consumer, typename col_number_consumer>
   void squeeze(row_number_consumer rnc, col_number_consumer cnc) {
      int r=0, rnew=0, c=0, cnew=0;
      if (restriction != only_cols)
	 for (row_tree_type *t=R->begin(), *end=R->end(); t!=end; ++t, ++r) {
	    if (t->size()) {
	       if (int rdiff=r-rnew) {
		  t->line_index=rnew;
		  for (typename Entire<row_tree_type>::iterator e=entire(*t); !e.at_end(); ++e)
		     e->key -= rdiff;
		  relocate(t, t-rdiff);
	       }
	       ++rnew; *rnc++=r;
	    } else {
	       t->~row_tree_type();
	    }
	 }
      if (restriction != only_rows)
	 for (col_tree_type *t=C->begin(), *end=C->end(); t!=end; ++t, ++c) {
	    if (t->size()) {
	       if (int cdiff=c-cnew) {
		  t->line_index=cnew;
		  for (typename Entire<col_tree_type>::iterator e=entire(*t); !e.at_end(); ++e)
		     e->key -= cdiff;
		  relocate(t, t-cdiff);
	       }
	       ++cnew; *cnc++=c;
	    } else {
	       t->~col_tree_type();
	    }
	 }
      if (rnew < r) R=row_ruler::resize(R,rnew,false);
      if (cnew < c) C=col_ruler::resize(C,cnew,false);
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   template <typename row_number_consumer>
   void squeeze(row_number_consumer rnc) { squeeze(rnc,black_hole<int>()); }

   void squeeze() { squeeze(black_hole<int>(), black_hole<int>()); }
private:
   template <typename _row_ruler, typename _col_ruler, bool _restricted>
   static void _permute(_row_ruler *R, _col_ruler *C, bool2type<_restricted>*) {
      if (!_restricted)
	 for (typename Entire<_row_ruler>::iterator rt=entire(*R);  !rt.at_end();  ++rt)
	    rt->init();
      int c=0;
      for (typename Entire<_col_ruler>::iterator ct=entire(*C); !ct.at_end();  ++ct, ++c) {
	 int old_c=ct->line_index, cdiff=c-old_c;
	 ct->line_index=c;
	 for (typename Entire<typename _col_ruler::value_type>::iterator e=entire(*ct); !e.at_end(); ++e) {
	    int r=e->key - old_c;
	    e->key += cdiff;
	    if (!_restricted) (*R)[r].push_back_node(e.operator->());
	 }
      }
   }
public:
   template <typename Iterator, bool inverse>
   void permute_rows(Iterator perm, bool2type<inverse>*) {
      DIMENSION_CHECK(restriction==only_cols, "sparse2d::Table::permute_rows - disabled in restricted mode");
      R=row_ruler::permute(R, perm, (bool2type<inverse>*)0);
      _permute(C, R, (bool2type<restriction==only_rows>*)0);
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   template <class Iterator, bool inverse>
   void permute_cols(Iterator perm, bool2type<inverse>*) {
      DIMENSION_CHECK(restriction==only_rows, "sparse2d::Table::permute_cols - disabled in restricted mode");
      C=col_ruler::permute(C, perm, (bool2type<inverse>*)0);
      _permute(R, C, (bool2type<restriction==only_cols>*)0);
      if (!restricted) {
	 R->prefix()=C;
	 C->prefix()=R;
      }
   }

   row_tree_type& row(int i) {
      return (*R)[i];
   }
   const row_tree_type& row(int i) const {
      return (*R)[i];
   }
   col_tree_type& col(int i) {
      return (*C)[i];
   }
   const col_tree_type& col(int i) const {
      return (*C)[i];
   }

#ifdef POLY_DEBUG
   void check() const {
      if (restriction != only_cols)
	 for (int r=0, rend=this->rows(); r<rend; ++r) {
	    std::ostringstream label;
	    label << "row " << r << ": ";
	    (*R)[r].check(label.str().c_str());
	 }
      if (restriction != only_cols)
	 for (int c=0, cend=this->cols(); c<cend; ++c) {
	    std::ostringstream label;
	    label << "column " << c << ": ";
	    (*C)[c].check(label.str().c_str());
	 }
   }
#endif // POLY_DEBUG

   template <typename, bool, restriction_kind, template <typename> class> friend class Rows;
   template <typename, bool, restriction_kind, template <typename> class> friend class Cols;
   template <typename, bool, restriction_kind> friend class Table;
};

template <typename E, restriction_kind restriction>
class Table<E, true, restriction> {
protected:
   static const bool restricted= restriction==dying;
   typedef traits<traits_base<E,false,true,restriction>, true, restriction> row_tree_traits;
   typedef row_tree_traits col_tree_traits;
   typedef AVL::tree<row_tree_traits> row_tree_type;
   typedef row_tree_type col_tree_type;
public:
   typedef ruler<row_tree_type> row_ruler;
   typedef row_ruler col_ruler;
protected:
   typedef Table<E,true,dying> restricted_Table;
   row_ruler *R;
public:
   Table() : R(row_ruler::construct(0)) { }

   explicit Table(int r, int=0)
      : R(row_ruler::construct(r)) { }

   Table(const Table& t)
      : R(row_ruler::construct(*t.R)) { }

   ~Table() {
      if (restricted) {
	 row_ruler::destroy(R);
      } else {
	 reinterpret_cast<restricted_Table*>(this)->~restricted_Table();
      }
   }

   Table& operator= (const Table& t) {
      this->~Table();
      new(this) Table(t);
      return *this;
   }

   void swap(Table& t) {
      std::swap(R,t.R);
   }

   int rows() const { return R->size(); }
   int cols() const { return this->rows(); }

   void clear() {
      R=row_ruler::resize(R,0);
   }

   void resize_rows(int r) {
      R=row_ruler::resize(R,r);
   }

   void resize_cols(int r) {
      resize_rows(r);
   }

   void resize() {
      resize_rows(this->rows());
   }

   void resize(int r, int=0) {
      resize_rows(r);
   }

   template <typename row_number_consumer>
   void squeeze(row_number_consumer rnc) {
      int r=0, rnew=0;
      for (row_tree_type *t=R->begin(), *end=R->end(); t!=end; ++t, ++r) {
	 if (t->size()) {
	    if (int rdiff=r-rnew) {
	       const int diag=2*r;
	       for (typename Entire<row_tree_type>::iterator e=entire(*t); !e.at_end(); ) {
		  cell<E>& c=*e; ++e;
		  c.key -= rdiff << (c.key==diag);
	       }
	       t->line_index=rnew;
	       relocate(t, t-rdiff);
	    }
	    ++rnew; *rnc++=r;
	 } else {
	    t->~row_tree_type();
	 }
      }
      if (rnew < this->rows()) R=row_ruler::resize(R,rnew,false);
   }

   void squeeze() { squeeze(black_hole<int>()); }

   row_tree_type& row(int i) {
      return (*R)[i];
   }
   const row_tree_type& row(int i) const {
      return (*R)[i];
   }
   col_tree_type& col(int i) {
      return row(i);
   }
   const col_tree_type& col(int i) const {
      return row(i);
   }

#ifdef POLY_DEBUG
   void check() const {
      for (int r=0, rend=this->rows(); r<rend; ++r) {
	 std::ostringstream label;
	 label << "row " << r << ": ";
	 (*R)[r].check(label.str().c_str());
      }
   }
#endif // POLY_DEBUG

   template <typename, bool, restriction_kind, template <typename> class> friend class Rows;
};

template <typename TreeType>
class line
   : public modified_tree< line<TreeType>,
	       cons< Hidden< TreeType >,
		     Accessor< pair< BuildUnary<cell_accessor>, BuildUnaryIt<cell_index_accessor> > > >
            > {
protected:
   ~line();
public:
   int dim() const { return this->max_size(); }
};

template <typename TreeRef>
struct line_index_accessor {
   typedef typename attrib<TreeRef>::plus_const_ref argument_type;
   typedef const int result_type;
   result_type operator() (argument_type t) const {
      return t.get_line_index();
   }
};

template <typename E, bool symmetric, restriction_kind restriction, template <typename> class MasqueradeLine>
class Rows
   : public modified_container_impl< Rows<E,symmetric,restriction,MasqueradeLine>,
	       cons< Container< typename Table<E,symmetric,restriction>::row_ruler >,
	       cons< Accessor< pair< operations::masquerade<MasqueradeLine>, BuildUnary<line_index_accessor> > >,
		     Hidden< Table<E,symmetric,restriction> > > >
            > {
   typedef modified_container_impl<Rows> _super;
public:
   typename _super::container& get_container()
   {
      return *this->hidden().R;
   }
   const typename _super::container& get_container() const
   {
      return *this->hidden().R;
   }
   void resize(int n)
   {
      this->hidden().resize_rows(n);
   }
};

template <typename E, bool symmetric, restriction_kind restriction, template <typename> class MasqueradeLine>
class Cols
   : public modified_container_impl< Cols<E,symmetric,restriction,MasqueradeLine>,
	       cons< Container< typename Table<E,symmetric,restriction>::col_ruler >,
	       cons< Accessor< pair< operations::masquerade<MasqueradeLine>, BuildUnary<line_index_accessor> > >,
		     Hidden< Table<E,symmetric,restriction> > > >
            > {
   typedef modified_container_impl<Cols> _super;
public:
   typename _super::container& get_container()
   {
      return *this->hidden().C;
   }
   const typename _super::container& get_container() const
   {
      return *this->hidden().C;
   }
   void resize(int n)
   {
      this->hidden().resize_cols(n);
   }
};

template <typename E, restriction_kind restriction, template <typename> class MasqueradeLine>
class Cols<E, true, restriction, MasqueradeLine> : public Rows<E, true, restriction, MasqueradeLine> { };

} // end namespace sparse2d

template <typename TreeRef>
struct check_container_feature<sparse2d::line<TreeRef>, pure_sparse> : True { };

} // end namespace pm

namespace std {
   template <typename E, bool symmetric, pm::sparse2d::restriction_kind restriction> inline
   void swap(pm::sparse2d::Table<E,symmetric,restriction>& t1, pm::sparse2d::Table<E,symmetric,restriction>& t2) {
      t1.swap(t2);
   }
} // end namespace std

namespace polymake {
   using pm::sparse2d::only_rows;
   using pm::sparse2d::only_cols;
}

#endif // _POLYMAKE_SPARSE2D_H

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