/* 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_SPARSE_VECTOR_H
#define _POLYMAKE_SPARSE_VECTOR_H "$Project: polymake $$Id: SparseVector.h,v 1.37 2004/09/20 15:05:55 gawrilow Exp $"

#ifndef _POLYMAKE_GENERIC_VECTOR_H
#  include <GenericVector.h>
#endif
#ifndef _POLYMAKE_TREE_CONTAINERS_H
#  include <tree_containers.h>
#endif
#ifndef _POLYMAKE_SHARED_OBJECT_H
#  include <shared_object.h>
#endif
#ifndef _POLYMAKE_AVL_H
#  include <AVL.h>
#endif

namespace pm {

template <typename NodeRef>
class sparse_vector_accessor : public AVL::node_accessor<NodeRef> {
   typedef AVL::node_accessor<NodeRef> _super;
public:
   typedef typename inherit_ref<typename deref<NodeRef>::type::data_type, typename _super::argument_type>::type result_type;
   result_type operator() (typename _super::argument_type n) const { return n.key_and_data.second; }
};

template <typename NodeRef>
struct sparse_vector_index_accessor {
   typedef typename attrib<NodeRef>::plus_const argument_type;
   typedef const int result_type;
   result_type operator() (argument_type n) const { return n.key_and_data.first; }
};

template <typename E, typename Predicate>
class SparseVector
   : public modified_tree< SparseVector<E,Predicate>,
               cons< Container< AVL::tree< AVL::traits<int, E, BuildBinary<operations::cmp> > > >,
		     Accessor< pair< BuildUnary<sparse_vector_accessor>, BuildUnary<sparse_vector_index_accessor> > > >
            >,
     public GenericVector<SparseVector<E,Predicate>, E> {
   typedef modified_tree<SparseVector> _super;
protected:
   typedef AVL::tree< AVL::traits<int, E, BuildBinary<operations::cmp> > > tree_type;
   shared_object<tree_type> tree;
   int d;
   Predicate non_zero;

   typedef sparse_proxy_base<SparseVector> proxy_base;
   typedef sparse_elem_proxy<proxy_base> proxy;

public:
   tree_type& get_container() { return *tree; }
   const tree_type& get_container() const { return *tree; }

   int dim() const { return d; }

   SparseVector() : d(0) { }

   explicit SparseVector(int dim_arg) : d(dim_arg) { }

   template <typename Iterator>
   SparseVector(int dim_arg, Iterator src)
      : tree( make_constructor(construct_sparse_iterator<Iterator,E>::_do(src, dim_arg), end_sensitive(), (tree_type*)0) ), d(dim_arg) { }

   /// Copy of a disguised SparseVector object.
   SparseVector(const GenericVector<SparseVector>& v)
      : tree(v.top().tree), d(v.top().d) { }

   template <typename Vector2>
   SparseVector(const GenericVector<Vector2,E>& v)
      : tree( make_constructor(ensure(v.top(), (pure_sparse*)0).begin(), end_sensitive(), (tree_type*)0) ), d(v.dim()) { }

   template <typename Vector2, typename E2>
   explicit SparseVector(const GenericVector<Vector2,E2>& v)
      : tree( make_constructor(ensure(attach_converter<E>(v.top()), (pure_sparse*)0).begin(), end_sensitive(), (tree_type*)0) ), d(v.dim()) { }

   template <int n>
   explicit SparseVector(const E (&a)[n])
      : tree( make_constructor(ensure(array2container(a), (pure_sparse*)0).begin(), end_sensitive(), (tree_type*)0) ), d(n) { }

   template <typename E2, int n>
   explicit SparseVector(const E2 (&a)[n])
      : tree( make_constructor(ensure(attach_converter<E>(array2container(a)), (pure_sparse*)0).begin(), end_sensitive(), (tree_type*)0) ), d(n) { }

   void clear() { this->fill(0); d=0; }

   void resize(int n)
   {
      if (n<d) {
	 typename _super::reverse_iterator i=this->rbegin();
	 while (!i.at_end() && i.index()>=n) erase(i++);
      }
      d=n;
   }

   SparseVector& operator= (const SparseVector& v)
   {
      assign(v);
      return *this;
   }

   using SparseVector::generic_type::operator=;

   void swap(SparseVector& v)
   {
      tree.swap(v.tree);
      std::swap(d, v.d);
   }

   friend void relocate(SparseVector* from, SparseVector* to)
   {
      pm::relocate(&from->tree, &to->tree);
      to->d=from->d;
   }

   proxy operator[] (int i) { return proxy_base(this,i); }

   const E& operator[] (int i) const
   {
      typename _super::const_iterator e=this->find(i);
      if (!e.at_end()) return *e;
      operations::clear<E> zero;
      return zero();
   }

   template <typename Vector2>
   SparseVector& operator|= (const GenericVector<Vector2,E>& v)
   {
      if (is_shared()) {
	 *this = const_cast<const SparseVector&>(*this) | v;
      } else {
	 tree_type *t=tree.get();
	 for (typename ensure_features<Vector2,pure_sparse>::const_iterator src=ensure(v.top(), (pure_sparse*)0).begin();
	      !src.at_end(); ++src)
	    t->push_back(src.index()+d, *src);
	 d += v.dim();
      }
      return *this;
   }

   SparseVector& operator|= (const E& r)
   {
      if (non_zero(r)) push_back(d, r);
      ++d;
      return *this;
   }

#ifdef POLY_DEBUG
   void check() const { tree->check(""); }
   void dump() const { tree->dump(); }
#endif
protected:
   friend class GenericVector<SparseVector>;
   friend class alias_to_shared<SparseVector>;

   bool is_shared() const { return tree.is_shared(); }

   void assign(const GenericVector<SparseVector>& v)
   {
      d=v.top().d;
      tree=v.top().tree;
   }

   template <typename Vector2>
   void assign(const GenericVector<Vector2>& v)
   {
      if (is_shared()) {
	 assign(SparseVector(v));
      } else {
	 tree.get()->assign(ensure(v.top(), (pure_sparse*)0).begin());
	 d=v.dim();
      }
   }

   template <typename E2, int _size>
   void assign(const E2 (&a)[_size])
   {
      if (is_shared()) {
	 assign(SparseVector(a));
      } else {
	 tree.get()->assign(ensure(array2container(a), (pure_sparse*)0).begin());
	 d=_size;
      }
   }

   template <typename E2>
   void _fill(const E2& x, pure_sparse*)
   {
      tree.clear();
      if (non_zero(x)) {
	 tree_type *t=tree.get();
	 for (int i=0; i<d; ++i) t->push_back(i,x);
      }
   }

   const shared_object<tree_type>& data_member() const { return tree; }
};

template <typename E, typename Predicate>
class alias_ptr< SparseVector<E, Predicate> > : public alias_to_shared< SparseVector<E,Predicate> > {
public:
   alias_ptr(const SparseVector<E, Predicate>* ptr_arg) : alias_to_shared< SparseVector<E, Predicate> >(ptr_arg) { }
};

template <typename E, typename Predicate>
struct check_container_feature<SparseVector<E, Predicate>, pure_sparse> : True { };

} // end namespace pm

namespace polymake {
   using pm::SparseVector;
}

namespace std {
   template <typename E, typename Predicate> inline
   void swap(pm::SparseVector<E, Predicate>& v1, pm::SparseVector<E,Predicate>& v2) { v1.swap(v2); }
}

#endif // _POLYMAKE_SPARSE_VECTOR_H

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