vector.hpp

Go to the documentation of this file.

/*****************************************************************************
    
    vector.hpp -- template class vector definition and relative operations.

    This file is a part of the Arageli library.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Sergey S. Lyalin, 2005
    University of Nizhni Novgorod, Russia

*****************************************************************************/


#ifndef _ARAGELI_vector_hpp_
#define _ARAGELI_vector_hpp_

#include "config.hpp"

#include <cstddef>
#include <vector>
#include <iostream>
#include <fstream>  // for temporary implementation of input/output
#include <sstream>  // for temporary implementation of input/output
#include <limits>
#include <cmath>
#include <algorithm>

#include "frwrddecl.hpp"

#include "type_opers.hpp"
#include "type_traits.hpp"
#include "type_pair_traits.hpp"
#include "function_traits.hpp"
#include "mixcomp.hpp"
#include "exception.hpp"
#include "vecalg.hpp"
#include "refcntr.hpp"
#include "_utility.hpp"
#include "factory.hpp"
#include "cmp.hpp"
#include "io.hpp"
#include "functional.hpp"
#include "big_int.hpp"

#include "subvector/indexed.hpp"

#include "std_import.hpp"


namespace Arageli
{


struct fromseq_t {};
const fromseq_t fromseq = fromseq_t();

struct fromval_t {};
const fromval_t fromval = fromval_t();

struct fromvec_t {};
const fromvec_t fromvec = fromvec_t();

struct fromsize_t {};
const fromsize_t fromsize = fromsize_t();

struct fromstr_t {};
const fromstr_t fromstr = fromstr_t();


template <typename T, bool REFCNT, typename Index>
struct binary_function_traits
    <function_tag::subscript, vector<T, REFCNT>, Index>
        : public vec_binary_function_traits
            <vector<T, REFCNT>, Index>
{};

template <typename T, bool REFCNT, typename Index>
struct binary_function_traits
    <function_tag::subscript, const vector<T, REFCNT>, Index>
        : public vec_binary_function_traits
            <const vector<T, REFCNT>, Index>
{};

template <typename T, bool REFCNT, typename Index>
struct binary_function_traits
    <function_tag::parentheses_1, vector<T, REFCNT>, Index>
        : public binary_function_traits
            <function_tag::subscript, vector<T, REFCNT>, Index>
{};

template <typename T, bool REFCNT, typename Index>
struct binary_function_traits
    <function_tag::parentheses_1, const vector<T, REFCNT>, Index>
        : public binary_function_traits
            <function_tag::subscript, const vector<T, REFCNT>, Index>
{};



template <typename X, bool is_assignable> struct _element_type_vec_val_1
{ typedef typename X::element_type type; };

template <typename X> struct _element_type_vec_val_1<X, true>
{ typedef X type; };

template <typename T, typename X> struct _element_type_vec_val
{
    typedef typename _element_type_vec_val_1
        <X, type_pair_traits<X, T>::is_assignable>::type type;
};



template
<
    typename T,
    bool REFCNT
>
class vector
{
    template <typename T1, bool REFCNT1>
    friend class vector;
    
    // Rep -- the internal representation of vector values;
    // std::vector -- temporary decision, we need more light-weight
    // vector contatiner (like native array of std::valarray).
    
    typedef std::vector<T> Rep;

public:


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



    typedef typename Rep::value_type value_type;
    
    typedef typename Rep::value_type element_type;

    typedef typename Rep::reference reference;

    typedef typename Rep::const_reference const_reference;
    

    typedef typename Rep::size_type size_type;

    typedef typename Rep::difference_type difference_type;
    
    typedef typename Rep::pointer pointer;

    typedef typename Rep::const_pointer const_pointer;

    typedef typename Rep::iterator iterator;

    typedef typename Rep::const_iterator const_iterator;

    //typedef typename Rep::reverse_iterator reverse_iterator;

    //typedef typename Rep::const_reverse_iterator const_reverse_iterator;



    template <typename T1> struct other_element_type
    { typedef vector<T1, REFCNT> type; };

    template <typename T1, bool REFCNT1> struct other_element_type_refcnt
    { typedef vector<T1, REFCNT1> type; };


    static const bool refcounting = REFCNT;


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    
    

    vector () {}

    // BE CAREFUL! There is one more constructor. It is automaticaly generated
    // copy-constructor. Worry about its meaning is being belonged to other
    // constructors during modifications.

    // ---------------------------------
    
    vector (std::size_t size_a, const fromsize_t& select)
    { assign_fromsize(size_a); }

    vector (const char* s, const fromstr_t& select)
    { assign_fromstr(s); }

    template <typename Vec>
    vector (const Vec& vec, const fromvec_t& select)
    { assign_fromvec(vec); }

    template <typename X>
    vector (const X& x)
    { assign(x); }

    // ---------------------------------

    template <typename Val>
    vector (std::size_t size_a, const Val& val, const fromval_t& select)
    { assign_fromval(size_a, val); }


    template <typename Seq>
    vector (std::size_t size_a, const Seq& seq, const fromseq_t& select)
    { assign_fromseq(size_a, seq); }

    template <typename X>
    vector (std::size_t size_a, const X& x)
    { assign(size_a, x); }




    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




    void assign ()
    { if(unique_clear())rep().clear(); }
    
    void assign_fromsize (size_type size_a)
    {
        unique_clear();
        rep().assign(size_a, factory<T>::null());
    }

    void assign_fromstr (const char* s);

    template <typename Vec>
    void assign_fromvec (const Vec& vec)
    {
        unique_clear();

        ARAGELI_ASSERT_0
        (
            reinterpret_cast<const void*>(this) !=
            reinterpret_cast<const void*>(&vec)
        );

        rep().assign(vec.begin(), vec.end());
    }


    template <typename X>
    void assign (const X& x)
    { _assign_from_size_str_vec(x, type_traits<X>::category_value); }

private:

    template <typename Size>
    void _assign_from_size_str_vec
    (const Size& size_a, const type_category::integer&)
    { assign_fromsize(size_a); }

    template <typename Str>
    void _assign_from_size_str_vec
    (const Str& s, const type_category::string&)
    { assign_fromstr(s); }

    template <typename Vec>
    void _assign_from_size_str_vec
    (const Vec& vec, const type_category::vector&)
    { assign_fromvec(vec); }

public:

    template <typename X>
    vector& operator= (const X& x)
    {
        _assign_from_val_str_vec
        (
            x, type_traits<X>::category_value,
            bool_type<type_pair_traits<X, T>::is_assignable>::value
        );
        
        return *this;
    }

private:

    template <typename Val>
    void _assign_from_val_str_vec
    (const Val& val, const type_category::type&, const true_type&)
    { fill_fromval(val); }

    template <typename Str>
    void _assign_from_val_str_vec
    (const Str& str, const type_category::string&, const false_type&)
    { assign_fromstr(str); }

    template <typename Vec>
    void _assign_from_val_str_vec
    (const Vec& vec, const type_category::vector&, const false_type&)
    { assign_fromvec(vec); }

public:

    // -------------------------------------

    template <typename Val>
    void assign_fromval (size_type size_a, const Val& val)
    {
        unique_clear();
        rep().assign(size_a, val);
    }


    template <typename Seq>
    void assign_fromseq (size_type size_a, Seq seq)
    {
        unique_clear();
        Seq last = seq;
        // TODO: Make the following unrestricted.
        std::advance(last, size_a); // WARNING! Temporary solution.
        rep().assign(seq, last);
    }


    template <typename X>
    void assign (size_type size_a, const X& x)
    {
        _assign_from_val_seq
        (
            size_a, x,
            bool_type<type_pair_traits<X, T>::is_convertible>::value
        );
    }

    
private:

    template <typename Val>
    void _assign_from_val_seq
    (size_type size_a, const Val& val, const true_type&)
    { assign_fromval(size_a, val); }


    template <typename Seq>
    void _assign_from_val_seq
    (size_type size_a, const Seq& seq, const false_type&)
    { assign_fromseq(size_a, seq); }

public:

    // TODO: Make it faster.
    template <typename Val>
    void fill_fromval (const Val& val)
    { assign_fromval(size(), val); }

    // TODO: Make it faster.
    template <typename Seq>
    void fill_fromseq (const Seq& seq)
    { assign_fromseq(size(), seq); }

    // TODO: Make it faster.
    template <typename X>
    void fill (const X& x)
    {
        // WARNING! TEMPORARY SOLUTION!
        assign(size(), x);
    }




    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // @name Element access.




    const_reference el (size_type i) const
    {
        ARAGELI_ASSERT_0(i < size());
        return rep(i);
    }
    

    reference el (size_type i)
    {
        ARAGELI_ASSERT_0(i < size());
        unique();
        return rep(i);
    }


    const_reference at (size_type i) const
    {
        if(i > size())throw out_of_range();
        return el(i);
    }
    

    reference at (size_type i)
    {
        if(i > size())throw out_of_range();
        return el(i);
    }

    value_type take (size_type i)
    {
        value_type t = el(i);
        erase(i);
    }

    // ---------------------------------------------------------------------

    template <typename Vec>
    indexed_subvector<const vector, Vec> subvector (const Vec& vec) const
    { return indexed_subvector<const vector, Vec>(this, vec); }
    
    template <typename Vec>
    indexed_subvector<vector, Vec> subvector (const Vec& vec)
    { return indexed_subvector<vector, Vec>(this, vec); }

    template <typename Vec>
    indexed_subvector<const vector, Vec> subvector_at (const Vec& vec) const
    {
        if(all_in_range(vec, size_type(0), size_type(size()-1)))
            return subvector(vec);
        else
            throw out_of_range();
    }
    
    template <typename Vec>
    indexed_subvector<vector, Vec> subvector_at (const Vec& vec)
    {
        if(all_in_range(vec, size_type(0), size_type(size()-1)))
            return subvector(vec);
        else
            throw out_of_range();
    }

    // ---------------------------------------------------------------------


    template <typename X>
    typename binary_function_traits<function_tag::subscript, const vector, X>::result_type
    operator[] (const X& x) const
    {
        //return _operator_sqbrackets_index_vector
        //  (x, type_traits<X>::category_value);
        return vec_operator_sqbrackets_index_vector
            (this, x, type_traits<X>::category_value);
    }
    


    template <typename X>
    typename binary_function_traits<function_tag::subscript, vector, X>::result_type
    operator[] (const X& x)
    {
        //return _operator_sqbrackets_index_vector
        //  (x, type_traits<X>::category_value);
        return vec_operator_sqbrackets_index_vector
            (this, x, type_traits<X>::category_value);
    }



    template <typename X>
    typename binary_function_traits
        <function_tag::parentheses_1, const vector, X>::result_type
    operator() (const X& x) const
    { return operator[](x); }
    


    template <typename X>
    typename binary_function_traits
        <function_tag::parentheses_1, vector, X>::result_type
    operator() (const X& x)
    { return operator[](x); }


    const_reference front () const { return rep().front(); }
    reference front () { unique(); return rep().front(); }
    const_reference back () const { return rep().back(); }
    reference back () { unique(); return rep().back(); }



    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // @name Subvector access.



    template <typename SV, typename V>
    V& take_subvector (const SV& sv, V& res)
    {
        copy_subvector(sv, res);
        erase_subvector(sv);
        return res;
    }


    template <typename SV>
    vector<T, true> take_subvector (const SV& sv)
    {
        vector<T, true> res;
        return take_subvector(sv, res);
    }

    template <typename SV, typename V>
    V& copy_subvector (const SV& sv, V& res) const;

    template <typename SV>
    vector<T, true> copy_subvector (const SV& sv) const
    {
        vector<T, true> res;
        return copy_subvector(sv, res);
    }

    template <typename SV>
    void erase_subvector (const SV& sv);

    // fill_subvector
    // assign_subvector
    // apply_subvector
    // insert_subvector
    // And special versions of some functions for sorted indexes.



    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // Some properties access.


    size_type size () const { return rep().size(); }


    size_type length () const { return size(); }
    

    bool is_empty () const { return rep().empty(); }


    bool is_null () const;


    bool is_unit () const;


    bool is_opposite_unit () const;


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // Capacity managing.


    size_type capacity () const { return rep().capacity(); }

    void reserve (size_type n)
    {
        unique();
        rep().reserve(n);
    }


    bool pack ()
    {
        if(size() != capacity())
        {
            do_pack();
            return true;
        }
        else return false;
    }


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // Some modificatory operations.



    vector& opposite ();


    vector& inverse ();


    vector& bitwise_not ();


    vector& logical_not ();


    // TODO: Make it faster.

    void resize (size_type sz) { unique(); rep().resize(sz, T()); }


    // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




    template <typename UOp>
    vector& apply (UOp f)
    {
        apply1_wores_vec(*this, f);
        return *this;
    }

    template <typename Val, typename BinAsnOp>
    vector& right_apply_val (const Val& val, BinAsnOp f)
    {
        apply2_wores_vec_by_val(*this, val, f);
        return *this;
    }
    
    template <typename Val, typename BinAsnOp>
    vector& left_apply_val (const Val& val, BinAsnOp f)
    {
        apply2_wores_val_by_vec(val, *this, f);
        return *this;
    }

    template <typename Vec, typename BinAsnOp>
    vector& right_apply_vec (const Vec& vec, BinAsnOp f)
    {
        apply2_wores_vec_by_vec(*this, vec, f);
        return *this;
    }
    
    template <typename Vec, typename BinAsnOp>
    vector& left_apply_vec (const Vec& vec, BinAsnOp f)
    {
        apply2_wores_vec_by_vec(vec, *this, f);
        return *this;
    }

    template <typename X, typename BinAsnOp>
    vector& right_apply (const X& x, BinAsnOp f)
    {
        return _right_apply_val_vec
        (
            x, f,
            bool_type<type_pair_traits<X, T>::is_assignable>::value
        );
    }

private:

    template <typename X, typename BinAsnOp>
    vector& _right_apply_val_vec (const X& x, BinAsnOp f, const true_type&)
    { return right_apply_val(x, f); }

    template <typename X, typename BinAsnOp>
    vector& _right_apply_val_vec (const X& x, BinAsnOp f, const false_type&)
    { return right_apply_vec(x, f); }

public:
    
    template <typename X, typename Binop>
    vector& left_apply (const X& x, Binop f)
    {
        return _left_apply_val_vec
        (
            x, f,
            bool_type<type_pair_traits<X, T>::is_assignable>::value
        );
    }

private:

    template <typename X, typename BinAsnOp>
    vector& _left_apply_val_vec (const X& x, BinAsnOp f, const true_type&)
    { return left_apply_val(x, f); }

    template <typename X, typename BinAsnOp>
    vector& _left_apply_val_vec (const X& x, BinAsnOp f, const false_type&)
    { return left_apply_vec(x, f); }

public:


    #define _ARAGELI_VECTOR_ASSIGN_FUNC(MNEM, OPER)                                 \
        template <typename Val> vector& right_assign_##MNEM##_val (const Val& val)  \
        { return right_apply_val(val, func::right_assign_##MNEM<T, Val, T&>()); }   \
        template <typename Val> vector& left_assign_##MNEM##_val (const Val& val)   \
        { return left_apply_val(val, func::left_assign_##MNEM<Val, T, T&>()); } \
        template <typename Val> vector& assign_##MNEM##_val (const Val& val)        \
        { return right_apply_val(val, func::assign_##MNEM<T, Val, T&>()); }     \
                                                                                    \
        template <typename Vec> vector& right_assign_##MNEM##_vec (const Vec& vec)  \
        { return right_apply_vec(vec, func::right_assign_##MNEM<T,                  \
            typename type_traits<Vec>::element_type, T&>()); }                      \
                                                                                    \
        template <typename Vec> vector& left_assign_##MNEM##_vec (const Vec& vec)   \
        { return left_apply_vec(vec, func::left_assign_##MNEM                       \
            <typename type_traits<Vec>::element_type, T, T&>()); }                  \
                                                                                    \
        template <typename Vec> vector& assign_##MNEM##_vec (const Vec& vec)        \
        { return right_apply_vec(vec, func::assign_##MNEM<T,                        \
            typename type_traits<Vec>::element_type, T&>()); }                      \
                                                                                    \
        template <typename X> vector& right_assign_##MNEM (const X& x)              \
        { return left_apply(x, func::right_assign_##MNEM<T,                     \
            typename _element_type_vec_val<T, X>::type, T&>()); }                   \
                                                                                    \
        template <typename X> vector& left_assign_##MNEM (const X& x)               \
        { return right_apply(x, func::left_assign_##MNEM                            \
            <typename _element_type_vec_val<T, X>::type, T, T&>()); }               \
                                                                                    \
        template <typename X> vector& assign_##MNEM (const X& x)                    \
        { return right_apply(x, func::assign_##MNEM<T,                              \
            typename _element_type_vec_val<T, X>::type, T&>()); }                   \
                                                                                    \
        template <typename X> vector& operator OPER (const X& x)                    \
        { return assign_##MNEM(x); }

        
    _ARAGELI_VECTOR_ASSIGN_FUNC(plus, +=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(minus, -=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(multiplies, *=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(divides, /=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(modulus, %=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(bitwise_or, |=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(bitwise_and, &=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(bitwise_xor, ^=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(shift_left, <<=);
    _ARAGELI_VECTOR_ASSIGN_FUNC(shift_right, >>=);




    // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



    vector operator- () const
    {
        vector res(*this);
        return res.opposite();
    }
    
    const vector& operator+ () const { return *this; }

    vector operator~ () const
    {
        vector res(*this);
        return res.bitwise_not();
    }

    bool operator! () const { return is_null(); }

    vector& operator++ ()
    {
        apply1_wores_vec(*this, func::prefix_increment<T, T&>());
        return *this;
    }

    vector operator++ (int) { vector t = *this; operator++(); return t; }

    vector& operator-- ()
    {
        apply1_wores_vec(*this, func::prefix_decrement<T, T&>());
        return *this;
    }

    vector operator-- (int) { vector t = *this; operator--(); return t; }



    bool unique () { return store.unique(); }
    

    bool unique_clear () { return store.unique_clear(); }
    

    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    // @{


    iterator begin () { unique(); return rep().begin(); }
    

    iterator end () { unique(); return rep().end(); }

    const_iterator begin () const { return rep().begin(); }

    const_iterator end () const { return rep().end(); }

    // @}


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    // @{

    // To developers. Be careful! Iterators passed to the functions may become
    // invalid after call function unique().
    
    template <typename Val>
    iterator insert_fromval (iterator pos, const Val& val)
    {
        // TODO: Make it faster.
        size_type ipos = pos - rep().begin();
        insert_fromval(ipos, val);
        return rep().begin() + ipos;
    }
    
    template <typename Val>
    void insert_fromval (size_type pos, const Val& val)
    {
        unique();
        rep().insert(rep().begin() + pos, val);
    }

    template <typename Vec>
    iterator insert_fromvec (iterator pos, const Vec& vec)
    {
        // TODO: Make it faster.
        size_type ipos = pos - rep().begin();
        insert_fromvec(ipos, vec);
        return rep().begin() + ipos;
    }
    
    template <typename Vec>
    void insert_fromvec (size_type pos, const Vec& vec)
    {
        // TODO: Make it faster.
        unique();
        rep().insert(rep().begin() + pos, vec.begin(), vec.end());
    }

    template <typename Str>
    iterator insert_fromstr (iterator pos, const Str& str)
    {
        // TODO: Make it faster.
        return insert_fromvec(pos, vector(str, fromstr));
    }
    
    template <typename Str>
    void insert_fromstr (size_type pos, const Str& str)
    {
        // TODO: Make it faster.
        insert_fromvec(pos, vector(str, fromstr));
    }

    
    template <typename X>
    iterator insert (iterator pos, const X& x)
    {
        size_type ipos = pos - rep().begin();
        insert(ipos, x);
        return rep().begin() + ipos;
    }

    template <typename X>
    void insert (size_type pos, const X& x)
    {
        _insert_from_val_str_vec
        (
            pos, x, type_traits<X>::category_value,
            bool_type<type_pair_traits<X, T>::is_assignable>::value
        );
    }

private:

    template <typename Val>
    void _insert_from_val_str_vec
    (size_type pos, const Val& val, const type_category::type&, const true_type&)
    { insert_fromval(pos, val); }

    template <typename Str>
    void _insert_from_val_str_vec
    (size_type pos, const Str& str, const type_category::string&, const false_type&)
    { insert_fromstr(pos, str); }

    template <typename Vec>
    void _insert_from_val_str_vec
    (size_type pos, const Vec& vec, const type_category::vector&, const false_type&)
    { insert_fromvec(pos, vec); }

public:

    template <typename Val>
    iterator insert_fromval (iterator pos, size_type size_a, const Val& val)
    {
        // TODO: Make it faster.
        return insert_fromvec(pos, vector(size_a, val, fromval));
    }
    
    template <typename Val>
    void insert_fromval (size_type pos, size_type size_a, const Val& val)
    {
        // TODO: Make it faster.
        insert_fromvec(pos, vector(size_a, val, fromval));
    }

    template <typename Seq>
    iterator insert_fromseq (iterator pos, size_type size_a, const Seq& seq)
    {
        // TODO: Make it faster.
        return insert_fromvec(pos, vector(size_a, seq, fromseq));
    }
    
    template <typename Seq>
    void insert_fromseq (size_type pos, size_type size_a, const Seq& seq)
    {
        // TODO: Make it faster.
        insert_fromvec(pos, vector(size_a, seq, fromseq));
    }


    template <typename X>
    void insert (size_type pos, size_type size_a, const X& x)
    {
        _insert_from_val_seq
        (
            pos, size_a, x,
            bool_type<type_pair_traits<X, T>::is_convertible>::value
        );
    }

private:

    template <typename Val>
    void _insert_from_val_seq
    (size_type pos, size_type size_a, const Val& val, const true_type&)
    { insert_fromval(pos, size_a, val); }

    template <typename Seq>
    void _insert_from_val_seq
    (size_type pos, size_type size_a, const Seq& seq, const false_type&)
    { insert_fromseq(pos, size_a, seq); }

public:

    //  before item 'pos' (it's iterator).
    //  All elements on and after 'pos' are shifting to back. */
    //template <typename In>
    //void insert (iterator pos, In first, In last)
    //{ unique(); return rep().insert(pos, first, last); }

    //  before item 'pos' (it's index).
    //  All elements on and after 'pos' are shifting to back. */
    //template <typename In>
    //void insert (size_type pos, In first, In last)
    //{ return insert(begin() + pos, first, last); }

    //  All elements on and after 'pos' are shifting to back. */
    //void insert (iterator pos, size_type n, const T& val)
    //{ unique(); rep().insert(pos, n, val); }

    //  All elements on and after 'pos' are shifting to back. */
    //void insert (size_type pos, size_type n, const T& val)
    //{ insert(begin() + pos, n, val); }

    iterator erase (iterator pos)
    {
        ARAGELI_ASSERT_0(pos != end());
        unique();
        return rep().erase(pos);
    }
    
    void erase (size_type pos) { erase(begin() + pos); }
    
    void erase (iterator first, iterator last)
    {
        ARAGELI_ASSERT_0(first <= last);
        ARAGELI_ASSERT_0(first != end() || last == end());
        unique(); rep().erase(first, last);
    }
    
    void erase (size_type pos, size_type n)
    { erase(begin() + pos, begin() + pos + n); }

    void push_back (const T& val) { unique(); rep().push_back(val); }
    
    void push_front (const T& val) { insert(begin(), val); }

    void pop_back ()
    {
        ARAGELI_ASSERT_0(!is_empty());
        unique();
        rep().pop_back();
    }
    
    void pop_front ()
    {
        ARAGELI_ASSERT_0(!is_empty());
        //unique();
        erase(size_type(0));
    }

    template <typename T2>
    void remove (const T2& v)
    { erase(std::remove(begin(), end(), v), end()); }

    template <typename Fu>
    void remove_if (Fu f)
    { erase(std::remove_if(begin(), end(), f), end()); }

    // @}


    // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


    // @{

    void swap_els (iterator x, iterator y)
    { if(x != y){ unique(); std::iter_swap(x, y); } }

    void swap_els (size_type xpos, size_type ypos)
    { if(xpos != ypos){ unique(); std::swap(el(xpos), el(ypos)); } }

    template <typename T1, bool REFCNT1>
    void swap (vector<T1, REFCNT1>& x)
    {
        _Internal::swap_help_1
            (*this, x, store, x.store, equal_types<T, T1>::value);
    }

    // @}


private:

    Rep& rep () { return store.value(); }
    const Rep& rep () const { return store.value(); }

    reference rep (size_type i) { return rep()[i]; }
    const_reference rep (size_type i) const { return rep()[i]; }

    bool do_pack ();

    refcntr_proxy<Rep, REFCNT> store;
};


template <typename T, bool REFCNT>
struct type_traits<vector<T, REFCNT> >
    : public type_traits_default<vector<T, REFCNT> >
{
    static const bool is_specialized = type_traits<T>::is_specialized;

    static const bool is_number = false;
    static const bool is_integer_number = false;
    static const bool is_polynom = false;
    static const bool is_real_number = false;
    static const bool is_rational_number = false;
    static const bool is_complex_number = false;
    static const bool is_ring = type_traits<T>::is_ring;    // +, -, *, null, unit
    static const bool is_field = false;
    static const bool is_finite = type_traits<T>::is_finite;
    static const bool is_additive_group = type_traits<T>::is_additive_group;    // +, -, null
    static const bool is_multiplicative_group = false;
    static const bool has_zero_divisor = type_traits<T>::has_zero_divisor;
    static const bool is_integer_modulo_ring = false;
    static const bool is_matrix = false;
    static const bool is_vector = true;
    
    static const bool has_commutative_multiplication =
                        type_traits<T>::has_commutative_multiplication;
    
    static const bool has_commutative_addition =
                        type_traits<T>::has_commutative_addition;

    static const bool has_null = type_traits<T>::has_null;
    static const bool has_unit = type_traits<T>::has_unit;
    static const bool has_opposite_unit = type_traits<T>::has_opposite_unit;
    static const bool is_aggregate = true;
    typedef T element_type;
    typedef type_category::dense_vector category_type;
    static const category_type category_value;

    template <typename T1, bool REFCNT2>
    struct other_element_type_refcnt { typedef vector<T1, REFCNT2> type; };

};


template <typename T, bool REFCNT>
const type_category::dense_vector
    type_traits<vector<T, REFCNT> >::category_value =
    type_category::dense_vector();



#define _ARAGELI_VECTOR_RIGHT_OPER(MNEM)                \
    template <typename T1, typename T2, bool REFCNT2>   \
    inline vector<T2, REFCNT2>& left_assign_##MNEM      \
    (const T1& x, vector<T2, REFCNT2>& y)               \
    { return y.left_assign_##MNEM(x); }

_ARAGELI_VECTOR_RIGHT_OPER(plus);
_ARAGELI_VECTOR_RIGHT_OPER(minus);
_ARAGELI_VECTOR_RIGHT_OPER(multiplies);
_ARAGELI_VECTOR_RIGHT_OPER(divides);
_ARAGELI_VECTOR_RIGHT_OPER(modulus);
_ARAGELI_VECTOR_RIGHT_OPER(bitwise_or);
_ARAGELI_VECTOR_RIGHT_OPER(bitwise_and);
_ARAGELI_VECTOR_RIGHT_OPER(bitwise_xor);
_ARAGELI_VECTOR_RIGHT_OPER(shift_left);
_ARAGELI_VECTOR_RIGHT_OPER(shift_right);


#undef _ARAGELI_GENERIC_VECTOR_OPERATORS

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <typename Tag, typename T, bool REFCNT>
struct unary_function_traits<Tag, vector<T, REFCNT> > :
    public unary_function_traits_base
    <
        Tag, vector<T, REFCNT>,
        vector<typename unary_function_traits<Tag, T>::result_type, REFCNT>,
        unary_function_traits<Tag, T>::alternates_argument,
        unary_function_traits<Tag, T>::has_side_effect
    >
{};



namespace _Internal
{

template <typename T1, typename T2> struct select_non_vector;

template <typename T1, bool REFCNT1, typename T2>
struct select_non_vector<vector<T1, REFCNT1>, T2>
{ typedef T2 type; };

template <typename T1, typename T2, bool REFCNT2>
struct select_non_vector<T1, vector<T2, REFCNT2> >
{ typedef T1 type; };

}


template                                                                
<                                                                       
    typename Tag, typename V1, typename V2,                                         
    bool IS_CONVERT_12, bool IS_CONVERT_21,
    typename Tag_class
>                                                                       
struct bfgs_vector_helper_1
{                                                                       
    typedef typename _Internal::select_non_vector<V1, V2>::type NV;
    
    typedef                                                             
        typename binary_function_gate_slot<Tag, NV, V1, V2>::function_traits
            function_traits;                                            
                                                                        
    static typename function_traits::result_type                        
    function (const V1& a, const V2& b)
    { return binary_function_gate_slot<Tag, NV, V1, V2>::function(a, b); }  
};                                                                      

// For operations that is not a compare operations.

template <typename Tag, typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<Tag, V1, V2, false, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <                                                                   
        Tag,
        typename type_traits<V1>::element_type,                         
        typename type_traits<V2>::element_type                          
    > Fte;                                                              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, V1,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static V1 function (const V1& a, const V2& b)                       
    { return apply2_vec_by_vec(a, b, gfunc::by_tag<Tag>()); }
};                                                                      
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<Tag, V1, V2, false, true, Tag_class>    
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag,
        typename type_traits<V1>::element_type,
        V2
    > Fte;              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, V1,                                                            
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static V1 function (const V1& a, const V2& b)                       
    { return apply2_vec_by_val(a, b, gfunc::by_tag<Tag>()); }
};
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2, typename Tag_class>               
struct bfgs_vector_helper_1<Tag, V1, V2, true, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag, V1,
        typename type_traits<V2>::element_type
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, V2,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static V2 function (const V1& a, const V2& b)                       
    { return apply2_val_by_vec(a, b, gfunc::by_tag<Tag>()); }
};                                                                      

// For cmp function.

template <typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<function_tag::cmp, V1, V2, false, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <                                                                   
        function_tag::cmp,
        typename type_traits<V1>::element_type,                         
        typename type_traits<V2>::element_type                          
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::cmp, V1, V2, int,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect
        >                                                               
    {};                                                                 
                                                                        
    static int function (const V1& a, const V2& b)                      
    { return cmpdef_vec_by_vec(a, b); }
};                                                                      
                                                                        
                                                                        
template <typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<function_tag::cmp, V1, V2, false, true, Tag_class>  
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        function_tag::cmp,
        typename type_traits<V1>::element_type,
        V2
    > Fte;              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::cmp, V1, V2, int,                                             
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static int function (const V1& a, const V2& b)                      
    { return cmpdef_vec_by_val(a, b); }
};
                                                                        
                                                                        
template <typename V1, typename V2, typename Tag_class>             
struct bfgs_vector_helper_1<function_tag::cmp, V1, V2, true, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        function_tag::cmp, V1,
        typename type_traits<V2>::element_type
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::cmp, V1, V2, int,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static int function (const V1& a, const V2& b)                      
    { return cmpdef_val_by_vec(a, b); }
};                                                                      

// For each_cmp function.

template <typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<function_tag::each_cmp, V1, V2, false, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <                                                                   
        function_tag::each_cmp,
        typename type_traits<V1>::element_type,                         
        typename type_traits<V2>::element_type                          
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::each_cmp, V1, V2, vector<int, true>,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect
        >                                                               
    {};                                                                 
                                                                        
    static vector<int, true> function (const V1& a, const V2& b)                        
    { return elwisecmp_vec_by_vec(a, b, gfunc::cmp()); }
};                                                                      
                                                                        
                                                                        
template <typename V1, typename V2, typename Tag_class>
struct bfgs_vector_helper_1<function_tag::each_cmp, V1, V2, false, true, Tag_class> 
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        function_tag::each_cmp,
        typename type_traits<V1>::element_type,
        V2
    > Fte;              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::each_cmp, V1, V2, vector<int, true>,              
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static vector<int, true> function (const V1& a, const V2& b)                        
    { return elwisecmp_vec_by_val(a, b, gfunc::cmp()); }
};
                                                                        
                                                                        
template <typename V1, typename V2, typename Tag_class>             
struct bfgs_vector_helper_1<function_tag::each_cmp, V1, V2, true, false, Tag_class>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        function_tag::each_cmp, V1,
        typename type_traits<V2>::element_type
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            function_tag::each_cmp, V1, V2, vector<int, true>,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static vector<int, true> function (const V1& a, const V2& b)                        
    { return elwisecmp_val_by_vec(a, b); }
};                                                                      

// For each* functions.

template <typename Tag, typename V1, typename V2>
struct bfgs_vector_helper_1<Tag, V1, V2, false, false, function_tag::each_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <                                                                   
        Tag,
        typename type_traits<V1>::element_type,                         
        typename type_traits<V2>::element_type                          
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, vector<bool, true>,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect
        >                                                               
    {};                                                                 
                                                                        
    static vector<bool, true> function (const V1& a, const V2& b)                       
    {
        return eachcmp_vec_by_vec
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};                                                                      
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2>
struct bfgs_vector_helper_1<Tag, V1, V2, false, true, function_tag::each_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag,
        typename type_traits<V1>::element_type,
        V2
    > Fte;              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, vector<bool, true>,                                    
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static vector<bool, true> function (const V1& a, const V2& b)                       
    {
        return eachcmp_vec_by_val
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2>               
struct bfgs_vector_helper_1<Tag, V1, V2, true, false, function_tag::each_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag, V1,
        typename type_traits<V2>::element_type
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, vector<bool, true>,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static vector<bool, true> function (const V1& a, const V2& b)                       
    {
        return eachcmp_val_by_vec
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};                                                                      


// For all* functions.

template <typename Tag, typename V1, typename V2>
struct bfgs_vector_helper_1<Tag, V1, V2, false, false, function_tag::all_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <                                                                   
        Tag,
        typename type_traits<V1>::element_type,                         
        typename type_traits<V2>::element_type                          
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, bool,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect
        >                                                               
    {};                                                                 
                                                                        
    static bool function (const V1& a, const V2& b)                     
    {
        return allcmp_vec_by_vec
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};                                                                      
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2>
struct bfgs_vector_helper_1<Tag, V1, V2, false, true, function_tag::all_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag,
        typename type_traits<V1>::element_type,
        V2
    > Fte;              
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, bool,                                  
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static bool function (const V1& a, const V2& b)                     
    {
        return allcmp_vec_by_val
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};
                                                                        
                                                                        
template <typename Tag, typename V1, typename V2>               
struct bfgs_vector_helper_1<Tag, V1, V2, true, false, function_tag::all_compare>
{                                                                       
private:                                                                
                                                                        
    typedef binary_function_traits
    <
        Tag, V1,
        typename type_traits<V2>::element_type
    > Fte;
                                                                        
public:                                                                 
                                                                        
    struct function_traits :                                            
        public binary_function_traits_base                              
        <                                                               
            Tag, V1, V2, bool,
            Fte::alternates_first_argument,                             
            Fte::alternates_second_argument,                            
            Fte::has_side_effect                                        
        >                                                               
    {};                                                                 
                                                                        
    static bool function (const V1& a, const V2& b)                     
    {
        return allcmp_val_by_vec
        (
            a, b,
            gfunc::by_tag<typename function_tag::omit_each<Tag>::type>()
        );
    }
};                                                                      

// -------------------------------------------------------

template <typename Tag, typename T1, typename T2>
struct bfgs_vector_helper_2:
    public bfgs_vector_helper_1
    <
        Tag, T1, T2,
        type_traits<T2>::is_vector &&
            type_pair_traits
            <
                T1,
                typename type_traits<T2>::element_type
            >::is_convertible,
        type_traits<T1>::is_vector &&
            type_pair_traits
            <
                T2,
                typename type_traits<T1>::element_type
            >::is_convertible,
        typename function_tag::compare_category<Tag>::type
    >
{};


template <typename Tag, typename T1, typename T2>
struct bfgs_vector_helper_3:
    public bfgs_vector_helper_2
    <
        Tag,
        typename omit_const_ref<T1>::type,
        typename omit_const_ref<T2>::type
    >
{};


template <typename Tag, typename T, bool REFCNT, typename T1, typename T2>
struct binary_function_gate_slot<Tag, vector<T, REFCNT>, T1, T2>:
    public bfgs_vector_helper_3<Tag, T1, T2>
{};

template <typename Tag, typename T, bool REFCNT, typename T1, typename T2>
struct binary_function_gate_slot<Tag, const vector<T, REFCNT>, T1, T2>:
    public bfgs_vector_helper_3<Tag, T1, T2>
{};

template <typename Tag, typename T, bool REFCNT, typename T1, typename T2>
struct binary_function_gate_slot<Tag, vector<T, REFCNT>&, T1, T2>:
    public bfgs_vector_helper_3<Tag, T1, T2>
{};

template <typename Tag, typename T, bool REFCNT, typename T1, typename T2>
struct binary_function_gate_slot<Tag, const vector<T, REFCNT>&, T1, T2>:
    public bfgs_vector_helper_3<Tag, T1, T2>
{};


// WARNING! Doxygen fails on the following fragment. We turn-off it from doxygen processing.
#ifndef DOXYGEN_SHOULD_SKIP_THIS


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_1_PARAMS  typename T1, bool REFCNT1
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_1_TYPE    const vector<T1, REFCNT1>&
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_2_PARAMS  typename T2, bool REFCNT2
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_2_TYPE    const vector<T2, REFCNT2>&


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS    typename T3
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE      const T3&
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA   ,   

ARAGELI_ALL_BINARY_ARITHM_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_LOGIC_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_CMP_MIXGATE
ARAGELI_ALL_EACH_ALL_CMP_FUNCTIONS_MIXGATE

#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OWNER_COMMA   ,

ARAGELI_ALL_BINARY_ARITHM_FUNCTIONS_SELF_MIXGATE
ARAGELI_ALL_BINARY_LOGIC_FUNCTIONS_SELF_MIXGATE
ARAGELI_ALL_BINARY_CMP_SELF_MIXGATE
ARAGELI_ALL_EACH_ALL_CMP_FUNCTIONS_SELF_MIXGATE

#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OWNER_COMMA


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE      const big_int&
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA   

ARAGELI_ALL_BINARY_ARITHM_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_LOGIC_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_CMP_MIXGATE
ARAGELI_ALL_EACH_ALL_CMP_FUNCTIONS_MIXGATE

#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS    typename T3, typename I3, bool REFCNT3
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE      const sparse_polynom<T3, I3, REFCNT3>
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA   ,

ARAGELI_ALL_BINARY_ARITHM_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_LOGIC_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_CMP_MIXGATE
ARAGELI_ALL_EACH_ALL_CMP_FUNCTIONS_MIXGATE

#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA


#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS    typename T
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE      const rational<T>&
#define ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA   ,

ARAGELI_ALL_BINARY_ARITHM_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_LOGIC_FUNCTIONS_MIXGATE
ARAGELI_ALL_BINARY_CMP_MIXGATE
ARAGELI_ALL_EACH_ALL_CMP_FUNCTIONS_MIXGATE

#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_2_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_2_TYPE
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OTHER_TYPE
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_OTHER_COMMA


#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_1_PARAMS
#undef ARAGELI_BINARY_FUNCTION_MIXGATE_OWNER_1_TYPE



#endif  // #ifndef DOXYGEN_SHOULD_SKIP_THIS



template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename T1_factory
>
T1 dotprod
(
    const vector<T1, REFCNT1>& a,
    const vector<T2, REFCNT2>& b,
    const T1_factory& t1fctr
);


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline T1 dotprod
(
    const vector<T1, REFCNT1>& a,
    const vector<T2, REFCNT2>& b
)
{ return dotprod(a, b, factory<T1>()); }



template <typename T, bool REFCNT, typename T2, typename T2_factory>
T2& product (const vector<T, REFCNT>& x, T2& res, const T2_factory& t2fctr);


template <typename T, bool REFCNT, typename T2, typename T2_factory>
T2& sum (const vector<T, REFCNT>& x, T2& res, const T2_factory& t2fctr);


template <typename T, bool REFCNT, typename T2>
inline T2& product (const vector<T, REFCNT>& x, T2& res)
{ return product(x, res, factory<T2>()); }


template <typename T, bool REFCNT, typename T2>
inline T2& sum (const vector<T, REFCNT>& x, T2& res)
{ return sum(x, res, factory<T2>()); }

//template <typename T, bool REFCNT, typename T_factory>
//inline T product (const vector<T, REFCNT>& x, const T_factory& tfctr)
//{
//  T res;
//  return product(x, res, tfctr);
//}
//
//template <typename T, bool REFCNT, typename T_factory>
//inline T sum (const vector<T, REFCNT>& x, const T_factory& tfctr)
//{
//  T res;
//  return sum(x, res, tfctr);
//}


template <typename T, bool REFCNT>
inline T product (const vector<T, REFCNT>& x)
{
    T res;
    return product(x, res, factory<T>());
}

template <typename T, bool REFCNT>
inline T sum (const vector<T, REFCNT>& x)
{
    T res;
    return sum(x, res, factory<T>());
}


// TODO: Migrate all input/output function to vecalg equivalents (begins with vec_).
// By the way, implement them! :)

template <typename Out, typename T, bool REFCNT>
inline Out& output_list
(
    Out& out,
    const vector<T, REFCNT>& x,
    const char* first_bracket = vector_output_list_first_bracket_default,
    const char* second_bracket = vector_output_list_second_bracket_default,
    const char* separator = vector_output_list_separator_default
)
{ return vec_output_list(out, x, first_bracket, second_bracket, separator); }


template <typename In, typename T, bool REFCNT>
In& input_list
(
    In& in,
    vector<T, REFCNT>& x,
    const char* first_bracket = vector_input_list_first_bracket_default,
    const char* second_bracket = vector_input_list_second_bracket_default,
    const char* separator = vector_input_list_separator_default,
    const char* range = vector_input_list_range_default
);


template <typename T, bool REFCNT>
std::ostream& output_aligned
(
    std::ostream& out,
    const vector<T, REFCNT>& x,
    const char* left_col = vector_output_aligned_left_col_default,
    const char* right_col = vector_output_aligned_right_col_default
);


template <typename T, bool REFCNT>
inline std::ostream& vector_output_row
(
    std::ostream& out,
    const vector<T, REFCNT>& x
)
{ return output_list(out, x, "", "", " "); }


template <typename T, bool REFCNT>
inline std::ostream& vector_output_col
(
    std::ostream& out,
    const vector<T, REFCNT>& x
)
{ return output_list(out, x, "", "", "\n"); }


template <typename T, bool REFCNT>
inline std::ostream& operator<< (std::ostream& out, const vector<T, REFCNT>& x)
{ return output_list(out, x); }


template <typename T, bool REFCNT>
inline std::istream& operator>> (std::istream& in, vector<T, REFCNT>& x)
{ return input_list(in, x); }


template <typename T, bool REFCNT>
inline std::ofstream& operator<< (std::ofstream& out, const vector<T, REFCNT>& x)
{ return static_cast<std::ofstream&>(output_list(out, x)); }


template <typename T, bool REFCNT>
inline std::ifstream& operator>> (std::ifstream& in, vector<T, REFCNT>& x)
{ return static_cast<std::ifstream&>(input_list(in, x)); }


template <typename T, bool REFCNT>
inline std::ostringstream& operator<< (std::ostringstream& out, const vector<T, REFCNT>& x)
{ return static_cast<std::ostringstream&>(output_list(out, x)); }


template <typename T, bool REFCNT>
inline std::istringstream& operator>> (std::istringstream& in, vector<T, REFCNT>& x)
{ return static_cast<std::istringstream&>(input_list(in, x)); }


template <typename T, bool REFCNT>
struct factory<vector<T, REFCNT> >
{
private:

    typedef vector<T, REFCNT> TTT;

public:

    static const bool is_specialized = true;
    
    static const TTT& unit ()
    {
        static const TTT unit_s(1, Arageli::unit<T>());
        return unit_s;
    }
    
    static TTT unit (const TTT& pat)
    {
        if(pat.is_empty())return unit();
        else return TTT(pat.size(), Arageli::unit<T>(pat.front()));
    }
    
    static const TTT& opposite_unit ()
    {
        static const TTT opposite_unit_s(1, Arageli::opposite_unit<T>());
        return opposite_unit_s;
    }
    
    static TTT opposite_unit (const TTT& pat)
    {
        if(pat.is_empty())return opposite_unit();
        else return TTT(pat.size(), Arageli::opposite_unit<T>(pat.front()));
    }
    
    static const TTT& null ()
    {
        static const TTT null_s(1, Arageli::null<T>());
        return null_s;
    }
    
    static TTT null (const TTT& pat)
    {
        if(pat.is_empty())return null();
        else return TTT(pat.size(), Arageli::null<T>(pat.front()));
    }

};


template <typename T, bool REFCNT>
inline vector<T, REFCNT> opposite
(const vector<T, REFCNT>& x)
{ return -x; }

template <typename T, bool REFCNT>
inline vector<T, REFCNT>& opposite
(const vector<T, REFCNT>& x, vector<T, REFCNT>* y)
{ return (*y = x).opposite(); }

template <typename T, bool REFCNT>
inline vector<T, REFCNT>& opposite
(vector<T, REFCNT>* x)
{ return x->opposite(); }

template <typename T, bool REFCNT>
inline vector<T, REFCNT> inverse
(const vector<T, REFCNT>& x)
{
    vector<T, REFCNT> t(x);
    return x.inverse();
}

template <typename T, bool REFCNT>
inline vector<T, REFCNT>& inverse
(const vector<T, REFCNT>& x, vector<T, REFCNT>* y)
{ return (*y = x).inverse(); }

template <typename T, bool REFCNT>
inline vector<T, REFCNT>& inverse
(vector<T, REFCNT>* x)
{ return x->inverse(); }


template <typename T, bool REFCNT>
inline bool is_unit (const vector<T, REFCNT>& x)
{ return x.is_unit(); }

template <typename T, bool REFCNT>
inline bool is_opposite_unit (const vector<T, REFCNT>& x)
{ return x.is_opposite_unit(); }

template <typename T, bool REFCNT>
inline bool is_null (const vector<T, REFCNT>& x)
{ return x.is_null(); }

template <typename T, bool REFCNT>
inline std::ostream& output_polynom_first
(std::ostream& out, const vector<T, REFCNT>& x)
{ return output_list(out, x); }

template <typename T, bool REFCNT>
inline std::ostream& output_polynom_internal
(std::ostream& out, const vector<T, REFCNT>& x)
{ return output_list(out << "+", x); }

template <typename T, bool REFCNT>
inline std::ostream& output_pow
(std::ostream& out, const vector<T, REFCNT>& x)
{ return output_list(out, x); }

template <typename T, bool REFCNT>
inline std::istream& input_polynom_first
(std::istream& in, vector<T, REFCNT>& x)
{ return input_list(in, x); }

template <typename T, bool REFCNT>
std::istream& input_polynom_internal
(std::istream& in, vector<T, REFCNT>& x);

template <typename T, bool REFCNT>
inline std::istream& input_pow
(std::istream& in, vector<T, REFCNT>& x)
{ return input_polynom_first(in, x); }




template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename T3, bool REFCNT3
>
void fill_subvector
(
    const vector<T1, REFCNT1>& orig,
    const vector<T2, REFCNT2>& indexes,
    vector<T3, REFCNT3>& res
)
{
    res.resize(indexes.size());

    for(typename vector<T2, REFCNT2>::size_type i = 0; i < indexes.size(); ++i)
    {
        ARAGELI_ASSERT_0(indexes[i] >= 0);
        ARAGELI_ASSERT_0(indexes[i] < orig.size());

        res[i] = orig[indexes[i]];
    }
}


//template <typename T, bool REFCNT>
//const vector<T, REFCNT>
//type_traits<vector<T, REFCNT> >::unit_s =
//  TTT(1::unit());
//
//template <typename T, bool REFCNT>
//const vector<T, REFCNT>
//type_traits<vector<T, REFCNT> >::null_s =
//  TTT(1::null());
//
//template <typename T, bool REFCNT>
//const vector<T, REFCNT>
//type_traits<vector<T, REFCNT> >::opposite_unit_s =
//  TTT(1::opposite_unit());



#define ARAGELI_VECTOR_MATH_FUNCS1_DECL(NAME)       \
    template <typename T, bool REFCNT>                  \
    vector<T, true> NAME (const vector<T, REFCNT>& x);


// @{
    
ARAGELI_VECTOR_MATH_FUNCS1_DECL(sin)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(cos)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(tan)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(sinh)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(cosh)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(tanh)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(asin)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(acos)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(atan)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(abs)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(exp)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(floor)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(ceil)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(log)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(log10)
ARAGELI_VECTOR_MATH_FUNCS1_DECL(sqrt)

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
vector<T1, REFCNT1> pow
(
    const vector<T1, REFCNT1>& a,
    const vector<T2, REFCNT2>& b
);

template
<
    typename T1, bool REFCNT1,
    typename P
>
inline vector<T1, REFCNT1> pow
(const vector<T1, REFCNT1>& a, const P& b);


// @}

#undef ARAGELI_VECTOR_MATH_FUNCS1_DECL

} // namespace Arageli


namespace std
{

#define ARAGELI_VECTOR_STD_MATH_FUNCS1(NAME)    \
    template <typename T, bool REFCNT>          \
    inline Arageli::vector<T, true> NAME        \
    (const Arageli::vector<T, REFCNT>& x)       \
    { return Arageli::NAME(x); }


// @{
    
ARAGELI_VECTOR_STD_MATH_FUNCS1(sin)
ARAGELI_VECTOR_STD_MATH_FUNCS1(cos)
ARAGELI_VECTOR_STD_MATH_FUNCS1(tan)
ARAGELI_VECTOR_STD_MATH_FUNCS1(sinh)
ARAGELI_VECTOR_STD_MATH_FUNCS1(cosh)
ARAGELI_VECTOR_STD_MATH_FUNCS1(tanh)
ARAGELI_VECTOR_STD_MATH_FUNCS1(asin)
ARAGELI_VECTOR_STD_MATH_FUNCS1(acos)
ARAGELI_VECTOR_STD_MATH_FUNCS1(atan)
ARAGELI_VECTOR_STD_MATH_FUNCS1(abs)
ARAGELI_VECTOR_STD_MATH_FUNCS1(exp)
ARAGELI_VECTOR_STD_MATH_FUNCS1(floor)
ARAGELI_VECTOR_STD_MATH_FUNCS1(ceil)
ARAGELI_VECTOR_STD_MATH_FUNCS1(log)
ARAGELI_VECTOR_STD_MATH_FUNCS1(log10)
ARAGELI_VECTOR_STD_MATH_FUNCS1(sqrt)

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline Arageli::vector<T1, REFCNT1> pow
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return Arageli::pow(a, b); }

template
<
    typename T1, bool REFCNT1,
    typename P
>
inline Arageli::vector<T1, REFCNT1> pow
(
    const Arageli::vector<T1, REFCNT1>& a,
    const P& b
)
{ return Arageli::pow(a, b); }

// @}

#undef ARAGELI_VECTOR_STD_MATH_FUNCS1


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline void swap
(
    Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b
)
{ a.swap(b); }


template <typename T1, bool REFCNT1>
inline void swap
(
    Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T1, REFCNT1>& b
)
{ a.swap(b); }


// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


// for_each

template <typename T, bool REFCNT, typename Fu>
inline Fu for_each (Arageli::vector<T, REFCNT>& x, Fu f)
{ return for_each(x.begin(), x.end(), f); }

template <typename T, bool REFCNT, typename Fu>
inline Fu for_each (const Arageli::vector<T, REFCNT>& x, Fu f)
{ return for_each(x.begin(), x.end(), f); }

// find

template <typename T, bool REFCNT, typename T1>
inline typename Arageli::vector<T, REFCNT>::iterator
find (Arageli::vector<T, REFCNT>& x, const T1& val)
{ return find(x.begin(), x.end(), val); }

template <typename T, bool REFCNT, typename T1>
inline typename Arageli::vector<T, REFCNT>::const_iterator
find (const Arageli::vector<T, REFCNT>& x, const T1& val)
{ return find(x.begin(), x.end(), val); }

// find_if

template <typename T, bool REFCNT, typename Fu>
inline typename Arageli::vector<T, REFCNT>::iterator
find_if (Arageli::vector<T, REFCNT>& x, Fu f)
{ return find_if(x.begin(), x.end(), f); }

template <typename T, bool REFCNT, typename Fu>
inline typename Arageli::vector<T, REFCNT>::const_iterator
find_if (const Arageli::vector<T, REFCNT>& x, Fu f)
{ return find_if(x.begin(), x.end(), f); }

// find_end

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
find_end
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return find_end(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
find_end
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return find_end(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
find_end
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return find_end(a.begin(), a.end(), b.begin(), b.end(), f); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
find_end
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return find_end(a.begin(), a.end(), b.begin(), b.end(), f); }

// find_first_of

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
find_first_of
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return find_first_of(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
find_first_of
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return find_first_of(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
find_first_of
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return find_first_of(a.begin(), a.end(), b.begin(), b.end(), f); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
find_first_of
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return find_first_of(a.begin(), a.end(), b.begin(), b.end(), f); }

// adjacent_find

template <typename T, bool REFCNT>
inline typename Arageli::vector<T, REFCNT>::iterator
adjacent_find (Arageli::vector<T, REFCNT>& x)
{ return adjacent_find(x.begin(), x.end()); }

template <typename T, bool REFCNT>
inline typename Arageli::vector<T, REFCNT>::const_iterator
adjacent_find (const Arageli::vector<T, REFCNT>& x)
{ return adjacent_find(x.begin(), x.end()); }

template <typename T, bool REFCNT, typename Fb>
inline typename Arageli::vector<T, REFCNT>::iterator
adjacent_find (Arageli::vector<T, REFCNT>& x, Fb f)
{ return adjacent_find(x.begin(), x.end(), f); }

template <typename T, bool REFCNT, typename Fb>
inline typename Arageli::vector<T, REFCNT>::const_iterator
adjacent_find (const Arageli::vector<T, REFCNT>& x, Fb f)
{ return adjacent_find(x.begin(), x.end(), f); }

// count

template <typename T, bool REFCNT, typename T1>
inline typename Arageli::vector<T, REFCNT>::difference_type
count (const Arageli::vector<T, REFCNT>& x, const T1& val)
{ return count(x.begin(), x.end(), val); }

// count_if

template <typename T, bool REFCNT, typename Fu>
inline typename Arageli::vector<T, REFCNT>::difference_type
count_if (const Arageli::vector<T, REFCNT>& x, Fu f)
{ return count_if(x.begin(), x.end(), f); }

// mismatch

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::const_iterator,
        typename Arageli::vector<T2, REFCNT2>::const_iterator
    >
mismatch
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin()
    );
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::const_iterator,
        typename Arageli::vector<T2, REFCNT2>::const_iterator
    >
mismatch
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin(), f
    );
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::const_iterator,
        typename Arageli::vector<T2, REFCNT2>::iterator
    >
mismatch
(
    const Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin()
    );
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::const_iterator,
        typename Arageli::vector<T2, REFCNT2>::iterator
    >
mismatch
(
    const Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin(), f
    );
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::iterator,
        typename Arageli::vector<T2, REFCNT2>::const_iterator
    >
mismatch
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin()
    );
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline
    pair
    <
        typename Arageli::vector<T1, REFCNT1>::iterator,
        typename Arageli::vector<T2, REFCNT2>::const_iterator
    >
mismatch
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{
    return mismatch
    (
        a.begin(), a.begin() + min(a.size(), b.size()),
        b.begin(), f
    );
}

// equal

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline bool equal
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return a == b; }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline bool equal
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{
    if(a.size() != b.size())return false;
    return equal(a.begin(), a.end(), b.begin(), f);
}

// search

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
search
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return search(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
search
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return search(a.begin(), a.end(), b.begin(), b.end(), f); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
search
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b
)
{ return search(a.begin(), a.end(), b.begin(), b.end()); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
search
(
    Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Fb f
)
{ return search(a.begin(), a.end(), b.begin(), b.end(), f); }

// search_n

template
<
    typename T1, bool REFCNT1,
    typename Size, typename T
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
search
(
    const Arageli::vector<T1, REFCNT1>& a,
    Size count, const T& value
)
{ return search_n(a.begin(), a.end(), count, value); }


template
<
    typename T1, bool REFCNT1,
    typename Size, typename T, typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
search
(
    const Arageli::vector<T1, REFCNT1>& a,
    Size count, const T& value, Fb f
)
{ return search_n(a.begin(), a.end(), count, value, f); }


template
<
    typename T1, bool REFCNT1,
    typename Size, typename T
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
search
(
    Arageli::vector<T1, REFCNT1>& a,
    Size count, const T& value
)
{ return search_n(a.begin(), a.end(), count, value); }


template
<
    typename T1, bool REFCNT1,
    typename Size, typename T, typename Fb
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
search
(
    Arageli::vector<T1, REFCNT1>& a,
    Size count, const T& value, Fb f
)
{ return search_n(a.begin(), a.end(), count, value, f); }

// copy

template
<
    typename T1, bool REFCNT1,
    typename Out
>
inline Out copy
(
    const Arageli::vector<T1, REFCNT1>& a,
    Out out
)
{ return copy(a.begin(), a.end(), out); }

// copy_backward

template
<
    typename T1, bool REFCNT1,
    typename Out
>
inline Out copy_backward
(
    const Arageli::vector<T1, REFCNT1>& a,
    Out out
)
{ return copy_backward(a.begin(), a.end(), out); }

// transform

template <typename T1, bool REFCNT1, typename Fu>
inline void transform (Arageli::vector<T1, REFCNT1>& a, Fu f)
{ return transform(a.begin(), a.end(), a.begin(), f); }



template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fu
>
inline void transform
(
    const Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b,
    Fu f
)
{
    ARAGELI_ASSERT_0(a.size() <= b.size());
    return transform(a.begin(), a.end(), b.begin(), f);
}


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename T3, bool REFCNT3,
    typename Fb
>
inline void transform
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Arageli::vector<T3, REFCNT3>& c,
    Fb f
)
{
    ARAGELI_ASSERT_0(a.size() <= b.size() && a.size() <= c.size());
    return transform(a.begin(), a.end(), b.begin(), c.begin(), f);
}

// replace

template
<
    typename T1, bool REFCNT1,
    typename T2
>
inline void replace
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& oldv, const T2& newv  // WARNING! Type of oldv must not be
                                    // equal to type of newv.
)
{ replace(a.begin(), a.end(), oldv, newv); }

// replace_if

template
<
    typename T1, bool REFCNT1,
    typename Fu, typename T2
>
inline void replace_if
(
    Arageli::vector<T1, REFCNT1>& a,
    Fu f, const T2& newv
)
{ replace_if(a.begin(), a.end(), f, newv); }

// replace_copy

template
<
    typename T1, bool REFCNT1,
    typename Out, typename T2
>
inline Out replace_copy
(
    Arageli::vector<T1, REFCNT1>& a,
    Out out,
    const T2& oldv, const T2& newv  // WARNING! Type of oldv must not be
                                    // equal to type of newv.
)
{ return replace_copy(a.begin(), a.end(), out, oldv, newv); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename T3
>
inline void replace_copy
(
    Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b,
    const T3& oldv, const T3& newv  // WARNING! Type of oldv must not be
                                    // equal to type of newv.
)
{
    ARAGELI_ASSERT_0(a.size() <= b.size());
    replace_copy(a.begin(), a.end(), b.begin(), oldv, newv);
}

// replace_copy_if

template
<
    typename T1, bool REFCNT1,
    typename Out, typename Fu, typename T2
>
inline Out replace_copy_if
(
    Arageli::vector<T1, REFCNT1>& a,
    Out out,
    Fu f, const T2& newv
)
{ return replace_copy_if(a.begin(), a.end(), out, f, newv); }


template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Fu, typename T3
>
inline void replace_copy_if
(
    Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b,
    Fu f, const T3& newv
)
{
    ARAGELI_ASSERT_0(a.size() <= b.size());
    replace_copy_if(a.begin(), a.end(), b.begin(), f, newv);
}

// fill

template
<
    typename T1, bool REFCNT1,
    typename T2
>
inline void fill
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ fill(a.begin(), a.end(), v); }

// generate

template
<
    typename T1, bool REFCNT1,
    typename Fn
>
inline void generate
(
    Arageli::vector<T1, REFCNT1>& a,
    Fn f
)
{ generate(a.begin(), a.end(), f); }

// remove

template
<
    typename T1, bool REFCNT1,
    typename T2
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
remove
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ return remove(a.begin(), a.end(), v); }

// remove_if

template
<
    typename T1, bool REFCNT1,
    typename Fu
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
remove_if
(
    Arageli::vector<T1, REFCNT1>& a,
    Fu f
)
{ return remove_if(a.begin(), a.end(), f); }

// remove_copy

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Out
>
inline Out remove_copy
(
    const Arageli::vector<T1, REFCNT1>& a,
    Out out, const T2& v
)
{ return remove_copy(a.begin(), a.end(), out, v); }


// remove_copy_if

template
<
    typename T1, bool REFCNT1,
    typename Fu, typename Out
>
inline Out remove_copy
(
    const Arageli::vector<T1, REFCNT1>& a,
    Out out, Fu f
)
{ return remove_copy_if(a.begin(), a.end(), out, f); }

// unique

template <typename T1, bool REFCNT1>
inline typename Arageli::vector<T1, REFCNT1>::iterator
unique (Arageli::vector<T1, REFCNT1>& a)
{ return unique(a.begin(), a.end()); }

template <typename T1, bool REFCNT1, typename Fb>
inline typename Arageli::vector<T1, REFCNT1>::iterator
unique (Arageli::vector<T1, REFCNT1>& a, Fb f)
{ return unique(a.begin(), a.end(), f); }

// unique_copy

template
<
    typename T1, bool REFCNT1,
    typename Out
>
inline Out unique_copy
(const Arageli::vector<T1, REFCNT1>& a, Out out)
{ return unique_copy(a.begin(), a.end(), out); }


template
<
    typename T1, bool REFCNT1,
    typename Out, typename Fu
>
inline Out unique_copy
(const Arageli::vector<T1, REFCNT1>& a, Out out, Fu f)
{ return unique_copy(a.begin(), a.end(), out, f); }

// reverse

template <typename T1, bool REFCNT1>
inline void reverse (Arageli::vector<T1, REFCNT1>& a)
{ reverse(a.begin(), a.end()); }

// reverse_copy

template <typename T1, bool REFCNT1, typename Out>
inline Out reverse_copy (const Arageli::vector<T1, REFCNT1>& a, Out out)
{ return reverse_copy(a.begin(), a.end(), out); }

// rotate

template <typename T1, bool REFCNT1>
inline void rotate
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle
)
{ rotate(a.begin(), middle, a.end()); }

template <typename T1, bool REFCNT1>
inline void rotate
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle
)
{ rotate(a.begin(), a.begin() + middle, a.end()); }

// rotate_copy

template <typename T1, bool REFCNT1, typename Out>
inline Out rotate
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle,
    Out out
)
{ return rotate_copy(a.begin(), middle, a.end(), out); }

template <typename T1, bool REFCNT1, typename Out>
inline Out rotate
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle,
    Out out
)
{ rotate_copy(a.begin(), a.begin() + middle, a.end(), out); }

// random_shuffle

template <typename T1, bool REFCNT1>
inline void random_shuffle (Arageli::vector<T1, REFCNT1>& a)
{ random_shuffle(a.begin(), a.end()); }

template <typename T1, bool REFCNT1, typename Rand>
inline void random_shuffle
(Arageli::vector<T1, REFCNT1>& a, Rand r)
{ random_shuffle(a.begin(), a.end(), r); }

// partition

template <typename T1, bool REFCNT1, typename Fu>
inline typename Arageli::vector<T1, REFCNT1>::iterator
partition (Arageli::vector<T1, REFCNT1>& a, Fu f)
{ return partition(a.begin(), a.end(), f); }

// stable_partition

template <typename T1, bool REFCNT1, typename Fu>
inline typename Arageli::vector<T1, REFCNT1>::iterator
stable_partition (Arageli::vector<T1, REFCNT1>& a, Fu f)
{ return stable_partition(a.begin(), a.end(), f); }

// sort

template <typename T1, bool REFCNT1>
inline void sort (Arageli::vector<T1, REFCNT1>& a)
{ sort(a.begin(), a.end()); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void sort (Arageli::vector<T1, REFCNT1>& a, Cmp cmp)
{ sort(a.begin(), a.end(), cmp); }

// stable_sort

template <typename T1, bool REFCNT1>
inline void stable_sort (Arageli::vector<T1, REFCNT1>& a)
{ stable_sort(a.begin(), a.end()); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void stable_sort (Arageli::vector<T1, REFCNT1>& a, Cmp cmp)
{ stable_sort(a.begin(), a.end(), cmp); }

// partial_sort

template <typename T1, bool REFCNT1>
inline void partial_sort
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle
)
{ partial_sort(a.begin(), middle, a.end()); }

template <typename T1, bool REFCNT1>
inline void partial_sort
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle
)
{ partial_sort(a.begin(), a.begin() + middle, a.end()); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void partial_sort
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle,
    Cmp cmp
)
{ partial_sort(a.begin(), middle, a.end(), cmp); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void partial_sort
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle,
    Cmp cmp
)
{ partial_sort(a.begin(), a.begin() + middle, a.end(), cmp); }

// partial_sort_copy

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
inline typename Arageli::vector<T2, REFCNT2>::iterator
partial_sort_copy
(
    const Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b
)
{ partial_sort_copy(a.begin(), a.end(), b.begin(), b.end()); }

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Cmp
>
inline typename Arageli::vector<T2, REFCNT2>::iterator
partial_sort_copy
(
    const Arageli::vector<T1, REFCNT1>& a,
    Arageli::vector<T2, REFCNT2>& b,
    Cmp cmp
)
{ partial_sort_copy(a.begin(), a.end(), b.begin(), b.end(), cmp); }

// nth_element

template <typename T1, bool REFCNT1>
inline void nth_element
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator nth
)
{ nth_element(a.begin(), nth, a.end()); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void nth_element
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator nth,
    Cmp cmp
)
{ nth_element(a.begin(), nth, a.end(), cmp); }

template <typename T1, bool REFCNT1>
inline void nth_element
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type nth
)
{ nth_element(a.begin(), a.begin() + nth, a.end()); }

template <typename T1, bool REFCNT1, typename Cmp>
inline void nth_element
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type nth,
    Cmp cmp
)
{ nth_element(a.begin(), a.begin() + nth, a.end(), cmp); }

// lower_bound

template <typename T1, bool REFCNT1, typename T2>
inline typename Arageli::vector<T1, REFCNT1>::iterator
lower_bound
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ lower_bound(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
lower_bound
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ lower_bound(a.begin(), a.begin(), v, cmp); }

template <typename T1, bool REFCNT1, typename T2>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
lower_bound
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ lower_bound(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
lower_bound
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ lower_bound(a.begin(), a.begin(), v, cmp); }

// upper_bound

template <typename T1, bool REFCNT1, typename T2>
inline typename Arageli::vector<T1, REFCNT1>::iterator
upper_bound
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ upper_bound(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline typename Arageli::vector<T1, REFCNT1>::iterator
upper_bound
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ upper_bound(a.begin(), a.begin(), v, cmp); }

template <typename T1, bool REFCNT1, typename T2>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
upper_bound
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ upper_bound(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline typename Arageli::vector<T1, REFCNT1>::const_iterator
upper_bound
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ upper_bound(a.begin(), a.begin(), v, cmp); }

// equal_range

template <typename T1, bool REFCNT1, typename T2>
inline
pair
<
    typename Arageli::vector<T1, REFCNT1>::iterator,
    typename Arageli::vector<T1, REFCNT1>::iterator
>
equal_range
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ equal_range(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline
pair
<
    typename Arageli::vector<T1, REFCNT1>::iterator,
    typename Arageli::vector<T1, REFCNT1>::iterator
>
equal_range
(
    Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ equal_range(a.begin(), a.begin(), v, cmp); }

template <typename T1, bool REFCNT1, typename T2>
inline
pair
<
    typename Arageli::vector<T1, REFCNT1>::const_iterator,
    typename Arageli::vector<T1, REFCNT1>::const_iterator
>
equal_range
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v
)
{ equal_range(a.begin(), a.begin(), v); }

template
<
    typename T1, bool REFCNT1,
    typename T2, typename Cmp
>
inline
pair
<
    typename Arageli::vector<T1, REFCNT1>::const_iterator,
    typename Arageli::vector<T1, REFCNT1>::const_iterator
>
equal_range
(
    const Arageli::vector<T1, REFCNT1>& a,
    const T2& v, Cmp cmp
)
{ equal_range(a.begin(), a.begin(), v, cmp); }

// binary_search

template <typename T, bool REFCNT, typename T1>
inline bool binary_search
(const Arageli::vector<T, REFCNT>& x, const T1& val)
{ return binary_search(x.begin(), x.end(), val); }

template
<
    typename T, bool REFCNT,
    typename T1, typename Cmp
>
inline bool binary_search
(const Arageli::vector<T, REFCNT>& x, const T1& val, Cmp cmp)
{ return binary_search(x.begin(), x.end(), val, cmp); }

// merge

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Out
>
inline Out merge
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Out out
)
{ merge(a.begin(), a.end(), b.begin(), b.end(), out); }

template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename Out, typename Cmp
>
inline Out merge
(
    const Arageli::vector<T1, REFCNT1>& a,
    const Arageli::vector<T2, REFCNT2>& b,
    Out out, Cmp cmp
)
{ merge(a.begin(), a.end(), b.begin(), b.end(), out, cmp); }

// inplace_merge

template <typename T1, bool REFCNT1, typename Out>
inline Out inplace_merge
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle
)
{ inplace_merge(a.begin(), middle, a.end()); }

template
<
    typename T1, bool REFCNT1,
    typename Out, typename Cmp
>
inline Out inplace_merge
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::iterator middle,
    Cmp cmp
)
{ inplace_merge(a.begin(), middle, a.end(), cmp); }

template <typename T1, bool REFCNT1, typename Out>
inline Out inplace_merge
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle
)
{ inplace_merge(a.begin(), a.begin() + middle, a.end()); }

template
<
    typename T1, bool REFCNT1,
    typename Out, typename Cmp
>
inline Out inplace_merge
(
    Arageli::vector<T1, REFCNT1>& a,
    typename Arageli::vector<T1, REFCNT1>::difference_type middle,
    Cmp cmp
)
{ inplace_merge(a.begin(), a.begin() + middle, a.end(), cmp); }


// WARNING. Implementation of all other standard algorithm for vector
// must be here. Those are 25.3.5--25.3.9.



}


#ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
    #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_VECTOR
    #include "vector.cpp"
    #undef  ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_VECTOR
#endif


#endif  //  #ifndef _ARAGELI_vector_hpp_

---