home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / include / deque < prev    next >
Text File  |  1998-06-16  |  17KB  |  567 lines
  1. // deque standard header
  2.  
  3. #if     _MSC_VER > 1000
  4. #pragma once
  5. #endif
  6.  
  7. #ifndef _DEQUE_
  8. #define _DEQUE_
  9. #include <iterator>
  10. #include <memory>
  11. #include <stdexcept>
  12. #include <xutility>
  13.  
  14. #ifdef  _MSC_VER
  15. #pragma pack(push,8)
  16. #endif  /* _MSC_VER */
  17. _STD_BEGIN
  18. #define _DEQUEMAPSIZ    2
  19. #define _DEQUESIZ (4096 < sizeof (_Ty) ? 1 : 4096 / sizeof (_Ty))
  20.         // TEMPLATE CLASS deque
  21. template<class _Ty, class _A = allocator<_Ty> >
  22.     class deque {
  23. public:
  24.     typedef deque<_Ty, _A> _Myt;
  25.     typedef _A allocator_type;
  26.     typedef _A::size_type size_type;
  27.     typedef _A::difference_type difference_type;
  28.     typedef _A::pointer _Tptr;
  29.     typedef _A::const_pointer _Ctptr;
  30.     typedef _POINTER_X(_Tptr, _A) _Mapptr;
  31.     typedef _A::reference reference;
  32.     typedef _A::const_reference const_reference;
  33.     typedef _A::value_type value_type;
  34.         // CLASS const_iterator
  35.     class iterator;
  36.     class const_iterator : public _Ranit<_Ty, difference_type> {
  37.     public:
  38.         friend class deque<_Ty, _A>;
  39.         const_iterator()
  40.             : _First(0), _Last(0), _Next(0), _Map(0) {}
  41.         const_iterator(_Tptr _P, _Mapptr _M)
  42.             : _First(*_M), _Last(*_M + _DEQUESIZ),
  43.                 _Next(_P), _Map(_M) {}
  44.         const_iterator(const iterator& _X)
  45.             : _First(_X._First), _Last(_X._Last), _Next(_X._Next), 
  46.               _Map(_X._Map) {}
  47.         const_reference operator*() const
  48.             {return (*_Next); }
  49.         _Ctptr operator->() const
  50.             {return (&**this); }
  51.         const_iterator& operator++()
  52.             {if (++_Next == _Last)
  53.                 {_First = *++_Map;
  54.                 _Last = _First + _DEQUESIZ;
  55.                 _Next = _First; }
  56.             return (*this); }
  57.         const_iterator operator++(int)
  58.             {const_iterator _Tmp = *this;
  59.             ++*this;
  60.             return (_Tmp); }
  61.         const_iterator& operator--()
  62.             {if (_Next == _First)
  63.                 {_First = *--_Map;
  64.                 _Last = _First + _DEQUESIZ;
  65.                 _Next = _Last; }
  66.             --_Next;
  67.             return (*this); }
  68.         const_iterator operator--(int)
  69.             {const_iterator _Tmp = *this;
  70.             --*this;
  71.             return (_Tmp); }
  72.         const_iterator& operator+=(difference_type _N)
  73.             {_Add(_N);
  74.             return (*this); }
  75.         const_iterator& operator-=(difference_type _N)
  76.             {return (*this += -_N); }
  77.         const_iterator operator+(difference_type _N) const
  78.             {const_iterator _Tmp = *this;
  79.             return (_Tmp += _N); }
  80.         const_iterator operator-(difference_type _N) const
  81.             {const_iterator _Tmp = *this;
  82.             return (_Tmp -= _N); }
  83.         difference_type operator-(const const_iterator& _X) const
  84.             {return (_Map == _X._Map ? _Next - _X._Next
  85.                 : _DEQUESIZ * (_Map - _X._Map - 1)
  86.                 + (_Next - _First) + (_X._Last - _X._Next)); }
  87.         const_reference operator[](difference_type _N) const
  88.             {return (*(*this + _N)); }
  89.         bool operator==(const const_iterator& _X) const
  90.             {return (_Next == _X._Next); }
  91.         bool operator!=(const const_iterator& _X) const
  92.             {return (!(*this == _X)); }
  93.         bool operator<(const const_iterator& _X) const
  94.             {return (_Map < _X._Map
  95.                 || _Map == _X._Map && _Next < _X._Next); }
  96.         bool operator<=(const const_iterator& _X) const
  97.             {return (!(_X < *this)); }
  98.         bool operator>(const const_iterator& _X) const
  99.             {return (_X < *this); }
  100.         bool operator>=(const const_iterator& _X) const
  101.             {return (!(*this < _X)); }
  102.     protected:
  103.         void _Add(difference_type _N)
  104.             {difference_type _Off = _N + _Next - _First;
  105.             difference_type _Moff = (0 <= _Off)
  106.                 ? _Off / _DEQUESIZ
  107.                 : -((_DEQUESIZ - 1 - _Off) / _DEQUESIZ);
  108.             if (_Moff == 0)
  109.                 _Next += _N;
  110.             else
  111.                 {_Map += _Moff;
  112.                 _First = *_Map;
  113.                 _Last = _First + _DEQUESIZ;
  114.                 _Next = _First + (_Off - _Moff * _DEQUESIZ); }}
  115.     _PROTECTED:
  116.         _Tptr _First, _Last, _Next;
  117.         _Mapptr _Map;
  118.         };
  119.         // CLASS iterator
  120.     class iterator : public const_iterator {
  121.     public:
  122.         iterator()
  123.             {}
  124.         iterator(_Tptr _P, _Mapptr _M)
  125.             : const_iterator(_P, _M) {}
  126.         reference operator*() const
  127.             {return (*_Next); }
  128.         _Tptr operator->() const
  129.             {return (&**this); }
  130.         iterator& operator++()
  131.             {if (++_Next == _Last)
  132.                 {_First = *++_Map;
  133.                 _Last = _First + _DEQUESIZ;
  134.                 _Next = _First; }
  135.             return (*this); }
  136.         iterator operator++(int)
  137.             {iterator _Tmp = *this;
  138.             ++*this;
  139.             return (_Tmp); }
  140.         iterator& operator--()
  141.             {if (_Next == _First)
  142.                 {_First = *--_Map;
  143.                 _Last = _First + _DEQUESIZ;
  144.                 _Next = _Last; }
  145.             --_Next;
  146.             return (*this); }
  147.         iterator operator--(int)
  148.             {iterator _Tmp = *this;
  149.             --*this;
  150.             return (_Tmp); }
  151.         iterator& operator+=(difference_type _N)
  152.             {_Add(_N);
  153.             return (*this); }
  154.         iterator& operator-=(difference_type _N)
  155.             {return (*this += -_N); }
  156.         iterator operator+(difference_type _N) const
  157.             {iterator _Tmp = *this;
  158.             return (_Tmp += _N); }
  159.         iterator operator-(difference_type _N) const
  160.             {iterator _Tmp = *this;
  161.             return (_Tmp -= _N); }
  162.         difference_type operator-(const iterator& _X) const
  163.             {return (_Map == _X._Map ? _Next - _X._Next
  164.                 : _DEQUESIZ * (_Map - _X._Map - 1)
  165.                 + (_Next - _First) + (_X._Last - _X._Next)); }
  166.         reference operator[](difference_type _N) const
  167.             {return (*(*this + _N)); }
  168.         bool operator==(const iterator& _X) const
  169.             {return (_Next == _X._Next); }
  170.         bool operator!=(const iterator& _X) const
  171.             {return (!(*this == _X)); }
  172.         bool operator<(const iterator& _X) const
  173.             {return (_Map < _X._Map
  174.                 || _Map == _X._Map && _Next < _X._Next); }
  175.         bool operator<=(const iterator& _X) const
  176.             {return (!(_X < *this)); }
  177.         bool operator>(const iterator& _X) const
  178.             {return (_X < *this); }
  179.         bool operator>=(const iterator& _X) const
  180.             {return (!(*this < _X)); }
  181.         };
  182.     typedef reverse_iterator<const_iterator, value_type,
  183.         const_reference, _Ctptr, difference_type>
  184.             const_reverse_iterator;
  185.     typedef reverse_iterator<iterator, value_type,
  186.         reference, _Tptr, difference_type>
  187.             reverse_iterator;
  188.     explicit deque(const _A& _Al = _A())
  189.         : allocator(_Al),
  190.             _First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
  191.         {}
  192.     explicit deque(size_type _N, const _Ty& _V = _Ty(),
  193.         const _A& _Al = _A())
  194.         : allocator(_Al),
  195.             _First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
  196.         {insert(begin(), _N, _V); }
  197.     deque(const _Myt& _X)
  198.         : allocator(_X.allocator),
  199.             _First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
  200.         {copy(_X.begin(), _X.end(), back_inserter(*this)); }
  201.     typedef const_iterator _It;
  202.         deque(_It _F, _It _L, const _A& _Al = _A())
  203.         : allocator(_Al),
  204.             _First(), _Last(), _Map(0), _Mapsize(0), _Size(0)
  205.         {copy(_F, _L, back_inserter(*this)); }
  206.     ~deque()
  207.         {while (!empty())
  208.             pop_front(); }
  209.     _Myt& operator=(const _Myt& _X)
  210.         {if (this != &_X)
  211.             {iterator _S;
  212.             if (_X.size() <= size())
  213.                 {_S = copy(_X.begin(), _X.end(), begin());
  214.                 erase(_S, end()); }
  215.             else
  216.                 {const_iterator _Sx = _X.begin() + size();
  217.                 _S = copy(_X.begin(), _Sx, begin());
  218.                 copy(_Sx, _X.end(), inserter(*this, _S)); }}
  219.         return (*this); }
  220.     iterator begin()
  221.         {return (_First); }
  222.     const_iterator begin() const
  223.         {return ((const_iterator)_First); }
  224.     iterator end()
  225.         {return (_Last); }
  226.     const_iterator end() const
  227.         {return ((const_iterator)_Last); }
  228.     reverse_iterator rbegin()
  229.         {return (reverse_iterator(end())); }
  230.     const_reverse_iterator rbegin() const
  231.         {return (const_reverse_iterator(end())); }
  232.     reverse_iterator rend()
  233.         {return (reverse_iterator(begin())); }
  234.     const_reverse_iterator rend() const
  235.         {return (const_reverse_iterator(begin())); }
  236.     void resize(size_type _N, _Ty _X = _Ty())
  237.         {if (size() < _N)
  238.             insert(end(), _N - size(), _X);
  239.         else if (_N < size())
  240.             erase(begin() + _N, end()); }
  241.     size_type size() const
  242.         {return (_Size); }
  243.     size_type max_size() const
  244.         {return (allocator.max_size()); }
  245.     bool empty() const
  246.         {return (size() == 0); }
  247.     _A get_allocator() const
  248.         {return (allocator); }
  249.     const_reference at(size_type _P) const
  250.         {if (size() <= _P)
  251.             _Xran();
  252.         return (*(begin() + _P)); }
  253.     reference at(size_type _P)
  254.         {if (size() <= _P)
  255.             _Xran();
  256.         return (*(begin() + _P)); }
  257.     const_reference operator[](size_type _P) const
  258.         {return (*(begin() + _P)); }
  259.     reference operator[](size_type _P)
  260.         {return (*(begin() + _P)); }
  261.     reference front()
  262.         {return (*begin()); }
  263.     const_reference front() const
  264.         {return (*begin()); }
  265.     reference back()
  266.         {return (*(end() - 1)); }
  267.     const_reference back() const
  268.         {return (*(end() - 1)); }
  269.     void push_front(const _Ty& _X)
  270.         {if (empty() || _First._Next == _First._First)
  271.             _Buyfront();
  272.         allocator.construct(--_First._Next, _X);
  273.         ++_Size; }
  274.     void pop_front()
  275.         {allocator.destroy(_First._Next++);
  276.         --_Size;
  277.         if (empty() || _First._Next == _First._Last)
  278.             _Freefront(); }
  279.     void push_back(const _Ty& _X)
  280.         {
  281.         if (empty() || (_Last._Next == _Last._Last))
  282.         {
  283.             _Buyback();
  284.             allocator.construct(_Last._Next++, _X);
  285.         }
  286.         else if (_Last._Next + 1 == _Last._Last)
  287.         {
  288.             allocator.construct(_Last._Next++, _X);
  289.             _Buyback();
  290.         }
  291.         else
  292.             allocator.construct(_Last._Next++, _X);
  293.         ++_Size; }
  294.     void pop_back()
  295.         {
  296.         if (_Last._Next == _Last._First)
  297.             _Freeback();
  298.         if (!empty())
  299.             allocator.destroy(--_Last._Next);
  300.         --_Size;
  301.         if (empty())
  302.             _Freeback(); }
  303.     void assign(_It _F, _It _L)
  304.         {erase(begin(), end());
  305.         insert(begin(), _F, _L); }
  306.     void assign(size_type _N, const _Ty& _X = _Ty())
  307.         {erase(begin(), end());
  308.         insert(begin(), _N, _X); }
  309.     iterator insert(iterator _P, const _Ty& _X = _Ty())
  310.         {if (_P == begin())
  311.             {push_front(_X);
  312.             return (begin()); }
  313.         else if (_P == end())
  314.             {push_back(_X);
  315.             return (end() - 1); }
  316.         else
  317.             {iterator _S;
  318.             size_type _Off = _P - begin();
  319.             if (_Off < size() / 2)
  320.                 {push_front(front());
  321.                 _S = begin() + _Off;
  322.                 copy(begin() + 2, _S + 1, begin() + 1); }
  323.             else
  324.                 {push_back(back());
  325.                 _S = begin() + _Off;
  326.                 copy_backward(_S, end() - 2, end() - 1); }
  327.             *_S = _X;
  328.             return (_S); }}
  329.     void insert(iterator _P, size_type _M, const _Ty& _X)
  330.         {iterator _S;
  331.         size_type _I;
  332.         size_type _Off = _P - begin();
  333.         size_type _Rem = _Size - _Off;
  334.         if (_Off < _Rem)
  335.             if (_Off < _M)
  336.                 {for (_I = _M - _Off; 0 < _I; --_I)
  337.                     push_front(_X);
  338.                 for (_I = _Off; 0 < _I; --_I)
  339.                     push_front(begin()[_M - 1]);
  340.                 _S = begin() + _M;
  341.                 fill(_S, _S + _Off, _X); }
  342.             else
  343.                 {for (_I = _M; 0 < _I; --_I)
  344.                     push_front(begin()[_M - 1]);
  345.                 _S = begin() + _M;
  346.                 copy(_S + _M, _S + _Off, _S);
  347.                 fill(begin() + _Off, _S + _Off, _X); }
  348.         else
  349.             if (_Rem < _M)
  350.                 {for (_I = _M - _Rem; 0 < _I; --_I)
  351.                     push_back(_X);
  352.                 for (_I = 0; _I < _Rem; ++_I)
  353.                     push_back(begin()[_Off + _I]);
  354.                 _S = begin() + _Off;
  355.                 fill(_S, _S + _Rem, _X); }
  356.             else
  357.                 {for (_I = 0; _I < _M; ++_I)
  358.                     push_back(begin()[_Off + _Rem - _M + _I]);
  359.                 _S = begin() + _Off;
  360.                 copy_backward(_S, _S + _Rem - _M, _S + _Rem);
  361.                 fill(_S, _S + _M, _X); }}
  362.     void insert(iterator _P, _It _F, _It _L)
  363.         {size_type _M = 0;
  364.         _Distance(_F, _L, _M);
  365.         size_type _I;
  366.         size_type _Off = _P - begin();
  367.         size_type _Rem = _Size - _Off;
  368.         if (_Off < _Rem)
  369.             if (_Off < _M)
  370.                 {_It _Qx = _F;
  371.                 advance(_Qx, _M - _Off);
  372.                 for (_It _Q = _Qx; _F != _Q; )
  373.                     push_front(*--_Q);
  374.                 for (_I = _Off; 0 < _I; --_I)
  375.                     push_front(begin()[_M - 1]);
  376.                 copy(_Qx, _L, begin() + _M); }
  377.             else
  378.                 {for (_I = _M; 0 < _I; --_I)
  379.                     push_front(begin()[_M - 1]);
  380.                 iterator _S = begin() + _M;
  381.                 copy(_S + _M, _S + _Off, _S);
  382.                 copy(_F, _L, begin() + _Off); }
  383.         else
  384.             if (_Rem < _M)
  385.                 {_It _Qx = _F;
  386.                 advance(_Qx, _Rem);
  387.                 for (_It _Q = _Qx; _Q != _L; ++_Q)
  388.                     push_back(*_Q);
  389.                 for (_I = 0; _I < _Rem; ++_I)
  390.                     push_back(begin()[_Off + _I]);
  391.                 copy(_F, _Qx, begin() + _Off); }
  392.             else
  393.                 {for (_I = 0; _I < _M; ++_I)
  394.                     push_back(begin()[_Off + _Rem - _M + _I]);
  395.                 iterator _S = begin() + _Off;
  396.                 copy_backward(_S, _S + _Rem - _M, _S + _Rem);
  397.                 copy(_F, _L, _S); }}
  398.     iterator erase(iterator _P)
  399.         {return (erase(_P, _P + 1)); }
  400.     iterator erase(iterator _F, iterator _L)
  401.         {size_type _N = _L - _F;
  402.         size_type _M = _F - begin();
  403.         if (_M < end() - _L)
  404.             {copy_backward(begin(), _F, _L);
  405.             for (; 0 < _N; --_N)
  406.                 pop_front(); }
  407.         else
  408.             {copy(_L, end(), _F);
  409.             for (; 0 < _N; --_N)
  410.                 pop_back(); }
  411.         return (_M == 0 ? begin() : begin() + _M); }
  412.     void clear()
  413.         {erase(begin(), end()); }
  414.     void swap(_Myt& _X)
  415.         {if (allocator == _X.allocator)
  416.             {std::swap(_First, _X._First);
  417.             std::swap(_Last, _X._Last);
  418.             std::swap(_Map, _X._Map);
  419.             std::swap(_Mapsize, _X._Mapsize);
  420.             std::swap(_Size, _X._Size); }
  421.         else
  422.             {_Myt _Ts = *this; *this = _X, _X = _Ts; }}
  423.     friend void swap(_Myt& _X, _Myt& _Y)
  424.         {_X.swap(_Y); }
  425. protected:
  426.     void _Buyback()
  427.         {_Tptr _P = allocator.allocate(_DEQUESIZ, (void *)0);
  428.         if (empty())
  429.             {_Mapsize = _DEQUEMAPSIZ;
  430.             size_type _N = _Mapsize / 2;
  431.             _Getmap();
  432.             _Setptr(_Map + _N, _P);
  433.             _First = iterator(_P + _DEQUESIZ / 2, _Map + _N);
  434.             _Last = _First; }
  435.         else if (_Last._Map < _Map + (_Mapsize - 1))
  436.             {_Setptr(++_Last._Map, _P);
  437.             _Last = iterator(_P, _Last._Map); }
  438.         else
  439.             {difference_type _I = _Last._Map - _First._Map + 1;
  440.             _Mapptr _M = _Growmap(2 * _I);
  441.             _Setptr(_M + _I, _P);
  442.             _First = iterator(_First._Next, _M);
  443.             _Last = iterator(_P, _M + _I); }}
  444.     void _Buyfront()
  445.         {_Tptr _P = allocator.allocate(_DEQUESIZ, (void *)0);
  446.         if (empty())
  447.             {_Mapsize = _DEQUEMAPSIZ;
  448.             size_type _N = _Mapsize / 2;
  449.             _Getmap();
  450.             _Setptr(_Map + _N, _P);
  451.             _First = iterator(_P + (_DEQUESIZ / 2 + 1),
  452.                 _Map + _N);
  453.             _Last = _First; }
  454.         else if (_Map < _First._Map)
  455.             {_Setptr(--_First._Map, _P);
  456.             _First = iterator(_P + _DEQUESIZ, _First._Map); }
  457.         else if (_Last._Map == _First._Map)
  458.             {_Setptr(_Last._Map++, *_First._Map);
  459.             _Setptr(_First._Map+1, *_First._Map);
  460.             _Setptr(_First._Map, _P);
  461.             _First = iterator(_P + _DEQUESIZ, _First._Map); }
  462.         else
  463.             {difference_type _I = _Last._Map - _First._Map + 1;
  464.             _Mapptr _M = _Growmap(2 * _I);
  465.             _Setptr(--_M, _P);
  466.             _First = iterator(_P + _DEQUESIZ, _M);
  467.             _Last = iterator(_Last._Next, _M + _I); }}
  468.     void _Freeback()
  469.         {_Freeptr(_Last._Map--);
  470.         if (empty())
  471.             {if (_First._Map == _Last._Map)
  472.                 _Freeptr(_First._Map);
  473.             _First = iterator();
  474.             _Last = _First;
  475.             _Freemap(); }
  476.         else
  477.             _Last = iterator(*_Last._Map + _DEQUESIZ,
  478.                 _Last._Map); }
  479.     void _Freefront()
  480.         {_Freeptr(_First._Map++);
  481.         if (empty())
  482.             {_First = iterator();
  483.             _Last = _First;
  484.             _Freemap(); }
  485.         else
  486.             _First = iterator(*_First._Map, _First._Map); }
  487.     void _Xran() const
  488.         {_THROW(out_of_range, "invalid deque<T> subscript"); }
  489.     void _Freemap()
  490.         {allocator.deallocate(_Map, _Mapsize); }
  491.     void _Freeptr(_Mapptr _M)
  492.         {allocator.deallocate(*_M, _DEQUESIZ); }
  493.     void _Getmap()
  494.         {_Map = (_Mapptr)allocator._Charalloc(
  495.             _Mapsize * sizeof (_Tptr)); }
  496.     _Mapptr _Growmap(size_type _Newsize)
  497.         {_Mapptr _M = (_Mapptr)allocator._Charalloc(
  498.             _Newsize * sizeof (_Tptr));
  499.         copy(_First._Map, _Last._Map + 1,
  500.             _M + _Newsize / 4);
  501.         allocator.deallocate(_Map, _Mapsize);
  502.         _Map = _M;
  503.         _Mapsize = _Newsize;
  504.         return (_M + _Newsize / 4); }
  505.     void _Setptr(_Mapptr _M, _Tptr _P)
  506.         {*_M = _P; }
  507.     _A allocator;
  508.     iterator _First, _Last;
  509.     _Mapptr _Map;
  510.     size_type _Mapsize, _Size;
  511.     };
  512.         // deque TEMPLATE OPERATORS
  513. template<class _Ty, class _A> inline
  514.     bool operator==(const deque<_Ty, _A>& _X,
  515.         const deque<_Ty, _A>& _Y)
  516.     {return (_X.size() == _Y.size()
  517.         && equal(_X.begin(), _X.end(), _Y.begin())); }
  518. template<class _Ty, class _A> inline
  519.     bool operator!=(const deque<_Ty, _A>& _X,
  520.         const deque<_Ty, _A>& _Y)
  521.     {return (!(_X == _Y)); }
  522. template<class _Ty, class _A> inline
  523.     bool operator<(const deque<_Ty, _A>& _X,
  524.         const deque<_Ty, _A>& _Y)
  525.     {return (lexicographical_compare(_X.begin(), _X.end(),
  526.         _Y.begin(), _Y.end())); }
  527. template<class _Ty, class _A> inline
  528.     bool operator<=(const deque<_Ty, _A>& _X,
  529.         const deque<_Ty, _A>& _Y)
  530.     {return (!(_Y < _X)); }
  531. template<class _Ty, class _A> inline
  532.     bool operator>(const deque<_Ty, _A>& _X,
  533.         const deque<_Ty, _A>& _Y)
  534.     {return (_Y < _X); }
  535. template<class _Ty, class _A> inline
  536.     bool operator>=(const deque<_Ty, _A>& _X,
  537.         const deque<_Ty, _A>& _Y)
  538.     {return (!(_X < _Y)); }
  539. _STD_END
  540. #ifdef  _MSC_VER
  541. #pragma pack(pop)
  542. #endif  /* _MSC_VER */
  543.  
  544. #endif /* _DEQUE_ */
  545.  
  546. /*
  547.  * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
  548.  * Consult your license regarding permissions and restrictions.
  549.  */
  550.  
  551. /*
  552.  * This file is derived from software bearing the following
  553.  * restrictions:
  554.  *
  555.  * Copyright (c) 1994
  556.  * Hewlett-Packard Company
  557.  *
  558.  * Permission to use, copy, modify, distribute and sell this
  559.  * software and its documentation for any purpose is hereby
  560.  * granted without fee, provided that the above copyright notice
  561.  * appear in all copies and that both that copyright notice and
  562.  * this permission notice appear in supporting documentation.
  563.  * Hewlett-Packard Company makes no representations about the
  564.  * suitability of this software for any purpose. It is provided
  565.  * "as is" without express or implied warranty.
  566.  */
  567.