• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.10.4 API Reference
  • KDE Home
  • Contact Us
 

WTF

  • kjs
  • wtf
HashSet.h
Go to the documentation of this file.
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB. If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21 
22 #ifndef WTF_HashSet_h
23 #define WTF_HashSet_h
24 
25 #include "HashTable.h"
26 
27 namespace WTF {
28 
29  template<typename Value, typename HashFunctions, typename Traits> class HashSet;
30  template<typename Value, typename HashFunctions, typename Traits>
31  void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
32 
33  template<typename T> struct IdentityExtractor;
34 
35  template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
36  typename TraitsArg = HashTraits<ValueArg> > class HashSet {
37  private:
38  typedef HashArg HashFunctions;
39  typedef TraitsArg ValueTraits;
40 
41  public:
42  typedef typename ValueTraits::TraitType ValueType;
43 
44  private:
45  typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
46  HashFunctions, ValueTraits, ValueTraits> HashTableType;
47 
48  public:
49  typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
50  typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
51 
52  void swap(HashSet&);
53 
54  int size() const;
55  int capacity() const;
56  bool isEmpty() const;
57 
58  iterator begin();
59  iterator end();
60  const_iterator begin() const;
61  const_iterator end() const;
62 
63  iterator find(const ValueType&);
64  const_iterator find(const ValueType&) const;
65  bool contains(const ValueType&) const;
66 
67  // An alternate version of find() that finds the object by hashing and comparing
68  // with some other type, to avoid the cost of type conversion. HashTranslator
69  // must have the following function members:
70  // static unsigned hash(const T&);
71  // static bool equal(const ValueType&, const T&);
72  template<typename T, typename HashTranslator> iterator find(const T&);
73  template<typename T, typename HashTranslator> const_iterator find(const T&) const;
74  template<typename T, typename HashTranslator> bool contains(const T&) const;
75 
76  // The return value is a pair of an interator to the new value's location,
77  // and a bool that is true if an new entry was added.
78  pair<iterator, bool> add(const ValueType&);
79 
80  // An alternate version of add() that finds the object by hashing and comparing
81  // with some other type, to avoid the cost of type conversion if the object is already
82  // in the table. HashTranslator must have the following methods:
83  // static unsigned hash(const T&);
84  // static bool equal(const ValueType&, const T&);
85  // static translate(ValueType&, const T&, unsigned hashCode);
86  template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
87 
88  void remove(const ValueType&);
89  void remove(iterator);
90  void clear();
91 
92  private:
93  friend void deleteAllValues<>(const HashSet&);
94 
95  HashTableType m_impl;
96  };
97 
98  template<typename T> struct IdentityExtractor {
99  static const T& extract(const T& t) { return t; }
100  };
101 
102  template<typename ValueType, typename ValueTraits, typename T, typename Translator>
103  struct HashSetTranslatorAdapter {
104  static unsigned hash(const T& key) { return Translator::hash(key); }
105  static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
106  static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
107  {
108  Translator::translate(location, key, hashCode);
109  }
110  };
111 
112  template<typename T, typename U, typename V>
113  inline void HashSet<T, U, V>::swap(HashSet& other)
114  {
115  m_impl.swap(other.m_impl);
116  }
117 
118  template<typename T, typename U, typename V>
119  inline int HashSet<T, U, V>::size() const
120  {
121  return m_impl.size();
122  }
123 
124  template<typename T, typename U, typename V>
125  inline int HashSet<T, U, V>::capacity() const
126  {
127  return m_impl.capacity();
128  }
129 
130  template<typename T, typename U, typename V>
131  inline bool HashSet<T, U, V>::isEmpty() const
132  {
133  return m_impl.isEmpty();
134  }
135 
136  template<typename T, typename U, typename V>
137  inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
138  {
139  return m_impl.begin();
140  }
141 
142  template<typename T, typename U, typename V>
143  inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
144  {
145  return m_impl.end();
146  }
147 
148  template<typename T, typename U, typename V>
149  inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
150  {
151  return m_impl.begin();
152  }
153 
154  template<typename T, typename U, typename V>
155  inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
156  {
157  return m_impl.end();
158  }
159 
160  template<typename T, typename U, typename V>
161  inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
162  {
163  return m_impl.find(value);
164  }
165 
166  template<typename T, typename U, typename V>
167  inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
168  {
169  return m_impl.find(value);
170  }
171 
172  template<typename T, typename U, typename V>
173  inline bool HashSet<T, U, V>::contains(const ValueType& value) const
174  {
175  return m_impl.contains(value);
176  }
177 
178  template<typename Value, typename HashFunctions, typename Traits>
179  template<typename T, typename Translator>
180  typename HashSet<Value, HashFunctions, Traits>::iterator
181  inline HashSet<Value, HashFunctions, Traits>::find(const T& value)
182  {
183  typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
184  return m_impl.template find<T, Adapter>(value);
185  }
186 
187  template<typename Value, typename HashFunctions, typename Traits>
188  template<typename T, typename Translator>
189  typename HashSet<Value, HashFunctions, Traits>::const_iterator
190  inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
191  {
192  typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
193  return m_impl.template find<T, Adapter>(value);
194  }
195 
196  template<typename Value, typename HashFunctions, typename Traits>
197  template<typename T, typename Translator>
198  inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
199  {
200  typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
201  return m_impl.template contains<T, Adapter>(value);
202  }
203 
204  template<typename T, typename U, typename V>
205  pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
206  {
207  return m_impl.add(value);
208  }
209 
210  template<typename Value, typename HashFunctions, typename Traits>
211  template<typename T, typename Translator>
212  pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
213  HashSet<Value, HashFunctions, Traits>::add(const T& value)
214  {
215  typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter;
216  return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
217  }
218 
219  template<typename T, typename U, typename V>
220  inline void HashSet<T, U, V>::remove(iterator it)
221  {
222  if (it.m_impl == m_impl.end())
223  return;
224  m_impl.checkTableConsistency();
225  m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
226  }
227 
228  template<typename T, typename U, typename V>
229  inline void HashSet<T, U, V>::remove(const ValueType& value)
230  {
231  remove(find(value));
232  }
233 
234  template<typename T, typename U, typename V>
235  inline void HashSet<T, U, V>::clear()
236  {
237  m_impl.clear();
238  }
239 
240  template<typename ValueType, typename HashTableType>
241  void deleteAllValues(HashTableType& collection)
242  {
243  typedef typename HashTableType::const_iterator iterator;
244  iterator end = collection.end();
245  for (iterator it = collection.begin(); it != end; ++it)
246  delete *it;
247  }
248 
249  template<typename T, typename U, typename V>
250  inline void deleteAllValues(const HashSet<T, U, V>& collection)
251  {
252  deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
253  }
254 
255  template<typename T, typename U, typename V, typename W>
256  inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
257  {
258  typedef typename HashSet<T, U, V>::const_iterator iterator;
259 
260  vector.resize(collection.size());
261 
262  iterator it = collection.begin();
263  iterator end = collection.end();
264  for (unsigned i = 0; it != end; ++it, ++i)
265  vector[i] = *it;
266  }
267 
268 } // namespace WTF
269 
270 using WTF::HashSet;
271 
272 #endif /* WTF_HashSet_h */
This file is part of the KDE documentation.
Documentation copyright © 1996-2013 The KDE developers.
Generated on Mon Jul 15 2013 05:10:10 by doxygen 1.8.3.1 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdelibs-4.10.4 API Reference

Skip menu "kdelibs-4.10.4 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal