home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / include / list < prev    next >
Text File  |  1998-06-16  |  13KB  |  471 lines
  1. // list standard header
  2.  
  3. #if     _MSC_VER > 1000
  4. #pragma once
  5. #endif
  6.  
  7. #ifndef _LIST_
  8. #define _LIST_
  9. #include <cstddef>
  10. #include <functional>
  11. #include <iterator>
  12. #include <memory>
  13. #include <stdexcept>
  14. #include <xutility>
  15.  
  16. #ifdef  _MSC_VER
  17. #pragma pack(push,8)
  18. #endif  /* _MSC_VER */
  19. _STD_BEGIN
  20.         // TEMPLATE CLASS list
  21. template<class _Ty, class _A = allocator<_Ty> >
  22.     class list {
  23. protected:
  24.     struct _Node;
  25.     friend struct _Node;
  26.     typedef _POINTER_X(_Node, _A) _Nodeptr;
  27.     struct _Node {
  28.         _Nodeptr _Next, _Prev;
  29.         _Ty _Value;
  30.         };
  31.     struct _Acc;
  32.     friend struct _Acc;
  33.     struct _Acc {
  34.         typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
  35.         typedef _A::reference _Vref;
  36.         static _Nodepref _Next(_Nodeptr _P)
  37.             {return ((_Nodepref)(*_P)._Next); }
  38.         static _Nodepref _Prev(_Nodeptr _P)
  39.             {return ((_Nodepref)(*_P)._Prev); }
  40.         static _Vref _Value(_Nodeptr _P)
  41.             {return ((_Vref)(*_P)._Value); }
  42.         };
  43. public:
  44.     typedef list<_Ty, _A> _Myt;
  45.     typedef _A allocator_type;
  46.     typedef _A::size_type size_type;
  47.     typedef _A::difference_type difference_type;
  48.     typedef _A::pointer _Tptr;
  49.     typedef _A::const_pointer _Ctptr;
  50.     typedef _A::reference reference;
  51.     typedef _A::const_reference const_reference;
  52.     typedef _A::value_type value_type;
  53.         // CLASS const_iterator
  54.     class iterator;
  55.     class const_iterator;
  56.     friend class const_iterator;
  57.     class const_iterator : public _Bidit<_Ty, difference_type> {
  58.     public:
  59.         const_iterator()
  60.             {}
  61.         const_iterator(_Nodeptr _P)
  62.             : _Ptr(_P) {}
  63.         const_iterator(const iterator& _X)
  64.             : _Ptr(_X._Ptr) {}
  65.         const_reference operator*() const
  66.             {return (_Acc::_Value(_Ptr)); }
  67.         _Ctptr operator->() const
  68.             {return (&**this); }
  69.         const_iterator& operator++()
  70.             {_Ptr = _Acc::_Next(_Ptr);
  71.             return (*this); }
  72.         const_iterator operator++(int)
  73.             {const_iterator _Tmp = *this;
  74.             ++*this;
  75.             return (_Tmp); }
  76.         const_iterator& operator--()
  77.             {_Ptr = _Acc::_Prev(_Ptr);
  78.             return (*this); }
  79.         const_iterator operator--(int)
  80.             {const_iterator _Tmp = *this;
  81.             --*this;
  82.             return (_Tmp); }
  83.         bool operator==(const const_iterator& _X) const
  84.             {return (_Ptr == _X._Ptr); }
  85.         bool operator!=(const const_iterator& _X) const
  86.             {return (!(*this == _X)); }
  87.         _Nodeptr _Mynode() const
  88.             {return (_Ptr); }
  89.     protected:
  90.         _Nodeptr _Ptr;
  91.         };
  92.         // CLASS iterator
  93.     friend class iterator;
  94.     class iterator : public const_iterator {
  95.     public:
  96.         iterator()
  97.             {}
  98.         iterator(_Nodeptr _P)
  99.             : const_iterator(_P) {}
  100.         reference operator*() const
  101.             {return (_Acc::_Value(_Ptr)); }
  102.         _Tptr operator->() const
  103.             {return (&**this); }
  104.         iterator& operator++()
  105.             {_Ptr = _Acc::_Next(_Ptr);
  106.             return (*this); }
  107.         iterator operator++(int)
  108.             {iterator _Tmp = *this;
  109.             ++*this;
  110.             return (_Tmp); }
  111.         iterator& operator--()
  112.             {_Ptr = _Acc::_Prev(_Ptr);
  113.             return (*this); }
  114.         iterator operator--(int)
  115.             {iterator _Tmp = *this;
  116.             --*this;
  117.             return (_Tmp); }
  118.         bool operator==(const iterator& _X) const
  119.             {return (_Ptr == _X._Ptr); }
  120.         bool operator!=(const iterator& _X) const
  121.             {return (!(*this == _X)); }
  122.         };
  123.     typedef reverse_bidirectional_iterator<iterator,
  124.         value_type, reference, _Tptr, difference_type>
  125.             reverse_iterator;
  126.     typedef reverse_bidirectional_iterator<const_iterator,
  127.         value_type, const_reference, _Ctptr, difference_type>
  128.             const_reverse_iterator;
  129.     explicit list(const _A& _Al = _A())
  130.         : allocator(_Al),
  131.         _Head(_Buynode()), _Size(0) {}
  132.     explicit list(size_type _N, const _Ty& _V = _Ty(),
  133.         const _A& _Al = _A())
  134.         : allocator(_Al),
  135.         _Head(_Buynode()), _Size(0)
  136.         {insert(begin(), _N, _V); }
  137.     list(const _Myt& _X)
  138.         : allocator(_X.allocator),
  139.         _Head(_Buynode()), _Size(0)
  140.         {insert(begin(), _X.begin(), _X.end()); }
  141.     list(const _Ty *_F, const _Ty *_L, const _A& _Al = _A())
  142.         : allocator(_Al),
  143.         _Head(_Buynode()), _Size(0)
  144.         {insert(begin(), _F, _L); }
  145.     typedef const_iterator _It;
  146.     list(_It _F, _It _L, const _A& _Al = _A())
  147.         : allocator(_Al),
  148.         _Head(_Buynode()), _Size(0)
  149.         {insert(begin(), _F, _L); }
  150.     ~list()
  151.         {erase(begin(), end());
  152.         _Freenode(_Head);
  153.         _Head = 0, _Size = 0; }
  154.     _Myt& operator=(const _Myt& _X)
  155.         {if (this != &_X)
  156.             {iterator _F1 = begin();
  157.             iterator _L1 = end();
  158.             const_iterator _F2 = _X.begin();
  159.             const_iterator _L2 = _X.end();
  160.             for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)
  161.                 *_F1 = *_F2;
  162.             erase(_F1, _L1);
  163.             insert(_L1, _F2, _L2); }
  164.         return (*this); }
  165.     iterator begin()
  166.         {return (iterator(_Acc::_Next(_Head))); }
  167.     const_iterator begin() const
  168.         {return (const_iterator(_Acc::_Next(_Head))); }
  169.     iterator end()
  170.         {return (iterator(_Head)); }
  171.     const_iterator end() const
  172.         {return (const_iterator(_Head)); }
  173.     reverse_iterator rbegin()
  174.         {return (reverse_iterator(end())); }
  175.     const_reverse_iterator rbegin() const
  176.         {return (const_reverse_iterator(end())); }
  177.     reverse_iterator rend()
  178.         {return (reverse_iterator(begin())); }
  179.     const_reverse_iterator rend() const
  180.         {return (const_reverse_iterator(begin())); }
  181.     void resize(size_type _N, _Ty _X = _Ty())
  182.         {if (size() < _N)
  183.             insert(end(), _N - size(), _X);
  184.         else
  185.             while (_N < size())
  186.                 pop_back(); }
  187.     size_type size() const
  188.         {return (_Size); }
  189.     size_type max_size() const
  190.         {return (allocator.max_size()); }
  191.     bool empty() const
  192.         {return (size() == 0); }
  193.     _A get_allocator() const
  194.         {return (allocator); }
  195.     reference front()
  196.         {return (*begin()); }
  197.     const_reference front() const
  198.         {return (*begin()); }
  199.     reference back()
  200.         {return (*(--end())); }
  201.     const_reference back() const
  202.         {return (*(--end())); }
  203.     void push_front(const _Ty& _X)
  204.         {insert(begin(), _X); }
  205.     void pop_front()
  206.         {erase(begin()); }
  207.     void push_back(const _Ty& _X)
  208.         {insert(end(), _X); }
  209.     void pop_back()
  210.         {erase(--end()); }
  211.     void assign(_It _F, _It _L)
  212.         {erase(begin(), end());
  213.         insert(begin(), _F, _L); }
  214.     void assign(size_type _N, const _Ty& _X = _Ty())
  215.         {erase(begin(), end());
  216.         insert(begin(), _N, _X); }
  217.     iterator insert(iterator _P, const _Ty& _X = _Ty())
  218.         {_Nodeptr _S = _P._Mynode();
  219.         _Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
  220.         _S = _Acc::_Prev(_S);
  221.         _Acc::_Next(_Acc::_Prev(_S)) = _S;
  222.         allocator.construct(&_Acc::_Value(_S), _X);
  223.         ++_Size;
  224.         return (iterator(_S)); }
  225.     void insert(iterator _P, size_type _M, const _Ty& _X)
  226.         {for (; 0 < _M; --_M)
  227.             insert(_P, _X); }
  228.     void insert(iterator _P, const _Ty *_F, const _Ty *_L)
  229.         {for (; _F != _L; ++_F)
  230.             insert(_P, *_F); }
  231.     void insert(iterator _P, _It _F, _It _L)
  232.         {for (; _F != _L; ++_F)
  233.             insert(_P, *_F); }
  234.     iterator erase(iterator _P)
  235.         {_Nodeptr _S = (_P++)._Mynode();
  236.         _Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
  237.         _Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
  238.         allocator.destroy(&_Acc::_Value(_S));
  239.         _Freenode(_S);
  240.         --_Size;
  241.         return (_P); }
  242.     iterator erase(iterator _F, iterator _L)
  243.         {while (_F != _L)
  244.             erase(_F++);
  245.         return (_F); }
  246.     void clear()
  247.         {erase(begin(), end()); }
  248.     void swap(_Myt& _X)
  249.         {if (allocator == _X.allocator)
  250.             {std::swap(_Head, _X._Head);
  251.             std::swap(_Size, _X._Size); }
  252.         else
  253.             {iterator _P = begin();
  254.             splice(_P, _X);
  255.             _X.splice(_X.begin(), *this, _P, end()); }}
  256.     friend void swap(_Myt& _X, _Myt& _Y)
  257.         {_X.swap(_Y); }
  258.     void splice(iterator _P, _Myt& _X)
  259.         {if (!_X.empty())
  260.             {_Splice(_P, _X, _X.begin(), _X.end());
  261.             _Size += _X._Size;
  262.             _X._Size = 0; }}
  263.     void splice(iterator _P, _Myt& _X, iterator _F)
  264.         {iterator _L = _F;
  265.         if (_P != _F && _P != ++_L)
  266.             {_Splice(_P, _X, _F, _L);
  267.             ++_Size;
  268.             --_X._Size; }}
  269.     void splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
  270.         {if (_F != _L)
  271.             {if (&_X != this)
  272.                 {difference_type _N = 0;
  273.                 _Distance(_F, _L, _N);
  274.                 _Size += _N;
  275.                 _X._Size -= _N; }
  276.             _Splice(_P, _X, _F, _L); }}
  277.     void remove(const _Ty& _V)
  278.         {iterator _L = end();
  279.         for (iterator _F = begin(); _F != _L; )
  280.             if (*_F == _V)
  281.                 erase(_F++);
  282.             else
  283.                 ++_F; }
  284.     typedef binder2nd<not_equal_to<_Ty> > _Pr1;
  285.     void remove_if(_Pr1 _Pr)
  286.         {iterator _L = end();
  287.         for (iterator _F = begin(); _F != _L; )
  288.             if (_Pr(*_F))
  289.                 erase(_F++);
  290.             else
  291.                 ++_F; }
  292.     void unique()
  293.         {iterator _F = begin(), _L = end();
  294.         if (_F != _L)
  295.             for (iterator _M = _F; ++_M != _L; _M = _F)
  296.                 if (*_F == *_M)
  297.                     erase(_M);
  298.                 else
  299.                     _F = _M; }
  300.     typedef not_equal_to<_Ty> _Pr2;
  301.     void unique(_Pr2 _Pr)
  302.         {iterator _F = begin(), _L = end();
  303.         if (_F != _L)
  304.             for (iterator _M = _F; ++_M != _L; _M = _F)
  305.                 if (_Pr(*_F, *_M))
  306.                     erase(_M);
  307.                 else
  308.                     _F = _M; }
  309.     void merge(_Myt& _X)
  310.         {if (&_X != this)
  311.             {iterator _F1 = begin(), _L1 = end();
  312.             iterator _F2 = _X.begin(), _L2 = _X.end();
  313.             while (_F1 != _L1 && _F2 != _L2)
  314.                 if (*_F2 < *_F1)
  315.                     {iterator _Mid2 = _F2;
  316.                     _Splice(_F1, _X, _F2, ++_Mid2);
  317.                     _F2 = _Mid2; }
  318.                 else
  319.                     ++_F1;
  320.             if (_F2 != _L2)
  321.                 _Splice(_L1, _X, _F2, _L2);
  322.             _Size += _X._Size;
  323.             _X._Size = 0; }}
  324.     typedef greater<_Ty> _Pr3;
  325.     void merge(_Myt& _X, _Pr3 _Pr)
  326.         {if (&_X != this)
  327.             {iterator _F1 = begin(), _L1 = end();
  328.             iterator _F2 = _X.begin(), _L2 = _X.end();
  329.             while (_F1 != _L1 && _F2 != _L2)
  330.                 if (_Pr(*_F2, *_F1))
  331.                     {iterator _Mid2 = _F2;
  332.                     _Splice(_F1, _X, _F2, ++_Mid2);
  333.                     _F2 = _Mid2; }
  334.                 else
  335.                     ++_F1;
  336.             if (_F2 != _L2)
  337.                 _Splice(_L1, _X, _F2, _L2);
  338.             _Size += _X._Size;
  339.             _X._Size = 0; }}
  340.     void sort()
  341.         {if (2 <= size())
  342.             {const size_t _MAXN = 15;
  343.             _Myt _X(allocator), _A[_MAXN + 1];
  344.             size_t _N = 0;
  345.             while (!empty())
  346.                 {_X.splice(_X.begin(), *this, begin());
  347.                 size_t _I;
  348.                 for (_I = 0; _I < _N && !_A[_I].empty(); ++_I)
  349.                     {_A[_I].merge(_X);
  350.                     _A[_I].swap(_X); }
  351.                 if (_I == _MAXN)
  352.                     _A[_I].merge(_X);
  353.                 else
  354.                     {_A[_I].swap(_X);
  355.                     if (_I == _N)
  356.                         ++_N; }}
  357.             while (0 < _N)
  358.                 merge(_A[--_N]); }}
  359.     void sort(_Pr3 _Pr)
  360.         {if (2 <= size())
  361.             {const size_t _MAXN = 15;
  362.             _Myt _X(allocator), _A[_MAXN + 1];
  363.             size_t _N = 0;
  364.             while (!empty())
  365.                 {_X.splice(_X.begin(), *this, begin());
  366.                 size_t _I;
  367.                 for (_I = 0; _I < _N && !_A[_I].empty(); ++_I)
  368.                     {_A[_I].merge(_X, _Pr);
  369.                     _A[_I].swap(_X); }
  370.                 if (_I == _MAXN)
  371.                     _A[_I].merge(_X, _Pr);
  372.                 else
  373.                     {_A[_I].swap(_X);
  374.                     if (_I == _N)
  375.                         ++_N; }}
  376.             while (0 < _N)
  377.                 merge(_A[--_N], _Pr); }}
  378.     void reverse()
  379.         {if (2 <= size())
  380.             {iterator _L = end();
  381.             for (iterator _F = ++begin(); _F != _L; )
  382.                 {iterator _M = _F;
  383.                 _Splice(begin(), *this, _M, ++_F); }}}
  384. protected:
  385.     _Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
  386.         {_Nodeptr _S = (_Nodeptr)allocator._Charalloc(
  387.             1 * sizeof (_Node));
  388.         _Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
  389.         _Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
  390.         return (_S); }
  391.     void _Freenode(_Nodeptr _S)
  392.         {allocator.deallocate(_S, 1); }
  393.     void _Splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
  394.         {if (allocator == _X.allocator)
  395.             {_Acc::_Next(_Acc::_Prev(_L._Mynode())) =
  396.                 _P._Mynode();
  397.             _Acc::_Next(_Acc::_Prev(_F._Mynode())) =
  398.                 _L._Mynode();
  399.             _Acc::_Next(_Acc::_Prev(_P._Mynode())) =
  400.                 _F._Mynode();
  401.             _Nodeptr _S = _Acc::_Prev(_P._Mynode());
  402.             _Acc::_Prev(_P._Mynode()) =
  403.                 _Acc::_Prev(_L._Mynode());
  404.             _Acc::_Prev(_L._Mynode()) =
  405.                 _Acc::_Prev(_F._Mynode());
  406.             _Acc::_Prev(_F._Mynode()) = _S; }
  407.         else
  408.             {insert(_P, _F, _L);
  409.             _X.erase(_F, _L); }}
  410.     void _Xran() const
  411.         {_THROW(out_of_range, "invalid list<T> subscript"); }
  412.     _A allocator;
  413.     _Nodeptr _Head;
  414.     size_type _Size;
  415.     };
  416.         // list TEMPLATE OPERATORS
  417. template<class _Ty, class _A> inline
  418.     bool operator==(const list<_Ty, _A>& _X,
  419.         const list<_Ty, _A>& _Y)
  420.     {return (_X.size() == _Y.size()
  421.         && equal(_X.begin(), _X.end(), _Y.begin())); }
  422. template<class _Ty, class _A> inline
  423.     bool operator!=(const list<_Ty, _A>& _X,
  424.         const list<_Ty, _A>& _Y)
  425.     {return (!(_X == _Y)); }
  426. template<class _Ty, class _A> inline
  427.     bool operator<(const list<_Ty, _A>& _X,
  428.         const list<_Ty, _A>& _Y)
  429.     {return (lexicographical_compare(_X.begin(), _X.end(),
  430.         _Y.begin(), _Y.end())); }
  431. template<class _Ty, class _A> inline
  432.     bool operator>(const list<_Ty, _A>& _X,
  433.         const list<_Ty, _A>& _Y)
  434.     {return (_Y < _X); }
  435. template<class _Ty, class _A> inline
  436.     bool operator<=(const list<_Ty, _A>& _X,
  437.         const list<_Ty, _A>& _Y)
  438.     {return (!(_Y < _X)); }
  439. template<class _Ty, class _A> inline
  440.     bool operator>=(const list<_Ty, _A>& _X,
  441.         const list<_Ty, _A>& _Y)
  442.     {return (!(_X < _Y)); }
  443. _STD_END
  444. #ifdef  _MSC_VER
  445. #pragma pack(pop)
  446. #endif  /* _MSC_VER */
  447.  
  448. #endif /* _LIST_ */
  449.  
  450. /*
  451.  * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
  452.  * Consult your license regarding permissions and restrictions.
  453.  */
  454.  
  455. /*
  456.  * This file is derived from software bearing the following
  457.  * restrictions:
  458.  *
  459.  * Copyright (c) 1994
  460.  * Hewlett-Packard Company
  461.  *
  462.  * Permission to use, copy, modify, distribute and sell this
  463.  * software and its documentation for any purpose is hereby
  464.  * granted without fee, provided that the above copyright notice
  465.  * appear in all copies and that both that copyright notice and
  466.  * this permission notice appear in supporting documentation.
  467.  * Hewlett-Packard Company makes no representations about the
  468.  * suitability of this software for any purpose. It is provided
  469.  * "as is" without express or implied warranty.
  470.  */
  471.