// -*- mode: C++; c-indent-level: 4; c-basic-offset: 4; indent-tabs-mode: nil; -*-
//
// Vector.h: Rcpp R/C++ interface class library -- vectors
//
// Copyright (C) 2010 - 2013 Dirk Eddelbuettel and Romain Francois
//
// This file is part of Rcpp.
//
// Rcpp 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 of the License, or
// (at your option) any later version.
//
// Rcpp 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.
//
// You should have received a copy of the GNU General Public License
// along with Rcpp.  If not, see <http://www.gnu.org/licenses/>.

#ifndef Rcpp__vector__Vector_h
#define Rcpp__vector__Vector_h

#include <Rcpp/vector/Subsetter.h>

namespace Rcpp{

template <int RTYPE, template <class> class StoragePolicy = PreserveStorage >
class Vector :
    public StoragePolicy< Vector<RTYPE,StoragePolicy> >,
    public SlotProxyPolicy< Vector<RTYPE,StoragePolicy> >,
    public AttributeProxyPolicy< Vector<RTYPE,StoragePolicy> >,
    public NamesProxyPolicy< Vector<RTYPE, StoragePolicy> >,
    public RObjectMethods< Vector<RTYPE, StoragePolicy> >,
    public VectorBase< RTYPE, true, Vector<RTYPE,StoragePolicy> >
{
public:

    typedef StoragePolicy<Vector> Storage ;

    typename traits::r_vector_cache_type<RTYPE>::type cache ;
    typedef typename traits::r_vector_proxy<RTYPE>::type Proxy ;
    typedef typename traits::r_vector_const_proxy<RTYPE>::type const_Proxy ;
    typedef typename traits::r_vector_name_proxy<RTYPE>::type NameProxy ;
    typedef typename traits::r_vector_proxy<RTYPE>::type value_type ;
    typedef typename traits::r_vector_iterator<RTYPE>::type iterator ;
    typedef typename traits::r_vector_const_iterator<RTYPE>::type const_iterator ;
    typedef typename traits::init_type<RTYPE>::type init_type ;
    typedef typename traits::r_vector_element_converter<RTYPE>::type converter_type ;
    typedef typename traits::storage_type<RTYPE>::type stored_type ;

    /**
     * Default constructor. Creates a vector of the appropriate type
     * and 0 length
     */
    Vector() {
      Storage::set__( Rf_allocVector(RTYPE, 0 ) );
      init() ;
    }

    /**
     * copy constructor. shallow copy of the SEXP
     */
    Vector( const Vector& other){
        Storage::copy__(other) ;
    }

    Vector& operator=(const Vector& rhs) {
        return Storage::copy__(rhs) ;
    }

    Vector( SEXP x ) {
        Storage::set__( r_cast<RTYPE>(x) ) ;
    }

    template <typename Proxy>
    Vector( const GenericProxy<Proxy>& proxy ){
        Storage::set__( r_cast<RTYPE>(proxy.get()) ) ;
    }

    explicit Vector( const no_init_vector& obj) {
        Storage::set__( Rf_allocVector( RTYPE, obj.get() ) ) ;
    }

    Vector( const int& size, const stored_type& u ) {
        RCPP_DEBUG_2( "Vector<%d>( const int& size = %d, const stored_type& u )", RTYPE, size)
        Storage::set__( Rf_allocVector( RTYPE, size) ) ;
        fill( u ) ;
    }

    // constructor for CharacterVector() 
    Vector( const std::string& st ){
        RCPP_DEBUG_2( "Vector<%d>( const std::string& = %s )", RTYPE, st.c_str() )
        Storage::set__( internal::vector_from_string<RTYPE>(st) ) ;
    }

    // constructor for CharacterVector() 
    Vector( const char* st ) {
        RCPP_DEBUG_2( "Vector<%d>( const char* = %s )", RTYPE, st )
        Storage::set__(internal::vector_from_string<RTYPE>(st) ) ;
    }

    Vector( const int& siz, stored_type (*gen)(void) ) {
        RCPP_DEBUG_2( "Vector<%d>( const int& siz = %s, stored_type (*gen)(void) )", RTYPE, siz )
        Storage::set__( Rf_allocVector( RTYPE, siz) ) ;
        std::generate( begin(), end(), gen );
    }

    Vector( const int& size ) {
        Storage::set__( Rf_allocVector( RTYPE, size) ) ;
        init() ;
    }
    Vector( const Dimension& dims) {
        Storage::set__( Rf_allocVector( RTYPE, dims.prod() ) ) ;
        init() ;
        if( dims.size() > 1 ){
            AttributeProxyPolicy<Vector>::attr( "dim" ) = dims;
        }
    }

    template <typename U>
    Vector( const Dimension& dims, const U& u) {
        RCPP_DEBUG_2( "Vector<%d>( const Dimension& (%d), const U& )", RTYPE, dims.size() )
        Storage::set__( Rf_allocVector( RTYPE, dims.prod() ) ) ;
        fill(u) ;
        if( dims.size() > 1 ){
            AttributeProxyPolicy<Vector>::attr( "dim" ) = dims;
        }
    }

    template <bool NA, typename VEC>
    Vector( const VectorBase<RTYPE,NA,VEC>& other ) {
        RCPP_DEBUG_2( "Vector<%d>( const VectorBase<RTYPE,NA,VEC>& ) [VEC = %s]", RTYPE, DEMANGLE(VEC) )
        import_sugar_expression( other, typename traits::same_type<Vector,VEC>::type() ) ;
    }
    template <typename U>
    Vector( const int& size, const U& u) {
        RCPP_DEBUG_2( "Vector<%d>( const int& size, const U& u )", RTYPE, size )
        Storage::set__( Rf_allocVector( RTYPE, size) ) ;
        fill_or_generate( u ) ;
    }
    template <bool NA, typename T>
    Vector( const sugar::SingleLogicalResult<NA,T>& obj ) {
        Storage::set__( r_cast<RTYPE>( const_cast<sugar::SingleLogicalResult<NA,T>&>(obj).get_sexp() ) ) ;
        RCPP_DEBUG_2( "Vector<%d>( const sugar::SingleLogicalResult<NA,T>& ) [T = %s]", RTYPE, DEMANGLE(T) )
    }

    template <typename U1>
    Vector( const int& siz, stored_type (*gen)(U1), const U1& u1) {
        Storage::set__( Rf_allocVector( RTYPE, siz) ) ;
        RCPP_DEBUG_2( "const int& siz, stored_type (*gen)(U1), const U1& u1 )", RTYPE, siz )
        iterator first = begin(), last = end() ;
        while( first != last ) *first++ = gen(u1) ;
    }

    template <typename U1, typename U2>
    Vector( const int& siz, stored_type (*gen)(U1,U2), const U1& u1, const U2& u2) {
        Storage::set__( Rf_allocVector( RTYPE, siz) ) ;
        RCPP_DEBUG_2( "const int& siz, stored_type (*gen)(U1,U2), const U1& u1, const U2& u2)", RTYPE, siz )
        iterator first = begin(), last = end() ;
        while( first != last ) *first++ = gen(u1,u2) ;
    }

    template <typename U1, typename U2, typename U3>
    Vector( const int& siz, stored_type (*gen)(U1,U2,U3), const U1& u1, const U2& u2, const U3& u3) {
        Storage::set__( Rf_allocVector( RTYPE, siz) ) ;
        RCPP_DEBUG_2( "const int& siz, stored_type (*gen)(U1,U2,U3), const U1& u1, const U2& u2, const U3& u3)", RTYPE, siz )
        iterator first = begin(), last = end() ;
        while( first != last ) *first++ = gen(u1,u2,u3) ;
    }

    template <typename InputIterator>
    Vector( InputIterator first, InputIterator last){
        RCPP_DEBUG_1( "Vector<%d>( InputIterator first, InputIterator last", RTYPE )
        Storage::set__( Rf_allocVector(RTYPE, std::distance(first, last) ) ) ;
        std::copy( first, last, begin() ) ;
    }

    template <typename InputIterator>
    Vector( InputIterator first, InputIterator last, int n) {
        Storage::set__(Rf_allocVector(RTYPE, n)) ;
        RCPP_DEBUG_2( "Vector<%d>( InputIterator first, InputIterator last, int n = %d)", RTYPE, n )
        std::copy( first, last, begin() ) ;
    }

    template <typename InputIterator, typename Func>
    Vector( InputIterator first, InputIterator last, Func func) {
        Storage::set__( Rf_allocVector( RTYPE, std::distance(first,last) ) );
        RCPP_DEBUG_1( "Vector<%d>( InputIterator, InputIterator, Func )", RTYPE )
        std::transform( first, last, begin(), func) ;
    }

    template <typename InputIterator, typename Func>
    Vector( InputIterator first, InputIterator last, Func func, int n){
        Storage::set__( Rf_allocVector( RTYPE, n ) );
        RCPP_DEBUG_2( "Vector<%d>( InputIterator, InputIterator, Func, int n = %d )", RTYPE, n )
        std::transform( first, last, begin(), func) ;
    }

#ifdef HAS_CXX0X_INITIALIZER_LIST
    Vector( std::initializer_list<init_type> list ) {
        assign( list.begin() , list.end() ) ;
    }
#endif

    template <typename T>
    Vector& operator=( const T& x) {
        assign_object( x, typename traits::is_sugar_expression<T>::type() ) ;
        return *this ;
    }

    static inline stored_type get_na() {
        return traits::get_na<RTYPE>();
    }
    static inline bool is_na( stored_type x){
        return traits::is_na<RTYPE>(x);
    }

    #ifdef RCPP_COMMA_INITIALIZATION
    internal::ListInitialization<iterator,init_type> operator=( init_type x){
        iterator start = begin() ; *start = x;
        return internal::ListInitialization<iterator,init_type>( start + 1 ) ; ;
    }
    #endif

    /**
     * the length of the vector, uses Rf_length
     */
    inline R_len_t length() const {
        return ::Rf_length( Storage::get__() ) ;
    }

    /**
     * alias of length
     */
    inline R_len_t size() const {
        return ::Rf_length( Storage::get__() ) ;
    }

    /**
     * offset based on the dimensions of this vector
     */
    size_t offset(const size_t& i, const size_t& j) const {
        if( !::Rf_isMatrix(Storage::get__()) ) throw not_a_matrix() ;

        /* we need to extract the dimensions */
        int *dim = dims() ;
        size_t nrow = static_cast<size_t>(dim[0]) ;
        size_t ncol = static_cast<size_t>(dim[1]) ;
        if( i >= nrow || j >= ncol ) throw index_out_of_bounds() ;
        return i + nrow*j ;
    }

    /**
     * one dimensional offset doing bounds checking to ensure
     * it is valid
     */
    size_t offset(const size_t& i) const {
        if( static_cast<R_len_t>(i) >= ::Rf_length(Storage::get__()) ) throw index_out_of_bounds() ;
        return i ;
    }

    R_len_t offset(const std::string& name) const {
        SEXP names = RCPP_GET_NAMES( Storage::get__() ) ;
        if( Rf_isNull(names) ) throw index_out_of_bounds();
        R_len_t n=size() ;
        for( R_len_t i=0; i<n; ++i){
            if( ! name.compare( CHAR(STRING_ELT(names, i)) ) ){
                return i ;
            }
        }
        throw index_out_of_bounds() ;
        return -1 ; /* -Wall */
    }

    template <typename U>
    void fill( const U& u){
        fill__dispatch( typename traits::is_trivial<RTYPE>::type(), u ) ;
    }

    inline iterator begin() { return cache.get() ; }
    inline iterator end() { return cache.get() + size() ; }
	inline const_iterator begin() const{ return cache.get_const() ; }
    inline const_iterator end() const{ return cache.get_const() + size() ; }

    inline Proxy operator[]( int i ){ return cache.ref(i) ; }
    inline const_Proxy operator[]( int i ) const { return cache.ref(i) ; }

    inline Proxy operator()( const size_t& i) {
        return cache.ref( offset(i) ) ;
    }
    inline const_Proxy operator()( const size_t& i) const {
        return cache.ref( offset(i) ) ;
    }

    inline Proxy operator()( const size_t& i, const size_t& j) {
        return cache.ref( offset(i,j) ) ;
    }
    inline const_Proxy operator()( const size_t& i, const size_t& j) const {
        return cache.ref( offset(i,j) ) ;
    }

    inline NameProxy operator[]( const std::string& name ){
        return NameProxy( *this, name ) ;
    }
    inline NameProxy operator()( const std::string& name ){
        return NameProxy( *this, name ) ;
    }

    inline NameProxy operator[]( const std::string& name ) const {
        return NameProxy( const_cast<Vector&>(*this), name ) ;
    }
    inline NameProxy operator()( const std::string& name ) const {
        return NameProxy( const_cast<Vector&>(*this), name ) ;
    }

    inline operator RObject() const {
        return RObject( Storage::get__() );
    }

    // sugar subsetting requires dispatch on VectorBase
    template <int RHS_RTYPE, bool RHS_NA, typename RHS_T>
    SubsetProxy<RTYPE, StoragePolicy, RHS_RTYPE, RHS_NA, RHS_T>
    operator[](const VectorBase<RHS_RTYPE, RHS_NA, RHS_T>& rhs) {
        return SubsetProxy<RTYPE, StoragePolicy, RHS_RTYPE, RHS_NA, RHS_T>(
            *this,
            rhs
        );
    }

    template <int RHS_RTYPE, bool RHS_NA, typename RHS_T>
    const SubsetProxy<RTYPE, StoragePolicy, RHS_RTYPE, RHS_NA, RHS_T>
    operator[](const VectorBase<RHS_RTYPE, RHS_NA, RHS_T>& rhs) const {
        return SubsetProxy<RTYPE, StoragePolicy, RHS_RTYPE, RHS_NA, RHS_T>(
            const_cast< Vector<RTYPE, StoragePolicy>& >(*this),
            rhs
        );
    }

    Vector& sort(){
        typename traits::storage_type<RTYPE>::type* start = internal::r_vector_start<RTYPE>( Storage::get__() ) ;
        std::sort(
            start,
            start + size(),
            internal::NAComparator<typename traits::storage_type<RTYPE>::type >()
        ) ;
        return *this ;
    }

    template <typename InputIterator>
    void assign( InputIterator first, InputIterator last){
        /* FIXME: we can do better than this r_cast to avoid
           allocating an unnecessary temporary object
        */
        Shield<SEXP> wrapped(wrap(first, last));
        Shield<SEXP> casted(r_cast<RTYPE>(wrapped));
        Storage::set__(casted) ;
    }

    template <typename InputIterator>
    static Vector import( InputIterator first, InputIterator last){
        Vector v ;
        v.assign( first , last ) ;
        return v ;
    }

    template <typename InputIterator, typename F>
    static Vector import_transform( InputIterator first, InputIterator last, F f){
        return Vector( first, last, f) ;
    }

    template <typename T>
    void push_back( const T& object){
        push_back__impl( converter_type::get(object),
                         typename traits::same_type<stored_type,SEXP>()
                         ) ;
    }

    template <typename T>
    void push_back( const T& object, const std::string& name ){
        push_back_name__impl( converter_type::get(object), name,
                              typename traits::same_type<stored_type,SEXP>()
                              ) ;
    }

    template <typename T>
    void push_front( const T& object){
        push_front__impl( converter_type::get(object),
                          typename traits::same_type<stored_type,SEXP>() ) ;
    }

    template <typename T>
    void push_front( const T& object, const std::string& name){
        push_front_name__impl( converter_type::get(object), name,
                               typename traits::same_type<stored_type,SEXP>() ) ;
    }


    template <typename T>
    iterator insert( iterator position, const T& object){
        return insert__impl( position, converter_type::get(object),
                             typename traits::same_type<stored_type,SEXP>()
                             ) ;
    }

    template <typename T>
    iterator insert( int position, const T& object){
        return insert__impl( cache.get() + position, converter_type::get(object),
                             typename traits::same_type<stored_type,SEXP>()
                             );
    }

    iterator erase( int position){
        return erase_single__impl( cache.get() + position) ;
    }

    iterator erase( iterator position){
        return erase_single__impl( position ) ;
    }

    iterator erase( int first, int last){
        iterator start = cache.get() ;
        return erase_range__impl( start + first, start + last ) ;
    }

    iterator erase( iterator first, iterator last){
        return erase_range__impl( first, last ) ;
    }

    void update(SEXP){
        cache.update(*this) ;
    }

    template <typename U>
    static void replace_element( iterator it, SEXP names, int index, const U& u){
        replace_element__dispatch( typename traits::is_named<U>::type(),
                                   it, names, index, u ) ;
    }

    template <typename U>
    static void replace_element__dispatch( traits::false_type, iterator it, SEXP names, int index, const U& u){
        *it = converter_type::get(u);
    }

    template <typename U>
    static void replace_element__dispatch( traits::true_type, iterator it, SEXP names, int index, const U& u){
        replace_element__dispatch__isArgument( typename traits::same_type<U,Argument>(), it, names, index, u ) ;
    }

    template <typename U>
    static void replace_element__dispatch__isArgument( traits::false_type, iterator it, SEXP names, int index, const U& u){
        RCPP_DEBUG_2( "  Vector::replace_element__dispatch<%s>(true, index= %d) ", DEMANGLE(U), index ) ;

        *it = converter_type::get(u.object ) ;
        SET_STRING_ELT( names, index, ::Rf_mkChar( u.name.c_str() ) ) ;
    }

    template <typename U>
    static void replace_element__dispatch__isArgument( traits::true_type, iterator it, SEXP names, int index, const U& u){
        RCPP_DEBUG_2( "  Vector::replace_element__dispatch<%s>(true, index= %d) ", DEMANGLE(U), index ) ;

        *it = R_MissingArg ;
        SET_STRING_ELT( names, index, ::Rf_mkChar( u.name.c_str() ) ) ;
    }

    typedef internal::RangeIndexer<RTYPE,true,Vector> Indexer ;

    inline Indexer operator[]( const Range& range ){
        return Indexer( const_cast<Vector&>(*this), range );
    }

    template <typename EXPR_VEC>
    Vector& operator+=( const VectorBase<RTYPE,true,EXPR_VEC>& rhs ) {
          const EXPR_VEC& ref = rhs.get_ref() ;
        iterator start = begin() ;
        int n = size() ;
        // TODO: maybe unroll this
        stored_type tmp ;
        for( int i=0; i<n; i++){
            Proxy left = start[i] ;
            if( ! traits::is_na<RTYPE>( left ) ){
                tmp = ref[i] ;
                left = traits::is_na<RTYPE>( tmp ) ? tmp : ( left + tmp ) ;
            }
        }
        return *this ;
    }

    template <typename EXPR_VEC>
    Vector& operator+=( const VectorBase<RTYPE,false,EXPR_VEC>& rhs ) {
          const EXPR_VEC& ref = rhs.get_ref() ;
        iterator start = begin() ;
        int n = size() ;
        stored_type tmp ;
        for( int i=0; i<n; i++){
            if( ! traits::is_na<RTYPE>(start[i]) ){
                start[i] += ref[i] ;
            }
        }
        return *this ;

    }

    /**
     *  Does this vector have an element with the target name
     */
    bool containsElementNamed( const char* target ) const {
          SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        if( Rf_isNull(names) ) return false ;
        int n = Rf_length(names) ;
        for( int i=0; i<n; i++){
            if( !strcmp( target, CHAR(STRING_ELT(names, i)) ) )
                return true ;
        }
        return false ;
    }

    int findName(const std::string& name) const {
        SEXP names = RCPP_GET_NAMES(Storage::get__());
        if (Rf_isNull(names)) stop("'names' attribute is null");
        int n = Rf_length(names);
        for (int i=0; i < n; ++i) {
            if (strcmp(name.c_str(), CHAR(STRING_ELT(names, i))) == 0) {
                return i;
            }
        }
        std::stringstream ss;
        ss << "no name '" << name << "' found";
        stop(ss.str());
        return -1;
    }


protected:
    inline int* dims() const {
        if( !::Rf_isMatrix(Storage::get__()) ) throw not_a_matrix() ;
        return INTEGER( ::Rf_getAttrib( Storage::get__(), R_DimSymbol ) ) ;
    }
    void init(){
        RCPP_DEBUG_2( "VECTOR<%d>::init( SEXP = <%p> )", RTYPE, Storage::get__() )
        internal::r_init_vector<RTYPE>(Storage::get__()) ;
    }

private:

    void push_back__impl(const stored_type& object, traits::true_type ) {
        Shield<SEXP> object_sexp( object ) ;
        int n = size() ;
        Vector target( n + 1 ) ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        if( Rf_isNull(names) ){
            for( ; it < this_end; ++it, ++target_it ){
                *target_it = *it ;
            }
        } else {
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1) ) ;
            int i = 0 ;
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
            SET_STRING_ELT( newnames, i, Rf_mkChar("") ) ;
            target.attr("names") = newnames ;
        }
        *target_it = object_sexp;
        Storage::set__( target.get__() ) ;
    }

    void push_back__impl(const stored_type& object, traits::false_type ) {
          int n = size() ;
        Vector target( n + 1 ) ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        if( Rf_isNull(names) ){
            for( ; it < this_end; ++it, ++target_it ){
                *target_it = *it ;
            }
        } else {
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1) ) ;
            int i = 0 ;
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
            SET_STRING_ELT( newnames, i, Rf_mkChar("") ) ;
            target.attr("names") = newnames ;
        }
        *target_it = object;
        Storage::set__( target.get__() ) ;
    }

    void push_back_name__impl(const stored_type& object, const std::string& name, traits::true_type ) {
        Shield<SEXP> object_sexp( object ) ;
        int n = size() ;
        Vector target( n + 1 ) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n+1 ) ) ;
        int i=0;
        if( Rf_isNull(names) ){
            for( ; it < this_end; ++it, ++target_it,i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i , R_BlankString );
            }
        } else {
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
        }
        SET_STRING_ELT( newnames, i, Rf_mkChar( name.c_str() ) );
        target.attr("names") = newnames ;

        *target_it = object_sexp;
        Storage::set__( target.get__() ) ;
    }
    void push_back_name__impl(const stored_type& object, const std::string& name, traits::false_type ) {
        int n = size() ;
        Vector target( n + 1 ) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n+1 ) ) ;
        int i=0;
        if( Rf_isNull(names) ){
            Shield<SEXP> dummy( Rf_mkChar("") );
            for( ; it < this_end; ++it, ++target_it,i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i , dummy );
            }
        } else {
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
        }
        SET_STRING_ELT( newnames, i, Rf_mkChar( name.c_str() ) );
        target.attr("names") = newnames ;

        *target_it = object;
        Storage::set__( target.get__() ) ;
    }

    void push_front__impl(const stored_type& object, traits::true_type ) {
            Shield<SEXP> object_sexp( object ) ;
        int n = size() ;
        Vector target( n+1);
        iterator target_it(target.begin());
        iterator it(begin());
        iterator this_end(end());
        *target_it = object_sexp ;
        ++target_it ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        if( Rf_isNull(names) ){
            for( ; it<this_end; ++it, ++target_it){
                *target_it = *it ;
            }
        } else{
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1) );
            int i=1 ;
            SET_STRING_ELT( newnames, 0, Rf_mkChar("") ) ;
            for( ; it<this_end; ++it, ++target_it, i++){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i-1 ) ) ;
            }
            target.attr("names") = newnames ;
        }
        Storage::set__( target.get__() ) ;

    }
    void push_front__impl(const stored_type& object, traits::false_type ) {
          int n = size() ;
        Vector target( n+1);
        iterator target_it(target.begin());
        iterator it(begin());
        iterator this_end(end());
        *target_it = object ;
        ++target_it ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        if( Rf_isNull(names) ){
            for( ; it<this_end; ++it, ++target_it){
                *target_it = *it ;
            }
        } else{
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1) );
            int i=1 ;
            SET_STRING_ELT( newnames, 0, Rf_mkChar("") ) ;
            for( ; it<this_end; ++it, ++target_it, i++){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i-1 ) ) ;
            }
            target.attr("names") = newnames ;
        }
        Storage::set__( target.get__() ) ;

    }

    void push_front_name__impl(const stored_type& object, const std::string& name, traits::true_type ) {
        Shield<SEXP> object_sexp(object) ;
        int n = size() ;
        Vector target( n + 1 ) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n+1 ) ) ;
        int i=1;
        SET_STRING_ELT( newnames, 0, Rf_mkChar( name.c_str() ) );
        *target_it = object_sexp;
        ++target_it ;

        if( Rf_isNull(names) ){
            for( ; it < this_end; ++it, ++target_it,i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i , R_BlankString );
            }
        } else {
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i-1 ) ) ;
            }
        }
        target.attr("names") = newnames ;
        Storage::set__( target.get__() ) ;

    }
    void push_front_name__impl(const stored_type& object, const std::string& name, traits::false_type ) {
          int n = size() ;
        Vector target( n + 1 ) ;
        iterator target_it( target.begin() ) ;
        iterator it(begin()) ;
        iterator this_end(end());
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n+1 ) ) ;
        int i=1;
        SET_STRING_ELT( newnames, 0, Rf_mkChar( name.c_str() ) );
        *target_it = object;
        ++target_it ;

        if( Rf_isNull(names) ){
            for( ; it < this_end; ++it, ++target_it,i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i , R_BlankString );
            }
        } else {
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i-1 ) ) ;
            }
        }
        target.attr("names") = newnames ;

        Storage::set__( target.get__() ) ;

    }

    iterator insert__impl( iterator position, const stored_type& object_, traits::true_type ) {
        Shield<SEXP> object( object_ ) ;
        int n = size() ;
        Vector target( n+1 ) ;
        iterator target_it = target.begin();
        iterator it = begin() ;
        iterator this_end = end() ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        iterator result ;
        if( Rf_isNull(names) ){
            for( ; it < position; ++it, ++target_it){
                *target_it = *it ;
            }
            result = target_it;
            *target_it = object ;
            ++target_it ;
            for( ; it < this_end; ++it, ++target_it ){
                *target_it = *it ;
            }
        } else{
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1 ) ) ;
            int i=0;
            for( ; it < position; ++it, ++target_it, i++){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
            result = target_it;
            *target_it = object ;
            SET_STRING_ELT( newnames, i, ::Rf_mkChar("") ) ;
            i++ ;
            ++target_it ;
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i - 1) ) ;
            }
            target.attr( "names" ) = newnames ;
        }
        Storage::set__( target.get__() ) ;
        return result ;
    }

    iterator insert__impl( iterator position, const stored_type& object, traits::false_type ) {
            int n = size() ;
        Vector target( n+1 ) ;
        iterator target_it = target.begin();
        iterator it = begin() ;
        iterator this_end = end() ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        iterator result ;
        if( Rf_isNull(names) ){
            for( ; it < position; ++it, ++target_it){
                *target_it = *it ;
            }
            result = target_it;
            *target_it = object ;
            ++target_it ;
            for( ; it < this_end; ++it, ++target_it ){
                *target_it = *it ;
            }
        } else{
            Shield<SEXP> newnames( ::Rf_allocVector( STRSXP, n + 1 ) ) ;
            int i=0;
            for( ; it < position; ++it, ++target_it, i++){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) ) ;
            }
            result = target_it;
            *target_it = object ;
            SET_STRING_ELT( newnames, i, ::Rf_mkChar("") ) ;
            i++ ;
            ++target_it ;
            for( ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i - 1) ) ;
            }
            target.attr( "names" ) = newnames ;
        }
        Storage::set__( target.get__() ) ;
        return result ;
    }

    iterator erase_single__impl( iterator position ) {
              if( position < begin() || position > end() ) throw index_out_of_bounds( ) ;
        int n = size() ;
        Vector target( n - 1 ) ;
        iterator target_it(target.begin()) ;
        iterator it(begin()) ;
        iterator this_end(end()) ;
        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        if( Rf_isNull(names) ){
            int i=0;
            for( ; it < position; ++it, ++target_it, i++){
                *target_it = *it;
            }
            ++it ;
            for( ; it < this_end ; ++it, ++target_it){
                *target_it = *it;
            }
            Storage::set__( target.get__() ) ;
            return begin()+i ;
        } else {
            Shield<SEXP> newnames(::Rf_allocVector( STRSXP, n-1 ));
            int i= 0 ;
            for( ; it < position; ++it, ++target_it,i++){
                *target_it = *it;
                SET_STRING_ELT( newnames, i , STRING_ELT(names,i) ) ;
            }
            int result=i ;
            ++it ;
            i++ ;
            for( ; it < this_end ; ++it, ++target_it, i++){
                *target_it = *it;
                SET_STRING_ELT( newnames, i-1, STRING_ELT(names,i) ) ;
            }
            target.attr( "names" ) = newnames ;
            Storage::set__( target.get__() ) ;
            return begin()+result ;
        }
    }

    iterator erase_range__impl( iterator first, iterator last ) {
        if( first > last ) throw std::range_error("invalid range") ;
        if( last > end() || first < begin() ) throw index_out_of_bounds() ;

        iterator it = begin() ;
        iterator this_end = end() ;
        int nremoved = std::distance(first,last) ;
        int target_size = size() - nremoved  ;
        Vector target( target_size ) ;
        iterator target_it = target.begin() ;

        SEXP names = RCPP_GET_NAMES(Storage::get__()) ;
        int result = 0;
        if( Rf_isNull(names) ){
            int i=0;
            for( ; it < first; ++it, ++target_it, i++ ){
                *target_it = *it ;
            }
            result = i;
            for( it = last ; it < this_end; ++it, ++target_it ){
                *target_it = *it ;
            }
        } else{
            Shield<SEXP> newnames( ::Rf_allocVector(STRSXP, target_size) ) ;
            int i= 0 ;
            for( ; it < first; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i ) );
            }
            result = i;
            for( it = last ; it < this_end; ++it, ++target_it, i++ ){
                *target_it = *it ;
                SET_STRING_ELT( newnames, i, STRING_ELT(names, i + nremoved ) );
            }
            target.attr("names" ) = newnames ;
        }
        Storage::set__( target.get__() ) ;

        return begin() + result;

    }

    template <typename T>
    inline void assign_sugar_expression( const T& x ) {
        int n = size() ;
        if( n == x.size() ){
            // just copy the data
            import_expression<T>(x, n ) ;
        } else{
            // different size, so we change the memory
            Shield<SEXP> wrapped(wrap(x));
            Shield<SEXP> casted(r_cast<RTYPE>(wrapped));
            Storage::set__(casted);
        }
    }

    // sugar
    template <typename T>
    inline void assign_object( const T& x, traits::true_type ) {
        assign_sugar_expression( x.get_ref() ) ;
    }

    // anything else
    template <typename T>
    inline void assign_object( const T& x, traits::false_type ) {
        Shield<SEXP> wrapped(wrap(x));
        Shield<SEXP> casted(r_cast<RTYPE>(wrapped));
        Storage::set__(casted);
    }

    // we are importing a real sugar expression, i.e. not a vector
    template <bool NA, typename VEC>
    inline void import_sugar_expression( const Rcpp::VectorBase<RTYPE,NA,VEC>& other, traits::false_type ) {
        RCPP_DEBUG_4( "Vector<%d>::import_sugar_expression( VectorBase<%d,%d,%s>, false_type )", RTYPE, NA, RTYPE, DEMANGLE(VEC) ) ;
        int n = other.size() ;
        Storage::set__( Rf_allocVector( RTYPE, n ) ) ;
        import_expression<VEC>( other.get_ref() , n ) ;
    }

    // we are importing a sugar expression that actually is a vector
    template <bool NA, typename VEC>
    inline void import_sugar_expression( const Rcpp::VectorBase<RTYPE,NA,VEC>& other, traits::true_type ) {
        RCPP_DEBUG_4( "Vector<%d>::import_sugar_expression( VectorBase<%d,%d,%s>, true_type )", RTYPE, NA, RTYPE, DEMANGLE(VEC) ) ;
        Storage::set__( other.get_ref() ) ;
    }


    template <typename T>
    inline void import_expression( const T& other, int n ) {
        iterator start = begin() ;
        RCPP_LOOP_UNROLL(start,other)
    }

    template <typename T>
    inline void fill_or_generate( const T& t) {
        fill_or_generate__impl( t, typename traits::is_generator<T>::type() ) ;
    }

    template <typename T>
    inline void fill_or_generate__impl( const T& gen, traits::true_type) {
        iterator first = begin() ;
        iterator last = end() ;
        while( first != last ) *first++ = gen() ;
    }

    template <typename T>
    inline void fill_or_generate__impl( const T& t, traits::false_type) {
        fill(t) ;
    }

    template <typename U>
    void fill__dispatch( traits::false_type, const U& u){
        // when this is not trivial, this is SEXP
        Shield<SEXP> elem( converter_type::get( u ) );
        iterator it(begin());
        for( int i=0; i<size() ; i++, ++it){
            *it = ::Rf_duplicate( elem ) ;
        }
    }

    template <typename U>
    void fill__dispatch( traits::true_type, const U& u){
        std::fill( begin(), end(), converter_type::get( u ) ) ;
    }

public:

    static Vector create(){
        return Vector( 0 ) ;
    }

    #include <Rcpp/generated/Vector__create.h>

public:

    inline SEXP eval() const {
        return Rcpp_eval( Storage::get__(), R_GlobalEnv ) ;
    }

    inline SEXP eval(SEXP env) const {
        return Rcpp_eval( Storage::get__(), env );
    }


} ; /* Vector */

}

#endif