/* 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_SPARSE_H
#define _POLYMAKE_SPARSE_H "$Project: polymake $$Id: sparse.h,v 1.17 2006/03/07 18:06:42 gawrilow Exp $"

#ifndef _POLYMAKE_SERIES_H
#  include <Series.h>
#endif
#ifndef _POLYMAKE_CONVERTERS_BASIC_DEFS_H
#  include <converters_basic_defs.h>
#endif
#ifndef _POLYMAKE_SELECTED_SUBSET_H
#  include <SelectedSubset.h>
#endif
#ifndef _POLYMAKE_ITERATOR_ZIPPER_H
#  include <iterator_zipper.h>
#endif

namespace pm {

template <typename Container>
class construct_sparse_compatible
   : public redirected_container< construct_sparse_compatible<Container>,
	       cons< Hidden< Container >,
		     ExpectedFeatures< cons<end_sensitive, indexed> > >
            > {
   typedef redirected_container<construct_sparse_compatible> _super;
public:
   int dim() const { return this->size(); }

   void erase(const typename _super::iterator& where)
   {
      operations::clear<typename _super::value_type> zero;
      *where=zero();
   }

   // Should be defined, although never called
   void insert(const typename _super::iterator&, int, const typename _super::value_type&) { }
};

template <typename Container>
struct default_enforce_feature<Container, sparse_compatible> {
   typedef construct_sparse_compatible<Container> container;
};

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

template <typename Container>
struct check_container_feature<construct_sparse_compatible<Container>, sparse_compatible> : True { };

struct pure_sparse_modifier {
   template <typename Iterator, typename Predicate, typename ExpectedFeatures>
   struct defs : public unary_predicate_selector_modifier::defs<Iterator,Predicate,ExpectedFeatures> {
      typedef typename mix_features<typename unary_predicate_selector_modifier::template
                                       defs<Iterator,Predicate,ExpectedFeatures>::needed_features,
				    sparse_compatible>::result
         needed_features;
   };
};

template <typename Container, int kind=object_classifier::what_is<Container>::answer>
class construct_pure_sparse
   : public modified_container_impl< construct_pure_sparse<Container>,
        cons< Hidden< Container >,
        cons< Accessor< conv<typename container_traits<Container>::value_type, bool> >,
	      Modifier< pure_sparse_modifier > > >
     > {
public:
   int dim() const { return this->hidden().size(); }
};

template <typename Container>
class construct_pure_sparse<Container, object_classifier::is_constant>
   : public construct_sparse_compatible<Container> {
   typedef construct_sparse_compatible<Container> _super;
public:
   typename _super::iterator begin() const
   {
      return this->hidden().front() ? _super::begin() : _super::end();
   }
   int size() const
   {
      return this->hidden().front() ? this->dim() : 0;
   }
   bool empty() const
   {
      return !this->hidden().front();
   }
};

template <typename Container>
struct default_enforce_feature<Container, pure_sparse> {
   typedef construct_pure_sparse<Container> container;
};

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

template <typename Container, int kind>
struct check_container_feature<construct_pure_sparse<Container,kind>, pure_sparse> : True { };

template <typename Iterator, typename value_type,
	  bool _good=((check_iterator_feature<Iterator,indexed>::answer &&
		       isomorphic<typename iterator_traits<Iterator>::value_type, value_type>::answer) ||
		      isomorphic<typename iterator_traits<Iterator>::value_type, pair<int,value_type> >::answer)>
struct construct_sparse_iterator {
   typedef Iterator iterator;
   static Iterator& _do(Iterator& src, int) { return src; }
};

template <typename Iterator, typename value_type>
struct construct_sparse_iterator<Iterator, value_type, false> {
   typedef ensure_features<sequence, sparse_compatible>::const_iterator indexer;
   typedef iterator_pair<Iterator, indexer, FeaturesViaSecond<indexed> > it_pair;
   typedef unary_predicate_selector<it_pair, conv<value_type,bool> > iterator;

   static iterator _do(const Iterator& src, int dim)
   {
      return it_pair(src, ensure(sequence(0,dim), (sparse_compatible*)0).begin());
   }
};

template <typename LeftRef, typename RightRef>
struct implicit_zero {
   typedef LeftRef first_argument_type;
   typedef int second_argument_type;
   typedef LeftRef result_type;

   result_type operator() (LeftRef l, second_argument_type) const { return l; }
   template <typename Iterator2>
   result_type operator() (operations::partial_left, LeftRef l, const Iterator2&) const { return l; }
   template <typename Iterator1>
   result_type operator() (operations::partial_right, const Iterator1&, second_argument_type) const
   {
      operations::clear<first_argument_type> zero;
      return zero();
   }
};

template <typename Container>
struct dense_helper {
   typedef cons< Container1< Container >,
	   cons< Container2< sequence >,
	   cons< Coupler< zipping_coupler< operations::cmp<>, set_union_zipper, true, false> >,
		 Hidden< Container > > > >
      traits;
};

template <typename Container>
class construct_dense_pair
   : public container_pair_impl< construct_dense_pair<Container>, typename dense_helper<Container>::traits> {
public:
   const Container& get_container1() const { return this->hidden(); }
   sequence get_container2() const { return sequence(0, this->size()); }
   int size() const { return this->hidden().dim(); }
};

template <typename Container>
class construct_dense
   : public modified_container_pair_impl< construct_dense<Container>,
	       cons< Accessor< pair< BuildBinary<implicit_zero>, BuildBinaryIt<operations::second_deref> > >,
		     typename dense_helper<Container>::traits >
   > {
public:
   const Container& get_container1() const { return this->hidden(); }
   sequence get_container2() const { return sequence(0, this->size()); }
   int size() const { return this->hidden().dim(); }
};

template <typename Container>
struct default_enforce_feature<Container, dense> {
   typedef construct_dense<Container> container;
};

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

template <typename Container>
struct check_container_feature<construct_dense<Container>, dense> : True { };

template <typename Controller, bool _reverse>
struct sparse_coupler {
   typedef typename if_else<_reverse, reverse_comparator< operations::cmp<> >, operations::cmp<> >::result
      Comparator;
   template <typename Iterator1, typename Iterator2, typename ExpectedFeatures>
   struct defs {
      typedef iterator_zipper<Iterator1, Iterator2, Comparator, Controller, true, true> iterator;
      typedef typename mix_features<ExpectedFeatures, sparse_compatible>::result needed_features1;
      typedef needed_features1 needed_features2;
   };
};

template <typename Controller, bool _reverse>
struct reverse_coupler< sparse_coupler<Controller, _reverse> > {
   typedef sparse_coupler<Controller, !_reverse> type;
};

template <typename Base, typename E=typename Base::value_type, typename Predicate=conv<E, bool> >
class sparse_elem_proxy : public Base {
protected:
   Predicate non_zero;
public:
   sparse_elem_proxy(const Base base_arg) : Base(base_arg) { }

   operator const E& () const
   {
      return this->get();
   }

   operator void* () const
   {
      return (void*)(this->exists());
   }

   bool operator! () const
   {
      return !this->exists();
   }

   sparse_elem_proxy& operator= (const sparse_elem_proxy& p2)
   {
      return *this=static_cast<const E&>(p2);
   }

   sparse_elem_proxy& operator= (const E& x)
   {
      if (non_zero(x))
	 this->insert(x);
      else
	 this->erase();
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator= (const E2& x2)
   {
      return (*this=E(x2));
   }

   sparse_elem_proxy& operator++ ()
   {
      typename Base::iterator where=this->find();
      if (!non_zero(++(*where))) this->erase(where);
      return *this;
   }

   sparse_elem_proxy& operator-- ()
   {
      typename Base::iterator where=this->find();
      if (!non_zero(--(*where))) this->erase(where);
      return *this;
   }

   const E operator++ (int)
   {
      typename Base::iterator where=this->find();
      E v=*where;
      if (!non_zero(++(*where))) this->erase(where);
      return v;
   }

   const E operator-- (int)
   {
      typename Base::iterator where=this->find();
      E v=*where;
      if (!non_zero(--(*where))) this->erase(where);
      return v;
   }

   template <typename E2>
   sparse_elem_proxy& operator+= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where += x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator-= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where -= x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator*= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where *= x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator/= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where /= x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator%= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where %= x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator<<= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where <<= x)) this->erase(where);
      return *this;
   }

   template <typename E2>
   sparse_elem_proxy& operator>>= (const E2& x)
   {
      typename Base::iterator where=this->find();
      if (!non_zero(*where >>= x)) this->erase(where);
      return *this;
   }
};

template <typename Base>
class sparse_elem_proxy<Base, bool, conv<bool, bool> > : public Base {
public:
   sparse_elem_proxy(const Base base_arg) : Base(base_arg) { }

   operator bool () const { return this->get(); }

   sparse_elem_proxy& operator= (const sparse_elem_proxy& p2)
   {
      return *this=static_cast<bool>(p2);
   }

   sparse_elem_proxy& operator= (bool x)
   {
      if (x)
	 this->insert();
      else
	 this->erase();
      return *this;
   }

   sparse_elem_proxy& operator&= (bool x)
   {
      if (!x) this->erase();
      return *this;
   }

   sparse_elem_proxy& operator|= (bool x)
   {
      if (x) this->insert();
      return *this;
   }

   sparse_elem_proxy& operator^= (bool x)
   {
      if (x) this->toggle();
      return *this;
   }
};

template <typename _Vector>
class sparse_proxy_base {
protected:
   typedef typename _Vector::iterator iterator;
public:
   typedef typename iterator_traits<iterator>::value_type value_type;
protected:
   _Vector* vec;
   int i;

   const value_type& get() const { return const_cast<const _Vector&>(*vec)[i]; }

   iterator find() { return vec->insert(i); }

   bool exists() const { return vec->exists(i); }

   void insert(const value_type& x) { vec->insert(i,x); }

   void erase() { vec->erase(i); }

   void erase(const iterator& pos) {
      vec->erase(pos);
   }
public:
   sparse_proxy_base(_Vector* vec_arg, int i_arg)
      : vec(vec_arg), i(i_arg) { }
};

template <typename Base, typename E>
struct object_traits< sparse_elem_proxy<Base,E> > : object_traits<E> { };

namespace operations {
   template <typename ContainerRef>
   struct front_index {
      typedef ContainerRef argument_type;
      typedef int result_type;
      result_type operator() (typename function_argument<ContainerRef>::const_type l) const { return l.begin().index(); }
   };

   template <typename ContainerRef>
   struct back_index {
      typedef ContainerRef argument_type;
      typedef int result_type;
      result_type operator() (typename function_argument<ContainerRef>::const_type l) const { return l.rbegin().index(); }
   };
}

template <typename Container, typename Iterator>
Iterator assign_sparse(Container& c, Iterator src)
{
   typename Container::iterator dst=c.begin();
   int state=(dst.at_end() ? 0 : zipper_first) + (src.at_end() ? 0 : zipper_second);
   while (state >= zipper_both) {
      const int idiff=dst.index()-src.index();
      if (idiff<0) {
	 c.erase(dst++);
	 if (dst.at_end()) state -= zipper_first;
      } else if (idiff>0) {
	 c.insert(dst, src.index(), *src);
	 ++src;
	 if (src.at_end()) state -= zipper_second;
      } else {
	 *dst=*src;
	 ++dst;
	 if (dst.at_end()) state -= zipper_first;
	 ++src;
	 if (src.at_end()) state -= zipper_second;
      }
   }
   if (state & zipper_first) {
      do {
	 c.erase(dst++);
      } while (!dst.at_end());
   } else if (state) {
      do {
	 c.insert(dst, src.index(), *src);  ++src;
      } while (!src.at_end());
   }
   return src;
}

template <typename Container1, typename Container2>
void swap_sparse(Container1& c1, Container2& c2)
{
   typename Container1::iterator e1=c1.begin();
   typename Container2::iterator e2=c2.begin();
   int state=(e1.at_end() ? 0 : zipper_first) + (e2.at_end() ? 0 : zipper_second);
   while (state >= zipper_both) {
      const int idiff=e1.index()-e2.index();
      if (idiff<0) {
	 c2.insert(e2, e1.index(), *e1);
	 c1.erase(e1++);
	 if (e1.at_end()) state -= zipper_first;
      } else if (idiff>0) {
	 c1.insert(e1, e2.index(), *e2);
	 c2.erase(e2++);
	 if (e2.at_end()) state -= zipper_second;
      } else {
	 std::swap(*e1,*e2);
	 ++e1;
	 if (e1.at_end()) state -= zipper_first;
	 ++e2;
	 if (e2.at_end()) state -= zipper_second;
      }
   }
   if (state & zipper_first) {
      do {
	 c2.insert(e2, e1.index(), *e1);
	 c1.erase(e1++);
      } while (!e1.at_end());
   } else if (state) {
      do { 
	 c1.insert(e1, e2.index(), *e2);
	 c2.erase(e2++);
      } while (!e2.at_end());
   }
}

} // end namespace pm

#endif // _POLYMAKE_SPARSE_H

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