deque

realview22.rar

// -*- C++ -*-
/***************************************************************************
 *
 * deque - Declaration and definition for the Standard Library deque class
 *
 * $Id: deque,v 1.1.1.1 2002/01/10 17:38:29 vkorstan Exp $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2001 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. pursuant to a written license agreement and may be used, copied,
 * transmitted, and stored only in accordance with the terms of such
 * license and with the inclusion of the above copyright notice.  This
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  Use, duplication, or disclosure by the
 * Government is subject to restrictions as set forth in subparagraph (c)
 * (1) (ii) of The Rights in Technical Data and Computer Software clause
 * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/

#ifndef _RWSTD_DEQUE_INCLUDED
#define _RWSTD_DEQUE_INCLUDED

#include <limits>
#include <memory>

#include <rw/_algobase.h>
#include <rw/_dispatch.h>
#include <rw/_iterator.h>
#include <rw/_defs.h>
#include <rw/_error.h>


_RWSTD_NAMESPACE_BEGIN (std)

template <class _TypeT, class _Allocator>
class deque;

template <class _TypeT, class _DiffT, class _Pointer,
          class _Reference, class _Allocator>
class __rw_deque_iter
    : public iterator <random_access_iterator_tag, _TypeT, _DiffT,
                       _Pointer, _Reference>
{
    typedef iterator <bidirectional_iterator_tag, _TypeT, _DiffT,
                      _Pointer, _Reference>           _C_iter_base;
public:

    typedef _Allocator                               allocator_type;
    typedef _TYPENAME allocator_type::size_type      size_type;
    typedef _TYPENAME _C_iter_base::value_type       value_type;
    typedef _TYPENAME _C_iter_base::difference_type  difference_type;
    typedef _TYPENAME _C_iter_base::pointer          pointer;
    typedef _TYPENAME _C_iter_base::reference        reference;

    typedef random_access_iterator_tag               iterator_category;
    
    typedef __rw_deque_iter<value_type, difference_type,
                            value_type*, value_type&, allocator_type>
    _C_mutable_iter;

    typedef _RWSTD_REBIND (allocator_type, value_type*)   _C_map_alloc_type;
    typedef _TYPENAME _C_map_alloc_type::pointer          _C_map_pointer;

    
    static size_type _C_bufsize () {
        // deque only uses __rw_new_capacity to retrieve the minimum
        // allocation amount; this may be specialized to provide a
        // customized minimum amount
        return _RW::__rw_new_capacity(0, (deque<_TypeT, _Allocator>*)0);
    }
    
    __rw_deque_iter () { }

    // dummy first argument used to easily switch between
    // iterators with and without support for debugging
    __rw_deque_iter (pointer __x, _C_map_pointer __y)
       : _C_current (__x), 
          _C_first (__y ? *__y : 0), 
          _C_last (__y ? *__y + _C_bufsize () : 0) , 
         _C_node (__y) {
        _RWSTD_ASSERT (__x && __y || !__x && !__y);
    }

    // no copy ctor other than the one below defined; will use
    // a compiler generated one if __rw_deque_iter != _C_mutable_iter
    __rw_deque_iter (const _C_mutable_iter &__rhs)
        : _C_current (__rhs._C_current),
          _C_first (__rhs._C_first), 
          _C_last (__rhs._C_last),
          _C_node (__rhs._C_node) { }
    
    __rw_deque_iter& operator++ () {
        if (++_C_current == _C_last)
            _C_last = (_C_current = _C_first = *++_C_node) + _C_bufsize ();
        return *this;
    }
    
    __rw_deque_iter& operator-- () {
        if (_C_current == _C_first) {
            _C_last = (_C_current = (_C_first = *--_C_node) + _C_bufsize ());
        }
        --_C_current;
        return *this;
    }
    
    __rw_deque_iter operator++ (int) {
        __rw_deque_iter __tmp = *this;
        return ++*this, __tmp;
    }

    __rw_deque_iter operator-- (int) {
        __rw_deque_iter __tmp = *this;
        return --*this, __tmp;
    }

    __rw_deque_iter& operator+= (difference_type __n);
    
    __rw_deque_iter& operator-= (difference_type __n) {
        return *this += -__n;
    }

    __rw_deque_iter operator+ (difference_type __n) const {
        return __rw_deque_iter (*this) += __n;
    }

    __rw_deque_iter operator- (difference_type __n) const {
        return __rw_deque_iter (*this) -= __n;
    }

    reference operator* () const {
        return *_C_current;
    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
    
    reference operator[] (difference_type __n) const {
        return *(*this + __n);
    }

    pointer        _C_current;
    pointer        _C_first;
    pointer        _C_last;
    _C_map_pointer _C_node;
};


template <class _TypeT, class _DiffT, class _Pointer,
           class _Reference, class _Allocator>
inline __rw_deque_iter<_TypeT, _DiffT, _Pointer, _Reference, _Allocator>&
__rw_deque_iter<_TypeT, _DiffT, _Pointer, _Reference, _Allocator>::
operator+= (difference_type __n)
{
    difference_type __offset = __n + (_C_current - _C_first);
    difference_type __jump   = __offset >= 0 ? __offset / _C_bufsize ()
        : -(difference_type)((-__offset + _C_bufsize () - 1) / _C_bufsize ());

    if (!__jump)
        _C_current += __n;
    else {
        _C_first   = *(_C_node += __jump);
        _C_last    = _C_first + _C_bufsize ();
        _C_current = _C_first + (__offset - __jump * _C_bufsize ());
    }
    return *this;
}


// for symmetry
template <class _TypeT, class _DiffT, class _Ptr, class _Ref, class _Alloc>
inline __rw_deque_iter<_TypeT, _DiffT, _Ptr, _Ref, _Alloc>
operator+ (_DiffT                                                     __lhs,
           const __rw_deque_iter<_TypeT, _DiffT, _Ptr, _Ref, _Alloc> &__rhs)
{
    return __rhs + __lhs;
}


#define _RWSTD_DEQUE_ITER(n) \
        __rw_deque_iter<_TypeT, _DiffT, _Ptr##n, _Ref##n, _Alloc>


template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline _DiffT
operator- (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return __x._C_node == __y._C_node  ? __x._C_current - __y._C_current 
        : _DiffT (__x._C_bufsize () * (__x._C_node - __y._C_node - 1)
           + (__x._C_current - __x._C_first) + (__y._C_last - __y._C_current));
}


template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator== (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return    __x._C_current == __y._C_current
           || (   (   __x._C_current == __x._C_first
                   || __y._C_current == __y._C_first)
               && __x - __y == 0);
}


template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator< (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return __x._C_node == __y._C_node ? (__x._C_current < __y._C_current)
        : (__x._C_node < __y._C_node);
}


template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator!= (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return !(__x == __y);
}


template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator<= (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return !(__y < __x);
}

template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator>= (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return !(__x < __y);
}

template <class _TypeT, class _DiffT,
         class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Alloc>
inline bool
operator> (const _RWSTD_DEQUE_ITER(1) &__x, const _RWSTD_DEQUE_ITER(2) &__y)
{
    return __y < __x;
}


#undef _RWSTD_DEQUE_ITER


template <class _TypeT, 
          class _Allocator _RWSTD_COMPLEX_DEFAULT (allocator<_TypeT>) >
class deque : private _Allocator
{
public:

    typedef _TypeT                                    value_type;
    typedef _Allocator                                allocator_type;
    typedef _TYPENAME allocator_type::size_type       size_type;
    typedef _TYPENAME allocator_type::difference_type difference_type;
    typedef _TYPENAME allocator_type::pointer         pointer;
    typedef _TYPENAME allocator_type::const_pointer   const_pointer;
    typedef _TYPENAME allocator_type::reference       reference;
    typedef _TYPENAME allocator_type::const_reference const_reference;

    typedef _RWSTD_ALLOC_TYPE (allocator_type, value_type) _C_value_alloc_type;

    // following two typedefs are used for convenience with debug iters
    typedef __rw_deque_iter<value_type, difference_type, pointer,
                            reference, allocator_type>         _C_deque_iter; 

    typedef __rw_deque_iter<value_type, difference_type, const_pointer,
                            const_reference, allocator_type>   _C_deque_citer;

    typedef _RWSTD_REBIND (allocator_type, value_type*)   _C_map_alloc_type;

    typedef _TYPENAME _C_map_alloc_type::pointer          _C_map_pointer;

#ifndef _RWSTD_NO_DEBUG_ITER

    typedef _RW::__rw_debug_iter<deque, _C_deque_iter, _C_deque_iter>
    iterator;
    
    typedef _RW::__rw_debug_iter<deque, _C_deque_citer, _C_deque_iter>
    const_iterator;
    
    iterator _C_make_iter (const _C_deque_iter&  __iter) { 
        return iterator (*this, __iter);
    }

    const_iterator _C_make_iter (const _C_deque_citer& __citer) const {
        return const_iterator (*this, __citer);
    }

#else   // if defined (_RWSTD_NO_DEBUG_ITER)
    
    typedef _C_deque_iter        iterator;
    typedef _C_deque_citer       const_iterator;
    
    iterator _C_make_iter (const _C_deque_iter&  __iter) {
        return __iter;
    }

    const_iterator _C_make_iter (const _C_deque_citer& __citer) const {
        return __citer;
    }

#endif   // _RWSTD_NO_DEBUG_ITER

    static size_type _C_bufsize () {
        return _C_deque_iter::_C_bufsize ();
    }

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 

    typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator>       reverse_iterator;

#else   // if defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

    typedef _STD::reverse_iterator<const_iterator, 
      random_access_iterator_tag, value_type, 
      const_reference, const_pointer, difference_type> const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator, 
      random_access_iterator_tag, value_type, 
      reference, pointer, difference_type>             reverse_iterator;

#endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC 

protected:

    _C_deque_iter  _C_begin;
    _C_deque_iter  _C_end;
    size_type      _C_size;

    _C_map_pointer _C_map;
    size_type      _C_map_size;
    
    void _C_init () {
        _C_begin =
        _C_end   = _C_deque_iter (0, 0);
        _C_size  = 0;
        _C_map   = 0;
    }

    void _C_alloc_at_begin ();    

    void _C_alloc_at_end ();

    void _C_free_at_begin ();

    void _C_free_at_end ();

    void __insert_aux (iterator __pos, size_type __n, const_reference __val);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    template<class _InputIter>
    void __insert_aux (iterator __pos,
                       _InputIter __first, _InputIter __last,
                       _RW_is_not_integer) {
        __insert_aux2 (__pos, __first, __last);
    }

    template<class _InputIter>
    void __insert_aux (iterator __pos,
                       _InputIter __first, _InputIter __last,
                       _RW_is_integer) {
        __insert_aux (__pos, (size_type)__first, __last);
    }

    template<class _InputIter>
    void __insert_aux2 (iterator, _InputIter, _InputIter);

    template <class _InputIter>
    void __insert_interval_dispatch (iterator __pos,
                                     _InputIter __first,
                                     _InputIter __last,
                                     forward_iterator_tag) {
        typedef _TYPENAME _RWdispatch<_InputIter>::_RWtype _RWtype;
        __insert_aux (__pos, __first, __last, _RWtype ());
    }

    template <class _InputIter>
    void __insert_interval_dispatch (iterator   __pos,
                                     _InputIter __first, 
                                     _InputIter __last,
                                     input_iterator_tag) {
        _RWSTD_ASSERT_RANGE (__pos, end ());
        _RWSTD_ASSERT_RANGE (__first, __last);
        for ( ; __first != __last; ++__pos, ++__first)
            __pos = insert (__pos, *__first); 
    }
 
#endif   // _RWSTD_NO_MEMBER_TEMPLATES

public:

    _EXPLICIT
    deque (const allocator_type &__alloc = allocator_type ())
      : allocator_type (__alloc), _C_map_size (0) {
        _C_init ();
    }

    _EXPLICIT
    deque (size_type __n, const_reference __val = value_type (), 
           const allocator_type& __alloc = allocator_type ())