BCP_vector_general.hpp

Go to the documentation of this file.

// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.

//##############################################################################

template <class T> inline void BCP_vec<T>::destroy(iterator pos)
{
        pos->~T();
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::destroy_range(iterator first, iterator last)
{
        while (first != last) {
                (--last)->~T();
        }
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::construct(iterator pos)
{
        ::new(static_cast<void*>(pos)) T();
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::construct(iterator pos, const_reference x)
{
        ::new(static_cast<void*>(pos)) T(x);
}

//##############################################################################
template <class T> inline typename BCP_vec<T>::iterator
BCP_vec<T>::allocate(size_t len)
{
        return static_cast<iterator>(::operator new(len * sizeof(T)));
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::deallocate()
{
        if (start) {
                destroy_range(start, finish);
                ::operator delete(start);
        }
}
//------------------------------------------------------------------------------
template <class T> void BCP_vec<T>::insert_aux(iterator position, const_reference x)
{
        if (finish != end_of_storage) {
                construct(finish);
                std::copy_backward(position, finish - 1, finish);
                *position = x;
                ++finish;
        } else {
                const size_t len = (2*size() + 0x100);
                iterator tmp = allocate(len);
                iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
                construct(tmp_finish++, x);
                tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
                deallocate();
                start = tmp;
                finish = tmp_finish;
                end_of_storage = tmp + len;
        }
}

//##############################################################################

template <class T> BCP_vec<T>::BCP_vec() :
        start(0), finish(0), end_of_storage(0) {}
//------------------------------------------------------------------------------
template <class T> BCP_vec<T>::BCP_vec(const BCP_vec<T>& x) :
        start(0), finish(0), end_of_storage(0)
{
        *this = x;
}
//------------------------------------------------------------------------------
template <class T>
BCP_vec<T>::BCP_vec(const size_t n, const_reference value) :
        start(0), finish(0), end_of_storage(0)
{
        if (n > 0) {
                start = allocate(n);
                end_of_storage = finish = start + n;
                std::uninitialized_fill_n(start, n, value);
        }
}
//------------------------------------------------------------------------------
template <class T>
BCP_vec<T>::BCP_vec(const_iterator first, const_iterator last) :
        start(0), finish(0), end_of_storage(0)
{
        const size_t len = last - first;
        if (len > 0) {
                start = allocate(len);
                end_of_storage = finish = std::uninitialized_copy(first, last, start);
        }
}
//------------------------------------------------------------------------------
template <class T>
BCP_vec<T>::BCP_vec(const T* x, const size_t num) :
        start(0), finish(0), end_of_storage(0)
{
        if (num > 0) {
                finish = start = allocate(num);
                const T* const lastx = x + num;
                while (x != lastx) {
                        construct(finish++, *x++);
                }
                end_of_storage = finish;
        }
}

//##############################################################################

template <class T> void BCP_vec<T>::reserve(const size_t n)
{
        if (capacity() < n) {
                iterator tmp = allocate(n);
                iterator tmp_finish = std::uninitialized_copy(start, finish, tmp);
                deallocate();
                start = tmp;
                finish = tmp_finish;
                end_of_storage = start + n;
        }
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::swap(BCP_vec<T>& x)
{
        std::swap(start, x.start);
        std::swap(finish, x.finish);
        std::swap(end_of_storage, x.end_of_storage);
}
//------------------------------------------------------------------------------
template <class T> BCP_vec<T>& BCP_vec<T>::operator=(const BCP_vec<T>& x)
{
        if (&x != this) {
                const size_t x_size = x.size();
                if (x_size > capacity()) {
                        deallocate();
                        start = allocate(x_size);
                        end_of_storage = start + x_size;
                        finish = std::uninitialized_copy(x.begin(), x.end(), start);
                } else {
                        if (x_size < size()) {
                                iterator oldfinish = finish;
                                finish = std::copy(x.begin(), x.end(), start);
                                destroy_range(finish, oldfinish);
                        } else {
                                std::copy(x.begin(), x.entry(size()), start);
                                finish = std::uninitialized_copy(x.entry(size()), x.end(), finish);
                        }
                }
        }
        return *this;
}

//##############################################################################
// need the void* here, since we occasionally want to copy out of a buffer

template <class T> void BCP_vec<T>::assign(const void* x, const size_t num)
{
        if (num > capacity()){
                deallocate();
                start = allocate(num);
                end_of_storage = start + num;
        } else {
                destroy_range(start, finish);
        }
        T entry;
        finish = start;
        const char* charx = static_cast<const char*>(x);
        for (int i = num; i > 0; --i) {
                memcpy(&entry, charx, sizeof(T));
                construct(finish++, entry);
                charx += sizeof(T);
        }
}
//------------------------------------------------------------------------------
template <class T> void BCP_vec<T>::insert(iterator position,
                                                                                   const void* first, const size_t n)
{
        if (n == 0) return;
        T entry;
        const char* charx = static_cast<const char*>(first);
        if ((size_t) (end_of_storage - finish) >= n) {
                const size_t to_move = finish - position;
                if (to_move <= n) {
                        std::uninitialized_copy(position, finish, position + n);
                        finish += n;
                        size_t i = n;
                        for ( ; i > to_move; --i) {
                                memcpy(&entry, charx, sizeof(T));
                                construct(position++, entry);
                                charx += sizeof(T);
                        }
                        for ( ; i > 0; --i) {
                                memcpy(&entry, charx, sizeof(T));
                                *position++ = entry; 
                                charx += sizeof(T);
                        }
                } else {
                        std::uninitialized_copy(finish - n, finish, finish);
                        std::copy_backward(position, finish - n, finish);
                        finish += n;
                        for (int i = n; i > 0; --i) {
                                memcpy(&entry, charx, sizeof(T));
                                *position++ = entry; 
                                charx += sizeof(T);
                        }
                }
        } else {
                const size_t new_size = (2*size() + n);
                iterator tmp = allocate(new_size);
                iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
                for (int i = n; i > 0; --i) {
                        memcpy(&entry, charx, sizeof(T));
                        construct(tmp_finish++, entry);
                        charx += sizeof(T);
                }
                tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
                deallocate();
                start = tmp;
                finish = tmp_finish;
                end_of_storage = tmp + new_size;
        }
}
//------------------------------------------------------------------------------
template <class T> void BCP_vec<T>::insert(iterator position,
                                                                                   const_iterator first,
                                                                                   const_iterator last)
{
        if (first == last) return;
        const size_t n = last - first;
        if ((size_t) (end_of_storage - finish) >= n) {
                const size_t to_move = finish - position;
                if (to_move <= n) {
                        std::uninitialized_copy(position, finish, position + n);
                        std::copy(first, first + to_move, position);
                        std::uninitialized_copy(first + to_move, last, finish);
                } else {
                        std::uninitialized_copy(finish - n, finish, finish);
                        std::copy_backward(position, finish - n, finish);
                        std::copy(first, last, position);
                }
                finish += n;
        } else {
                const size_t new_size = (2*size() + n);
                iterator tmp = allocate(new_size);
                iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
                tmp_finish = std::uninitialized_copy(first, last, tmp_finish);
                tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
                deallocate();
                start = tmp;
                finish = tmp_finish;
                end_of_storage = tmp + new_size;
        }
}
//------------------------------------------------------------------------------
template <class T> void BCP_vec<T>::insert(iterator position, const size_t n,
                                                                                   const_reference x)
{
        if (n == 0) return;
        if ((size_t) (end_of_storage - finish) >= n) {
                const size_t to_move = finish - position;
                if (to_move <= n) {
                        std::uninitialized_copy(position, finish, position + n);
                        std::fill_n(position, to_move, x);
                        std::uninitialized_fill_n(finish, n - to_move, x);
                } else {
                        std::uninitialized_copy(finish - n, finish, finish);
                        std::copy_backward(position, finish - n, finish);
                        std::fill_n(position, n, x);
                }
                finish += n;
        } else {
                const size_t new_size = (2*size() + n);
                iterator tmp = allocate(new_size);
                iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
                std::uninitialized_fill_n(tmp_finish, n, x);
                tmp_finish += n;
                tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
                deallocate();
                start = tmp;
                finish = tmp_finish;
                end_of_storage = tmp + new_size;
        }
}
//------------------------------------------------------------------------------
template <class T> inline typename BCP_vec<T>::iterator
BCP_vec<T>::insert(iterator position, const_reference x)
{
        const size_t n = position - start;
        if (finish != end_of_storage && position == finish) {
                construct(finish++, x);
        } else {
                insert_aux(position, x);
        }
        return start + n;
}

   
//##############################################################################
template <class T> inline void BCP_vec<T>::push_back(const_reference x)
{
        if (finish != end_of_storage) {
                construct(finish++, x);
        } else
                insert_aux(finish, x);
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::unchecked_push_back(const_reference x)
{
        construct(finish++, x);
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::pop_back()
{
        destroy(--finish);
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::clear()
{
        if (start) erase(start, finish);
}
//------------------------------------------------------------------------------
template <class T> void
BCP_vec<T>::unchecked_update(const BCP_vec<int>& positions,
                                                         const BCP_vec<T>& values)
{
        if (positions.size() == 0)
                return;
        const_iterator val = values.begin();
        BCP_vec<int>::const_iterator pos = positions.begin();
        const BCP_vec<int>::const_iterator lastpos = positions.end();
        while (pos != lastpos)
                operator[](*pos++) = *val++;
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::update(const BCP_vec<int>& positions,
                                                                                                  const BCP_vec<T>& values)
{
        if (positions.size() != values.size())
                throw BCP_fatal_error("BCP_vec::update() called with unequal sizes.\n");
        BCP_vec_sanity_check(positions.begin(), positions.end(), size());
        unchecked_update(positions, values);
}

//##############################################################################

template <class T> inline void BCP_vec<T>::keep(iterator pos)
{
        iterator oldfinish = finish;
        finish = std::copy(pos, pos + 1, start);
        destroy_range(finish, oldfinish);
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::keep(iterator first, iterator last)
{
        iterator oldfinish = finish;
        finish = std::copy(first, last, start);
        destroy_range(finish, oldfinish);
}
//------------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::keep_by_index(const BCP_vec<int>& positions)
{
        BCP_vec_sanity_check(positions.begin(), positions.end(), size());
        unchecked_keep_by_index(positions.begin(), positions.end());
}
//------------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::unchecked_keep_by_index(const BCP_vec<int>& positions)
{
        unchecked_keep_by_index(positions.begin(), positions.end());
}
//------------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::keep_by_index(BCP_vec<int>::const_iterator firstpos,
                                                  BCP_vec<int>::const_iterator lastpos)
{
        BCP_vec_sanity_check(firstpos, lastpos, size());
        unchecked_keep_by_index(firstpos, lastpos);
}
//------------------------------------------------------------------------------
template <class T> void
BCP_vec<T>::unchecked_keep_by_index(BCP_vec<int>::const_iterator firstpos,
                                                                        BCP_vec<int>::const_iterator lastpos)
{
        if (firstpos == lastpos) {
                clear();
        } else {
                iterator target = start;
                while ( firstpos != lastpos )
                        *target++ = operator[](*firstpos++);
                destroy_range(target, finish);
                finish = target;
        }
}

//##############################################################################

template <class T> inline void BCP_vec<T>::erase(iterator position)
{
        if (position + 1 != finish)
                std::copy(position + 1, finish, position);
        destroy(--finish);
}
//------------------------------------------------------------------------------
template <class T> inline void BCP_vec<T>::erase(iterator first, iterator last)
{
        iterator oldfinish = finish;
        finish = std::copy(last, finish, first);
        destroy_range(finish, oldfinish);
}
//------------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::erase_by_index(const BCP_vec<int>& positions)
{
        BCP_vec_sanity_check(positions.begin(), positions.end(), size());
        unchecked_erase_by_index(positions.begin(), positions.end());
}
//-----------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::unchecked_erase_by_index(const BCP_vec<int>& positions)
{
        unchecked_erase_by_index(positions.begin(), positions.end());
}
//------------------------------------------------------------------------------
template <class T> inline void
BCP_vec<T>::erase_by_index(BCP_vec<int>::const_iterator firstpos,
                                                   BCP_vec<int>::const_iterator lastpos)
{
        BCP_vec_sanity_check(firstpos, lastpos, size());
        unchecked_erase_by_index(firstpos, lastpos);
}
//------------------------------------------------------------------------------
template <class T> void
BCP_vec<T>::unchecked_erase_by_index(BCP_vec<int>::const_iterator firstpos,
                                                                         BCP_vec<int>::const_iterator lastpos)
{
        if (firstpos == lastpos)
                return;
        --lastpos;
        int source;
        iterator target = entry(*firstpos);
        while (firstpos != lastpos){
                source = *firstpos + 1;
                ++firstpos;
                if (*firstpos > source)
                        target = std::copy( entry(source), entry(*firstpos), target );
        }
        iterator oldfinish = finish;
        finish = std::copy( entry(*firstpos + 1), end(), target );
        destroy_range(finish, oldfinish);
}

//##############################################################################