// Hashing set implementation -*- C++ -*-// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING. If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction. Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License. This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./** Copyright (c) 1996* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation. Silicon Graphics makes no* representations about the suitability of this software for any* purpose. It is provided "as is" without express or implied warranty.*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation. Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose. It is provided "as is" without express or implied warranty.**//** @file ext/hash_set* This file is a GNU extension to the Standard C++ Library (possibly* containing extensions from the HP/SGI STL subset).*/#ifndef _HASH_SET#define _HASH_SET 1#include <ext/hashtable.h>#include <bits/concept_check.h>namespace __gnu_cxx{using std::equal_to;using std::allocator;using std::pair;using std::_Identity;// Forward declaration of equality operator; needed for friend// declaration.template <class _Value, class _HashFcn = hash<_Value>,class _EqualKey = equal_to<_Value>,class _Alloc = allocator<_Value> >class hash_set;template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2);/*** This is an SGI extension.* @ingroup SGIextensions* @doctodo*/template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>class hash_set{// concept requirements__glibcxx_class_requires(_Value, _SGIAssignableConcept)__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)private:typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,_EqualKey, _Alloc> _Ht;_Ht _M_ht;public:typedef typename _Ht::key_type key_type;typedef typename _Ht::value_type value_type;typedef typename _Ht::hasher hasher;typedef typename _Ht::key_equal key_equal;typedef typename _Ht::size_type size_type;typedef typename _Ht::difference_type difference_type;typedef typename _Alloc::pointer pointer;typedef typename _Alloc::const_pointer const_pointer;typedef typename _Alloc::reference reference;typedef typename _Alloc::const_reference const_reference;typedef typename _Ht::const_iterator iterator;typedef typename _Ht::const_iterator const_iterator;typedef typename _Ht::allocator_type allocator_type;hasherhash_funct() const{ return _M_ht.hash_funct(); }key_equalkey_eq() const{ return _M_ht.key_eq(); }allocator_typeget_allocator() const{ return _M_ht.get_allocator(); }public:hash_set(): _M_ht(100, hasher(), key_equal(), allocator_type()) {}explicithash_set(size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()) {}hash_set(size_type __n, const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()) {}hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a) {}template <class _InputIterator>hash_set(_InputIterator __f, _InputIterator __l): _M_ht(100, hasher(), key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_set(_InputIterator __f, _InputIterator __l, size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_set(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_set(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a){ _M_ht.insert_unique(__f, __l); }public:size_typesize() const{ return _M_ht.size(); }size_typemax_size() const{ return _M_ht.max_size(); }boolempty() const{ return _M_ht.empty(); }voidswap(hash_set& __hs){ _M_ht.swap(__hs._M_ht); }template <class _Val, class _HF, class _EqK, class _Al>friend booloperator==(const hash_set<_Val, _HF, _EqK, _Al>&,const hash_set<_Val, _HF, _EqK, _Al>&);iteratorbegin() const{ return _M_ht.begin(); }iteratorend() const{ return _M_ht.end(); }public:pair<iterator, bool>insert(const value_type& __obj){pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);return pair<iterator,bool>(__p.first, __p.second);}template <class _InputIterator>voidinsert(_InputIterator __f, _InputIterator __l){ _M_ht.insert_unique(__f, __l); }pair<iterator, bool>insert_noresize(const value_type& __obj){pair<typename _Ht::iterator, bool> __p= _M_ht.insert_unique_noresize(__obj);return pair<iterator, bool>(__p.first, __p.second);}iteratorfind(const key_type& __key) const{ return _M_ht.find(__key); }size_typecount(const key_type& __key) const{ return _M_ht.count(__key); }pair<iterator, iterator>equal_range(const key_type& __key) const{ return _M_ht.equal_range(__key); }size_typeerase(const key_type& __key){return _M_ht.erase(__key); }voiderase(iterator __it){ _M_ht.erase(__it); }voiderase(iterator __f, iterator __l){ _M_ht.erase(__f, __l); }voidclear(){ _M_ht.clear(); }public:voidresize(size_type __hint){ _M_ht.resize(__hint); }size_typebucket_count() const{ return _M_ht.bucket_count(); }size_typemax_bucket_count() const{ return _M_ht.max_bucket_count(); }size_typeelems_in_bucket(size_type __n) const{ return _M_ht.elems_in_bucket(__n); }};template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2){ return __hs1._M_ht == __hs2._M_ht; }template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2){ return !(__hs1 == __hs2); }template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>inline voidswap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2){ __hs1.swap(__hs2); }template <class _Value,class _HashFcn = hash<_Value>,class _EqualKey = equal_to<_Value>,class _Alloc = allocator<_Value> >class hash_multiset;template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2);/*** This is an SGI extension.* @ingroup SGIextensions* @doctodo*/template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>class hash_multiset{// concept requirements__glibcxx_class_requires(_Value, _SGIAssignableConcept)__glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)__glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)private:typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,_EqualKey, _Alloc> _Ht;_Ht _M_ht;public:typedef typename _Ht::key_type key_type;typedef typename _Ht::value_type value_type;typedef typename _Ht::hasher hasher;typedef typename _Ht::key_equal key_equal;typedef typename _Ht::size_type size_type;typedef typename _Ht::difference_type difference_type;typedef typename _Alloc::pointer pointer;typedef typename _Alloc::const_pointer const_pointer;typedef typename _Alloc::reference reference;typedef typename _Alloc::const_reference const_reference;typedef typename _Ht::const_iterator iterator;typedef typename _Ht::const_iterator const_iterator;typedef typename _Ht::allocator_type allocator_type;hasherhash_funct() const{ return _M_ht.hash_funct(); }key_equalkey_eq() const{ return _M_ht.key_eq(); }allocator_typeget_allocator() const{ return _M_ht.get_allocator(); }public:hash_multiset(): _M_ht(100, hasher(), key_equal(), allocator_type()) {}explicithash_multiset(size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()) {}hash_multiset(size_type __n, const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()) {}hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a) {}template <class _InputIterator>hash_multiset(_InputIterator __f, _InputIterator __l): _M_ht(100, hasher(), key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a){ _M_ht.insert_equal(__f, __l); }public:size_typesize() const{ return _M_ht.size(); }size_typemax_size() const{ return _M_ht.max_size(); }boolempty() const{ return _M_ht.empty(); }voidswap(hash_multiset& hs){ _M_ht.swap(hs._M_ht); }template <class _Val, class _HF, class _EqK, class _Al>friend booloperator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,const hash_multiset<_Val, _HF, _EqK, _Al>&);iteratorbegin() const{ return _M_ht.begin(); }iteratorend() const{ return _M_ht.end(); }public:iteratorinsert(const value_type& __obj){ return _M_ht.insert_equal(__obj); }template <class _InputIterator>voidinsert(_InputIterator __f, _InputIterator __l){ _M_ht.insert_equal(__f,__l); }iteratorinsert_noresize(const value_type& __obj){ return _M_ht.insert_equal_noresize(__obj); }iteratorfind(const key_type& __key) const{ return _M_ht.find(__key); }size_typecount(const key_type& __key) const{ return _M_ht.count(__key); }pair<iterator, iterator>equal_range(const key_type& __key) const{ return _M_ht.equal_range(__key); }size_typeerase(const key_type& __key){ return _M_ht.erase(__key); }voiderase(iterator __it){ _M_ht.erase(__it); }voiderase(iterator __f, iterator __l){ _M_ht.erase(__f, __l); }voidclear(){ _M_ht.clear(); }public:voidresize(size_type __hint){ _M_ht.resize(__hint); }size_typebucket_count() const{ return _M_ht.bucket_count(); }size_typemax_bucket_count() const{ return _M_ht.max_bucket_count(); }size_typeelems_in_bucket(size_type __n) const{ return _M_ht.elems_in_bucket(__n); }};template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2){ return __hs1._M_ht == __hs2._M_ht; }template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>inline booloperator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2){ return !(__hs1 == __hs2); }template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>inline voidswap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2){ __hs1.swap(__hs2); }} // namespace __gnu_cxxnamespace std{// Specialization of insert_iterator so that it will work for hash_set// and hash_multiset.template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,_EqualKey, _Alloc> >{protected:typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>_Container;_Container* container;public:typedef _Container container_type;typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;insert_iterator(_Container& __x): container(&__x) {}insert_iterator(_Container& __x, typename _Container::iterator): container(&__x) {}insert_iterator<_Container>&operator=(const typename _Container::value_type& __value){container->insert(__value);return *this;}insert_iterator<_Container>&operator*(){ return *this; }insert_iterator<_Container>&operator++(){ return *this; }insert_iterator<_Container>&operator++(int){ return *this; }};template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,_EqualKey, _Alloc> >{protected:typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>_Container;_Container* container;typename _Container::iterator iter;public:typedef _Container container_type;typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;insert_iterator(_Container& __x): container(&__x) {}insert_iterator(_Container& __x, typename _Container::iterator): container(&__x) {}insert_iterator<_Container>&operator=(const typename _Container::value_type& __value){container->insert(__value);return *this;}insert_iterator<_Container>&operator*(){ return *this; }insert_iterator<_Container>&operator++(){ return *this; }insert_iterator<_Container>&operator++(int) { return *this; }};} // namespace std#ifdef _GLIBCXX_DEBUG# include <debug/hash_set>#endif#endif