home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _deque.h < prev    next >
C/C++ Source or Header  |  2002-02-02  |  32KB  |  1,010 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Copyright (c) 1996,1997
  7.  * Silicon Graphics Computer Systems, Inc.
  8.  *
  9.  * Copyright (c) 1997
  10.  * Moscow Center for SPARC Technology
  11.  *
  12.  * Copyright (c) 1999 
  13.  * Boris Fomitchev
  14.  *
  15.  * This material is provided "as is", with absolutely no warranty expressed
  16.  * or implied. Any use is at your own risk.
  17.  *
  18.  * Permission to use or copy this software for any purpose is hereby granted 
  19.  * without fee, provided the above notices are retained on all copies.
  20.  * Permission to modify the code and to distribute modified code is granted,
  21.  * provided the above notices are retained, and a notice that the code was
  22.  * modified is included with the above copyright notice.
  23.  *
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef _STLP_INTERNAL_DEQUE_H
  31. #define _STLP_INTERNAL_DEQUE_H
  32.  
  33. # ifndef _STLP_INTERNAL_ALGOBASE_H
  34. #  include <stl/_algobase.h>
  35. # endif
  36.  
  37. # ifndef _STLP_INTERNAL_ALLOC_H
  38. #  include <stl/_alloc.h>
  39. # endif
  40.  
  41. # ifndef _STLP_INTERNAL_ITERATOR_H
  42. #  include <stl/_iterator.h>
  43. # endif
  44.  
  45. # ifndef _STLP_INTERNAL_UNINITIALIZED_H
  46. #  include <stl/_uninitialized.h>
  47. # endif
  48.  
  49. # ifndef _STLP_RANGE_ERRORS_H
  50. #  include <stl/_range_errors.h>
  51. # endif
  52.  
  53. /* Class invariants:
  54.  *  For any nonsingular iterator i:
  55.  *    i.node is the address of an element in the map array.  The
  56.  *      contents of i.node is a pointer to the beginning of a node.
  57.  *    i.first == *(i.node) 
  58.  *    i.last  == i.first + node_size
  59.  *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
  60.  *      the implication of this is that i.cur is always a dereferenceable
  61.  *      pointer, even if i is a past-the-end iterator.
  62.  *  Start and Finish are always nonsingular iterators.  NOTE: this means
  63.  *    that an empty deque must have one node, and that a deque
  64.  *    with N elements, where N is the buffer size, must have two nodes.
  65.  *  For every node other than start.node and finish.node, every element
  66.  *    in the node is an initialized object.  If start.node == finish.node,
  67.  *    then [start.cur, finish.cur) are initialized objects, and
  68.  *    the elements outside that range are uninitialized storage.  Otherwise,
  69.  *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
  70.  *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
  71.  *    are uninitialized storage.
  72.  *  [map, map + map_size) is a valid, non-empty range.  
  73.  *  [start.node, finish.node] is a valid range contained within 
  74.  *    [map, map + map_size).  
  75.  *  A pointer in the range [map, map + map_size) points to an allocated node
  76.  *    if and only if the pointer is in the range [start.node, finish.node].
  77.  */
  78.  
  79. # undef deque
  80. # define deque __WORKAROUND_DBG_RENAME(deque)
  81.  
  82. _STLP_BEGIN_NAMESPACE
  83.  
  84. template <class _Tp>
  85. struct _Deque_iterator_base {
  86.  
  87.   enum _Constants { 
  88.     _blocksize = _MAX_BYTES, 
  89.     __buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?
  90.                ( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))
  91.   };
  92.  
  93.   typedef random_access_iterator_tag iterator_category;
  94.  
  95.   typedef _Tp value_type;
  96.   typedef size_t size_type;
  97.   typedef ptrdiff_t difference_type;
  98.  
  99.   typedef value_type** _Map_pointer;
  100.  
  101.   typedef _Deque_iterator_base< _Tp > _Self;
  102.  
  103.   value_type* _M_cur;
  104.   value_type* _M_first;
  105.   value_type* _M_last;
  106.   _Map_pointer _M_node;
  107.  
  108.   _Deque_iterator_base(value_type* __x, _Map_pointer __y) 
  109.     : _M_cur(__x), _M_first(*__y),
  110.       _M_last(*__y + __buffer_size), _M_node(__y) {}
  111.   _Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
  112.  
  113.   difference_type _M_subtract(const _Self& __x) const {
  114.     return difference_type(__buffer_size) * (_M_node - __x._M_node - 1) +
  115.       (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
  116.   }
  117.  
  118.   void _M_increment() {
  119.     if (++_M_cur == _M_last) {
  120.       _M_set_node(_M_node + 1);
  121.       _M_cur = _M_first;
  122.     }
  123.   }
  124.  
  125.   void _M_decrement() {
  126.     if (_M_cur == _M_first) {
  127.       _M_set_node(_M_node - 1);
  128.       _M_cur = _M_last;
  129.     }
  130.     --_M_cur;
  131.   }
  132.  
  133.   void _M_advance(difference_type __n)
  134.   {
  135.     difference_type __offset = __n + (_M_cur - _M_first);
  136.     if (__offset >= 0 && __offset < difference_type(__buffer_size))
  137.       _M_cur += __n;
  138.     else {
  139.       difference_type __node_offset =
  140.         __offset > 0 ? __offset / __buffer_size
  141.                    : -difference_type((-__offset - 1) / __buffer_size) - 1;
  142.       _M_set_node(_M_node + __node_offset);
  143.       _M_cur = _M_first + 
  144.         (__offset - __node_offset * difference_type(__buffer_size));
  145.     }
  146.   }
  147.  
  148.   void _M_set_node(_Map_pointer __new_node) {
  149.     _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(__buffer_size);
  150.   }
  151. };
  152.  
  153.  
  154.  
  155. template <class _Tp, class _Traits>
  156. struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
  157.  
  158.   typedef random_access_iterator_tag iterator_category;
  159.   typedef _Tp value_type;
  160.   typedef typename _Traits::reference  reference;
  161.   typedef typename _Traits::pointer    pointer;
  162.   typedef size_t size_type;
  163.   typedef ptrdiff_t difference_type;
  164.   typedef value_type** _Map_pointer;
  165.  
  166.   typedef _Deque_iterator_base< _Tp > _Base;
  167.   typedef _Deque_iterator<_Tp, _Traits> _Self;
  168.   typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > _Nonconst_self;
  169.   typedef _Deque_iterator<_Tp, _Const_traits<_Tp> > _Const_self;
  170.  
  171.   _Deque_iterator(value_type* __x, _Map_pointer __y) :
  172.     _Deque_iterator_base<value_type>(__x,__y) {}
  173.  
  174.   _Deque_iterator() {}
  175.   _Deque_iterator(const _Nonconst_self& __x) : 
  176.     _Deque_iterator_base<value_type>(__x) {}
  177.  
  178.   reference operator*() const { 
  179.       return *this->_M_cur; 
  180.   }
  181.  
  182.   _STLP_DEFINE_ARROW_OPERATOR
  183.  
  184.   difference_type operator-(const _Self& __x) const { return this->_M_subtract(__x); }
  185.  
  186.   _Self& operator++() { this->_M_increment(); return *this; }
  187.   _Self operator++(int)  {
  188.     _Self __tmp = *this;
  189.     ++*this;
  190.     return __tmp;
  191.   }
  192.  
  193.   _Self& operator--() { this->_M_decrement(); return *this; }
  194.   _Self operator--(int) {
  195.     _Self __tmp = *this;
  196.     --*this;
  197.     return __tmp;
  198.   }
  199.  
  200.   _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
  201.   _Self operator+(difference_type __n) const
  202.   {
  203.     _Self __tmp = *this;
  204.     return __tmp += __n;
  205.   }
  206.  
  207.   _Self& operator-=(difference_type __n) { return *this += -__n; }
  208.   _Self operator-(difference_type __n) const {
  209.     _Self __tmp = *this;
  210.     return __tmp -= __n;
  211.   }
  212.  
  213.   reference operator[](difference_type __n) const { return *(*this + __n); }
  214. };
  215.  
  216. template <class _Tp, class _Traits>
  217. inline _Deque_iterator<_Tp, _Traits> _STLP_CALL
  218. operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Traits>& __x)
  219. {
  220.    return __x + __n;
  221. }
  222.  
  223.  
  224. #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
  225.  
  226. template <class _Tp>
  227. inline bool _STLP_CALL 
  228. operator==(const _Deque_iterator_base<_Tp >& __x,
  229.        const _Deque_iterator_base<_Tp >& __y) { 
  230.     return __x._M_cur == __y._M_cur; 
  231. }
  232.  
  233. template <class _Tp>
  234. inline bool _STLP_CALL 
  235. operator < (const _Deque_iterator_base<_Tp >& __x,
  236.         const _Deque_iterator_base<_Tp >& __y) { 
  237.   return (__x._M_node == __y._M_node) ? 
  238.     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
  239. }
  240.  
  241. template <class _Tp>
  242. inline bool _STLP_CALL 
  243. operator!=(const _Deque_iterator_base<_Tp >& __x,
  244.        const _Deque_iterator_base<_Tp >& __y) { 
  245.     return __x._M_cur != __y._M_cur; 
  246. }
  247. template <class _Tp>
  248. inline bool _STLP_CALL 
  249. operator>(const _Deque_iterator_base<_Tp >& __x,
  250.       const _Deque_iterator_base<_Tp >& __y) { 
  251.     return __y < __x;
  252. }
  253. template <class _Tp>
  254. inline bool  _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
  255.                                    const _Deque_iterator_base<_Tp >& __y) { 
  256.     return !(__x < __y);
  257. }
  258. template <class _Tp>
  259. inline bool  _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
  260.                                    const _Deque_iterator_base<_Tp >& __y) { 
  261.     return !(__y < __x);
  262. }
  263.  
  264. # else
  265.  
  266. template <class _Tp, class _Traits1, class _Traits2>
  267. inline bool  _STLP_CALL
  268. operator==(const _Deque_iterator<_Tp, _Traits1 >& __x,
  269.        const _Deque_iterator<_Tp, _Traits2 >& __y) { 
  270.     return __x._M_cur == __y._M_cur; 
  271. }
  272.  
  273. template <class _Tp, class _Traits1, class _Traits2>
  274. inline bool _STLP_CALL 
  275. operator < (const _Deque_iterator<_Tp, _Traits1 >& __x,
  276.         const _Deque_iterator<_Tp, _Traits2 >& __y) { 
  277.   return (__x._M_node == __y._M_node) ? 
  278.     (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
  279. }
  280.  
  281. template <class _Tp>
  282. inline bool _STLP_CALL 
  283. operator!=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
  284.        const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) { 
  285.     return __x._M_cur != __y._M_cur; 
  286. }
  287. template <class _Tp>
  288. inline bool _STLP_CALL 
  289. operator>(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
  290.       const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) { 
  291.     return __y < __x;
  292. }
  293. template <class _Tp>
  294. inline bool  _STLP_CALL
  295. operator>=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
  296.            const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) { 
  297.     return !(__x < __y);
  298. }
  299. template <class _Tp>
  300. inline bool _STLP_CALL
  301. operator<=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
  302.            const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) { 
  303.     return !(__y < __x);
  304. }
  305. # endif
  306.  
  307. # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  308. template <class _Tp, class _Traits> inline _Tp*  _STLP_CALL value_type(const _Deque_iterator<_Tp, _Traits  >&) { return (_Tp*)0; }
  309. template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL 
  310. iterator_category(const _Deque_iterator<_Tp, _Traits  >&) { return random_access_iterator_tag(); }
  311. template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL 
  312. distance_type(const _Deque_iterator<_Tp, _Traits  >&) { return 0; }
  313. #endif
  314.  
  315. // Deque base class.  It has two purposes.  First, its constructor
  316. //  and destructor allocate (but don't initialize) storage.  This makes
  317. //  exception safety easier.  Second, the base class encapsulates all of
  318. //  the differences between SGI-style allocators and standard-conforming
  319. //  allocators.
  320.  
  321. template <class _Tp, class _Alloc>
  322. class _Deque_base {
  323. public:
  324.   typedef _Tp value_type;
  325.   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  326.   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type  allocator_type;
  327.   typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;
  328.  
  329.   typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
  330.   typedef _Deque_iterator<_Tp, _Const_traits<_Tp> >   const_iterator;
  331.  
  332.   static size_t  _STLP_CALL buffer_size() { return (size_t)_Deque_iterator_base<_Tp>::__buffer_size; } 
  333.  
  334.   _Deque_base(const allocator_type& __a, size_t __num_elements)
  335.     : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
  336.       _M_map_size(__a, (size_t)0) {
  337.     _M_initialize_map(__num_elements);
  338.   }
  339.   _Deque_base(const allocator_type& __a)
  340.     : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0), 
  341.       _M_map_size(__a, (size_t)0) {
  342.   }
  343.   ~_Deque_base();    
  344.  
  345. protected:
  346.   void _M_initialize_map(size_t);
  347.   void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  348.   void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  349.   enum { _S_initial_map_size = 8 };
  350.  
  351. protected:
  352.   iterator _M_start;
  353.   iterator _M_finish;
  354.   _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type>  _M_map;
  355.   _STLP_alloc_proxy<size_t, value_type,  allocator_type>   _M_map_size;  
  356. };
  357.  
  358.  
  359. template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
  360. class deque : protected _Deque_base<_Tp, _Alloc> {
  361.   typedef _Deque_base<_Tp, _Alloc> _Base;
  362.   typedef deque<_Tp, _Alloc> _Self;
  363. public:                         // Basic types
  364.   typedef _Tp value_type;
  365.   typedef value_type* pointer;
  366.   typedef const value_type* const_pointer;
  367.   typedef value_type& reference;
  368.   typedef const value_type& const_reference;
  369.   typedef size_t size_type;
  370.   typedef ptrdiff_t difference_type;
  371.   typedef random_access_iterator_tag _Iterator_category;
  372.   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  373.   typedef typename _Base::allocator_type allocator_type;
  374.  
  375. public:                         // Iterators
  376.   typedef typename _Base::iterator       iterator;
  377.   typedef typename _Base::const_iterator const_iterator;
  378.  
  379.   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
  380.  
  381. protected:                      // Internal typedefs
  382.   typedef pointer* _Map_pointer;
  383.   typedef typename  __type_traits<_Tp>::has_trivial_assignment_operator _TrivialAss;
  384.   typedef typename  __type_traits<_Tp>::has_trivial_assignment_operator _IsPODType;
  385.  
  386. public:                         // Basic accessors
  387.   iterator begin() { return this->_M_start; }
  388.   iterator end() { return this->_M_finish; }
  389.   const_iterator begin() const { return const_iterator(this->_M_start); }
  390.   const_iterator end() const { return const_iterator(this->_M_finish); }
  391.  
  392.   reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
  393.   reverse_iterator rend() { return reverse_iterator(this->_M_start); }
  394.   const_reverse_iterator rbegin() const 
  395.     { return const_reverse_iterator(this->_M_finish); }
  396.   const_reverse_iterator rend() const 
  397.     { return const_reverse_iterator(this->_M_start); }
  398.  
  399.   reference operator[](size_type __n)
  400.     { return this->_M_start[difference_type(__n)]; }
  401.   const_reference operator[](size_type __n) const 
  402.     { return this->_M_start[difference_type(__n)]; }
  403.  
  404.   void _M_range_check(size_type __n) const {
  405.     if (__n >= this->size())
  406.       __stl_throw_out_of_range("deque");
  407.   }
  408.   reference at(size_type __n)
  409.     { _M_range_check(__n); return (*this)[__n]; }
  410.   const_reference at(size_type __n) const
  411.     { _M_range_check(__n); return (*this)[__n]; }
  412.  
  413.   reference front() { return *this->_M_start; }
  414.   reference back() {
  415.     iterator __tmp = this->_M_finish;
  416.     --__tmp;
  417.     return *__tmp;
  418.   }
  419.   const_reference front() const { return *this->_M_start; }
  420.   const_reference back() const {
  421.     const_iterator __tmp = this->_M_finish;
  422.     --__tmp;
  423.     return *__tmp;
  424.   }
  425.  
  426.   size_type size() const { return this->_M_finish - this->_M_start; }
  427.   size_type max_size() const { return size_type(-1); }
  428.   bool empty() const { return this->_M_finish == this->_M_start; }
  429.   allocator_type get_allocator() const { return _M_map_size; }
  430.  
  431. public:                         // Constructor, destructor.
  432.   explicit deque(const allocator_type& __a = allocator_type()) 
  433.     : _Deque_base<_Tp, _Alloc>(__a, 0) {}
  434.  
  435.   deque(const _Self& __x) : 
  436.     _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size()) { 
  437.       __uninitialized_copy(__x.begin(), __x.end(), this->_M_start, _IsPODType()); 
  438.   }
  439.  
  440.   deque(size_type __n, const value_type& __val,
  441.         const allocator_type& __a = allocator_type()) : 
  442.     _Deque_base<_Tp, _Alloc>(__a, __n)
  443.     { _M_fill_initialize(__val); }
  444.   // int,long variants may be needed 
  445.   explicit deque(size_type __n) : _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
  446.     { _M_fill_initialize(value_type()); }
  447.  
  448. #ifdef _STLP_MEMBER_TEMPLATES
  449.  
  450.   template <class _Integer>
  451.   void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
  452.     this->_M_initialize_map(__n);
  453.     _M_fill_initialize(__x);
  454.   }
  455.  
  456.   template <class _InputIter>
  457.   void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
  458.                               const __false_type&) {
  459.     _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
  460.   }
  461.  
  462. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  463.   // VC++ needs this
  464.   template <class _InputIterator>
  465.   deque(_InputIterator __first, _InputIterator __last) : 
  466.     _Deque_base<_Tp, _Alloc>(allocator_type()) {
  467.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  468.     _M_initialize_dispatch(__first, __last, _Integral());
  469.   }
  470. # endif
  471.  
  472.   // Check whether it's an integral type.  If so, it's not an iterator.
  473.   template <class _InputIterator>
  474.   deque(_InputIterator __first, _InputIterator __last,
  475.         const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) : 
  476.     _Deque_base<_Tp, _Alloc>(__a) {
  477.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  478.     _M_initialize_dispatch(__first, __last, _Integral());
  479.   }
  480.  
  481. # else
  482.   deque(const value_type* __first, const value_type* __last,
  483.         const allocator_type& __a = allocator_type() ) 
  484.     : _Deque_base<_Tp, _Alloc>(__a, __last - __first) { 
  485.     __uninitialized_copy(__first, __last, this->_M_start, _IsPODType()); 
  486.   }
  487.  
  488.   deque(const_iterator __first, const_iterator __last,
  489.         const allocator_type& __a = allocator_type() ) 
  490.     : _Deque_base<_Tp, _Alloc>(__a, __last - __first) { 
  491.     __uninitialized_copy(__first, __last, this->_M_start, _IsPODType()); 
  492.   }
  493. #endif /* _STLP_MEMBER_TEMPLATES */
  494.  
  495.   ~deque() { 
  496.     _Destroy(this->_M_start, this->_M_finish); 
  497.   }
  498.  
  499.   _Self& operator= (const _Self& __x);
  500.  
  501.   void swap(_Self& __x) {
  502.     _STLP_STD::swap(this->_M_start, __x._M_start);
  503.     _STLP_STD::swap(this->_M_finish, __x._M_finish);
  504.     _STLP_STD::swap(this->_M_map, __x._M_map);
  505.     _STLP_STD::swap(this->_M_map_size, __x._M_map_size);
  506.   }
  507.  
  508. public: 
  509.   // assign(), a generalized assignment member function.  Two
  510.   // versions: one that takes a count, and one that takes a range.
  511.   // The range version is a member template, so we dispatch on whether
  512.   // or not the type is an integer.
  513.  
  514.   void _M_fill_assign(size_type __n, const _Tp& __val) {
  515.     if (__n > size()) {
  516.       _STLP_STD::fill(begin(), end(), __val);
  517.       insert(end(), __n - size(), __val);
  518.     }
  519.     else {
  520.       erase(begin() + __n, end());
  521.       _STLP_STD::fill(begin(), end(), __val);
  522.     }
  523.   }
  524.  
  525.   void assign(size_type __n, const _Tp& __val) {
  526.     _M_fill_assign(__n, __val);
  527.   }
  528.  
  529. #ifdef _STLP_MEMBER_TEMPLATES
  530.  
  531.   template <class _InputIterator>
  532.   void assign(_InputIterator __first, _InputIterator __last) {
  533.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  534.     _M_assign_dispatch(__first, __last, _Integral());
  535.   }
  536.  
  537. private:                        // helper functions for assign() 
  538.  
  539.   template <class _Integer>
  540.   void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
  541.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  542.  
  543.   template <class _InputIterator>
  544.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  545.                           const __false_type&) {
  546.     _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
  547.   }
  548.  
  549.   template <class _InputIter>
  550.   void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
  551.     iterator __cur = begin();
  552.     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  553.       *__cur = *__first;
  554.     if (__first == __last)
  555.       erase(__cur, end());
  556.     else
  557.       insert(end(), __first, __last);
  558.   }
  559.  
  560.   template <class _ForwardIterator>
  561.   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  562.                      const forward_iterator_tag &) {
  563.     size_type __len = distance(__first, __last);
  564.     if (__len > size()) {
  565.       _ForwardIterator __mid = __first;
  566.       advance(__mid, size());
  567.       copy(__first, __mid, begin());
  568.       insert(end(), __mid, __last);
  569.     }
  570.     else
  571.       erase(copy(__first, __last, begin()), end());
  572.   }
  573.  
  574. #endif /* _STLP_MEMBER_TEMPLATES */
  575.  
  576. public:                         // push_* and pop_*
  577.   
  578.   void push_back(const value_type& __t) {
  579.     if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
  580.       _Construct(this->_M_finish._M_cur, __t);
  581.       ++this->_M_finish._M_cur;
  582.     }
  583.     else
  584.       _M_push_back_aux_v(__t);
  585.   }
  586.   void push_front(const value_type& __t) {
  587.     if (this->_M_start._M_cur != this->_M_start._M_first) {
  588.       _Construct(this->_M_start._M_cur - 1, __t);
  589.       --this->_M_start._M_cur;
  590.     }
  591.     else
  592.       _M_push_front_aux_v(__t);
  593.   }
  594.  
  595. # ifndef _STLP_NO_ANACHRONISMS
  596.   void push_back() {
  597.     if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
  598.       _Construct(this->_M_finish._M_cur);
  599.       ++this->_M_finish._M_cur;
  600.     }
  601.     else
  602.       _M_push_back_aux();
  603.   }
  604.   void push_front() {
  605.     if (this->_M_start._M_cur != this->_M_start._M_first) {
  606.       _Construct(this->_M_start._M_cur - 1);
  607.       --this->_M_start._M_cur;
  608.     }
  609.     else
  610.       _M_push_front_aux();
  611.   }
  612. # endif
  613.  
  614.   void pop_back() {
  615.     if (this->_M_finish._M_cur != this->_M_finish._M_first) {
  616.       --this->_M_finish._M_cur;
  617.       _Destroy(this->_M_finish._M_cur);
  618.     }
  619.     else
  620.       _M_pop_back_aux();
  621.   }
  622.  
  623.   void pop_front() {
  624.     if (this->_M_start._M_cur != this->_M_start._M_last - 1) {
  625.       _Destroy(this->_M_start._M_cur);
  626.       ++this->_M_start._M_cur;
  627.     }
  628.     else 
  629.       _M_pop_front_aux();
  630.   }
  631.  
  632. public:                         // Insert
  633.  
  634.   iterator insert(iterator __position, const value_type& __x) {
  635.     if (__position._M_cur == this->_M_start._M_cur) {
  636.       push_front(__x);
  637.       return this->_M_start;
  638.     }
  639.     else if (__position._M_cur == this->_M_finish._M_cur) {
  640.       push_back(__x);
  641.       iterator __tmp = this->_M_finish;
  642.       --__tmp;
  643.       return __tmp;
  644.     }
  645.     else {
  646.       return _M_insert_aux(__position, __x);
  647.     }
  648.   }
  649.  
  650.   iterator insert(iterator __position)
  651.     { return insert(__position, value_type()); }
  652.  
  653.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  654.     _M_fill_insert(__pos, __n, __x);
  655.   }
  656.  
  657.   void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
  658.  
  659. #ifdef _STLP_MEMBER_TEMPLATES  
  660.  
  661.   // Check whether it's an integral type.  If so, it's not an iterator.
  662.   template <class _InputIterator>
  663.   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
  664.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  665.     _M_insert_dispatch(__pos, __first, __last, _Integral());
  666.   }
  667.  
  668.   template <class _Integer>
  669.   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
  670.                           const __true_type&) {
  671.     _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
  672.   }
  673.  
  674.   template <class _InputIterator>
  675.   void _M_insert_dispatch(iterator __pos,
  676.                           _InputIterator __first, _InputIterator __last,
  677.                           const __false_type&) {
  678.     insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
  679.   }
  680.  
  681. #else /* _STLP_MEMBER_TEMPLATES */
  682.  
  683.   void insert(iterator __pos,
  684.               const value_type* __first, const value_type* __last);
  685.   void insert(iterator __pos,
  686.               const_iterator __first, const_iterator __last);
  687.  
  688. #endif /* _STLP_MEMBER_TEMPLATES */
  689.  
  690.   void resize(size_type __new_size, const value_type& __x) {
  691.     const size_type __len = size();
  692.     if (__new_size < __len) 
  693.       erase(this->_M_start + __new_size, this->_M_finish);
  694.     else
  695.       insert(this->_M_finish, __new_size - __len, __x);
  696.   }
  697.  
  698.   void resize(size_type new_size) { resize(new_size, value_type()); }
  699.  
  700. public:                         // Erase
  701.   iterator erase(iterator __pos) {
  702.     iterator __next = __pos;
  703.     ++__next;
  704.     difference_type __index = __pos - this->_M_start;
  705.     if (size_type(__index) < this->size() >> 1) {
  706.       copy_backward(this->_M_start, __pos, __next);
  707.       pop_front();
  708.     }
  709.     else {
  710.       copy(__next, this->_M_finish, __pos);
  711.       pop_back();
  712.     }
  713.     return this->_M_start + __index;
  714.   }
  715.  
  716.   iterator erase(iterator __first, iterator __last);
  717.   void clear(); 
  718.  
  719. protected:                        // Internal construction/destruction
  720.  
  721.   void _M_fill_initialize(const value_type& __val);
  722.  
  723. #ifdef _STLP_MEMBER_TEMPLATES 
  724.  
  725.   template <class _InputIterator>
  726.   void _M_range_initialize(_InputIterator __first,
  727.                _InputIterator __last,
  728.                const input_iterator_tag &) {
  729.     this->_M_initialize_map(0);
  730.     _STLP_TRY {
  731.       for ( ; __first != __last; ++__first)
  732.         push_back(*__first);
  733.     }
  734.     _STLP_UNWIND(clear());
  735.   }
  736.  template <class _ForwardIterator>
  737.  void  _M_range_initialize(_ForwardIterator __first,
  738.                            _ForwardIterator __last,
  739.                            const forward_iterator_tag &)  {
  740.    size_type __n = distance(__first, __last);
  741.    this->_M_initialize_map(__n);
  742.    _Map_pointer __cur_node;
  743.    _STLP_TRY {
  744.     for (__cur_node = this->_M_start._M_node; 
  745.          __cur_node < this->_M_finish._M_node; 
  746.      ++__cur_node) {
  747.       _ForwardIterator __mid = __first;
  748.       advance(__mid, this->buffer_size());
  749.       uninitialized_copy(__first, __mid, *__cur_node);
  750.       __first = __mid;
  751.     }
  752.     uninitialized_copy(__first, __last, this->_M_finish._M_first);
  753.    }
  754.   _STLP_UNWIND(_Destroy(this->_M_start, iterator(*__cur_node, __cur_node)));
  755.  }
  756. #endif /* _STLP_MEMBER_TEMPLATES */
  757.  
  758. protected:                        // Internal push_* and pop_*
  759.  
  760.   void _M_push_back_aux_v(const value_type&);
  761.   void _M_push_front_aux_v(const value_type&);
  762. # ifndef _STLP_NO_ANACHRONISMS
  763.   void _M_push_back_aux();
  764.   void _M_push_front_aux();
  765. # endif
  766.   void _M_pop_back_aux();
  767.   void _M_pop_front_aux();
  768.  
  769. protected:                        // Internal insert functions
  770.  
  771. #ifdef _STLP_MEMBER_TEMPLATES
  772.  
  773. template <class _InputIterator>
  774. void 
  775. insert(iterator __pos,
  776.        _InputIterator __first,
  777.        _InputIterator __last,
  778.        const input_iterator_tag &)
  779. {
  780.   copy(__first, __last, inserter(*this, __pos));
  781. }
  782.  
  783. template <class _ForwardIterator>
  784. void  insert(iterator __pos,
  785.          _ForwardIterator __first,
  786.          _ForwardIterator __last,
  787.          const forward_iterator_tag &)
  788.  {
  789.   size_type __n = distance(__first, __last);
  790.   if (__pos._M_cur == this->_M_start._M_cur) {
  791.     iterator __new_start = _M_reserve_elements_at_front(__n);
  792.     _STLP_TRY {
  793.       uninitialized_copy(__first, __last, __new_start);
  794.       this->_M_start = __new_start;
  795.     }
  796.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  797.   }
  798.   else if (__pos._M_cur == this->_M_finish._M_cur) {
  799.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  800.     _STLP_TRY {
  801.       uninitialized_copy(__first, __last, this->_M_finish);
  802.       this->_M_finish = __new_finish;
  803.     }
  804.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
  805.   }
  806.   else
  807.     _M_insert_aux(__pos, __first, __last, __n);
  808. }
  809. #endif /* _STLP_MEMBER_TEMPLATES */
  810.  
  811.   iterator _M_insert_aux(iterator __pos, const value_type& __x);
  812.   iterator _M_insert_aux(iterator __pos);
  813.   iterator _M_insert_aux_prepare(iterator __pos);
  814.  
  815.   void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
  816.  
  817. #ifdef _STLP_MEMBER_TEMPLATES  
  818.   template <class _ForwardIterator>
  819.   void _M_insert_aux(iterator __pos,
  820.                      _ForwardIterator __first,
  821.                      _ForwardIterator __last,
  822.                      size_type __n) {
  823.     
  824.     const difference_type __elemsbefore = __pos - this->_M_start;
  825.     size_type __length = size();
  826.     if (__elemsbefore < difference_type(__length / 2)) {
  827.       iterator __new_start = _M_reserve_elements_at_front(__n);
  828.       iterator __old_start = this->_M_start;
  829.       __pos = this->_M_start + __elemsbefore;
  830.       _STLP_TRY {
  831.     if (__elemsbefore >= difference_type(__n)) {
  832.       iterator __start_n = this->_M_start + difference_type(__n); 
  833.       uninitialized_copy(this->_M_start, __start_n, __new_start);
  834.       this->_M_start = __new_start;
  835.       copy(__start_n, __pos, __old_start);
  836.       copy(__first, __last, __pos - difference_type(__n));
  837.     }
  838.     else {
  839.       _ForwardIterator __mid = __first;
  840.       advance(__mid, difference_type(__n) - __elemsbefore);
  841.       __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
  842.                     __new_start, _IsPODType());
  843.       this->_M_start = __new_start;
  844.       copy(__mid, __last, __old_start);
  845.     }
  846.       }
  847.       _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  848.     }
  849.     else {
  850.       iterator __new_finish = _M_reserve_elements_at_back(__n);
  851.       iterator __old_finish = this->_M_finish;
  852.       const difference_type __elemsafter = 
  853.     difference_type(__length) - __elemsbefore;
  854.       __pos = this->_M_finish - __elemsafter;
  855.       _STLP_TRY {
  856.       if (__elemsafter > difference_type(__n)) {
  857.         iterator __finish_n = this->_M_finish - difference_type(__n);
  858.         uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
  859.         this->_M_finish = __new_finish;
  860.         copy_backward(__pos, __finish_n, __old_finish);
  861.         copy(__first, __last, __pos);
  862.       }
  863.       else {
  864.         _ForwardIterator __mid = __first;
  865.         advance(__mid, __elemsafter);
  866.         __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
  867.         this->_M_finish = __new_finish;
  868.         copy(__first, __mid, __pos);
  869.       }
  870.       }
  871.       _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
  872.     }
  873.   }
  874. #else /* _STLP_MEMBER_TEMPLATES */
  875.   
  876.   void _M_insert_aux(iterator __pos,
  877.                      const value_type* __first, const value_type* __last,
  878.                      size_type __n);
  879.  
  880.   void _M_insert_aux(iterator __pos, 
  881.                      const_iterator __first, const_iterator __last,
  882.                      size_type __n);
  883.  
  884. #endif /* _STLP_MEMBER_TEMPLATES */
  885.  
  886.   iterator _M_reserve_elements_at_front(size_type __n) {
  887.     size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
  888.     if (__n > __vacancies) 
  889.       _M_new_elements_at_front(__n - __vacancies);
  890.     return this->_M_start - difference_type(__n);
  891.   }
  892.  
  893.   iterator _M_reserve_elements_at_back(size_type __n) {
  894.     size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
  895.     if (__n > __vacancies)
  896.       _M_new_elements_at_back(__n - __vacancies);
  897.     return this->_M_finish + difference_type(__n);
  898.   }
  899.  
  900.   void _M_new_elements_at_front(size_type __new_elements);
  901.   void _M_new_elements_at_back(size_type __new_elements);
  902.  
  903. protected:                      // Allocation of _M_map and nodes
  904.  
  905.   // Makes sure the _M_map has space for new nodes.  Does not actually
  906.   //  add the nodes.  Can invalidate _M_map pointers.  (And consequently, 
  907.   //  deque iterators.)
  908.  
  909.   void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
  910.     if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
  911.       _M_reallocate_map(__nodes_to_add, false);
  912.   }
  913.  
  914.   void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
  915.     if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
  916.       _M_reallocate_map(__nodes_to_add, true);
  917.   }
  918.  
  919.   void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
  920.  
  921. };
  922.  
  923. // Nonmember functions.
  924.  
  925. template <class _Tp, class _Alloc >
  926. inline bool  _STLP_CALL operator==(const deque<_Tp, _Alloc>& __x,
  927.                                    const deque<_Tp, _Alloc>& __y)
  928. {
  929.   return __x.size() == __y.size() &&
  930.   equal(__x.begin(), __x.end(), __y.begin());
  931. }
  932.  
  933. template <class _Tp, class _Alloc >
  934. inline bool  _STLP_CALL operator<(const deque<_Tp, _Alloc>& __x,
  935.                                   const deque<_Tp, _Alloc>& __y)
  936. {
  937.   return lexicographical_compare(__x.begin(), __x.end(), 
  938.                                  __y.begin(), __y.end());
  939. }
  940.  
  941. #if defined(_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
  942.  
  943. template <class _Tp, class _Alloc >
  944. inline bool  _STLP_CALL operator!=(const deque<_Tp, _Alloc>& __x,
  945.                                   const deque<_Tp, _Alloc>& __y)
  946. {
  947.   return  !(__x == __y); 
  948. }
  949.  
  950. template <class _Tp, class _Alloc >
  951. inline bool  _STLP_CALL operator>(const deque<_Tp, _Alloc>& __x,
  952.                                   const deque<_Tp, _Alloc>& __y)
  953. {
  954.   return __y < __x; 
  955. }
  956.  
  957. template <class _Tp, class _Alloc >
  958. inline bool _STLP_CALL operator>=(const deque<_Tp, _Alloc>& __x,
  959.                                   const deque<_Tp, _Alloc>& __y)
  960. {
  961.   return !(__x < __y); 
  962. }
  963.  
  964. template <class _Tp, class _Alloc >
  965. inline bool _STLP_CALL operator<=(const deque<_Tp, _Alloc>& __x,
  966.                                   const deque<_Tp, _Alloc>& __y)
  967. {
  968.  return !(__y < __x); 
  969. }
  970.  
  971.  
  972. # endif /* _STLP_SEPARATE_RELOPS_NAMESPACE */
  973.  
  974. # if defined(_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
  975.  
  976. template <class _Tp, class _Alloc>
  977. inline void _STLP_CALL 
  978. swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
  979. {
  980.   __x.swap(__y);
  981. }
  982.  
  983. # endif
  984.  
  985. _STLP_END_NAMESPACE 
  986.  
  987. // do a cleanup
  988. # undef deque
  989. # undef __deque__
  990. # define __deque__ __WORKAROUND_DBG_RENAME(deque)
  991.  
  992. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  993. #  include <stl/_deque.c>
  994. # endif
  995.  
  996. #if defined (_STLP_DEBUG)
  997. # include <stl/debug/_deque.h>
  998. #endif
  999.  
  1000. # if defined (_STLP_USE_WRAPPER_FOR_ALLOC_PARAM)
  1001. #  include <stl/wrappers/_deque.h>
  1002. # endif
  1003.   
  1004. #endif /* _STLP_INTERNAL_DEQUE_H */
  1005.  
  1006. // Local Variables:
  1007. // mode:C++
  1008. // End:
  1009.  
  1010.