Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright (c) 1996
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  *
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_HASH_SET_H
  32. #define __SGI_STL_INTERNAL_HASH_SET_H
  33.  
  34. #include <ext/stl_hashtable.h>
  35. #include <bits/concept_check.h>
  36.  
  37. namespace std
  38. {
  39.  
  40. // Forward declaration of equality operator; needed for friend declaration.
  41.  
  42. template <class _Value,
  43.           class _HashFcn  = hash<_Value>,
  44.           class _EqualKey = equal_to<_Value>,
  45.           class _Alloc =  allocator<_Value> >
  46. class hash_set;
  47.  
  48. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  49. inline bool
  50. operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  51.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
  52.  
  53. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  54. class hash_set
  55. {
  56.   // concept requirements
  57.   __glibcpp_class_requires(_Value, _SGIAssignableConcept);
  58.   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
  59.   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
  60.  
  61. private:
  62.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  63.                     _EqualKey, _Alloc> _Ht;
  64.   _Ht _M_ht;
  65.  
  66. public:
  67.   typedef typename _Ht::key_type key_type;
  68.   typedef typename _Ht::value_type value_type;
  69.   typedef typename _Ht::hasher hasher;
  70.   typedef typename _Ht::key_equal key_equal;
  71.  
  72.   typedef typename _Ht::size_type size_type;
  73.   typedef typename _Ht::difference_type difference_type;
  74.   typedef typename _Ht::const_pointer pointer;
  75.   typedef typename _Ht::const_pointer const_pointer;
  76.   typedef typename _Ht::const_reference reference;
  77.   typedef typename _Ht::const_reference const_reference;
  78.  
  79.   typedef typename _Ht::const_iterator iterator;
  80.   typedef typename _Ht::const_iterator const_iterator;
  81.  
  82.   typedef typename _Ht::allocator_type allocator_type;
  83.  
  84.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  85.   key_equal key_eq() const { return _M_ht.key_eq(); }
  86.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  87.  
  88. public:
  89.   hash_set()
  90.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  91.   explicit hash_set(size_type __n)
  92.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  93.   hash_set(size_type __n, const hasher& __hf)
  94.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  95.   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  96.            const allocator_type& __a = allocator_type())
  97.     : _M_ht(__n, __hf, __eql, __a) {}
  98.  
  99.   template <class _InputIterator>
  100.   hash_set(_InputIterator __f, _InputIterator __l)
  101.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  102.     { _M_ht.insert_unique(__f, __l); }
  103.   template <class _InputIterator>
  104.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
  105.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  106.     { _M_ht.insert_unique(__f, __l); }
  107.   template <class _InputIterator>
  108.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  109.            const hasher& __hf)
  110.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  111.     { _M_ht.insert_unique(__f, __l); }
  112.   template <class _InputIterator>
  113.   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  114.            const hasher& __hf, const key_equal& __eql,
  115.            const allocator_type& __a = allocator_type())
  116.     : _M_ht(__n, __hf, __eql, __a)
  117.     { _M_ht.insert_unique(__f, __l); }
  118.  
  119. public:
  120.   size_type size() const { return _M_ht.size(); }
  121.   size_type max_size() const { return _M_ht.max_size(); }
  122.   bool empty() const { return _M_ht.empty(); }
  123.   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
  124.  
  125.   template <class _Val, class _HF, class _EqK, class _Al>  
  126.   friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
  127.                           const hash_set<_Val, _HF, _EqK, _Al>&);
  128.  
  129.   iterator begin() const { return _M_ht.begin(); }
  130.   iterator end() const { return _M_ht.end(); }
  131.  
  132. public:
  133.   pair<iterator, bool> insert(const value_type& __obj)
  134.     {
  135.       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
  136.       return pair<iterator,bool>(__p.first, __p.second);
  137.     }
  138.   template <class _InputIterator>
  139.   void insert(_InputIterator __f, _InputIterator __l)
  140.     { _M_ht.insert_unique(__f,__l); }
  141.   pair<iterator, bool> insert_noresize(const value_type& __obj)
  142.   {
  143.     pair<typename _Ht::iterator, bool> __p =
  144.       _M_ht.insert_unique_noresize(__obj);
  145.     return pair<iterator, bool>(__p.first, __p.second);
  146.   }
  147.  
  148.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  149.  
  150.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  151.  
  152.   pair<iterator, iterator> equal_range(const key_type& __key) const
  153.     { return _M_ht.equal_range(__key); }
  154.  
  155.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  156.   void erase(iterator __it) { _M_ht.erase(__it); }
  157.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  158.   void clear() { _M_ht.clear(); }
  159.  
  160. public:
  161.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  162.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  163.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  164.   size_type elems_in_bucket(size_type __n) const
  165.     { return _M_ht.elems_in_bucket(__n); }
  166. };
  167.  
  168. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  169. inline bool
  170. operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  171.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
  172. {
  173.   return __hs1._M_ht == __hs2._M_ht;
  174. }
  175.  
  176. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  177. inline bool
  178. operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  179.            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  180.   return !(__hs1 == __hs2);
  181. }
  182.  
  183. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  184. inline void
  185. swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  186.      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  187. {
  188.   __hs1.swap(__hs2);
  189. }
  190.  
  191.  
  192. template <class _Value,
  193.           class _HashFcn  = hash<_Value>,
  194.           class _EqualKey = equal_to<_Value>,
  195.           class _Alloc =  allocator<_Value> >
  196. class hash_multiset;
  197.  
  198. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  199. inline bool
  200. operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  201.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
  202.  
  203.  
  204. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  205. class hash_multiset
  206. {
  207.   // concept requirements
  208.   __glibcpp_class_requires(_Value, _SGIAssignableConcept);
  209.   __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
  210.   __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
  211.  
  212. private:
  213.   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  214.                     _EqualKey, _Alloc> _Ht;
  215.   _Ht _M_ht;
  216.  
  217. public:
  218.   typedef typename _Ht::key_type key_type;
  219.   typedef typename _Ht::value_type value_type;
  220.   typedef typename _Ht::hasher hasher;
  221.   typedef typename _Ht::key_equal key_equal;
  222.  
  223.   typedef typename _Ht::size_type size_type;
  224.   typedef typename _Ht::difference_type difference_type;
  225.   typedef typename _Ht::const_pointer pointer;
  226.   typedef typename _Ht::const_pointer const_pointer;
  227.   typedef typename _Ht::const_reference reference;
  228.   typedef typename _Ht::const_reference const_reference;
  229.  
  230.   typedef typename _Ht::const_iterator iterator;
  231.   typedef typename _Ht::const_iterator const_iterator;
  232.  
  233.   typedef typename _Ht::allocator_type allocator_type;
  234.  
  235.   hasher hash_funct() const { return _M_ht.hash_funct(); }
  236.   key_equal key_eq() const { return _M_ht.key_eq(); }
  237.   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  238.  
  239. public:
  240.   hash_multiset()
  241.     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  242.   explicit hash_multiset(size_type __n)
  243.     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  244.   hash_multiset(size_type __n, const hasher& __hf)
  245.     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  246.   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
  247.                 const allocator_type& __a = allocator_type())
  248.     : _M_ht(__n, __hf, __eql, __a) {}
  249.  
  250.   template <class _InputIterator>
  251.   hash_multiset(_InputIterator __f, _InputIterator __l)
  252.     : _M_ht(100, hasher(), key_equal(), allocator_type())
  253.     { _M_ht.insert_equal(__f, __l); }
  254.   template <class _InputIterator>
  255.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
  256.     : _M_ht(__n, hasher(), key_equal(), allocator_type())
  257.     { _M_ht.insert_equal(__f, __l); }
  258.   template <class _InputIterator>
  259.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  260.                 const hasher& __hf)
  261.     : _M_ht(__n, __hf, key_equal(), allocator_type())
  262.     { _M_ht.insert_equal(__f, __l); }
  263.   template <class _InputIterator>
  264.   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  265.                 const hasher& __hf, const key_equal& __eql,
  266.                 const allocator_type& __a = allocator_type())
  267.     : _M_ht(__n, __hf, __eql, __a)
  268.     { _M_ht.insert_equal(__f, __l); }
  269.  
  270. public:
  271.   size_type size() const { return _M_ht.size(); }
  272.   size_type max_size() const { return _M_ht.max_size(); }
  273.   bool empty() const { return _M_ht.empty(); }
  274.   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
  275.  
  276.   template <class _Val, class _HF, class _EqK, class _Al>  
  277.   friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
  278.                           const hash_multiset<_Val, _HF, _EqK, _Al>&);
  279.  
  280.   iterator begin() const { return _M_ht.begin(); }
  281.   iterator end() const { return _M_ht.end(); }
  282.  
  283. public:
  284.   iterator insert(const value_type& __obj)
  285.     { return _M_ht.insert_equal(__obj); }
  286.   template <class _InputIterator>
  287.   void insert(_InputIterator __f, _InputIterator __l)
  288.     { _M_ht.insert_equal(__f,__l); }
  289.   iterator insert_noresize(const value_type& __obj)
  290.     { return _M_ht.insert_equal_noresize(__obj); }    
  291.  
  292.   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
  293.  
  294.   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
  295.  
  296.   pair<iterator, iterator> equal_range(const key_type& __key) const
  297.     { return _M_ht.equal_range(__key); }
  298.  
  299.   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
  300.   void erase(iterator __it) { _M_ht.erase(__it); }
  301.   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  302.   void clear() { _M_ht.clear(); }
  303.  
  304. public:
  305.   void resize(size_type __hint) { _M_ht.resize(__hint); }
  306.   size_type bucket_count() const { return _M_ht.bucket_count(); }
  307.   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  308.   size_type elems_in_bucket(size_type __n) const
  309.     { return _M_ht.elems_in_bucket(__n); }
  310. };
  311.  
  312. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  313. inline bool
  314. operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  315.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
  316. {
  317.   return __hs1._M_ht == __hs2._M_ht;
  318. }
  319.  
  320. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  321. inline bool
  322. operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  323.            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  324.   return !(__hs1 == __hs2);
  325. }
  326.  
  327. template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  328. inline void
  329. swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
  330.      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
  331.   __hs1.swap(__hs2);
  332. }
  333.  
  334. // Specialization of insert_iterator so that it will work for hash_set
  335. // and hash_multiset.
  336.  
  337. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  338. class insert_iterator<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
  339. protected:
  340.   typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
  341.   _Container* container;
  342. public:
  343.   typedef _Container          container_type;
  344.   typedef output_iterator_tag iterator_category;
  345.   typedef void                value_type;
  346.   typedef void                difference_type;
  347.   typedef void                pointer;
  348.   typedef void                reference;
  349.  
  350.   insert_iterator(_Container& __x) : container(&__x) {}
  351.   insert_iterator(_Container& __x, typename _Container::iterator)
  352.     : container(&__x) {}
  353.   insert_iterator<_Container>&
  354.   operator=(const typename _Container::value_type& __value) {
  355.     container->insert(__value);
  356.     return *this;
  357.   }
  358.   insert_iterator<_Container>& operator*() { return *this; }
  359.   insert_iterator<_Container>& operator++() { return *this; }
  360.   insert_iterator<_Container>& operator++(int) { return *this; }
  361. };
  362.  
  363. template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  364. class insert_iterator<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
  365. protected:
  366.   typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
  367.   _Container* container;
  368.   typename _Container::iterator iter;
  369. public:
  370.   typedef _Container          container_type;
  371.   typedef output_iterator_tag iterator_category;
  372.   typedef void                value_type;
  373.   typedef void                difference_type;
  374.   typedef void                pointer;
  375.   typedef void                reference;
  376.  
  377.   insert_iterator(_Container& __x) : container(&__x) {}
  378.   insert_iterator(_Container& __x, typename _Container::iterator)
  379.     : container(&__x) {}
  380.   insert_iterator<_Container>&
  381.   operator=(const typename _Container::value_type& __value) {
  382.     container->insert(__value);
  383.     return *this;
  384.   }
  385.   insert_iterator<_Container>& operator*() { return *this; }
  386.   insert_iterator<_Container>& operator++() { return *this; }
  387.   insert_iterator<_Container>& operator++(int) { return *this; }
  388. };
  389.  
  390. } // namespace std
  391.  
  392. #endif /* __SGI_STL_INTERNAL_HASH_SET_H */
  393.  
  394. // Local Variables:
  395. // mode:C++
  396. // End:
  397.