blob: 427366cd3a3d95463e03fd0d2bfc84e301c954b1 [file] [log] [blame]
/***************************************************************************
*
* deque.cc - Non-iniline definitions for the Standard Library deque class
*
* $Id$
*
***************************************************************************
*
* 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.
*
***************************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied. See the License for the specific language governing
* permissions and limitations under the License.
*
* Copyright 1994-2006 Rogue Wave Software.
*
**************************************************************************/
_RWSTD_NAMESPACE (std) {
template <class _TypeT, class _Allocator>
deque<_TypeT, _Allocator>&
deque<_TypeT, _Allocator>::
operator= (const deque &__rhs)
{
_RWSTD_ASSERT (_C_is_valid ());
_RWSTD_ASSERT (__rhs._C_is_valid ());
const size_type __size = size ();
if (__size < __rhs.size ()) {
const const_iterator __mid = __rhs.begin () + __size;
_STD::copy (__mid, __rhs.end (),
_STD::inserter (*this, _STD::copy (__rhs.begin (), __mid,
begin ())));
}
else
erase (_STD::copy (__rhs.begin (), __rhs.end (), begin ()), end ());
return *this;
}
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator
deque<_TypeT, _Allocator>::
insert (iterator __it, const_reference __x)
{
_RWSTD_ASSERT_RANGE (begin (), __it);
_RWSTD_ASSERT (_C_is_valid ());
if (__it == begin ()) {
push_front (__x);
return begin ();
}
if (__it == end ()) {
push_back (__x);
__it = end () - 1;
return __it;
}
const size_type __inx = _DISTANCE (begin (), __it, size_type);
_RWSTD_ASSERT (__inx < size ());
if (__inx < size () - __inx) {
push_front (front ());
_STD::copy (begin () + 2, begin () + (__inx + 1), begin () + 1);
}
else {
push_back (back ());
_STD::copy_backward (begin () + __inx, end () - 2, end () - 1);
}
__it = begin () + __inx;
*__it = __x;
return __it;
}
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator
deque<_TypeT, _Allocator>::
erase (iterator __it)
{
// `it' must be a dereferenceable iterator into `*this'
_RWSTD_ASSERT_RANGE (begin (), __it);
_RWSTD_ASSERT (!(__it == end ()));
_RWSTD_ASSERT (_C_is_valid (0 /* valid and non-empty */));
const iterator __next = ++iterator (__it);
if (__it - begin () < end () - __it) {
_STD::copy_backward (begin (), __it, __next);
pop_front ();
return empty () ? end () : __next;
}
_STD::copy (__next, end (), __it);
pop_back ();
return __it;
}
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator
deque<_TypeT, _Allocator>::
erase (iterator __first, iterator __last)
{
// (`first', `last'] must be a valid range into `*this'
_RWSTD_ASSERT_RANGE (__first, __last);
_RWSTD_ASSERT_RANGE (begin (), __first);
_RWSTD_ASSERT (_C_is_valid ());
size_type __n = _DISTANCE (__first, __last, size_type);
_RWSTD_ASSERT (__n <= size ());
if (__first - begin () < end () - __last) {
_STD::copy_backward (begin (), __first, __last);
while (__n-- != 0)
pop_front ();
return __last;
}
_STD::copy (__last, end (), __first);
while (__n-- != 0)
pop_back ();
return __first;
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
swap (deque<_TypeT, _Allocator> &__rhs)
{
_RWSTD_ASSERT (_C_is_valid ());
_RWSTD_ASSERT (__rhs._C_is_valid ());
if (get_allocator () == __rhs.get_allocator ()) {
_STD::swap (_C_beg, __rhs._C_beg);
_STD::swap (_C_end, __rhs._C_end);
_STD::swap (_C_nodes, __rhs._C_nodes);
_STD::swap (_C_node_size, __rhs._C_node_size);
if (pointer() == _C_beg._C_cur) {
_RWSTD_ASSERT (pointer() == _C_end._C_cur);
_RWSTD_ASSERT ( _C_beg._C_node == &__rhs._C_end._C_cur
&& _C_end._C_node == &__rhs._C_end._C_cur);
_C_beg._C_node =
_C_end._C_node = &_C_end._C_cur;
}
else {
_RWSTD_ASSERT (pointer() != _C_end._C_cur);
}
if (pointer() == __rhs._C_beg._C_cur) {
_RWSTD_ASSERT (pointer() == __rhs._C_end._C_cur);
_RWSTD_ASSERT ( __rhs._C_beg._C_node == &_C_end._C_cur
&& __rhs._C_end._C_node == &_C_end._C_cur);
__rhs._C_beg._C_node =
__rhs._C_end._C_node = &__rhs._C_end._C_cur;
}
else {
_RWSTD_ASSERT (pointer() != __rhs._C_end._C_cur);
}
}
else {
deque __tmp (*this);
*this = __rhs;
__rhs = __tmp;
}
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_push (bool __at_back, const_reference __x)
{
_RWSTD_ASSERT (_C_is_valid ());
const size_type __bufsize = _C_bufsize ();
_C_value_alloc_type __alloc (*this);
// allocate a new buffer to store elements in
const pointer __buf = __alloc.allocate (__bufsize, pointer ());
const bool __empty = empty ();
if ( __empty
|| __at_back && _C_end._C_node == _C_nodes + _C_node_size - 1
|| !__at_back && _C_beg._C_node == _C_nodes) {
_C_node_alloc_type __node_alloc (*this);
_RWSTD_ASSERT (_C_beg._C_node <= _C_end._C_node);
// compute the current number of used nodes
// and the new number of nodes
const _C_node_pointer __end = _C_end._C_node + !__empty;
const size_type __nodes = size_type (__end - _C_beg._C_node);
// obtain the next greater number of nodes for the new vector
const size_type __nvecsize = _C_vecsize (__nodes);
_RWSTD_ASSERT (__nvecsize > __nodes);
// compute the beginning of the old (current) vector
const _C_node_pointer __ovec = _C_nodes - !__empty;
_C_node_pointer __nvec;
_TRY {
// allocate enough for two extra unused nodes
__nvec = __node_alloc.allocate (__nvecsize + 2, __ovec);
_RWSTD_ASSERT (!(_C_node_pointer () == __nvec));
const pointer __where = __buf
+ ( __empty ? __bufsize / 2 - !__at_back
: __at_back ? 0 : __bufsize - 1);
_TRY {
__alloc.construct (__where, __x);
}
_CATCH (...) {
__node_alloc.deallocate (__nvec, __nvecsize + 2);
_RETHROW;
}
// reserve the first and last nodes (must always be 0)
++__nvec;
}
_CATCH (...) {
// deallocate buffer and rethrow
__alloc.deallocate (__buf, __bufsize);
_RETHROW;
}
// compute the new indices into the newly allocated vector
// of the first and last occuppied node, respectively
const size_type __beg_inx = __nvecsize / (__empty ? 2 : 4);
const size_type __end_inx = __beg_inx + __nodes;
// copy existing nodes into the new buffer
_STD::copy (_C_beg._C_node, __end, __nvec + (__beg_inx + !__at_back));
// deallocate the current buffer only when non-0 to satisfy
// the requirement that deallocate() argument be non-zero
if (!(__ovec == _C_node_pointer ()))
__node_alloc.deallocate (__ovec, _C_node_size + 2);
// set the pointer and size
_C_nodes = __nvec;
_C_node_size = __nvecsize;
// insert the fixed-size array into the vector of nodes...
if (__at_back) {
// ...at the end
_C_nodes [__end_inx] = __buf;
_C_beg._C_node = _C_nodes + __beg_inx;
_C_end = _C_deque_iter (__buf, _C_nodes + __end_inx);
}
else {
// ...at the beginning
_C_nodes [__beg_inx] = __buf;
_C_beg = _C_deque_iter (__buf + __bufsize, _C_nodes + __beg_inx);
_C_end._C_node = _C_nodes + __end_inx;
}
if (__empty) {
// set the beginning and end pointers both
// to point at the same (future) element
_C_beg._C_cur =
_C_end._C_cur = __buf + __bufsize / 2;
}
}
else {
_RWSTD_ASSERT (_C_is_valid (0 /* valid and non-empty */));
_TRY {
if (__at_back) {
__alloc.construct (__buf, __x);
// append the newly allocated buffer to the end of the vector
// of pointers and increment `end' to point at the first
// element in it; zero out the following node
*++_C_end._C_node = __buf;
_C_end._C_cur = __buf;
}
else {
__alloc.construct (__buf + (__bufsize - 1), __x);
// prepend the newly allocated buffer to the beginning of
// the vector of pointers and decrement `begin' to point
// at the last element in it; zero out the preceding node
*--_C_beg._C_node = __buf;
_C_beg._C_cur = __buf + __bufsize;
}
}
_CATCH (...) {
__alloc.deallocate (__buf, __bufsize);
_RETHROW;
}
}
_C_end._C_node [+1] = pointer ();
_C_beg._C_node [-1] = pointer ();
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_free_at_begin ()
{
const size_type __bufsize = _C_bufsize ();
_RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this,
deallocate (*_C_beg._C_node, __bufsize));
if (empty ()) {
_C_node_alloc_type (*this).
deallocate (_C_nodes - 1, _C_node_size + 2);
_C_init ();
}
else {
*_C_beg._C_node++ = pointer ();
_C_beg = _C_deque_iter (*_C_beg._C_node, _C_beg._C_node);
}
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_free_at_end ()
{
const size_type __bufsize = _C_bufsize ();
_RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this,
deallocate (*_C_end._C_node, __bufsize));
if (empty ()) {
_C_node_alloc_type (*this).
deallocate (_C_nodes - 1, _C_node_size + 2);
_C_init ();
}
else {
*_C_end._C_node-- = pointer ();
_C_end = _C_deque_iter (*_C_end._C_node + __bufsize, _C_end._C_node);
}
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_assign_n (size_type __n, const_reference __x)
{
_RWSTD_ASSERT (_C_is_valid ());
#ifndef _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
// assign over existing elements for better efficiency
// and exception safety
// complexity: linear in n
// exception safety:
// -- nothrow if size() >= n, and value_type's assignment operator
// and iterator operations do not throw
// -- basic otherwise
const iterator __end = end ();
// avoid using the name __i or __it below so as not to trigger
// a (bogus) gcc 2.95.2 -Wshadow warning: declaration of `__i'
// shadows previous local
for (iterator __ix = begin (); !(__ix == __end); ++__ix, --__n) {
if (size_type () == __n) {
erase (__ix, __end);
return;
}
*__ix = __x;
}
insert (__end, __n, __x);
#else // if defined (_RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE)
// follow the inefficient requirement in 23.2.1.1, p8
// complexity: linear in n
// exception safety: basic
clear ();
insert (begin (), __n, __x);
#endif // _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
}
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_insert_n (const iterator &__it, size_type __n, const_reference __x)
{
_RWSTD_ASSERT_RANGE (begin (), __it);
_RWSTD_ASSERT (_C_is_valid ());
const size_type __inx = _DISTANCE (begin (), __it, size_type);
const size_type __rem = size () - __inx;
_RWSTD_ASSERT (__inx <= size ());
if (__inx < __rem) {
// inserting `x' into the first half of the container
if (__inx < __n) {
for (size_type __i = __n - __inx; __i; --__i)
push_front (__x);
for (size_type __j = __inx; __j; --__j)
push_front (*(begin () + (__n - 1)));
_STD::fill (begin () + __n, begin () + (__n + __inx), __x);
}
else if (__n) {
for (size_type __i = __n; __i; --__i)
push_front (*(begin () + __n - 1));
const iterator __tmp = begin () + __n;
_STD::copy (__tmp + __n, __tmp + __inx, __tmp);
_STD::fill (begin () + __inx, __tmp + __inx, __x);
}
}
else {
// inserting `x' into the second half of the container
const size_type __size0 = size ();
if (__rem < __n) {
for (size_type __i = __n - __rem; __i; --__i)
push_back (__x);
for (size_type __j = 0; __j != __rem; ++__j)
push_back (*(begin () + (__inx + __j)));
_STD::fill (begin () + __inx, begin () + __size0, __x);
}
else if (__n) {
for (size_type __i = 0;__i != __n; ++__i)
push_back (*(begin () + __size0 - __n + __i));
const iterator __tmp = begin () + __inx;
_STD::copy_backward (__tmp, begin () + __size0 - __n,
begin () + __size0);
_STD::fill (__tmp, __tmp + __n, __x);
}
}
}
template <class _TypeT, class _Allocator>
template <class _InputIter>
void deque<_TypeT, _Allocator>::
_C_assign_range (_InputIter __first, _InputIter __last, input_iterator_tag)
{
typedef deque _Deque;
_RWSTD_ASSERT_RANGE (__first, __last);
_RWSTD_ASSERT (this->_C_is_valid ());
#ifndef _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
// assign over existing elements for better efficiency
// and exception safety
// complexity: linear in distance(first, last)
// exception safety:
// -- nothrow if size() >= distance(first, last), and value_type's
// assignment operator and iterator operations do not throw
// -- basic otherwise
const iterator __end = this->end ();
// avoid using the name __i or __it below so as not to trigger
// a (bogus) gcc 2.95.2 -Wshadow warning: declaration of `__i'
// shadows previous local
for (iterator __ix = this->begin (); !(__ix == __end);
++__ix, ++__first) {
if (__first == __last) {
this->erase (__ix, __end);
return;
}
*__ix = *__first;
}
this->insert (__end, __first, __last);
#else // if defined (_RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE)
// follow the inefficient requirement in 23.2.1.1, p7
// complexity: linear in distance(first, last)
// exception safety: basic
this->clear ();
this->insert (this->begin (), __first, __last);
#endif // _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
}
template<class _TypeT, class _Allocator>
template <class _InputIter>
void deque<_TypeT, _Allocator>::
_C_insert_range (iterator __it,
_InputIter __first, _InputIter __last,
input_iterator_tag)
{
typedef deque _Deque;
_RWSTD_ASSERT_RANGE (__it, this->end ());
_RWSTD_ASSERT_RANGE (__first, __last);
#ifndef _RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE
// insert one element at a time to prevent a loss of data
// from the input sequence in the case of an exception
for ( ; !(__first == __last); ++__it, ++__first)
__it = this->insert (__it, *__first);
#else // if defined (_RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE)
// 23.2.1.3, p2: if an exception is thrown other than by the copy
// constructor or assignment operator of T there are no effects.
_Deque __tmp (this->begin (), __it, this->get_allocator ());
for (; !(__first == __last); ++__first)
__tmp.push_back (*__first);
__tmp.insert (__tmp.end (), __it, this->end ());
this->swap (__tmp);
#endif // _RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE
}
// template<class _TypeT, class _Allocator>
// template <class _FwdIter>
// void deque<_TypeT, _Allocator>::
// _C_insert_range (iterator __it,
// _FwdIter __first, _FwdIter __last,
// forward_iterator_tag)
// {
// typedef deque _Deque;
// // implemented in terms of the Input Iterator overload
// _RWSTD_INSERT_RANGE (__it, __first, __last, input_iterator_tag ());
// }
template <class _TypeT, class _Allocator>
template <class _BidirIter>
void deque<_TypeT, _Allocator>::
_C_insert_range (iterator __it,
_BidirIter __first, _BidirIter __last,
bidirectional_iterator_tag)
{
typedef deque _Deque;
_RWSTD_ASSERT_RANGE (this->begin (), __it);
_RWSTD_ASSERT_RANGE (__first, __last);
_RWSTD_ASSERT (this->_C_is_valid ());
// compute the distance of `it' from the beginning of the container,
// the distance of `it' to the end of the container, and the number
// of elements to be inserted
const size_type __sz0 = this->size ();
const size_type __inx = _DISTANCE (this->begin (), __it, size_type);
const size_type __rem = __sz0 - __inx;
const size_type __n = _DISTANCE (__first, __last, size_type);
_RWSTD_ASSERT (__inx <= __sz0);
if (__inx < __rem) {
// inserting into the first half of the container
if (__inx < __n) {
// the number of elements in the range controlled by *this,
// [begin, it), is less than the number of elements in the
// range [first, last)
_BidirIter __from (__last);
_STD::advance (__from, -difference_type (__inx));
const _BidirIter __mid (__from);
while (!(__from == __first))
this->push_front (*--__from);
for (size_type __i = __inx; __i; --__i)
this->push_front (*(this->begin () + (__n - 1)));
_STD::copy (__mid, __last, this->begin () + __n);
}
else {
// the number of elements in the range to be inserted,
// [first, last), is less than or equal to the number
// of elements in the range [begin, it)
for (size_type __i = __n; __i; --__i)
this->push_front (*(this->begin () + (__n - 1)));
const iterator __to = this->begin () + __n;
_STD::copy (__to + __n, __to + __inx, __to);
_STD::copy (__first, __last, this->begin () + __inx);
}
}
else {
// inserting into the second half of the container
if (__rem < __n) {
_BidirIter __from (__first);
_STD::advance (__from, __rem);
const _BidirIter __to (__from);
for ( ; !(__from == __last); ++__from)
this->push_back (*__from);
for (size_type __i = 0; __i != __rem; ++__i)
this->push_back (*(this->begin () + (__inx + __i)));
_STD::copy (__first, __to, this->begin () + __inx);
}
else {
for (size_type __i = 0; __i != __n; ++__i)
this->push_back (*(this->begin () + (__sz0 - __n + __i)));
const iterator __to = this->begin () + __sz0;
const iterator __from = this->begin () + __inx;
const iterator __from_end = this->begin () + (__sz0 - __n);
_STD::copy_backward (__from, __from_end, __to);
_STD::copy (__first, __last, __from);
}
}
}
template<class _TypeT, class _Allocator>
bool deque<_TypeT, _Allocator>::
_C_is_valid (int __emptyfl) const
{
#ifdef _RWSTDDEBUG
if (__emptyfl < 0 /* don't care */)
return _C_is_valid (0 + empty ());
// the nodes just prior the first valid node and
// just past the last valid node must always be 0
if (_C_node_pointer () != _C_nodes) {
_RWSTD_ASSERT (pointer () == _C_beg._C_node [-1]);
_RWSTD_ASSERT (pointer () == _C_end._C_node [+1]);
}
if (__emptyfl) {
// container must be empty
_RWSTD_ASSERT (empty ());
// both `current' pointers must be 0
_RWSTD_ASSERT (pointer () == _C_beg._C_cur);
_RWSTD_ASSERT (pointer () == _C_end._C_cur);
// node pointers must be dereferenceable...
_RWSTD_ASSERT (_C_node_pointer () != _C_beg._C_node);
_RWSTD_ASSERT (_C_node_pointer () != _C_end._C_node);
// ...and both must dereference the same pointer
_RWSTD_ASSERT (*_C_beg._C_node == *_C_end._C_node);
return true;
}
const size_type __bufsize = _C_bufsize ();
// container must be non-empty
_RWSTD_ASSERT (!empty ());
// current pointers must be non-0
_RWSTD_ASSERT (pointer () != _C_beg._C_cur);
_RWSTD_ASSERT (pointer () != _C_end._C_cur);
// `begin' must be less than `end'
_RWSTD_ASSERT (_C_beg._C_node <= _C_end._C_node);
// `begin' must point into the vector of nodes
_RWSTD_ASSERT (_C_nodes <= _C_beg._C_node);
_RWSTD_ASSERT (_C_beg._C_node <= _C_nodes + _C_node_size);
// `begin' must point to a non-empty array of elements
_RWSTD_ASSERT (pointer () != *_C_beg._C_node);
// `begin' must point into an array of `bufsize' elements
_RWSTD_ASSERT (_C_beg._C_cur >= *_C_beg._C_node);
_RWSTD_ASSERT (_C_beg._C_cur <= *_C_beg._C_node + __bufsize);
// `end' must point into the vector of nodes
_RWSTD_ASSERT (_C_nodes <= _C_end._C_node);
_RWSTD_ASSERT (_C_end._C_node <= _C_nodes + _C_node_size);
// `end' must point to a non-empty array of elements
_RWSTD_ASSERT (pointer () != *_C_end._C_node);
// `end' must point into an array of `bufsize' elements
_RWSTD_ASSERT (_C_end._C_cur >= *_C_end._C_node);
_RWSTD_ASSERT (_C_end._C_cur <= *_C_end._C_node + __bufsize);
#else // if !defined (_RWSTDDEBUG)
_RWSTD_UNUSED (__emptyfl);
#endif // _RWSTDDEBUG
return true;
}
} // namespace std