#ifndef glas_container_mapped_vector_hpp
#define glas_container_mapped_vector_hpp

#include <glas/algorithm/zero.hpp>
#include <glas/concept/concept.hpp>
#include <glas/concept/sparse_expression_concept.hpp>
#include <glas/concept/vector_collection_concept.hpp>
#include <glas/utilities/project2nd.hpp>
#include <boost/mpl/vector.hpp>
#include <map>
#include <iterator>
#include <iostream> 
#include <cassert>

namespace glas {

  // inefficient implementation of a sparse-vector just to
  // test the interface
  template < class T, class Alloc = std::allocator< std::pair< int const, T > >, class S = int, class ZeroFunctor = zero<T>, class DuplicateFunctor = project2nd<T,T> >
  class mapped_vector
  {
    typedef std::map< S, T, std::less<S>, Alloc > map_type ;

  public:

    typedef S                                      size_type ;       /// VectorExpression
    typedef T                                      value_type ;      /// VectorExpression
    typedef value_type                             const_reference ; /// VectorExpression, is equal to value_type because also ZeroFunctor might be returned
    typedef typename map_type::size_type           nnz_type ;        /// SparseExpression
    typedef boost::mpl::vector< vector_collection_concept, sparse_expression_concept > concept_type ;
    typedef value_type const &                     const_nz_reference ;
    typedef value_type&                            nz_reference ;

    /// proxy
    class reference // VectorCollection
    {
      public:

        reference(mapped_vector& v,size_type i) : v_( v ), i_( i ) {}

        operator value_type() const
        { 
           mapped_vector const & vc_( v_ ) ;
           return vc_[i_] ;
        }

        value_type operator=(value_type const & e)
        { v_.insert(i_,e) ; return e ; }

      private: 
        mapped_vector& v_ ;
        size_type      i_ ;
    } ;

  public:

    /// DefaultConstructible
    mapped_vector()
      : size_( 0 )
    {}

    /// SizeConstructible
    /// size-constructor will not allocate structure
    mapped_vector( size_type n )
      : size_( n )
    {}

    /// Assignable, Expression
    mapped_vector(mapped_vector const & that)
      : map_( that.map_ ) 
    { assert( that.size_ == size_ ) ; }
    
    /// Expression
    ~mapped_vector()
    {} 
    
    /// EqualityComparable
    bool operator==(mapped_vector const & that)
    { return that.size_ == size_ && that.map_ == map_ ; }
    
    /// EqualityComparable
    bool operator!=(mapped_vector const & that)
    { return ! ( *this == that ) ; }
    
    /// VectorExpression, SizeConstructible
    size_type size() const
    { return size_ ; }
    
    /// SizeConstructible
    void resize(size_type n)
    {
      if ( n < size_ ) map_.erase( map_.lower_bound(n),map_.end() ) ;
      size_ = n ;
    }
    
    /// VectorExpression
    const_reference operator[](size_type i) const
    {
      assert( i < size_ ) ;
      typename map_type::const_iterator it = map_.find(i) ;
      if ( it != map_.end() ) return (*it).second ;
      else return ZeroFunctor()() ;
    }
    
    /// VectorExpression
    const_reference operator()(size_type i) const
    { return (*this)[i] ; }

    reference operator[](size_type i)
    {
      assert( i < size_ ) ;
      return reference(*this,i) ;
    }

    reference operator()(size_type i)
    { return (*this)[i] ; }

    /// SparseExpression
    nnz_type nnz() const
    { return map_.size() ; }
    
    /// SparseExpression
    const_nz_reference nz(nnz_type i) const
    { 
      typename map_type::const_iterator it = map_.begin() ;
      std::advance( it, i ) ;
      return it->second ;
    }

    /// SparseCollection
    nz_reference nz(nnz_type i) 
    { 
      typename map_type::iterator it = map_.begin() ;
      std::advance( it, i ) ;
      return it->second ;
    }

    /// SparseVector
    void insert(size_type i, value_type const & new_value)
    { 
      value_type old_value = map_[i] ;
      map_[i] = DuplicateFunctor()( old_value, new_value ) ;
    }


  private:

    // size is stored seperatly because the size of the map_ is not
    // necessarily equal to the size of the vector (only when there
    // no non-zeros
    size_type                     size_ ;
    map_type                      map_ ;
  } ;

  template <class T, class A, class S, class Z, class D>
  std::ostream& operator<<(std::ostream& os, mapped_vector<T,A,S,Z,D> const & vec)
  {
    typename mapped_vector<T,A,S,Z,D>::size_type n = vec.size() ; 
    typename mapped_vector<T,A,S,Z,D>::size_type i = 0 ;
    if ( n > 0 ) {
      os << vec[0] ;
      for( ; i < n ; ++i ) os << "," << vec[i] ;
    }
    return os ;
  }
}


#endif // glas_container_mapped_vector_hpp