home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / ext / hash_set < prev    next >
Encoding:
Text File  |  2003-12-15  |  16.3 KB  |  446 lines
  1. // Hashing set implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  * Copyright (c) 1996
  32.  * Silicon Graphics Computer Systems, Inc.
  33.  *
  34.  * Permission to use, copy, modify, distribute and sell this software
  35.  * and its documentation for any purpose is hereby granted without fee,
  36.  * provided that the above copyright notice appear in all copies and
  37.  * that both that copyright notice and this permission notice appear
  38.  * in supporting documentation.  Silicon Graphics makes no
  39.  * representations about the suitability of this software for any
  40.  * purpose.  It is provided "as is" without express or implied warranty.
  41.  *
  42.  *
  43.  * Copyright (c) 1994
  44.  * Hewlett-Packard Company
  45.  *
  46.  * Permission to use, copy, modify, distribute and sell this software
  47.  * and its documentation for any purpose is hereby granted without fee,
  48.  * provided that the above copyright notice appear in all copies and
  49.  * that both that copyright notice and this permission notice appear
  50.  * in supporting documentation.  Hewlett-Packard Company makes no
  51.  * representations about the suitability of this software for any
  52.  * purpose.  It is provided "as is" without express or implied warranty.
  53.  *
  54.  */
  55.  
  56. /** @file ext/hash_set
  57.  *  This file is a GNU extension to the Standard C++ Library (possibly
  58.  *  containing extensions from the HP/SGI STL subset).  You should only
  59.  *  include this header if you are using GCC 3 or later.
  60.  */
  61.  
  62. #ifndef __SGI_STL_INTERNAL_HASH_SET_H
  63. #define __SGI_STL_INTERNAL_HASH_SET_H
  64.  
  65. #include <ext/stl_hashtable.h>
  66. #include <bits/concept_check.h>
  67.  
  68. namespace __gnu_cxx
  69. {
  70. using std::equal_to;
  71. using std::allocator;
  72. using std::pair;
  73. using std::_Identity;
  74.  
  75. // Forward declaration of equality operator; needed for friend declaration.
  76.  
  77. template <class _Value,
  78.           class _HashFcn  = hash<_Value>,
  79.           class _EqualKey = equal_to<_Value>,
  80.           class _Alloc =  allocator<_Value> >
  81. class hash_set;
  82.  
  83. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  84. inline bool 
  85. operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  86.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
  87.  
  88. /**
  89.  *  This is an SGI extension.
  90.  *  @ingroup SGIextensions
  91.  *  @doctodo
  92. */
  93. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  94. class hash_set
  95. {
  96.   // concept requirements
  97.   __glibcpp_class_requires(_Value, _SGIAssignableConcept)
  98.   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
  99.   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
  100.  
  101. private:
  102.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
  103.                     _EqualKey, _Alloc> _Ht;
  104.   _Ht _M_ht;
  105.  
  106. public:
  107.   typedef typename _Ht::key_type key_type;
  108.   typedef typename _Ht::value_type value_type;
  109.   typedef typename _Ht::hasher hasher;
  110.   typedef typename _Ht::key_equal key_equal;
  111.  
  112.   typedef typename _Ht::size_type size_type;
  113.   typedef typename _Ht::difference_type difference_type;
  114.   typedef typename _Ht::const_pointer pointer;
  115.   typedef typename _Ht::const_pointer const_pointer;
  116.   typedef typename _Ht::const_reference reference;
  117.   typedef typename _Ht::const_reference const_reference;
  118.  
  119.   typedef typename _Ht::const_iterator iterator;
  120.   typedef typename _Ht::const_iterator const_iterator;
  121.  
  122.   typedef typename _Ht::allocator_type allocator_type;
  123.  
  124.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  125.   key_equal key_eq() const { return _M_ht.key_eq(); }
  126.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  127.  
  128. public:
  129.   hash_set()
  130.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  131.   explicit hash_set(size_type __n)
  132.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  133.   hash_set(size_type __n, const hasher& __hf)
  134.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  135.   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  136.            const allocator_type& __a = allocator_type())
  137.     : _M_ht(__n, __hf, __eql, __a) {}
  138.  
  139.   template <class _InputIterator>
  140.   hash_set(_InputIterator __f, _InputIterator __l)
  141.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  142.     { _M_ht.insert_unique(__f, __l); }
  143.   template <class _InputIterator>
  144.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
  145.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  146.     { _M_ht.insert_unique(__f, __l); }
  147.   template <class _InputIterator>
  148.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  149.            const hasher& __hf)
  150.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  151.     { _M_ht.insert_unique(__f, __l); }
  152.   template <class _InputIterator>
  153.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  154.            const hasher& __hf, const key_equal& __eql,
  155.            const allocator_type& __a = allocator_type())
  156.     : _M_ht(__n, __hf, __eql, __a)
  157.     { _M_ht.insert_unique(__f, __l); }
  158.  
  159. public:
  160.   size_type size() const { return _M_ht.size(); }
  161.   size_type max_size() const { return _M_ht.max_size(); }
  162.   bool empty() const { return _M_ht.empty(); }
  163.   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
  164.  
  165.   template <class _Val, class _HF, class _EqK, class _Al>  
  166.   friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
  167.                           const hash_set<_Val, _HF, _EqK, _Al>&);
  168.  
  169.   iterator begin() const { return _M_ht.begin(); }
  170.   iterator end() const { return _M_ht.end(); }
  171.  
  172. public:
  173.   pair<iterator, bool> insert(const value_type& __obj)
  174.     {
  175.       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
  176.       return pair<iterator,bool>(__p.first, __p.second);
  177.     }
  178.   template <class _InputIterator>
  179.   void insert(_InputIterator __f, _InputIterator __l) 
  180.     { _M_ht.insert_unique(__f,__l); }
  181.   pair<iterator, bool> insert_noresize(const value_type& __obj)
  182.   {
  183.     pair<typename _Ht::iterator, bool> __p = 
  184.       _M_ht.insert_unique_noresize(__obj);
  185.     return pair<iterator, bool>(__p.first, __p.second);
  186.   }
  187.  
  188.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  189.  
  190.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  191.   
  192.   pair<iterator, iterator> equal_range(const key_type& __key) const
  193.     { return _M_ht.equal_range(__key); }
  194.  
  195.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  196.   void erase(iterator __it) { _M_ht.erase(__it); }
  197.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  198.   void clear() { _M_ht.clear(); }
  199.  
  200. public:
  201.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  202.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  203.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  204.   size_type elems_in_bucket(size_type __n) const
  205.     { return _M_ht.elems_in_bucket(__n); }
  206. };
  207.  
  208. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  209. inline bool 
  210. operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  211.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
  212. {
  213.   return __hs1._M_ht == __hs2._M_ht;
  214. }
  215.  
  216. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  217. inline bool 
  218. operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  219.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  220.   return !(__hs1 == __hs2);
  221. }
  222.  
  223. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  224. inline void 
  225. swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  226.      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  227. {
  228.   __hs1.swap(__hs2);
  229. }
  230.  
  231.  
  232. template <class _Value,
  233.           class _HashFcn  = hash<_Value>,
  234.           class _EqualKey = equal_to<_Value>,
  235.           class _Alloc =  allocator<_Value> >
  236. class hash_multiset;
  237.  
  238. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  239. inline bool 
  240. operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  241.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
  242.  
  243.  
  244. /**
  245.  *  This is an SGI extension.
  246.  *  @ingroup SGIextensions
  247.  *  @doctodo
  248. */
  249. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  250. class hash_multiset
  251. {
  252.   // concept requirements
  253.   __glibcpp_class_requires(_Value, _SGIAssignableConcept)
  254.   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
  255.   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
  256.  
  257. private:
  258.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 
  259.                     _EqualKey, _Alloc> _Ht;
  260.   _Ht _M_ht;
  261.  
  262. public:
  263.   typedef typename _Ht::key_type key_type;
  264.   typedef typename _Ht::value_type value_type;
  265.   typedef typename _Ht::hasher hasher;
  266.   typedef typename _Ht::key_equal key_equal;
  267.  
  268.   typedef typename _Ht::size_type size_type;
  269.   typedef typename _Ht::difference_type difference_type;
  270.   typedef typename _Ht::const_pointer pointer;
  271.   typedef typename _Ht::const_pointer const_pointer;
  272.   typedef typename _Ht::const_reference reference;
  273.   typedef typename _Ht::const_reference const_reference;
  274.  
  275.   typedef typename _Ht::const_iterator iterator;
  276.   typedef typename _Ht::const_iterator const_iterator;
  277.  
  278.   typedef typename _Ht::allocator_type allocator_type;
  279.  
  280.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  281.   key_equal key_eq() const { return _M_ht.key_eq(); }
  282.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  283.  
  284. public:
  285.   hash_multiset()
  286.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  287.   explicit hash_multiset(size_type __n)
  288.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  289.   hash_multiset(size_type __n, const hasher& __hf)
  290.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  291.   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
  292.                 const allocator_type& __a = allocator_type())
  293.     : _M_ht(__n, __hf, __eql, __a) {}
  294.  
  295.   template <class _InputIterator>
  296.   hash_multiset(_InputIterator __f, _InputIterator __l)
  297.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  298.     { _M_ht.insert_equal(__f, __l); }
  299.   template <class _InputIterator>
  300.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
  301.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  302.     { _M_ht.insert_equal(__f, __l); }
  303.   template <class _InputIterator>
  304.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  305.                 const hasher& __hf)
  306.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  307.     { _M_ht.insert_equal(__f, __l); }
  308.   template <class _InputIterator>
  309.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  310.                 const hasher& __hf, const key_equal& __eql,
  311.                 const allocator_type& __a = allocator_type())
  312.     : _M_ht(__n, __hf, __eql, __a)
  313.     { _M_ht.insert_equal(__f, __l); }
  314.  
  315. public:
  316.   size_type size() const { return _M_ht.size(); }
  317.   size_type max_size() const { return _M_ht.max_size(); }
  318.   bool empty() const { return _M_ht.empty(); }
  319.   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
  320.  
  321.   template <class _Val, class _HF, class _EqK, class _Al>  
  322.   friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
  323.                           const hash_multiset<_Val, _HF, _EqK, _Al>&);
  324.  
  325.   iterator begin() const { return _M_ht.begin(); }
  326.   iterator end() const { return _M_ht.end(); }
  327.  
  328. public:
  329.   iterator insert(const value_type& __obj)
  330.     { return _M_ht.insert_equal(__obj); }
  331.   template <class _InputIterator>
  332.   void insert(_InputIterator __f, _InputIterator __l) 
  333.     { _M_ht.insert_equal(__f,__l); }
  334.   iterator insert_noresize(const value_type& __obj)
  335.     { return _M_ht.insert_equal_noresize(__obj); }    
  336.  
  337.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  338.  
  339.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  340.   
  341.   pair<iterator, iterator> equal_range(const key_type& __key) const
  342.     { return _M_ht.equal_range(__key); }
  343.  
  344.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  345.   void erase(iterator __it) { _M_ht.erase(__it); }
  346.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  347.   void clear() { _M_ht.clear(); }
  348.  
  349. public:
  350.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  351.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  352.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  353.   size_type elems_in_bucket(size_type __n) const
  354.     { return _M_ht.elems_in_bucket(__n); }
  355. };
  356.  
  357. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  358. inline bool 
  359. operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  360.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  361. {
  362.   return __hs1._M_ht == __hs2._M_ht;
  363. }
  364.  
  365. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  366. inline bool 
  367. operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  368.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  369.   return !(__hs1 == __hs2);
  370. }
  371.  
  372. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  373. inline void 
  374. swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  375.      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  376.   __hs1.swap(__hs2);
  377. }
  378.  
  379. } // namespace __gnu_cxx
  380.  
  381. namespace std
  382. {
  383. // Specialization of insert_iterator so that it will work for hash_set
  384. // and hash_multiset.
  385.  
  386. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  387. class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
  388. protected:
  389.   typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
  390.   _Container* container;
  391. public:
  392.   typedef _Container          container_type;
  393.   typedef output_iterator_tag iterator_category;
  394.   typedef void                value_type;
  395.   typedef void                difference_type;
  396.   typedef void                pointer;
  397.   typedef void                reference;
  398.  
  399.   insert_iterator(_Container& __x) : container(&__x) {}
  400.   insert_iterator(_Container& __x, typename _Container::iterator)
  401.     : container(&__x) {}
  402.   insert_iterator<_Container>&
  403.   operator=(const typename _Container::value_type& __value) { 
  404.     container->insert(__value);
  405.     return *this;
  406.   }
  407.   insert_iterator<_Container>& operator*() { return *this; }
  408.   insert_iterator<_Container>& operator++() { return *this; }
  409.   insert_iterator<_Container>& operator++(int) { return *this; }
  410. };
  411.  
  412. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  413. class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
  414. protected:
  415.   typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
  416.   _Container* container;
  417.   typename _Container::iterator iter;
  418. public:
  419.   typedef _Container          container_type;
  420.   typedef output_iterator_tag iterator_category;
  421.   typedef void                value_type;
  422.   typedef void                difference_type;
  423.   typedef void                pointer;
  424.   typedef void                reference;
  425.  
  426.   insert_iterator(_Container& __x) : container(&__x) {}
  427.   insert_iterator(_Container& __x, typename _Container::iterator)
  428.     : container(&__x) {}
  429.   insert_iterator<_Container>&
  430.   operator=(const typename _Container::value_type& __value) { 
  431.     container->insert(__value);
  432.     return *this;
  433.   }
  434.   insert_iterator<_Container>& operator*() { return *this; }
  435.   insert_iterator<_Container>& operator++() { return *this; }
  436.   insert_iterator<_Container>& operator++(int) { return *this; }
  437. };
  438.  
  439. } // namespace std
  440.  
  441. #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
  442.  
  443. // Local Variables:
  444. // mode:C++
  445. // End:
  446.