vector.hpp

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <vector>
#include <iostream>
 
#include <ext/ostream>
 
#include <extensions/range.hpp>
 
namespace ext {
 
template < class T, class Alloc = std::allocator < T > >
class vector : public std::vector < T, Alloc > {
public:
    using std::vector< T, Alloc >::vector; // NOLINT(modernize-use-equals-default)
 
    using std::vector< T, Alloc >::operator =;
 
    using iterator = typename std::vector < T, Alloc >::iterator;
 
    using const_iterator = typename std::vector < T, Alloc >::const_iterator;
 
    using reverse_iterator = typename std::vector < T, Alloc >::reverse_iterator;
 
    using const_reverse_iterator = typename std::vector < T, Alloc >::const_reverse_iterator;
 
#ifndef __clang__
 
    vector ( ) = default;
 
    vector ( const vector & other ) = default;
 
    vector ( vector && other ) = default;
 
    vector & operator = ( vector && other ) = default;
 
    vector & operator = ( const vector & other ) = default;
#endif
    template < class Iterator >
    explicit vector ( const ext::iterator_range < Iterator > & range ) : vector ( range.begin ( ), range.end ( ) ) {
    }
 
    auto begin ( ) & {
        return std::vector < T, Alloc >::begin ( );
    }
 
    auto begin ( ) const & {
        return std::vector < T, Alloc >::begin ( );
    }
 
    auto begin ( ) && {
        return make_move_iterator ( this->begin ( ) );
    }
 
    auto end ( ) & {
        return std::vector < T, Alloc >::end ( );
    }
 
    auto end ( ) const & {
        return std::vector < T, Alloc >::end ( );
    }
 
    auto end ( ) && {
        return make_move_iterator ( this->end ( ) );
    }
 
    auto range ( ) & {
        auto endIter = end ( );
        auto beginIter = begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    auto range ( ) const & {
        auto endIter = end ( );
        auto beginIter = begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    auto range ( ) && {
        auto endIter = std::move ( * this ).end ( );
        auto beginIter = std::move ( * this ).begin ( );
        return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
    }
 
    using std::vector < T, Alloc >::insert;
 
    reverse_iterator insert ( const_reverse_iterator pos, const T & value ) {
        return reverse_iterator ( std::next ( insert ( pos.base ( ), value ) ) );
    }
 
    reverse_iterator insert ( const_reverse_iterator pos, T && value ) {
        return reverse_iterator ( std::next ( insert ( pos.base ( ), std::move ( value ) ) ) );
    }
 
    reverse_iterator insert ( const_reverse_iterator pos, size_t count, const T & value ) {
        return reverse_iterator ( std::next ( insert ( pos.base ( ), count, value ) ) );
    }
 
    template < class InputIt >
    reverse_iterator insert ( const_reverse_iterator pos, InputIt first, InputIt last ) {
        return reverse_iterator ( std::next ( insert ( pos.base ( ), first, last ) ) );
    }
 
    reverse_iterator insert ( const_reverse_iterator pos, std::initializer_list < T > ilist ) {
        return reverse_iterator ( std::next ( insert ( pos.base ( ), std::move ( ilist ) ) ) );
    }
 
    using std::vector < T, Alloc >::emplace;
 
    template < class ... Args >
    reverse_iterator emplace ( const_reverse_iterator pos, Args && ... args ) {
        return reverse_iterator ( std::next ( emplace ( pos.base ( ), std::forward < Args > ( args ) ... ) ) );
    }
 
    using std::vector < T, Alloc >::erase;
 
    iterator erase ( iterator pos ) {
        return erase ( const_iterator ( pos ) );
    }
 
    reverse_iterator erase ( reverse_iterator pos ) {
        return erase ( const_reverse_iterator ( pos ) );
    }
 
    reverse_iterator erase ( const_reverse_iterator pos ) {
        return reverse_iterator ( erase ( std::next ( pos ).base ( ) ) );
    }
 
    iterator erase ( iterator first, iterator last ) {
        return erase ( const_iterator ( first ), const_iterator ( last ) );
    }
 
    reverse_iterator erase ( reverse_iterator first, reverse_iterator last ) {
        return erase ( const_reverse_iterator ( first ), const_reverse_iterator ( last ) );
    }
 
    reverse_iterator erase ( const_reverse_iterator first, const_reverse_iterator last ) {
        return reverse_iterator ( erase ( std::next ( first ).base ( ), std::next ( last ).base ( ) ) );
    }
 
};
 
template< class T , class ... Ts >
ext::ostream& operator<<(ext::ostream& out, const ext::vector<T, Ts ...>& vector) {
    out << "[";
 
    bool first = true;
    for(const T& item : vector) {
        if(!first) out << ", ";
        first = false;
        out << item;
    }
 
    out << "]";
    return out;
}
 
/*// the same type as the ext::vector bool's internal storage type
typedef typename std::decay < decltype ( * ( std::declval < ext::vector < bool > > ( ).begin ( )._M_p ) ) >::type vectorBoolInternalType;
// the size of the ext::vector bool's internal storage type
const unsigned vectorBoolInternalTypeInBits = sizeof ( vectorBoolInternalType ) * 8;
 
// private helper for mask computation
inline vectorBoolInternalType getMask ( size_t dist ) {
    if ( dist == 0 )
        return ~ vectorBoolInternalType { };
    else
        return ( ( vectorBoolInternalType { } + 1 ) << dist ) - 1;
}*/
 
template < class ... Ts >
ext::vector < bool, Ts ... > & operator |= ( ext::vector < bool, Ts ... > & A, const ext::vector < bool, Ts ... > & B ) {
    // c++ implementation-specific
    /* A.resize ( std::max ( A.size ( ), B.size ( ) ), false );
 
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    while ( itB + 1 < B.end ( ) ) // A is longer or of the same size as B
        * ( itA._M_p ++ ) |= * ( itB._M_p ++ ); // word-at-a-time bitwise operation
 
    size_t sizeWithin = B.size ( ) % vectorBoolInternalTypeInBits;
 
    if ( itB < B.end ( ) ) {
        * ( itA._M_p ++ ) |= * ( itB._M_p ++ ) & getMask ( sizeWithin );
    }
 
    // The rest of A above the size of B can be left intact */
 
    A.resize ( std::max ( A.size ( ), B.size ( ) ), false );
 
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    for ( ; itB < B.end ( ); ++ itB, ++ itA )
        * itA = * itA | * itB;
 
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator | ( ext::vector < bool, Ts ... > A, const ext::vector < bool, Ts ... > & B ) {
    A |= B;
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > & operator &= ( ext::vector < bool, Ts ... > & A, const ext::vector < bool, Ts ... > & B ) {
    // c++ implementation-specific
    /* A.resize ( std::max ( A.size ( ), B.size ( ) ), false );
 
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    while ( itB + 1 < B.end ( ) ) { // A is longer or of the same size as B
        * ( itA._M_p ++ ) &= * ( itB._M_p ++ ); // word-at-a-time bitwise operation
    }
 
    size_t sizeWithin = B.size ( ) % vectorBoolInternalTypeInBits;
 
    if ( itB < B.end ( ) ) {
        * ( itA._M_p ++ ) &= * ( itB._M_p ++ ) & getMask ( sizeWithin );
    }
 
    while ( itA < A.end ( ) ) { // The rest of A above the size of B shall be zeroed
        * ( itA._M_p ++ ) = 0;
    }*/
 
    // c++ compilant
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    for ( ; itB < B.end ( ) && itA < A.end ( ); ++ itB, ++ itA )
        * itA = * itA & * itB;
 
    for ( ; itA < A.end ( ); ++ itA )
        * itA = false;
 
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator & ( ext::vector < bool, Ts ... > A, const ext::vector < bool, Ts ... > & B ) {
    A &= B;
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > & operator ^= ( ext::vector < bool, Ts ... > & A, const ext::vector < bool, Ts ... > & B ) {
    // c++ implementation-specific
    /* A.resize ( std::max ( A.size ( ), B.size ( ) ), false );
 
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    while ( itB + 1 < B.end ( ) ) // A is longer or of the same size as B
        * ( itA._M_p ++ ) ^= * ( itB._M_p ++ ); // word-at-a-time bitwise operation
 
    size_t sizeWithin = B.size ( ) % vectorBoolInternalTypeInBits;
 
    if ( itB < B.end ( ) ) {
        * ( itA._M_p ++ ) ^= * ( itB._M_p ++ ) & getMask ( sizeWithin );
    }
 
    while ( itA < A.end ( ) ) { // The rest of A above the size of B shall be flipped
        * ( itA._M_p ) = ~ * ( itA._M_p );
        itA._M_p ++;
    }*/
 
    // c++ compilant
    A.resize ( std::max ( A.size ( ), B.size ( ) ), false );
 
    typename ext::vector < bool, Ts ... >::iterator itA = A.begin ( );
    typename ext::vector < bool, Ts ... >::const_iterator itB = B.begin ( );
 
    for ( ; itB < B.end ( ); ++ itB, ++ itA )
        * itA = * itA ^ * itB;
 
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator ^ ( ext::vector < bool, Ts ... > A, const ext::vector < bool, Ts ... > & B ) {
    A ^= B;
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator ~ ( ext::vector < bool, Ts ... > A ) {
    A.flip ( );
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > & operator <<= ( ext::vector < bool, Ts ... > & A, size_t dist ) {
/*  if ( A.size ( ) == 0 )
        return A;
 
    size_t distBlocks = dist / vectorBoolInternalTypeInBits;
    size_t distWithin = dist % vectorBoolInternalTypeInBits;
    size_t backDist = vectorBoolInternalTypeInBits - distWithin;
 
    // shift blocks if needed
    if ( distBlocks ) {
        // simulate behavior of reverse iterator
        auto itAReverse = A.end ( ) - 1;
        auto itASource = itAReverse;
        itASource._M_p -= distBlocks;
 
        while ( itASource >= A.begin ( ) )
            * ( itAReverse._M_p -- ) = * ( itASource._M_p -- );
 
        while ( itAReverse >= A.begin ( ) )
            * ( itAReverse._M_p -- ) = 0;
    }
 
    if ( distWithin == 0 )
        return A;
 
    // shift by the rest dist
    vectorBoolInternalType bits1 { };
    vectorBoolInternalType bits2 { };
 
    // it might be more clear to iterate from the begining. However this is working nicely
    auto itA = A.begin ( );
 
    while ( itA < A.end ( ) ) {
        bits2 = * ( itA._M_p );
        * ( itA._M_p ) = * ( itA._M_p ) << distWithin | bits1 >> backDist;
        bits1 = bits2;
 
        itA._M_p ++;
    }*/
 
    // c++ compilant
    if ( dist > A.size ( ) ) {
        clear ( A );
    } else {
        typename ext::vector < bool, Ts ... >::reverse_iterator itASource = A.rbegin ( ) + dist;
        typename ext::vector < bool, Ts ... >::reverse_iterator itADest = A.rbegin ( );
 
        for ( ; itASource < A.rend ( ); ++ itASource, ++ itADest )
            * itADest = * itASource;
 
        for ( ; itADest < A.rend ( ); ++ itADest )
            * itADest = false;
    }
 
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator << ( ext::vector < bool, Ts ... > A, size_t dist ) {
    A <<= dist;
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > & operator >>= ( ext::vector < bool, Ts ... > & A, size_t dist ) {
    /*if ( A.size ( ) == 0 )
        return A;
 
    size_t distBlocks = dist / vectorBoolInternalTypeInBits;
    size_t distWithin = dist % vectorBoolInternalTypeInBits;
    size_t sizeWithin = A.size ( ) % vectorBoolInternalTypeInBits;
    size_t backDist = vectorBoolInternalTypeInBits - distWithin;
 
    // upper part of the last word in the ext::vector can contain some garbage so it needs to be cleared
    * ( ( A.end ( ) - 1 )._M_p ) &= getMask ( sizeWithin );
 
    // shift blocks if needed
    if ( distBlocks ) {
        auto itA = A.begin ( );
        auto itASource = itA;
        itASource._M_p += distBlocks;
 
        while ( itASource < A.end ( ) )
            * ( itA._M_p ++ ) = * ( itASource._M_p ++ );
 
        while ( itA < A.end ( ) )
            * ( itA._M_p ++ ) = 0;
    }
 
    if ( distWithin == 0 )
        return A;
 
    // shift by the rest dist
    vectorBoolInternalType bits1 { };
    vectorBoolInternalType bits2 { };
 
    // it might be more clear to iterate from the begining. However this is working nicely
    auto itAReverse = A.end ( ) - 1;
 
    // simulate behavior of reverse iterator
    while ( itAReverse >= A.begin ( ) ) {
        bits2 = * ( itAReverse._M_p );
        * ( itAReverse._M_p ) = * ( itAReverse._M_p ) >> distWithin | bits1 << backDist;
        bits1 = bits2;
 
        itAReverse._M_p --;
    }*/
 
    // c++ compilant
    if ( dist > A.size ( ) ) {
        clear ( A );
    } else {
        typename ext::vector < bool, Ts ... >::iterator itASource = A.begin ( ) + dist;
        typename ext::vector < bool, Ts ... >::iterator itADest = A.begin ( );
 
        for ( ; itASource < A.end ( ); ++ itASource, ++ itADest )
            * itADest = * itASource;
 
        for ( ; itADest < A.end ( ); ++ itADest )
            * itADest = false;
    }
 
    return A;
}
 
template < class ... Ts >
ext::vector < bool, Ts ... > operator >> ( ext::vector < bool, Ts ... > A, size_t dist ) {
    A >>= dist;
    return A;
}
 
template < class ... Ts >
bool any ( const ext::vector < bool, Ts ... > & v ) {
    // c++ implementation-specific
    /*typename ext::vector < bool, Ts ... >::const_iterator itV = v.begin ( );
 
    size_t sizeWithin = v.size ( ) % vectorBoolInternalTypeInBits;
 
    while ( itV + 1 < v.end ( ) )
        if ( * ( itV._M_p ++ ) != 0 )
            return true;
 
    return ( * itV._M_p & getMask ( sizeWithin ) ) != 0;*/
 
    // c++ compilant
    typename ext::vector < bool, Ts ... >::const_iterator itV = v.begin ( );
    for ( ; itV != v.end ( ); ++ itV )
        if ( * itV )
            return true;
 
    return false;
}
 
template < class ... Ts >
void fill ( ext::vector < bool, Ts ... > & v ) {
    // c++ implementation-specific
    /*typename ext::vector < bool, Ts ... >::iterator itV = v.begin ( );
 
    while ( itV < v.end ( ) )
        * ( itV._M_p ++ ) = ~ vectorBoolInternalType { };*/
 
    // c++ compilant
    typename ext::vector < bool, Ts ... >::iterator itV = v.begin ( );
    for ( ; itV != v.end ( ); ++ itV )
        * itV = true;
}
 
template < class ... Ts >
void clear ( ext::vector < bool, Ts ... > & v ) {
    // c++ implementation-specific
    /* typename ext::vector < bool, Ts ... >::iterator itV = v.begin ( );
 
    while ( itV < v.end ( ) )
        * ( itV._M_p ++ ) = 0;*/
 
    // c++ compilant
    typename ext::vector < bool, Ts ... >::iterator itV = v.begin ( );
    for ( ; itV != v.end ( ); ++ itV )
        * itV = false;
}
 
} /* namespace ext */