home *** CD-ROM | disk | FTP | other *** search
/ PC Plus SuperCD (UK) 2000 May / PCP163A.iso / Runimage / Cbuilder4 / Include / LIST.CC < prev    next >
Encoding:
C/C++ Source or Header  |  1999-01-26  |  10.3 KB  |  354 lines
  1. #ifndef __LIST_CC
  2. #define __LIST_CC
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * list.cc - Non-nline list definitions for the Standard Library
  8.  *
  9.  ***************************************************************************
  10.  *
  11.  * Copyright (c) 1994
  12.  * Hewlett-Packard Company
  13.  *
  14.  * Permission to use, copy, modify, distribute and sell this software
  15.  * and its documentation for any purpose is hereby granted without fee,
  16.  * provided that the above copyright notice appear in all copies and
  17.  * that both that copyright notice and this permission notice appear
  18.  * in supporting documentation.  Hewlett-Packard Company makes no
  19.  * representations about the suitability of this software for any
  20.  * purpose.  It is provided "as is" without express or implied warranty.
  21.  *
  22.  *
  23.  ***************************************************************************
  24.  *
  25.  * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
  26.  * ALL RIGHTS RESERVED
  27.  *
  28.  * The software and information contained herein are proprietary to, and
  29.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  30.  * intends to preserve as trade secrets such software and information.
  31.  * This software is furnished pursuant to a written license agreement and
  32.  * may be used, copied, transmitted, and stored only in accordance with
  33.  * the terms of such license and with the inclusion of the above copyright
  34.  * notice.  This software and information or any other copies thereof may
  35.  * not be provided or otherwise made available to any other person.
  36.  *
  37.  * Notwithstanding any other lease or license that may pertain to, or
  38.  * accompany the delivery of, this computer software and information, the
  39.  * rights of the Government regarding its use, reproduction and disclosure
  40.  * are as set forth in Section 52.227-19 of the FARS Computer
  41.  * Software-Restricted Rights clause.
  42.  * 
  43.  * Use, duplication, or disclosure by the Government is subject to
  44.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  45.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  46.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  47.  * P.O. Box 2328, Corvallis, Oregon 97339.
  48.  *
  49.  * This computer software and information is distributed with "restricted
  50.  * rights."  Use, duplication or disclosure is subject to restrictions as
  51.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  52.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  53.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  54.  * then the "Alternate III" clause applies.
  55.  *
  56.  **************************************************************************/
  57.  
  58. #include <stdcomp.h>
  59. #include <limits>
  60.  
  61. #define _RWSTD_LIST_SORT_COUNTERS 64
  62.  
  63. #ifndef _RWSTD_NO_NAMESPACE
  64. namespace std {
  65. #endif
  66.  
  67.   template <class T, class Allocator>
  68.   void list<T,Allocator>::__deallocate_buffers ()
  69.   {
  70.     while (__buffer_list.data())
  71.     {
  72.       __buffer_pointer tmp = __buffer_list;
  73.       __buffer_list = (__buffer_pointer)(__buffer_list.data()->next_buffer);
  74.       __list_node_alloc_type(__buffer_list).deallocate(tmp->buffer,tmp->size);
  75.       __buffer_alloc_type(__buffer_list).deallocate(tmp,1);
  76.     }
  77.     __free_list = 0;
  78.     __next_avail = 0;
  79.     __last = 0;
  80.   }
  81.  
  82. //
  83. // This requires that T have a default constructor.
  84. //
  85.  
  86.   template <class T, class Allocator>
  87.   void list<T,Allocator>::resize (size_type new_size)
  88.   {
  89.     T value;
  90.     if (new_size > size())
  91.       insert(end(), new_size - size(), value);
  92.     else if (new_size < size())
  93.     {
  94.       iterator tmp = begin();
  95.       advance(tmp, (difference_type) new_size);
  96.       erase(tmp, end());
  97.     }
  98.   }
  99.  
  100.   template <class T, class Allocator>
  101.   void list<T,Allocator>::resize (size_type new_size, T value)
  102.   {
  103.     if (new_size > size())
  104.       insert(end(), new_size - size(), value);
  105.     else if (new_size < size())
  106.     {
  107.       iterator tmp = begin();
  108.       advance(tmp, (difference_type) new_size);
  109.       erase(tmp, end());
  110.     }
  111.   }
  112.  
  113. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  114.   template <class T, class Allocator>   
  115.   template<class InputIterator>
  116.   void list<T,Allocator>::insert (iterator position, InputIterator first,
  117.                                   InputIterator locallast)
  118.   {
  119.     while (first != locallast) insert(position, *first++);
  120.   }
  121. #else
  122.   template <class T, class Allocator>   
  123.   void list<T, Allocator>::insert (iterator position, 
  124.                                    const_iterator first,
  125.                                    const_iterator locallast)
  126.   {
  127.     while (first != locallast) insert(position, *first++);
  128.   }
  129.   template <class T, class Allocator>
  130.   void list<T, Allocator>::insert (iterator position, 
  131.                                    const T* first, const T* locallast)
  132.   {
  133.     while (first != locallast) insert(position, *first++);
  134.   }
  135. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  136.  
  137.   template <class T, class Allocator>
  138.   void list<T, Allocator>::__insert_aux (iterator position, 
  139.                                          size_type n, const T& x)
  140.   {
  141.     while (n--) insert(position, x);
  142.   }
  143.  
  144.   template <class T, class Allocator>
  145.   _TYPENAME list<T, Allocator>::iterator 
  146.   list<T, Allocator>::erase (iterator first, iterator locallast)
  147.   {
  148.     iterator tmp = end();
  149.     while (first != locallast) 
  150.     {
  151.       tmp = erase(first++);
  152.     }
  153.     return tmp;
  154.   }
  155.  
  156.   template <class T, class Allocator>
  157.   list<T, Allocator>& list<T, Allocator>::operator= (const list<T, Allocator>& x)
  158.   {
  159.     if (this != &x)
  160.     {
  161.       iterator first1 = begin();
  162.       iterator last1 = end();
  163.       const_iterator first2 = x.begin();
  164.       const_iterator last2 = x.end();
  165.       while (first1 != last1 && first2 != last2) *first1++ = *first2++;
  166.       if (first2 == last2)
  167.         erase(first1, last1);
  168.       else
  169.         insert(last1, first2, last2);
  170.     }
  171.     return *this;
  172.   }
  173.  
  174.   template <class T, class Allocator>
  175.   void list<T, Allocator>::remove (const T& value)
  176.   {
  177.     iterator first = begin();
  178.     iterator last = end();
  179.     while (first != last)
  180.     {
  181.       iterator next = first;
  182.       ++next;
  183.       if (*first == value) erase(first);
  184.       first = next;
  185.     }
  186.   }
  187.  
  188.   template <class T, class Allocator>
  189.   void list<T, Allocator>::unique ()
  190.   {
  191.     iterator first = begin();
  192.     iterator last = end();
  193.     if (first == last) return;
  194.     iterator next = first;
  195.     while (++next != last)
  196.     {
  197.       if (*first == *next)
  198.         erase(next);
  199.       else
  200.         first = next;
  201.       next = first;
  202.     }
  203.   }
  204.  
  205.   template <class T, class Allocator>
  206.   void list<T, Allocator>::merge (list<T, Allocator>& x)
  207.   {
  208.     iterator first1 = begin();
  209.     iterator last1 = end();
  210.     iterator first2 = x.begin();
  211.     iterator last2 = x.end();
  212.     while (first1 != last1 && first2 != last2)
  213.     {
  214.       if (*first2 < *first1)
  215.       {
  216.         iterator next = first2;
  217.         __transfer(first1, first2, ++next, x);
  218.         first2 = next;
  219.       }
  220.       else
  221.         first1++;
  222.     }
  223.     if (first2 != last2) 
  224.       __transfer(last1, first2, last2, x);
  225.   }
  226.  
  227.   template <class T, class Allocator>
  228.   void list<T, Allocator>::reverse ()
  229.   {
  230.     if (size() < 2) return;
  231.     for (iterator first = ++begin(); first != end();)
  232.     {
  233.       iterator old = first++;
  234.       __transfer(begin(), old, first, *this);
  235.     }
  236.   }    
  237.   template <class T, class Allocator>
  238.   void list<T, Allocator>::sort ()
  239.   {
  240.     if (size() < 2) return;
  241.  
  242.     list<T, Allocator> carry(get_allocator());
  243.     list<T, Allocator> counter[_RWSTD_LIST_SORT_COUNTERS];
  244.     for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
  245.       counter[i].__set_allocator(get_allocator());
  246.  
  247.     int fill = 0;
  248.     while (!empty())
  249.     {
  250.       carry.splice(carry.begin(), *this, begin());
  251.  
  252.       int i = 0;
  253.       while (i < fill && !counter[i].empty())
  254.       {
  255.         counter[i].merge(carry);
  256.         carry.swap(counter[i++]);
  257.       }
  258.       carry.swap(counter[i]);         
  259.       if (i == fill) ++fill;
  260.     } 
  261.     while (fill--) 
  262.     {  
  263.       merge(counter[fill]);
  264.     }
  265.   }
  266.  
  267. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  268.   template<class T, class Allocator>
  269.   template<class Predicate> void list<T, Allocator>::remove_if (Predicate pred)
  270.   {
  271.     iterator first = begin();
  272.     iterator last = end();
  273.     while (first != last)
  274.     {
  275.       iterator next = first;
  276.       ++next;
  277.       if (pred(*first)) erase(first);
  278.       first = next;
  279.     }
  280.   }
  281.  
  282.   template<class T, class Allocator>
  283.   template<class BinaryPredicate> void list<T, Allocator>::unique (BinaryPredicate pred)
  284.   {
  285.     iterator first = begin();
  286.     iterator last = end();
  287.     if (first == last) return;
  288.     iterator next = first;
  289.     while (++next != last)
  290.     {
  291.       if (pred(*first, *next))
  292.         erase(next);
  293.       else
  294.         first = next;
  295.       next = first;
  296.     }
  297.   }
  298.  
  299.   template<class T, class Allocator>
  300.   template<class Compare> void list<T, Allocator>::merge (list<T, Allocator>& x, Compare comp)
  301.   {
  302.     iterator first1 = begin();
  303.     iterator last1  = end();
  304.     iterator first2 = x.begin();
  305.     iterator last2  = x.end();
  306.     while (first1 != last1 && first2 != last2)
  307.     {
  308.       if (comp(*first2, *first1))
  309.       {
  310.         iterator next = first2;
  311.         __transfer(first1, first2, ++next, x);
  312.         first2 = next;
  313.       }
  314.       else
  315.         first1++;
  316.     }
  317.     if (first2 != last2) 
  318.       __transfer(last1, first2, last2, x);
  319.   }
  320.  
  321.   template<class T, class Allocator>
  322.   template<class Compare> void list<T, Allocator>::sort (Compare comp)
  323.   {
  324.     if (size() < 2) return;
  325.  
  326.     list<T, Allocator> carry(get_allocator());
  327.     list<T, Allocator> counter[ _RWSTD_LIST_SORT_COUNTERS];
  328.     for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
  329.       counter[i].__set_allocator(get_allocator());
  330.     int fill = 0;
  331.     while (!empty())
  332.     {
  333.       carry.splice(carry.begin(), *this, begin());
  334.       int i = 0;
  335.       while (i < fill && !counter[i].empty())
  336.       {
  337.         counter[i].merge(carry, comp);
  338.         carry.swap(counter[i++]);
  339.       }
  340.       carry.swap(counter[i]);         
  341.       if (i == fill) ++fill;
  342.     } 
  343.     while (fill--) merge(counter[fill], comp);
  344.   }
  345. #endif /*_RWSTD_NO_MEMBER_TEMPLATES*/
  346.  
  347. #undef _RWSTD_LIST_SORT_COUNTERS
  348.  
  349. #ifndef _RWSTD_NO_NAMESPACE
  350. }
  351. #endif
  352. #pragma option pop
  353. #endif /* __LIST_CC */
  354.