home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / INC.PAK / SET.H < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  14.3 KB  |  438 lines
  1. #ifndef __STD_SET__
  2. #define __STD_SET__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * set - declarations for the Standard Library set class
  8.  *
  9.  * $Id: set,v 1.26 1995/09/15 20:48:58 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. #include <stdcomp.h>
  61.  
  62. #ifndef Allocator
  63. #define Allocator allocator
  64. #include <memory>
  65. #endif
  66.  
  67. #ifdef __BORLANDC__
  68. #pragma warn -inl
  69. #endif
  70.  
  71. #include <tree>
  72.  
  73. #ifndef RWSTD_NO_NAMESPACE
  74. namespace std {
  75. #endif
  76.  
  77. //
  78. // This is used in the implementation of set and multiset.
  79. //
  80.  
  81. template <class T, class U>
  82. struct ident : public unary_function<T, U>
  83. {
  84.     const U& operator() (const T& x) const { return x; }
  85. };
  86.  
  87. #ifndef RWSTD_NO_DEFAULT_TEMPLATES
  88. template<class Key, class Compare = less<Key> >
  89. #else
  90. template <class Key, class Compare>
  91. #endif
  92. class set
  93. {
  94.   public:
  95.     //
  96.     // Types
  97.     //
  98.     typedef Key                                        key_type;
  99.     typedef Key                                        value_type;
  100.     typedef Compare                                    key_compare;
  101.     typedef Compare                                    value_compare;
  102.  
  103.   private:
  104.  
  105.     typedef rb_tree<key_type, value_type,
  106.                     ident<value_type, key_type>, key_compare> rep_type;
  107.     rep_type t;
  108.  
  109.   public:
  110.     //
  111.     // Types
  112.     //
  113.     typedef typename rep_type::const_reference         reference;
  114.     typedef typename rep_type::const_reference         const_reference;
  115.     typedef typename rep_type::const_iterator          iterator;
  116.     typedef typename rep_type::const_iterator          const_iterator;
  117.     typedef typename rep_type::size_type               size_type;
  118.     typedef typename rep_type::difference_type         difference_type;
  119.     typedef typename rep_type::reverse_iterator        reverse_iterator;
  120.     typedef typename rep_type::const_reverse_iterator  const_reverse_iterator;
  121.     //
  122.     // construct/copy/destroy
  123.     //
  124.     explicit set (const Compare& comp = Compare()) : t(comp, false) {}
  125.  
  126. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  127.     template<class InputIterator>
  128.     set (InputIterator first, InputIterator last,
  129.          const Compare& comp = Compare()) : t(comp, false)
  130.     {
  131.         while (first != last) t.insert(*first++);
  132.     }
  133. #else
  134.     set (const value_type* first, const value_type* last,
  135.          const Compare& comp = Compare()) : t(comp, false)
  136.     {
  137.         while (first != last) t.insert(*first++);
  138.     }
  139.     set (const_iterator first, const_iterator last,
  140.          const Compare& comp = Compare()) : t(comp, false)
  141.     {
  142.         while (first != last) t.insert(*first++);
  143.     }
  144. #endif
  145.  
  146.     set (const set<Key, Compare>& x) : t(x.t, false) {}
  147.     set<Key, Compare>& operator= (const set<Key, Compare>& x)
  148.     {
  149.           t = x.t; return *this;
  150.     }
  151.     //
  152.     // iterators
  153.     //
  154.     iterator                 begin  ()       { return t.begin();  }
  155.     const_iterator           begin  () const { return t.begin();  }
  156.     iterator                 end    ()       { return t.end();    }
  157.     const_iterator           end    () const { return t.end();    }
  158.     reverse_iterator         rbegin ()       { return t.rbegin(); }
  159.     const_reverse_iterator   rbegin () const { return t.rbegin(); }
  160.     reverse_iterator         rend   ()       { return t.rend();   }
  161.     const_reverse_iterator   rend   () const { return t.rend();   }
  162.     //
  163.     // capacity
  164.     //
  165.     bool        empty    () const { return t.empty();    }
  166.     size_type   size     () const { return t.size();     }
  167.     size_type   max_size () const { return t.max_size(); }
  168.     //
  169.     // modifiers
  170.     //
  171. #ifdef RWSTD_NO_MEMBER_TYPE_TPARAM
  172.     typedef typename rep_type::iterator t_iterator;
  173. #endif
  174. #ifndef RWSTD_NO_RET_TEMPLATE
  175.     pair<iterator,bool> insert (const value_type& x)
  176. #else
  177.     typedef pair<iterator, bool> pair_iterator_bool;
  178.     //
  179.     // typedef done to get around compiler bug.
  180.     //
  181.     pair_iterator_bool insert (const value_type& x)
  182. #endif
  183.     {
  184. #ifndef RWSTD_NO_MEMBER_TYPE_TPARAM
  185.         pair<typename rep_type::iterator, bool> p = t.insert(x);
  186. #else
  187.         pair<t_iterator,bool> p = t.insert(x);
  188. #endif
  189.         return pair<iterator, bool>(p.first, p.second);
  190.     }
  191.     iterator insert (iterator position, const value_type& x)
  192.     {
  193.         return t.insert((typename rep_type::iterator&)position, x);
  194.     }
  195.  
  196. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  197.     template<class InputIterator>
  198.     void insert (InputIterator first, InputIterator last)
  199.     {
  200.         while (first != last) t.insert(*first++);
  201.     }
  202. #else
  203.     void insert (const value_type* first, const value_type* last)
  204.     {
  205.         while (first != last) t.insert(*first++);
  206.     }
  207.     void insert (const_iterator first, const_iterator last)
  208.     {
  209.         while (first != last) t.insert(*first++);
  210.     }
  211. #endif
  212.  
  213.     void erase (iterator position)
  214.     {
  215.         t.erase((typename rep_type::iterator&)position);
  216.     }
  217.     size_type erase (const key_type& x)
  218.     {
  219.         return t.erase(x);
  220.     }
  221.     void erase (iterator first, iterator last)
  222.     {
  223.         t.erase((typename rep_type::iterator&)first,
  224.                 (typename rep_type::iterator&)last);
  225.     }
  226.     void swap (set<Key, Compare>& x) { t.swap(x.t); }
  227.     //
  228.     // observers
  229.     //
  230.     key_compare        key_comp   () const { return t.key_comp(); }
  231.     value_compare      value_comp () const { return t.key_comp(); }
  232.     //
  233.     // set operations
  234.     //
  235.     iterator  find        (const key_type& x) const { return t.find(x);       }
  236.     size_type count       (const key_type& x) const { return t.count(x);      }
  237.     iterator  lower_bound (const key_type& x) const { return t.lower_bound(x);}
  238.     iterator  upper_bound (const key_type& x) const { return t.upper_bound(x);}
  239.  
  240. #ifndef RWSTD_NO_RET_TEMPLATE
  241.     pair<iterator,iterator> equal_range(const key_type& x) const
  242. #else
  243.     typedef  pair<iterator, iterator> pair_iterator_iterator;
  244.     //
  245.     // typedef done to get around compiler bug
  246.     //
  247.     pair_iterator_iterator equal_range (const key_type& x) const
  248. #endif
  249.     {
  250.         return t.equal_range(x);
  251.     }
  252. };
  253.  
  254. #ifndef RWSTD_NO_DEFAULT_TEMPLATES
  255. template<class Key, class Compare = less<Key> >
  256. #else
  257. template <class Key, class Compare>
  258. #endif
  259. class multiset
  260. {
  261.   public:
  262.     //
  263.     // types
  264.     //
  265.     typedef Key      key_type;
  266.     typedef Key      value_type;
  267.     typedef Compare  key_compare;
  268.     typedef Compare  value_compare;
  269.  
  270.   private:
  271.  
  272.     typedef rb_tree<key_type, value_type,
  273.                     ident<value_type, key_type>, key_compare> rep_type;
  274.     rep_type t;
  275.  
  276.   public:
  277.     //
  278.     // types
  279.     //
  280.     typedef typename rep_type::const_reference         reference;
  281.     typedef typename rep_type::const_reference         const_reference;
  282.     typedef typename rep_type::const_iterator          iterator;
  283.     typedef typename rep_type::const_iterator          const_iterator;
  284.     typedef typename rep_type::size_type               size_type;
  285.     typedef typename rep_type::difference_type         difference_type;
  286.     typedef typename rep_type::reverse_iterator        reverse_iterator;
  287.     typedef typename rep_type::const_reverse_iterator  const_reverse_iterator;
  288.     //
  289.     // construct/copy/destroy
  290.     //
  291.     explicit multiset (const Compare& comp = Compare()) : t(comp, true) {}
  292.  
  293. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  294.     template<class InputIterator>
  295.     multiset (InputIterator first, InputIterator last,
  296.               const Compare& comp = Compare()) : t(comp, true)
  297.     {
  298.         while (first != last) t.insert(*first++);
  299.     }
  300. #else
  301.     multiset (const value_type* first, const value_type* last,
  302.               const Compare& comp = Compare()) : t(comp, true)
  303.     {
  304.         while (first != last) t.insert(*first++);
  305.     }
  306.     multiset (const_iterator first, const_iterator last,
  307.               const Compare& comp = Compare()) : t(comp, true)
  308.     {
  309.         while (first != last) t.insert(*first++);
  310.     }
  311. #endif
  312.  
  313.     multiset (const multiset<Key, Compare>& x) : t(x.t, true) {}
  314.     multiset<Key, Compare>& operator= (const multiset<Key, Compare>& x)
  315.     {
  316.         t = x.t; return *this;
  317.     }
  318.     //
  319.     // iterators
  320.     //
  321.     iterator                 begin  ()       { return t.begin();  }
  322.     const_iterator           begin  () const { return t.begin();  }
  323.     iterator                 end    ()       { return t.end();    }
  324.     const_iterator           end    () const { return t.end();    }
  325.     reverse_iterator         rbegin ()       { return t.rbegin(); }
  326.     const_reverse_iterator   rbegin () const { return t.rbegin(); }
  327.     reverse_iterator         rend   ()       { return t.rend();   }
  328.     const_reverse_iterator   rend   () const { return t.rend();   }
  329.  
  330.     //
  331.     // capacity
  332.     //
  333.     bool       empty    () const { return t.empty();    }
  334.     size_type  size     () const { return t.size();     }
  335.     size_type  max_size () const { return t.max_size(); }
  336.     //
  337.     // modifiers
  338.     //
  339.     iterator insert (const value_type& x) { return t.insert(x).first; }
  340.     iterator insert (iterator position, const value_type& x)
  341.     {
  342.         return t.insert((typename rep_type::iterator&)position, x);
  343.     }
  344.  
  345. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  346.     template<class InputIterator>
  347.     void insert (InputIterator first, InputIterator last)
  348.     {
  349.         while (first != last) t.insert(*first++);
  350.     }
  351. #else
  352.     void insert (const value_type* first, const value_type* last)
  353.     {
  354.         while (first != last) t.insert(*first++);
  355.     }
  356.     void insert (const_iterator first, const_iterator last)
  357.     {
  358.         while (first != last) t.insert(*first++);
  359.     }
  360. #endif
  361.  
  362.     void erase (iterator position)
  363.     {
  364.         t.erase((typename rep_type::iterator&)position);
  365.     }
  366.     size_type erase (const key_type& x) { return t.erase(x); }
  367.     void erase (iterator first, iterator last)
  368.     {
  369.         t.erase((typename rep_type::iterator&)first,
  370.                 (typename rep_type::iterator&)last);
  371.     }
  372.     void swap (multiset<Key, Compare>& x) { t.swap(x.t); }
  373.     //
  374.     // observers
  375.     //
  376.     key_compare   key_comp   () const { return t.key_comp(); }
  377.     value_compare value_comp () const { return t.key_comp(); }
  378.     //
  379.     // set operations
  380.     //
  381.     iterator  find        (const key_type& x) const { return t.find(x);  }
  382.     size_type count       (const key_type& x) const { return t.count(x); }
  383.     iterator  lower_bound (const key_type& x) const
  384.     {
  385.         return t.lower_bound(x);
  386.     }
  387.     iterator  upper_bound (const key_type& x) const
  388.     {
  389.         return t.upper_bound(x);
  390.     }
  391. #ifndef RWSTD_NO_RET_TEMPLATE
  392.     pair<iterator,iterator> equal_range (const key_type& x) const
  393. #else
  394.     typedef  pair<iterator, iterator> pair_iterator_iterator;
  395.     //
  396.     // typedef done to get around compiler bug
  397.     //
  398.     pair_iterator_iterator equal_range (const key_type& x) const
  399. #endif
  400.     {
  401.         return t.equal_range(x);
  402.     }
  403. };
  404.  
  405. template <class Key, class Compare>
  406. inline bool operator== (const set<Key, Compare>& x, const set<Key, Compare>& y)
  407. {
  408.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  409. }
  410.  
  411. template <class Key, class Compare>
  412. inline bool operator< (const set<Key, Compare>& x, const set<Key, Compare>& y)
  413. {
  414.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  415. }
  416.  
  417. template <class Key, class Compare>
  418. inline bool operator== (const multiset<Key, Compare>& x,
  419.                         const multiset<Key, Compare>& y)
  420. {
  421.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  422. }
  423.  
  424. template <class Key, class Compare>
  425. inline bool operator< (const multiset<Key, Compare>& x,
  426.                        const multiset<Key, Compare>& y)
  427. {
  428.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  429. }
  430.  
  431. #ifndef RWSTD_NO_NAMESPACE
  432. }
  433. #endif
  434.  
  435. #undef Allocator
  436.  
  437. #endif
  438.