TDynamicArray.h

Go to the documentation of this file.

/*****************************************************************************
* Copyright (c) 2001 - 2008 Marcus Boerger.  All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library 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
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
* ========================================================================= */

/* ------------------------------------------------------------------------ */
/* Name:      TDynamicArray.h
 *
 * Requires:  
 * - Mbo.h
 * - reallocator.h
 */
/* ------------------------------------------------------------------------ */

#ifndef _TDYNAMICARRAY_H_
#define _TDYNAMICARRAY_H_

#include "Mbo.h"

#include "reallocator.h"

#if defined(_MSC_VER)
# pragma warning(push)
# pragma warning(disable: 4290) // C++ exception specification ignored except to indicate a function is not __declspec(nothrow)
#endif

namespace mbo
{

#ifndef MBO_TDA_VERIFY
# define MBO_TDA_VERIFY 1
#endif

#ifndef MBO_TDA_STL_ITERATOR
# define MBO_TDA_STL_ITERATOR 1
#endif

#if MBO_TDA_VERIFY
# define mbo_tda_throw_if_not(exception, condition)  mbo_throw_if_not(exception, condition)
#else
# define mbo_tda_throw_if_not(exception, condition)
#endif

/* \def __DEPRECATED
 * Postfix increment and decrement are marked as deprecated. However they are
 * used by the microsoft STL so we do not expose this fact to the compiler.
 */
#ifndef __DEPRECATED
# if !MBO_TDA_STL_ITERATOR && !defined(DOXYGEN) && _MSC_VER >= 1300
#  define __DEPRECATED __declspec(deprecated)
# else
#  define __DEPRECATED
# endif
#endif

template< class  __ValueType
        , class  __Allocator                = mem_reallocator<__ValueType>
# if defined(_MSC_VER) && _MSC_VER < 1300
        , size_t  __MinSize                 = 8
        , size_t  __Append                  = 8
#else
        , typename __Allocator::size_type __MinSize  = 8
        , typename __Allocator::size_type __Append   = 8
# endif
        >
class TDynamicArray
{
public:

    typedef TDynamicArray<__ValueType, __Allocator, __MinSize, __Append>  _MyType;         
    typedef typename __Allocator                  allocator;               
    typedef typename __Allocator::size_type       size_type;               
    typedef typename __Allocator::value_type      value_type;              
    typedef typename __Allocator::reference       reference;               
    typedef typename __Allocator::const_reference const_reference;         
    typedef typename __Allocator::pointer         pointer;                 
    typedef typename __Allocator::const_pointer   const_pointer;           
    typedef typename __Allocator::difference_type difference_type;         
    class iterator; // forward declaration

    class const_iterator
#if MBO_TDA_STL_ITERATOR
# if !defined(_MSC_VER) || _MSC_VER >= 1300 || defined(_STLPORT_VERSION)
        : public std::iterator<std::random_access_iterator_tag, value_type, difference_type, const_pointer, const_reference>
# else
        : public std::_Ranit<value_type, difference_type>
# endif
#endif
    {
    public:

        explicit inline const_iterator(const _MyType & array, size_type pos = 0)
            : m_array(array), m_pos(pos)
        {
        }

        inline const_iterator(const const_iterator& oth)
            : m_array(oth.m_array), m_pos(oth.m_pos)
        {
        }

        inline const_iterator(const iterator& oth)
            : m_array(oth.m_array), m_pos(oth.m_pos)
        {
        }

        inline const_reference operator * () const
        {
            return m_array[m_pos];
        }

        inline const_pointer operator -> () const
        {
            return &(operator*());
        }

        inline const_iterator & operator ++ ()
        {
            ++m_pos;
            return *this;
        }

        inline __DEPRECATED const_iterator operator ++ (int)
        {
            /* postfix operator return an unchanged copy prior to the operaration */
            return const_iterator(m_array, m_pos++);
        }

        inline const_iterator & operator -- ()
        {
            --m_pos;
            return *this;
        }

        inline __DEPRECATED const_iterator operator -- (int)
        {
            /* postfix operator return an unchanged copy prior to the operaration */
            return const_iterator(m_array, m_pos--);
        }

        inline bool operator == (const const_iterator &rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos == rhs.m_pos;
        }

        inline bool operator != (const const_iterator &rhs) const __THROWS(logic_error)
        {
            return !operator == (rhs);
        }

        inline const_iterator & operator = (const const_iterator & rhs)
        {
            new (this) const_iterator(rhs.m_array, rhs.m_pos);
            return *this;
        }

        inline const_reference operator [] (size_type pos) const __THROWS(out_of_range)
        {
            return m_array[pos];
        }

        inline difference_type operator - (const const_iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos - rhs.m_pos;
        }

        inline const_iterator & operator -= (difference_type diff) __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos >= diff);
            m_pos -= diff;
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            return *this;
        }

        inline const_iterator & operator += (difference_type diff) __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos + diff >= m_pos && m_pos + diff >= diff && m_pos + diff <= m_array.size());
            m_pos += diff;
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(default: 4018)
#endif
            return *this;
        }

        inline const_iterator operator - (difference_type diff) const __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos >= diff);
            return const_iterator(m_array, m_pos - diff);
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
        }

        inline const_iterator operator + (difference_type diff) const __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos + diff >= m_pos && m_pos + diff >= diff && m_pos + diff <= m_array.size());
            return const_iterator(m_array, m_pos + diff);
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(default: 4018)
#endif
        }

        inline bool operator < (const const_iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos < rhs.m_pos;
        }

        inline bool operator > (const const_iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos > rhs.m_pos;
        }

        inline bool operator <= (const const_iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos <= rhs.m_pos;
        }

        inline bool operator >= (const const_iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhsrhs.m_array);
            return m_pos >= rhs.m_pos;
        }

    protected:
        const _MyType &   m_array; 
        size_type         m_pos;  
    };

    class iterator
#if MBO_TDA_STL_ITERATOR
# if !defined(_MSC_VER) || _MSC_VER >= 1300 || defined(_STLPORT_VERSION)
        : public std::iterator<std::random_access_iterator_tag, value_type, difference_type, pointer, reference>
# else
        : public std::_Ranit<value_type, difference_type>
# endif
#endif
    {
    public:

        explicit inline iterator(_MyType & array, size_type pos = 0)
            : m_array(array), m_pos(pos)
        {
        }

        explicit inline iterator(const iterator& oth)
            : m_array(oth.m_array), m_pos(oth.m_pos)
        {
        }

        operator const_iterator()
        {
            return const_iterator(m_array, m_pos);
        }

        inline const_reference operator * () const
        {
            return m_array[m_pos];
        }

        inline reference operator * ()
        {
            return m_array[m_pos];
        }

        inline const_pointer operator -> () const
        {
            return &(operator*());
        }

        inline pointer operator -> ()
        {
            return &(operator*());
        }

        inline iterator & operator ++ ()
        {
            ++m_pos;
            return *this;
        }

        inline __DEPRECATED iterator operator ++ (int)
        {
            /* postfix operator return an unchanged copy prior to the operaration */
            return iterator(m_array, m_pos++);
        }

        inline iterator & operator -- ()
        {
            --m_pos;
            return *this;
        }

        inline __DEPRECATED iterator operator -- (int)
        {
            /* postfix operator return an unchanged copy prior to the operaration */
            return iterator(m_array, m_pos--);
        }

        inline bool operator == (const iterator &rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos == rhs.m_pos;
        }

        inline bool operator != (const iterator &rhs) const __THROWS(logic_error)
        {
            return !operator == (rhs);
        }

        inline iterator & operator = (const iterator & rhs)
        {
            new (this) iterator(rhs.m_array, rhs.m_pos);
            return *this;
        }

        inline reference operator [] (size_type pos) __THROWS(out_of_range)
        {
            return m_array[pos];
        }

        inline const_reference operator [] (size_type pos) const __THROWS(out_of_range)
        {
            return m_array[pos];
        }

        inline difference_type operator - (const iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos - rhs.m_pos;
        }

        inline iterator & operator -= (difference_type diff) __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos >= diff);
            m_pos -= diff;
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            return *this;
        }

        inline iterator & operator += (difference_type diff) __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos + diff >= m_pos && m_pos + diff >= diff && m_pos + diff <= m_array.size());
            m_pos += diff;
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(default: 4018)
#endif
            return *this;
        }

        inline iterator operator - (difference_type diff) const __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos >= diff);
            return iterator(m_array, m_pos - diff);
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(default: 4018)
#endif
        }

        inline iterator operator + (difference_type diff) const __THROWS(logic_error)
        {
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(disable: 4018) // '>=' : signed/unsigned mismatch
#endif
            mbo_tda_throw_if_not(logic_error, m_pos + diff >= m_pos && m_pos + diff >= diff && m_pos + diff <= m_array.size());
            return iterator(m_array, m_pos + diff);
#if defined(_MSC_VER) && _MSC_VER >= 1300
# pragma warning(default: 4018)
#endif
        }

        inline bool operator < (const iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos < rhs.m_pos;
        }

        inline bool operator > (const iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos > rhs.m_pos;
        }

        inline bool operator <= (const iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos <= rhs.m_pos;
        }

        inline bool operator >= (const iterator & rhs) const __THROWS(logic_error)
        {
            mbo_tda_throw_if_not(logic_error, &m_array == &rhs.m_array);
            return m_pos >= rhs.m_pos;
        }

    protected:
        _MyType &         m_array; 
        size_type         m_pos;  
    };

#if MBO_TDA_STL_ITERATOR

# if !defined(_MSC_VER) || _MSC_VER >= 1300
    typedef std::reverse_iterator<iterator> reverse_iterator;
# else
    typedef std::reverse_iterator<iterator, value_type, reference, pointer, difference_type> reverse_iterator;
# endif
                                 

# if !defined(_MSC_VER) || _MSC_VER >= 1300
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
# else
    typedef std::reverse_iterator<const_iterator, value_type, const_reference, const_pointer, difference_type> const_reverse_iterator;
# endif
#endif

    explicit TDynamicArray(
            size_type nMinSize = __MinSize, 
            size_type nAppend  = __Append, 
            size_type nMaxSize = 0
        ) __THROWS(bad_alloc)
        : m_alloc()
        , m_nSize(0)
        , m_nCapacity(nMinSize)
        , m_nAppend(  nAppend)
        , m_nMaxSize( nMaxSize ? nMaxSize : m_alloc.max_size())
        , m_acValues(0L)
    {
        if (m_nCapacity)
        {
            reserve(m_nCapacity);
        }
        mbo_tda_throw_if_not(bad_alloc, !m_nCapacity || m_acValues);
    }

    TDynamicArray(const TDynamicArray & oth) __THROWS(bad_alloc)
        : m_alloc(oth.m_alloc)
        , m_nSize(0)
        , m_nCapacity(0)
        , m_nAppend(  oth.append())
        , m_nMaxSize( oth.max_size())
        , m_acValues(0L)
    {
        assign(oth.begin(), oth.end());
    }

    TDynamicArray & operator = (const TDynamicArray & oth) __THROWS(bad_alloc)
    {
        assign(oth.begin(), oth.end());
        return *this;
    }

    virtual ~TDynamicArray() __THROWS(logic_error)
    {
        clear();
        mbo_tda_throw_if_not(logic_error, !m_acValues);
    }

    inline size_type size() const
    {
        return m_nSize;
    }

    inline bool empty() const
    {
        return size() == 0;
    }

    inline size_type capacity() const
    {
        return m_nCapacity;
    }

    size_type max_size() const
    {
        return m_nMaxSize;
    }

    inline size_type append() const
    {
        return m_nAppend;
    }

    inline const_reference operator [] (_IN size_type index) const __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, index < m_nSize);
        return m_acValues[index];
    }

    inline reference operator [] (_IN size_type index) __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, index < m_nSize);
        return m_acValues[index];
    }

    inline const_reference at(_IN size_type index) const __THROWS(out_of_range)
    {
        return operator [] (index);
    }

    inline reference at(_IN size_type index) __THROWS(out_of_range)
    {
        return operator [] (index);
    }

    inline const_reference back() const __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);
        return m_acValues[m_nSize-1];
    }

    inline reference back() __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);
        return m_acValues[m_nSize-1];
    }

    inline const_reference front() const __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);
        return m_acValues[0];
    }

    inline reference front() __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);
        return m_acValues[0];
    }

    inline void push_front(_IN const_reference value) __THROW2(bad_alloc, overflow_error)
    {
        check_resize();
        
        if (m_nSize)
        {
            m_alloc.move(m_alloc.address(m_acValues[1]), m_alloc.address(m_acValues[0]), m_nSize);
        }
        
        ++m_nSize;
        insert_at(0, value);
    }
    
    inline void pop_front() __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);

        delete_at(0);

        if (--m_nSize)
        {
            m_alloc.move(m_alloc.address(m_acValues[0]), m_alloc.address(m_acValues[1]), m_nSize);
        }
    }
    
    inline void push_back(_IN const_reference value) __THROW2(bad_alloc, overflow_error)
    {
        check_resize();

        insert_at(m_nSize++, value);
    }

    inline void pop_back() __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, m_nSize > 0);
        delete_at(m_nSize-1);
        --m_nSize;
    }

    inline const_iterator begin() const
    {
        return const_iterator(*this, 0);
    }

    inline iterator begin()
    {
        return iterator(*this, 0);
    }

    inline const_iterator end() const
    {
        return const_iterator(*this, m_nSize);
    }

    inline iterator end()
    {
        return iterator(*this, m_nSize);
    }

#if MBO_TDA_STL_ITERATOR

    inline const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }

    inline reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    inline const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

    inline reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
#endif

    void assign(size_type count, const_reference val)
    {
        clear();
        if (count > capacity())
        {
            reserve(count);
        }
        while(count--)
        {
            push_back(val);
        }
    }

    template<class InputIterator>
    void assign(InputIterator first, InputIterator end)
    {
        clear();
        if (static_cast<size_type>(end - first) > capacity())
        {
            reserve(end - first);
        }
        while(first != end)
        {
            push_back(*first);
            ++first;
        }
    }

    void erase(size_t where)
    {
        mbo_tda_throw_if_not(logic_error, where < m_nSize);
        if (where == 0)
        {
            pop_front();
        }
        else if (where + 1 == m_nSize)
        {
            pop_back();
        }
        else
        {
            delete_at(where);

            if (--m_nSize)
            {
                m_alloc.move(m_alloc.address(m_acValues[where]), m_alloc.address(m_acValues[where+1]), m_nSize - where);
            }
        }
    }

    iterator erase(iterator where)
    {
        erase(where - begin());
        return where;
    }

    iterator erase(iterator first, iterator end)
    {
        size_type nLength = end - first;

        if (nLength == 1)
        {
            return erase(first);
        }
        else if (nLength)
        {
            size_type nStart = first - begin();
            size_type nPos   = nStart + nLength;

            while(nPos > nStart)
            {
                delete_at(--nPos);
            }

            m_nSize -= nLength;

            if (m_nSize)
            {
                m_alloc.move(m_alloc.address(m_acValues[nStart]), m_alloc.address(m_acValues[nStart + nLength]), m_nSize - nStart);
            }
        }
        return first;
    }

    inline void clear()
    {
        while(m_nSize)
        {
            m_alloc.destroy(m_alloc.address(m_acValues[--m_nSize]));
        }
        if (m_acValues)
        {
            m_alloc.deallocate(m_acValues, m_nCapacity);
            m_acValues = 0L;
            m_nCapacity = 0;
        }
    }

    inline reserve(size_type nNewCapacity) __THROW2(bad_alloc, overflow_error)
    {
        mbo_tda_throw_if_not(overflow_error, nNewCapacity >= m_nSize && nNewCapacity <= max_size());

        pointer pNewValues = m_alloc.reallocate(m_acValues, m_nCapacity, nNewCapacity);

        mbo_tda_throw_if_not(bad_alloc, pNewValues || !nNewCapacity);

        m_acValues = pNewValues;
        m_nCapacity = nNewCapacity;
    }

    void resize(size_type nNewSize) __THROW2(bad_alloc, overflow_error)
    {
        resize(nNewSize, value_type());
    }

    void resize(size_type nNewSize, value_type value) __THROW2(bad_alloc, overflow_error)
    {
        while(size() < nNewSize)
        {
            push_back(value);
        }
        while(size() > nNewSize)
        {
            pop_back();
        }
    }

    inline void limit_size(size_type nNewSize)
    {
        while(size() > nNewSize)
        {
            pop_back();
        }
    }

protected:

    inline void check_resize() __THROW2(bad_alloc, overflow_error)
    {   
        if (m_nSize == m_nCapacity)
        {
            mbo_tda_throw_if_not(overflow_error, m_nSize + m_nAppend > m_nSize);

            reserve(m_nSize + m_nAppend);
        }
    }

    inline void delete_at(size_type nPos) __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, nPos < m_nSize);
        m_alloc.destroy(m_alloc.address(m_acValues[nPos]));
    }

    inline void insert_at(size_type nPos, _IN const_reference value) __THROWS(out_of_range)
    {
        mbo_tda_throw_if_not(out_of_range, nPos < m_nSize);
        m_alloc.construct(m_alloc.address(m_acValues[nPos]), value);
    }

    allocator       m_alloc;        
    size_type       m_nSize;        
    size_type       m_nCapacity;    
    size_type       m_nAppend;      
    size_type       m_nMaxSize;     
    pointer         m_acValues;     
};

}; // namespace mbo

#if defined(_MSC_VER)
# pragma warning(pop)
#endif

#endif // _TDYNAMICARRAY_H_

---