home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Internet 2000 May / MICD_2000_05.iso / CBuilder5 / INSTALL / DATA1.CAB / Program_Built_Files / Include / deque.cc < prev    next >
C/C++ Source or Header  |  2000-02-01  |  16KB  |  496 lines
  1. #ifndef __DEQUE_CC
  2. #define __DEQUE_CC
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. /***************************************************************************
  5.  *
  6.  * deque.cc - Non-iniline definitions for the Standard Library deque class
  7.  *
  8.  ***************************************************************************
  9.  *
  10.  * Copyright (c) 1994
  11.  * Hewlett-Packard Company
  12.  *
  13.  * Permission to use, copy, modify, distribute and sell this software
  14.  * and its documentation for any purpose is hereby granted without fee,
  15.  * provided that the above copyright notice appear in all copies and
  16.  * that both that copyright notice and this permission notice appear
  17.  * in supporting documentation.  Hewlett-Packard Company makes no
  18.  * representations about the suitability of this software for any
  19.  * purpose.  It is provided "as is" without express or implied warranty.
  20.  *
  21.  *
  22.  ***************************************************************************
  23.  *
  24.  * Copyright (c) 1994-1999 Rogue Wave Software, Inc.  All Rights Reserved.
  25.  *
  26.  * This computer software is owned by Rogue Wave Software, Inc. and is
  27.  * protected by U.S. copyright laws and other laws and by international
  28.  * treaties.  This computer software is furnished by Rogue Wave Software,
  29.  * Inc. pursuant to a written license agreement and may be used, copied,
  30.  * transmitted, and stored only in accordance with the terms of such
  31.  * license and with the inclusion of the above copyright notice.  This
  32.  * computer software or any other copies thereof may not be provided or
  33.  * otherwise made available to any other person.
  34.  *
  35.  * U.S. Government Restricted Rights.  This computer software is provided
  36.  * with Restricted Rights.  Use, duplication, or disclosure by the
  37.  * Government is subject to restrictions as set forth in subparagraph (c)
  38.  * (1) (ii) of The Rights in Technical Data and Computer Software clause
  39.  * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
  40.  * Commercial Computer Software û Restricted Rights at 48 CFR 52.227-19,
  41.  * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
  42.  * Flatiron Parkway, Boulder, Colorado 80301 USA.
  43.  *
  44.  **************************************************************************/
  45. #include <stdcomp.h>
  46.  
  47. #ifndef _RWSTD_NO_NAMESPACE
  48. namespace std {
  49. #endif
  50.   template <class T, class Allocator>
  51.   deque<T,Allocator>::~deque()
  52.   {
  53.     while (!empty()) pop_front();
  54.   }
  55.  
  56.   template <class T, class Allocator>
  57.   _TYPENAME deque<T,Allocator>::size_type deque<T,Allocator>::__buffer_size ()
  58.   {
  59.     static size_type b_size = 
  60.     max((size_type)1,__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0));
  61.     return b_size; 
  62.   }
  63.  
  64.   template <class T, class Allocator>
  65.   void deque<T,Allocator>::__allocate_at_begin ()
  66.   {
  67.     pointer p = __value_alloc_type(__map_size).allocate(__buffer_size(),__start.current);
  68.     if (!empty())
  69.     {
  70.       if (__start.node == __map)
  71.       {
  72.         __map_alloc_type ma(__map_size);
  73.         difference_type i = __finish.node - __start.node;
  74.         size_type new_map_size = (i + 1) * 2;
  75.         __map_pointer tmp;
  76. #ifndef _RWSTD_NO_EXCEPTIONS
  77.         try {
  78.           tmp = ma.allocate(new_map_size,__map);
  79.         } catch(...) {
  80.           __value_alloc_type(__map_size).deallocate(p,__buffer_size());
  81.           throw;
  82.         }      
  83. #else
  84.         tmp = ma.allocate(new_map_size,__map);
  85. #endif //  _RWSTD_NO_EXCEPTIONS
  86.         copy(__start.node, __finish.node + 1, tmp + new_map_size / 4 + 1);
  87.         ma.deallocate(__map,__map_size.data());
  88.         __map = tmp;
  89.         __map[new_map_size / 4] = p;
  90.         __start = iterator(p + __buffer_size(), __map + new_map_size / 4);
  91.         __finish = iterator(__finish.current, __map + new_map_size / 4 + i + 1);
  92.         __map_size = new_map_size;
  93.       }
  94.       else
  95.       {
  96.         *--__start.node = p;
  97.         __start = iterator(p + __buffer_size(), __start.node);
  98.       }
  99.     }
  100.     else
  101.     {
  102. #ifndef _RWSTD_NO_EXCEPTIONS
  103.       try {
  104.         __map = __map_alloc_type(__map_size).allocate(__buffer_size(),__map);
  105.       } catch(...) {
  106.         __value_alloc_type(__map_size).deallocate(p,__buffer_size());
  107.         throw;
  108.       }      
  109. #else
  110.       __map = __map_alloc_type(__map_size).allocate(__buffer_size(),__map);
  111. #endif // _RWSTD_NO_EXCEPTIONS
  112.       __map_size = __buffer_size();
  113.       __map[__map_size.data() / 2] = p;
  114.       __start = iterator(p + __buffer_size() / 2 + 1, __map + __map_size.data() / 2);
  115.       __finish = __start;
  116.     }
  117.   }
  118.   template <class T, class Allocator>
  119.   void deque<T,Allocator>::__allocate_at_end ()
  120.   {
  121.     pointer p = __value_alloc_type(__map_size).allocate(__buffer_size(),__start.current);
  122.  
  123.     if (!empty())
  124.     {
  125.       if (__finish.node == __map + __map_size.data() - 1)
  126.       {
  127.         __map_alloc_type ma(__map_size);
  128.         difference_type i = __finish.node - __start.node;
  129.         size_type new_map_size = (i + 1) * 2;
  130.         __map_pointer tmp;
  131. #ifndef _RWSTD_NO_EXCEPTIONS
  132.         try {
  133.           tmp = ma.allocate(new_map_size,__map);
  134.         } catch(...) {
  135.           __value_alloc_type(__map_size).deallocate(p,__buffer_size());
  136.           throw;
  137.         }      
  138. #else
  139.         tmp = ma.allocate(new_map_size,__map);
  140. #endif // _RWSTD_NO_EXCEPTIONS
  141.         copy(__start.node, __finish.node + 1, tmp + new_map_size / 4);
  142.         ma.deallocate(__map,__map_size.data());
  143.         __map = tmp;
  144.         __map[new_map_size / 4 + i + 1] = p;
  145.         __start = iterator(__start.current, __map + new_map_size / 4);
  146.         __finish = iterator(p, __map + new_map_size / 4 + i + 1);
  147.         __map_size = new_map_size;
  148.       }
  149.       else
  150.       {
  151.         *++__finish.node = p;
  152.         __finish = iterator(p, __finish.node);
  153.       }
  154.     }
  155.     else
  156.     {
  157.       __map_size = __buffer_size();
  158. #ifndef _RWSTD_NO_EXCEPTIONS
  159.       try {
  160.         __map = __map_alloc_type(__map_size).allocate(__map_size.data(),__map);
  161.       } catch(...) {
  162.         __value_alloc_type(__map_size).deallocate(p,__buffer_size());
  163.         throw;
  164.       }      
  165. #else
  166.       __map = __map_alloc_type(__map_size).allocate(__map_size.data(),__map);
  167. #endif // _RWSTD_NO_EXCEPTIONS
  168.       __map[__map_size.data() / 2] = p;
  169.       __start = iterator(p + __buffer_size() / 2, __map + __map_size.data() / 2);
  170.       __finish = __start;
  171.     }
  172.   }
  173.  
  174.   template <class T, class Allocator>
  175.   void deque<T,Allocator>::__deallocate_at_begin ()
  176.   {
  177.     __value_alloc_type(__map_size).deallocate(*__start.node++,__buffer_size());
  178.     if (empty())
  179.     {
  180.       __start = iterator();
  181.       __finish = __start;
  182.       __map_alloc_type(__map_size).deallocate(__map,__map_size.data());
  183.     }
  184.     else
  185.       __start = iterator(*__start.node, __start.node);
  186.   }
  187.  
  188.   template <class T, class Allocator>
  189.   void deque<T,Allocator>::__deallocate_at_end ()
  190.   {
  191.     __value_alloc_type(__map_size).deallocate(*__finish.node--,__buffer_size());
  192.     if (empty())
  193.     {
  194.       __start = iterator();
  195.       __finish = __start;
  196.       __map_alloc_type(__map_size).deallocate(__map,__map_size.data());
  197.     }
  198.     else
  199.       __finish = iterator(*__finish.node + __buffer_size(), __finish.node);
  200.   }
  201.  
  202.   template <class T, class Allocator>
  203.   void deque<T,Allocator>::resize (size_type new_size)
  204.   {
  205.     T value;
  206.     if (new_size > size())
  207.       insert(end(), new_size - size(), value);
  208.     else if (new_size < size())
  209.       erase(begin() + new_size,end());
  210.   }
  211.  
  212.   template <class T, class Allocator>
  213.   void deque<T,Allocator>::resize (size_type new_size, T value)
  214.   {
  215.     if (new_size > size())
  216.       insert(end(), new_size - size(), value);
  217.     else if (new_size < size())
  218.       erase(begin() + new_size,end());
  219.   }
  220.  
  221.   template <class T, class Allocator>
  222.   _TYPENAME deque<T,Allocator>::iterator 
  223.   deque<T,Allocator>::insert (iterator position, const T& x)
  224.   {
  225.     if (position == begin())
  226.     {
  227.       push_front(x); return begin();
  228.     }
  229.     else if (position == end())
  230.     {
  231.       push_back(x); return end() - 1;
  232.     }
  233.     else
  234.     {
  235.       difference_type index = position - begin();
  236.       if ((size_type)index < __length/2)
  237.       {
  238.         push_front(*begin());
  239.         copy(begin() + 2, begin() + index + 1, begin() + 1);
  240.       }
  241.       else
  242.       {
  243.         push_back(*(end() - 1));
  244.         copy_backward(begin() + index, end() - 2, end() - 1);
  245.       }
  246.       *(begin() + index) = x;
  247.       return begin() + index;
  248.     }
  249.   }
  250.  
  251.   template <class T, class Allocator>
  252.   void deque<T,Allocator>::__insert_aux(iterator position,      
  253.                                       size_type n, const T& x)
  254.   {
  255.     difference_type index     = position - begin();
  256.     difference_type remainder = __length   - index;
  257.  
  258.     if (remainder > index)
  259.     {
  260.       if (n > (size_type)index)
  261.       {
  262.         difference_type m = n - index;
  263.         while (m-- > 0) push_front(x);
  264.         difference_type i = index;
  265.         while (i--) push_front(*(begin() + n - 1));
  266.         fill(begin() + n, begin() + n + index, x);
  267.       }
  268.       else
  269.       {
  270.         difference_type i = n;
  271.         while (i--) push_front(*(begin() + n - 1));
  272.         copy(begin() + n + n, begin() + n + index, begin() + n);
  273.         fill(begin() + index, begin() + n + index, x);
  274.       }
  275.     }
  276.     else
  277.     {
  278.       difference_type orig_len = index + remainder;
  279.       if (n > (size_type)remainder)
  280.       {
  281.         difference_type m = n - remainder;
  282.         while (m-- > 0) push_back(x);
  283.         difference_type i = 0;
  284.         while (i < remainder) push_back(*(begin() + index + i++));
  285.         fill(begin() + index, begin() + orig_len, x);
  286.       }
  287.       else
  288.       {
  289.         difference_type i = 0;
  290.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  291.         copy_backward(begin() + index, begin() + orig_len - n,
  292.                       begin() + orig_len);
  293.         fill(begin() + index, begin() + index + n, x);
  294.       }
  295.     }
  296.   }
  297. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  298.   template <class T, class Allocator>
  299.   template <class InputIterator>
  300.   void deque<T,Allocator>::__insert_aux2 (iterator position,
  301.                                    InputIterator first, InputIterator last)
  302.   {
  303.     difference_type index     = position - begin();
  304.     difference_type remainder = __length   - index;
  305.     size_type n;
  306.     __initialize(n, size_type(0));
  307.     distance(first, last, n);
  308.  
  309.     if (remainder > (size_type)index)
  310.     {
  311.       if (n > (size_type)index)
  312.       {
  313.         InputIterator m = last - index;
  314.         while (m != first) push_front(*--m);
  315.         difference_type i = index;
  316.         while (i--) push_front(*(begin() + n - 1));
  317.         copy(last - index, last, begin() + n);
  318.       }
  319.       else
  320.       {
  321.         difference_type i = n;
  322.         while (i--) push_front(*(begin() + n - 1));
  323.         copy(begin() + n + n, begin() + n + index, begin() + n);
  324.         copy(first, last, begin() + index);
  325.       }
  326.     }
  327.     else
  328.     {
  329.       difference_type orig_len = index + remainder;
  330.       if (n > (size_type)remainder)
  331.       {
  332.         InputIterator m = first + remainder;
  333.         while (m != last) push_back(*m++);
  334.         difference_type i = 0;
  335.         while (i < remainder) push_back(*(begin() + index + i++));
  336.         copy(first, first + remainder, begin() + index);
  337.       }
  338.       else
  339.       {
  340.         difference_type i = 0;
  341.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  342.         copy_backward(begin() + index, begin() + orig_len - n,
  343.                       begin() + orig_len);
  344.         copy(first, last, begin() + index);
  345.       }
  346.     }
  347.   }
  348.  
  349. #else
  350.  
  351.   template<class T, class Allocator>
  352.   void deque<T,Allocator>::insert (iterator position, 
  353.                                    const_iterator first, 
  354.                                    const_iterator last)
  355.   {
  356.     difference_type index     = position - begin();
  357.     difference_type remainder = __length   - index;
  358.     size_type n;
  359.     __initialize(n, size_type(0));
  360.     distance(first, last, n);
  361.  
  362.     if (remainder > index)
  363.     {
  364.       if (n > (size_type)index)
  365.       {
  366.         const_iterator m = last - index;
  367.         while (m != first) push_front(*--m);
  368.         difference_type i = index;
  369.         while (i--) push_front(*(begin() + n - 1));
  370.         copy(last - index, last, begin() + n);
  371.       }
  372.       else
  373.       {
  374.         difference_type i = n;
  375.         while (i--) push_front(*(begin() + n - 1));
  376.         copy(begin() + n + n, begin() + n + index, begin() + n);
  377.         copy(first, last, begin() + index);
  378.       }
  379.     }
  380.     else
  381.     {
  382.       difference_type orig_len = index + remainder;
  383.       if (n > (size_type)remainder)
  384.       {
  385.         const_iterator m = first + remainder;
  386.         while (m != last) push_back(*m++);
  387.         difference_type i = 0;
  388.         while (i < remainder) push_back(*(begin() + index + i++));
  389.         copy(first, first + remainder, begin() + index);
  390.       }
  391.       else
  392.       {
  393.         difference_type i = 0;
  394.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  395.         copy_backward(begin() + index, begin() + orig_len - n,
  396.                       begin() + orig_len);
  397.         copy(first, last, begin() + index);
  398.       }
  399.     }
  400.   }
  401.  
  402.   template<class T, class Allocator>
  403.   void deque<T,Allocator>::insert (iterator position, 
  404.                                    const T* first, const T* last)
  405.   {
  406.     difference_type index     = position - begin();
  407.     difference_type remainder = __length   - index;
  408.     size_type n;
  409.     __initialize(n, size_type(0));
  410.     distance(first, last, n);
  411.  
  412.     if (remainder > index)
  413.     {
  414.       if (n > (size_type)index)
  415.       {
  416.         const T* m = last - index;
  417.         while (m != first) push_front(*--m);
  418.         difference_type i = index;
  419.         while (i--) push_front(*(begin() + n - 1));
  420.         copy(last - index, last, begin() + n);
  421.       }
  422.       else
  423.       {
  424.         difference_type i = n;
  425.         while (i--) push_front(*(begin() + n - 1));
  426.         copy(begin() + n + n, begin() + n + index, begin() + n);
  427.         copy(first, last, begin() + index);
  428.       }
  429.     }
  430.     else
  431.     {
  432.       difference_type orig_len = index + remainder;
  433.       if (n > (size_type)remainder)
  434.       {
  435.         const T* m = first + remainder;
  436.         while (m != last) push_back(*m++);
  437.         difference_type i = 0;
  438.         while (i < remainder) push_back(*(begin() + index + i++));
  439.         copy(first, first + remainder, begin() + index);
  440.       }
  441.       else
  442.       {
  443.         difference_type i = 0;
  444.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  445.         copy_backward(begin() + index, begin() + orig_len - n,
  446.                       begin() + orig_len);
  447.         copy(first, last, begin() + index);
  448.       }
  449.     }
  450.   }
  451.  
  452. #endif /*_RWSTD_NO_MEMBER_TEMPLATES*/
  453.  
  454.   template <class T, class Allocator>
  455.   _TYPENAME deque<T,Allocator>::iterator 
  456.   deque<T,Allocator>::erase (iterator position)
  457.   {
  458.     if (end() - position > position - begin())
  459.     {
  460.       copy_backward(begin(), position, position + 1); 
  461.       pop_front();
  462.       return position + 1;
  463.     }
  464.     else
  465.     {
  466.       copy(position + 1, end(), position); 
  467.       pop_back();
  468.       return position;
  469.     }
  470.   }
  471.     
  472.   template <class T, class Allocator>
  473.   _TYPENAME deque<T,Allocator>::iterator 
  474.   deque<T,Allocator>::erase (iterator first, iterator last)
  475.   {
  476.     difference_type n = last - first;
  477.     if (end() - last > first - begin())
  478.     {
  479.       copy_backward(begin(), first, last);
  480.       while(n-- > 0) pop_front();
  481.       return last;
  482.     }
  483.     else
  484.     {
  485.       copy(last, end(), first);
  486.       while(n-- > 0) pop_back();
  487.       return first;
  488.     }
  489.   }
  490.  
  491. #ifndef _RWSTD_NO_NAMESPACE
  492. }
  493. #endif
  494. #pragma option pop
  495. #endif /* __DEQUE_CC */
  496.