home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / INC.PAK / MAP.H < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  16.4 KB  |  487 lines
  1. #ifndef __STD_MAP__
  2. #define __STD_MAP__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * map - declarations for the Standard Library map class
  8.  *
  9.  * $Id: map,v 1.31 1995/08/23 23:54:42 lijewski 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 map and multimap.
  79. //
  80.  
  81. template <class T, class U>
  82. struct select1st : public unary_function<T, U>
  83. {
  84.     const U& operator() (const T& x) const { return x.first; }
  85. };
  86.  
  87. //
  88. // First the map stuff.
  89. //
  90.  
  91. #ifndef RWSTD_NO_DEFAULT_TEMPLATES
  92. template<class Key, class T, class Compare = less<Key> >
  93. #else
  94. template<class Key, class T, class Compare>
  95. #endif /* RWSTD_NO_DEFAULT_TEMPLATES */
  96. class map
  97. {
  98.   public:
  99.     //
  100.     // types
  101.     //
  102.     typedef Key                key_type;
  103. #ifndef RWSTD_NO_CONST_INST
  104.     typedef pair<const Key, T> value_type;
  105. #else
  106.     typedef pair<Key, T>       value_type;
  107. #endif
  108.     typedef Compare            key_compare;
  109.  
  110.     class value_compare : public binary_function<value_type, value_type, bool>
  111.     {
  112.         friend class map<Key, T, Compare>;
  113.       protected:
  114.         Compare comp;
  115.         value_compare (Compare c) : comp(c) {}
  116.       public:
  117.         bool operator() (const value_type& x, const value_type& y) const
  118.         {
  119.             return comp(x.first, y.first);
  120.         }
  121.     };
  122.  
  123.   private:
  124.  
  125.     typedef rb_tree<key_type, value_type,
  126.                     select1st<value_type, key_type>, key_compare> rep_type;
  127.     rep_type t;
  128.  
  129.   public:
  130.     //
  131.     // types
  132.     //
  133.     typedef typename rep_type::reference                reference;
  134.     typedef typename rep_type::const_reference          const_reference;
  135.     typedef typename rep_type::iterator                 iterator;
  136.     typedef typename rep_type::const_iterator           const_iterator;
  137.     typedef typename rep_type::size_type                size_type;
  138.     typedef typename rep_type::difference_type          difference_type;
  139.     typedef typename rep_type::reverse_iterator         reverse_iterator;
  140.     typedef typename rep_type::const_reverse_iterator   const_reverse_iterator;
  141.     //
  142.     // construct/copy/destroy
  143.     //
  144.     explicit map (const Compare& comp = Compare()) : t(comp, false) {}
  145.  
  146. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  147.     template<class InputIterator>
  148.     map (InputIterator first, InputIterator last,
  149.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  150. #else
  151.     map (const value_type* first, const value_type* last,
  152.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  153.     map (iterator first, iterator last,
  154.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  155.     map (const_iterator first, const_iterator last,
  156.          const Compare& comp = Compare()) : t(first, last, comp, false) {}
  157. #endif
  158.  
  159.     map (const map<Key, T, Compare>& x) : t(x.t, false) {}
  160.     map<Key, T, Compare>& operator= (const map<Key, T, Compare>& x)
  161.     {
  162.           t = x.t; return *this;
  163.     }
  164.     //
  165.     // iterators
  166.     //
  167.  
  168.     iterator               begin  ()       { return t.begin();  }
  169.     const_iterator         begin  () const { return t.begin();  }
  170.     iterator               end    ()       { return t.end();    }
  171.     const_iterator         end    () const { return t.end();    }
  172.     reverse_iterator       rbegin ()       { return t.rbegin(); }
  173.     const_reverse_iterator rbegin () const { return t.rbegin(); }
  174.     reverse_iterator       rend   ()       { return t.rend();   }
  175.     const_reverse_iterator rend   () const { return t.rend();   }
  176.     //
  177.     // capacity
  178.     //
  179.     bool      empty    () const { return t.empty();    }
  180.     size_type size     () const { return t.size();     }
  181.     size_type max_size () const { return t.max_size(); }
  182.     //
  183.     // element access
  184.     //
  185.     T& operator[] (const key_type& k)
  186.     {
  187.         value_type tmp(k,T()); return (*((insert(tmp)).first)).second;
  188.     }
  189.     //
  190.     // TODO - fix this once required functionality is specified by WP!!!
  191.     //
  192.     //const T& operator[] (const key_type& k) const
  193.     //{
  194.     //    value_type tmp(k,T()); return (*((insert(tmp)).first)).second;
  195.     //}
  196.     //
  197.     // modifiers
  198.     //
  199. #ifndef RWSTD_NO_RET_TEMPLATE
  200.     pair<iterator,bool> insert (const value_type& x) { return t.insert(x); }
  201. #else
  202.     typedef pair<iterator, bool> pair_iterator_bool;
  203.     //
  204.     // typedef done to get around compiler bug
  205.     //
  206.     pair_iterator_bool insert (const value_type& x) { return t.insert(x); }
  207. #endif
  208.     iterator insert (iterator position, const value_type& x)
  209.     {
  210.         return t.insert(position, x);
  211.     }
  212.  
  213. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  214.     template<class InputIterator>
  215.     void insert (InputIterator first, InputIterator last)
  216.     {
  217.         t.insert(first, last);
  218.     }
  219. #else
  220.     void insert (const value_type* first, const value_type* last)
  221.     {
  222.         t.insert(first, last);
  223.     }
  224.     void insert (iterator first, iterator last)
  225.     {
  226.         t.insert(first, last);
  227.     }
  228.     void insert (const_iterator first, const_iterator last)
  229.     {
  230.         t.insert(first, last);
  231.     }
  232. #endif
  233.  
  234.     void      erase (iterator position)             { t.erase(position);    }
  235.     size_type erase (const key_type& x)             { return t.erase(x);    }
  236.     void      erase (iterator first, iterator last) { t.erase(first, last); }
  237.     void      swap  (map<Key, T, Compare>& x)       { t.swap(x.t);          }
  238.     //
  239.     // observers
  240.     //
  241.     key_compare key_comp () const { return t.key_comp(); }
  242.     value_compare value_comp () const { return value_compare(t.key_comp()); }
  243.     //
  244.     // map operations
  245.     //
  246.     iterator       find (const key_type& x)        { return t.find(x);        }
  247.     const_iterator find (const key_type& x)  const { return t.find(x);        }
  248.     size_type      count (const key_type& x) const { return t.count(x);       }
  249.     iterator       lower_bound (const key_type& x) { return t.lower_bound(x); }
  250.     iterator       upper_bound (const key_type& x) { return t.upper_bound(x); }
  251.     const_iterator lower_bound (const key_type& x) const
  252.     {
  253.         return t.lower_bound(x);
  254.     }
  255.     const_iterator upper_bound (const key_type& x) const
  256.     {
  257.         return t.upper_bound(x);
  258.     }
  259. #ifndef RWSTD_NO_RET_TEMPLATE
  260.     pair<iterator,iterator> equal_range (const key_type& x)
  261. #else
  262.     typedef pair<iterator, iterator> pair_iterator_iterator;
  263.     //
  264.     // typedef done to get around compiler bug
  265.     //
  266.     pair_iterator_iterator equal_range (const key_type& x)
  267. #endif
  268.     {
  269.         return t.equal_range(x);
  270.     }
  271. #ifndef RWSTD_NO_RET_TEMPLATE
  272.     pair<const_iterator, const_iterator> equal_range (const key_type& x) const
  273. #else
  274.     typedef pair<const_iterator, const_iterator> pair_citerator_citerator;
  275.     //
  276.     // typedef done to get around compiler bug
  277.     //
  278.     pair_citerator_citerator equal_range (const key_type& x) const
  279. #endif
  280.     {
  281.         return t.equal_range(x);
  282.     }
  283. };
  284.  
  285. template <class Key, class T, class Compare>
  286. class multimap
  287. {
  288.   public:
  289.     //
  290.     // types
  291.     //
  292.     typedef Key                  key_type;
  293. #ifndef RWSTD_NO_CONST_INST
  294.     typedef pair<const Key, T>   value_type;
  295. #else
  296.     typedef pair<Key, T>         value_type;
  297. #endif
  298.     typedef Compare              key_compare;
  299.  
  300.     class value_compare : public binary_function<value_type, value_type, bool>
  301.     {
  302.         friend class multimap<Key, T, Compare>;
  303.       protected:
  304.         Compare comp;
  305.         value_compare (Compare c) : comp(c) {}
  306.       public:
  307.         bool operator() (const value_type& x, const value_type& y) const
  308.         {
  309.             return comp(x.first, y.first);
  310.         }
  311.     };
  312.  
  313.   private:
  314.  
  315.     typedef rb_tree<key_type, value_type,
  316.                     select1st<value_type, key_type>, key_compare> rep_type;
  317.     rep_type t;
  318.  
  319.   public:
  320.     //
  321.     // types
  322.     //
  323.     typedef typename rep_type::reference                reference;
  324.     typedef typename rep_type::const_reference          const_reference;
  325.     typedef typename rep_type::iterator                 iterator;
  326.     typedef typename rep_type::const_iterator           const_iterator;
  327.     typedef typename rep_type::size_type                size_type;
  328.     typedef typename rep_type::difference_type          difference_type;
  329.     typedef typename rep_type::reverse_iterator         reverse_iterator;
  330.     typedef typename rep_type::const_reverse_iterator   const_reverse_iterator;
  331.     //
  332.     // construct/copy/destroy
  333.     //
  334.     explicit multimap (const Compare& comp = Compare()) : t(comp, true) { }
  335.  
  336. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  337.     template<class InputIterator>
  338.     multimap (InputIterator first, InputIterator last,
  339.               const Compare& comp = Compare()) : t(first, last, comp, true) { }
  340. #else
  341.     multimap (const value_type* first, const value_type* last,
  342.               const Compare& comp = Compare()) : t(first, last, comp, true) { }
  343.     multimap (iterator first, iterator last,
  344.               const Compare& comp = Compare()) : t(first, last, comp, true) { }
  345.     multimap (const_iterator first, const_iterator last,
  346.               const Compare& comp = Compare()) : t(first, last, comp,true) { }
  347. #endif
  348.  
  349.     multimap (const multimap<Key, T, Compare>& x) : t(x.t, true) { }
  350.     multimap<Key, T, Compare>& operator= (const multimap<Key, T, Compare>& x)
  351.     {
  352.           t = x.t; return *this;
  353.     }
  354.     //
  355.     // iterators
  356.     //
  357.     iterator                 begin  ()       { return t.begin();  }
  358.     const_iterator           begin  () const { return t.begin();  }
  359.     iterator                 end    ()       { return t.end();    }
  360.     const_iterator           end    () const { return t.end();    }
  361.     reverse_iterator         rbegin ()       { return t.rbegin(); }
  362.     const_reverse_iterator   rbegin () const { return t.rbegin(); }
  363.     reverse_iterator         rend   ()       { return t.rend();   }
  364.     const_reverse_iterator   rend   () const { return t.rend();   }
  365.     //
  366.     // capacity
  367.     //
  368.     bool        empty   () const { return t.empty();    }
  369.     size_type   size    () const { return t.size();     }
  370.     size_type   max_size() const { return t.max_size(); }
  371.     //
  372.     // modifiers
  373.     //
  374.     iterator insert (const value_type& x) { return t.insert(x).first; }
  375.     iterator insert (iterator position, const value_type& x)
  376.     {
  377.         return t.insert(position, x);
  378.     }
  379.  
  380. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  381.     template<class InputIterator>
  382.     void insert (InputIterator first, InputIterator last)
  383.     {
  384.         t.insert(first, last);
  385.     }
  386. #else
  387.     void insert (const value_type* first, const value_type* last)
  388.     {
  389.         t.insert(first, last);
  390.     }
  391.     void insert (iterator first, iterator last)
  392.     {
  393.         t.insert(first, last);
  394.     }
  395.     void insert (const_iterator first, const_iterator last)
  396.     {
  397.         t.insert(first, last);
  398.     }
  399. #endif
  400.  
  401.     void      erase (iterator position)             { t.erase(position);    }
  402.     size_type erase (const key_type& x)             { return t.erase(x);    }
  403.     void      erase (iterator first, iterator last) { t.erase(first, last); }
  404.     void      swap  (multimap<Key, T, Compare>& x)  { t.swap(x.t);          }
  405.     //
  406.     // observers
  407.     //
  408.     key_compare   key_comp   () const { return t.key_comp();                }
  409.     value_compare value_comp () const { return value_compare(t.key_comp()); }
  410.     //
  411.     // map operations
  412.     //
  413.     iterator        find (const key_type& x)        { return t.find(x);      }
  414.     const_iterator  find (const key_type& x)  const { return t.find(x);      }
  415.     size_type       count (const key_type& x) const { return t.count(x);     }
  416.     iterator        lower_bound (const key_type& x) {return t.lower_bound(x);}
  417.     iterator        upper_bound (const key_type& x) {return t.upper_bound(x);}
  418.     const_iterator  lower_bound (const key_type& x) const
  419.     {
  420.         return t.lower_bound(x);
  421.     }
  422.     const_iterator  upper_bound (const key_type& x) const
  423.     {
  424.         return t.upper_bound(x);
  425.     }
  426. #ifndef RWSTD_NO_RET_TEMPLATE
  427.     pair<iterator,iterator> equal_range (const key_type& x)
  428. #else
  429.     typedef  pair<iterator, iterator> pair_iterator_iterator;
  430.     //
  431.     // typedef done to get around compiler bug
  432.     //
  433.     pair_iterator_iterator equal_range (const key_type& x)
  434. #endif
  435.     {
  436.         return t.equal_range(x);
  437.     }
  438. #ifndef RWSTD_NO_RET_TEMPLATE
  439.     pair<const_iterator,const_iterator> equal_range (const key_type& x) const
  440. #else
  441.     typedef  pair<const_iterator, const_iterator> pair_citerator_citerator;
  442.     //
  443.     // typedef done to get around compiler bug
  444.     //
  445.     pair_citerator_citerator equal_range (const key_type& x) const
  446. #endif
  447.     {
  448.         return t.equal_range(x);
  449.     }
  450. };
  451.  
  452. template <class Key, class T, class Compare>
  453. inline bool operator== (const map<Key, T, Compare>& x,
  454.                         const map<Key, T, Compare>& y)
  455. {
  456.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  457. }
  458.  
  459. template <class Key, class T, class Compare>
  460. inline bool operator< (const map<Key, T, Compare>& x,
  461.                        const map<Key, T, Compare>& y)
  462. {
  463.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  464. }
  465.  
  466. template <class Key, class T, class Compare>
  467. inline bool operator== (const multimap<Key, T, Compare>& x,
  468.                         const multimap<Key, T, Compare>& y)
  469. {
  470.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  471. }
  472.  
  473. template <class Key, class T, class Compare>
  474. inline bool operator< (const multimap<Key, T, Compare>& x,
  475.                        const multimap<Key, T, Compare>& y)
  476. {
  477.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  478. }
  479.  
  480. #ifndef RWSTD_NO_NAMESPACE
  481. }
  482. #endif
  483.  
  484. #undef Allocator
  485.  
  486. #endif
  487.