/[pcsx2_0.9.7]/trunk/common/include/Utilities/HashMap.h
ViewVC logotype

Annotation of /trunk/common/include/Utilities/HashMap.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 62 - (hide annotations) (download)
Tue Sep 7 11:08:22 2010 UTC (10 years, 2 months ago) by william
File MIME type: text/plain
File size: 25418 byte(s)
Auto Commited Import of: pcsx2-0.9.7-r3738-debug in ./trunk
1 william 62 /* PCSX2 - PS2 Emulator for PCs
2     * Copyright (C) 2002-2010 PCSX2 Dev Team
3     *
4     * PCSX2 is free software: you can redistribute it and/or modify it under the terms
5     * of the GNU Lesser General Public License as published by the Free Software Found-
6     * ation, either version 3 of the License, or (at your option) any later version.
7     *
8     * PCSX2 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
9     * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
10     * PURPOSE. See the GNU General Public License for more details.
11     *
12     * You should have received a copy of the GNU General Public License along with PCSX2.
13     * If not, see <http://www.gnu.org/licenses/>.
14     */
15    
16 william 31 #pragma once
17    
18     #include <google/type_traits.h>
19     #include <google/dense_hash_set>
20     #include <google/dense_hash_map>
21     #include <google/sparsehash/densehashtable.h>
22    
23 william 62 #include <wx/string.h>
24    
25 william 31 namespace HashTools {
26    
27     #define HashFriend(Key,T) friend class HashMap<Key,T>
28    
29     /// Defines an equality comparison unary method.
30     /// Generally intended for internal use only.
31     #define _EQUALS_UNARY_OP( Type ) bool operator()(const Type s1, const Type s2) const { return s1.Equals( s2 ); }
32    
33     /// Defines a hash code unary method
34     /// Generally intended for internal use only.
35     #define _HASHCODE_UNARY_OP( Type ) hash_key_t operator()( const Type& val ) const { return val.GetHashCode(); }
36    
37     /// <summary>
38     /// Defines an equality comparison method within an encapsulating struct, using the 'unary method' approach.
39     /// </summary>
40     /// <remarks>
41     /// <para>
42     /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
43     /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
44     /// the HashCode predicate and Compare predicate.
45     /// </para>
46     /// The code generated by this macro is equivalent to this:
47     /// <code>
48     /// // where 'Type' is the parameter used in the macro.
49     /// struct UnaryEquals
50     /// {
51     /// bool operator()(const Type s1, const Type s2) const
52     /// {
53     /// return s1.Equals( s2 ); // this operator must be implemented by the user.
54     /// }
55     /// };
56     /// </code>
57     /// Note:
58     /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
59     /// <c>operator ()</c>, such that the object instance itself acts as a method.
60     /// Note:
61     /// This methodology is similar to C# / .NET's <c>object.Equals()</c> method: The class member method
62     /// implementation of <c>Equals</c> should *not* throw exceptions -- it should instead return <c>false</c>
63     /// if either side of the comparison is not a matching type. See <see cref="IHashable" /> for details.
64     /// Note:
65     /// The reason for this (perhaps seemingly) hogwash red tape is because you can define custom
66     /// equality behavior for individual hashmaps, which are independent of the type used. The only
67     /// obvious scenario where such a feature is useful is in
68     /// </remarks>
69     /// <seealso cref="DEFINE_HASHCODE_UNARY"/>
70     /// <seealso cref="DEFINE_HASH_API"/>
71     /// <seealso cref="IHashable"/>
72     /// <seealso cref="HashMap"/>
73     #define DEFINE_EQUALS_UNARY( Type ) struct UnaryEquals{ _EQUALS_UNARY_OP( Type ) }
74    
75     /// <summary>
76     /// Defines a hash code predicate within an encapsulating struct; for use in hashable user datatypes
77     /// </summary>
78     /// <remarks>
79     /// <para>
80     /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
81     /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
82     /// the HashCode predicate and Compare predicate.
83     /// </para>
84     /// The code generated by this macro is equivalent to this:
85     /// <code>
86     /// // where 'Type' is the parameter used in the macro.
87     /// struct UnaryHashCode
88     /// {
89     /// hash_key_t operator()( const Type& val ) const
90     /// {
91     /// return val.GetHashCode(); // this member function must be implemented by the user.
92     /// }
93     /// };
94     /// </code>
95     /// </remarks>
96     /// <seealso cref="DEFINE_EQUALS_UNARY"/>
97     /// <seealso cref="DEFINE_HASH_API"/>
98     /// <seealso cref="IHashable"/>
99     /// <seealso cref="HashMap"/>
100     #define DEFINE_HASHCODE_UNARY( Type ) struct UnaryHashCode{ _HASHCODE_UNARY_OP( Type ) }
101    
102     /// <summary>
103     /// Defines the API for hashcode and comparison unary methods; for use in hashable user datatypes
104     /// </summary>
105     /// <remarks>
106     /// This macro creates APIs that allow the class or struct to be used as a key in a <see cref="HashMap"/>.
107     /// It requires that the data type implement the following items:
108     /// * An equality test via an <c>operator==</c> overload.
109     /// * A public instance member method <c>GetHashCode.</c>
110     /// The code generated by this macro is equivalent to this:
111     /// <code>
112     /// // where 'Type' is the parameter used in the macro.
113     /// struct UnaryHashCode
114     /// {
115     /// hash_key_t operator()( const Type& val ) const
116     /// {
117     /// return val.GetHashCode(); // this member function must be implemented by the user.
118     /// }
119     /// };
120     ///
121     /// struct UnaryEquals
122     /// {
123     /// bool operator()(const Type s1, const Type s2) const
124     /// {
125     /// return s1.Equals( s2 ); // this operator must be implemented by the user.
126     /// }
127     /// };
128     /// </code>
129     /// Note:
130     /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
131     /// <c>operator ()</c>, such that the object instance itself acts as a method.
132     /// Note:
133     /// For class types you can use the <see cref="IHashable"/> interface, which also allows you to group
134     /// multiple types of objects into a single complex HashMap.
135     /// Note:
136     /// Generally speaking, you do not use the <c>IHashable</c> interface on simple C-style structs, since it
137     /// would incur the overhead of a vtbl and could potentially break code that assumes the structs to have
138     /// 1-to-1 data-to-declaration coorlations.
139     /// Note:
140     /// Internally, using this macro is functionally equivalent to using both <see cref="DEFINE_HASHCODE_CLASS"/>
141     /// and <see cref="DEFINE_EQUALS_CLASS"/>.
142     /// </remarks>
143     /// <seealso cref="IHashable"/>
144     /// <seealso cref="DEFINE_HASHCODE_CLASS"/>
145     /// <seealso cref="DEFINE_COMPARE_CLASS"/>
146     /// <seealso cref="DEFINE_HASH_API"/>
147     /// <seealso cref="HashMap"/>
148     #define DEFINE_HASH_API( Type ) DEFINE_HASHCODE_UNARY( Type ); DEFINE_EQUALS_UNARY( Type );
149    
150     /// <summary>
151     /// A helper macro for creating custom types that can be used as <see cref="HashMap" /> keys.
152     /// </summary>
153     /// <remarks>
154     /// Use of this macro is only needed if the hashable type in question is a struct that is a private
155     /// local to the namespace of a containing class.
156     /// </remarks>
157     #define PRIVATE_HASHMAP( Key, T ) \
158     typedef SpecializedHashMap<Key, T> Key##HashMap; \
159     friend Key##HashMap;
160    
161     /// <summary>
162     /// Type that represents a hashcode; returned by all hash functions.
163     /// </summary>
164     /// <remarks>
165     /// In theory this could be changed to a 64 bit value in the future, although many of the hash algorithms
166     /// would have to be changed to take advantage of the larger data type.
167     /// </remarks>
168     typedef u32 hash_key_t;
169    
170     hash_key_t Hash(const char* data, int len);
171    
172     struct CommonHashClass;
173     extern const CommonHashClass GetCommonHash;
174    
175     /// <summary>
176     /// A unary-style set of methods for getting the hash code of C++ fundamental types.
177     /// </summary>
178     /// <remarks>
179     /// This class is used to pass hash functions into the <see cref="HashMap"/> class and
180     /// it's siblings. It houses methods for most of the fundamental types of C++ and the STL,
181     /// such as all int and float types, and also <c>std::string</c>. All functions can be
182     /// accessed via the () overload on an instance of the class, such as:
183     /// <code>
184     /// const CommonHashClass GetHash;
185     /// int v = 27;
186     /// std::string s = "Joe's World!";
187     /// hash_key_t hashV = GetHash( v );
188     /// hash_key_t hashS = GetHash( s );
189     /// </code>
190     /// Note:
191     /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
192     /// <c>operator ()</c>, such that the object instance itself acts as a method.
193     /// </remarks>
194     /// <seealso cref="GetCommonHash"/>
195     struct CommonHashClass
196     {
197     public:
198     // GCC needs empty constructors on const instances, because it likes pointlessness.
199     CommonHashClass() {}
200    
201     hash_key_t DoInt( u32 val ) const
202     {
203     u32 key = val;
204     key = ~key + (key << 15);
205     key = key ^ (key >> 12);
206     key = key + (key << 2);
207     key = key ^ (key >> 4);
208     key = key * 2057;
209     key = key ^ (key >> 16);
210    
211     return val;
212     }
213    
214     hash_key_t operator()(const std::string& src) const
215     {
216     return Hash( src.data(), src.length() );
217     }
218    
219     hash_key_t operator()( const std::wstring& src ) const
220     {
221     return Hash( (const char *)src.data(), src.length() * sizeof( wchar_t ) );
222     }
223    
224 william 62 hash_key_t operator()( const wxString& src ) const
225     {
226     return Hash( (const char *)src.data(), src.length() * sizeof( wxChar ) );
227     }
228    
229 william 31 // Returns a hashcode for a character.
230     // This has function has been optimized to return an even distribution
231     // across the range of an int value. In theory that should be more rewarding
232     // to hastable performance than a straight up char lookup.
233     hash_key_t operator()( const char c1 ) const
234     {
235     // Most chars contain values between 0 and 128, so let's mix it up a bit:
236     int cs = (int)( c1 + (char)64 );
237     return ( cs + ( cs<<8 ) + ( cs << 16 ) + (cs << 24 ) );
238     }
239    
240     hash_key_t operator()( const wchar_t wc1 ) const
241     {
242     // Most unicode values are between 0 and 128, with 0-1024
243     // making up the bulk of the rest. Everything else is spatially used.
244     /*int wcs = (int) ( wc1 + 0x2000 );
245     return wcs ^ ( wcs + 0x19000 );*/
246    
247     // or maybe I'll just feed it into the int hash:
248     return GetCommonHash( (u32)wc1 );
249     }
250    
251     /// <summary>
252     /// Gets the hash code for a 32 bit integer.
253     /// </summary>
254     /// <remarks>
255     /// This method performs a very fast algorithm optimized for typical integral
256     /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
257     /// leaving the extremes un-used).
258     /// Note:
259     /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
260     /// </remarks>
261     hash_key_t operator()( const u32 val ) const
262     {
263     return DoInt(val);
264     }
265    
266     /// <summary>
267     /// Gets the hash code for a 32 bit integer.
268     /// </summary>
269     /// <remarks>
270     /// This method performs a very fast algorithm optimized for typical integral
271     /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
272     /// leaving the extremes un-used).
273     /// Note:
274     /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
275     /// </remarks>
276     hash_key_t operator()( const s32 val ) const
277     {
278     return DoInt(val);
279     }
280    
281     /// <summary>
282     /// Gets the hash code for a 64 bit integer.
283     /// </summary>
284     /// <remarks>
285     /// This method performs a very fast algorithm optimized for typical integral
286     /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
287     /// leaving the extremes un-used).
288     /// Note:
289     /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
290     /// </remarks>
291     hash_key_t operator()( const u64 val ) const
292     {
293     u64 key = val;
294     key = (~key) + (key << 18);
295     key = key ^ (key >> 31);
296     key = key * 21; // key = (key + (key << 2)) + (key << 4);
297     key = key ^ (key >> 11);
298     key = key + (key << 6);
299     key = key ^ (key >> 22);
300     return (u32) key;
301     }
302    
303     /// <summary>
304     /// Gets the hash code for a 64 bit integer.
305     /// </summary>
306     /// <remarks>
307     /// This method performs a very fast algorithm optimized for typical integral
308     /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
309     /// leaving the extremes un-used).
310     /// Note:
311     /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
312     /// </remarks>
313     hash_key_t operator()( const s64 val ) const
314     {
315     return GetCommonHash((u64)val);
316     }
317    
318     hash_key_t operator()( const float val ) const
319     {
320     // floats do a fine enough job of being scattered about
321     // the universe:
322     return *((hash_key_t *)&val);
323     }
324    
325     hash_key_t operator()( const double val ) const
326     {
327     // doubles have to be compressed into a 32 bit value:
328     return GetCommonHash( *((u64*)&val) );
329     }
330    
331     /// <summary>
332     /// Calculates the hash of a pointer.
333     /// </summary>
334     /// <remarks>
335     /// This method has been optimized to give typical 32 bit pointers a reasonably
336     /// wide spread across the integer spectrum.
337     /// Note:
338     /// This method is optimized for 32 bit pointers only. 64 bit pointer support
339     /// has not been implemented, and thus on 64 bit platforms performance could be poor or,
340     /// worse yet, results may not have a high degree of uniqueness.
341     /// </remarks>
342     hash_key_t operator()( const void* addr ) const
343     {
344     hash_key_t key = (hash_key_t) addr;
345     return (hash_key_t)((key >> 3) * 2654435761ul);
346     }
347 william 62
348    
349 william 31 };
350    
351     /// <summary>
352     /// This class contains comparison methods for most fundamental types; and is used by the CommonHashMap class.
353     /// </summary>
354     /// <remarks>
355     /// The predicates of this class do standard equality comparisons between fundamental C/STL types such as
356     /// <c>int, float</c>, and <c>std::string.</c> Usefulness of this class outside the <see cref="CommonHashMap"/>
357     /// class is limited.
358     /// </remarks>
359     /// <seealso cref="CommonHashMap">
360     struct CommonComparisonClass
361     {
362     bool operator()(const char* s1, const char* s2) const
363     {
364     return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
365     }
366     };
367    
368     /// <summary>
369     /// An interface for classes that implement hashmap functionality.
370     /// </summary>
371     /// <remarks>
372     /// This class provides interface methods for getting th hashcode of a class and checking for object
373     /// equality. It's general intent is for use in situations where you have to store *non-similar objects*
374     /// in a single unified hash map. As all object instances derive from this type, it allows the equality
375     /// comparison to use typeid or dynamic casting to check for type similarity, and then use more detailed
376     /// equality checks for similar types.
377     /// </remarks>
378     class IHashable
379     {
380     public:
381     /// Obligatory Virtual destructor mess!
382     virtual ~IHashable() {};
383    
384     /// <summary>
385     /// Your basic no-thrills equality comparison; using a pointer comparison by default.
386     /// </summary>
387     /// <remarks>
388     /// This method uses a pointer comparison by default, which is the only way to really compare objects
389     /// of unrelated types or of derrived types. When implementing this method, you may want to use typeid comparisons
390     /// if you want derived types to register as being non-equal, or <c>dynamic_cast</c> for a more robust
391     /// base-class comparison (illustrated in the example below).
392     /// Note:
393     /// It's recommended important to always do a pointer comparison as the first step of any object equality check.
394     /// It is fast and easy, and 100% reliable.
395     /// </remarks>
396     /// <example>
397     /// Performing non-pointer comparisons:
398     /// <code>
399     /// class Hasher : IHashable
400     /// {
401     /// int someValue;
402     ///
403     /// virtual bool Equals( const IHashable& right ) const
404     /// {
405     /// // Use pointer comparison first since it's fast and accurate:
406     /// if( &right == this ) return true;
407     ///
408     /// Hasher* them = dynamic_cast&lt;Hasher*&gt;( right );
409     /// if( them == NULL ) return false;
410     /// return someValue == them->SomeValue;
411     /// }
412     /// }
413     /// </code>
414     /// </example>
415     virtual bool Equals( const IHashable& right ) const
416     {
417     return ( &right == this ); // pointer comparison.
418     }
419    
420     /// <summary>
421     /// Returns a hash value for this object; by default the hash of its pointer address.
422     /// </summary>
423     /// <remarks>
424     /// </remarks>
425     /// <seealso cref="HashMap"/>
426     virtual hash_key_t GetHashCode() const
427     {
428     return GetCommonHash( this );
429     }
430     };
431    
432     template< typename Key >
433     class HashSet : public google::dense_hash_set< Key, CommonHashClass >
434     {
435     public:
436     /// <summary>
437     /// Constructor.
438     /// </summary>
439     /// <remarks>
440     /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
441     /// are *not* used as actual values in the set.
442     /// </remarks>
443     HashSet( Key emptyKey, Key deletedKey, int initialCapacity=33 ) :
444     google::dense_hash_set<Key, CommonHashClass>( initialCapacity )
445     {
446     set_empty_key( emptyKey );
447     set_deleted_key( deletedKey );
448     }
449     };
450    
451     /// <summary>
452     /// Defines a hashed collection of objects and provides methods for adding, removing, and reading items.
453     /// </summary>
454     /// <remarks>
455     /// <para>This class is for hashing out a set data using objects as keys. Objects should derive from the
456     /// <see cref="IHashable"/> type, and in either case *must* implement the UnaryHashCode and UnaryEquals
457     /// unary classes.</para>
458     /// <para>*Details On Implementing Key Types*</para>
459     /// <para>
460     /// Custom hash keying uses what I consider a somewhat contrived method of implementing the Key type;
461     /// involving a handful of macros in the best case, and a great deal of syntaxical red tape in
462     /// the worst case. Most cases should fall within the realm of the macros, which make life a lot easier,
463     /// so that's the only implementation I will cover in detail here (see below for example).
464     /// </para>
465     /// Note:
466     /// For most hashs based on common or fundamental types or types that can be adequately compared using
467     /// the default equality operator ==, such as <c>int</c> or structs that have no padding alignment concerns,
468     /// use <see cref="HashMap" /> instead. For string-based hashs, use <see cref="Dictionary" /> or <see cref="UnicodeDictionary" />.
469     /// </remarks>
470     /// <example>
471     /// This is an example of making a hashable type out of a struct. This is useful in situations where
472     /// inheriting the <see cref="IHashable"/> type would cause unnecessary overhead and/or broken C/C++
473     /// compatability.
474     /// <code>
475     /// struct Point
476     /// {
477     /// int x, y;
478     ///
479     /// // Empty constructor is necessary for HashMap.
480     /// // This can either be initialized to zero, or uninitialized as here:
481     /// Point() {}
482     ///
483     /// // Copy Constructor is just always necessary.
484     /// Point( const Point& src ) : first( src.first ), second( src.second ) {}
485     ///
486     /// // Standard content constructor (Not needed by HashMap)
487     /// Point( int xpos, int ypos ) : x( xpos ), y( ypos ) {}
488     ///
489     /// /**** Begin Hashmap Interface Implementation ****/
490     ///
491     /// // HashMap Requires both GetEmptyKey() and GetDeleteKey() instance member
492     /// // methods to be defined. These act as defaults. The actual values used
493     /// // can be overridden on an individual HashMap basis via the HashMap constructor.
494     ///
495     /// static Point GetEmptyKey() { return Point( -0xffffff, 0xffffff ); }
496     /// static Point GetDeletedKey() { return Kerning( -0xffffee, 0xffffee ); }
497     ///
498     /// // HashMap Requires an Equality Overload.
499     /// // The inequality overload is not required but is probably a good idea since
500     /// // orphaned equality (without sibling inequality) operator overloads are ugly code.
501     ///
502     /// bool Equals( const Point& right ) const
503     /// {
504     /// return ( x == right.x ) && ( y == right.y );
505     /// }
506     ///
507     /// hash_key_t GetHashCode() const
508     /// {
509     /// // This is a decent "universal" hash method for when you have multiple int types:
510     /// return GetCommonHash( x ) ^ GetCommonHash( y );
511     /// }
512     ///
513     /// // Use a macro to expose the hash API to the HashMap templates.
514     /// // This macro creates MakeHashCode and Compare structs, which use the ()
515     /// // operator to create "unary methods" for the GetHashCode and == operator above.
516     /// // Feeling dizzy yet? Don't worry. Just follow this template. It works!
517     ///
518     /// DEFINE_HASH_API( Point );
519     ///
520     /// /**** End HashMap Interface Implementation ****/
521     /// };
522     /// </code>
523     /// </example>
524     template< class Key, class T >
525     class SpecializedHashMap : public google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>
526     {
527     public:
528     virtual ~SpecializedHashMap() {}
529     SpecializedHashMap( int initialCapacity=33, Key emptyKey=Key::GetEmptyKey(), Key deletedKey=Key::GetDeletedKey() ) :
530     google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>( initialCapacity )
531     {
532     set_empty_key( emptyKey );
533     set_deleted_key( deletedKey );
534     }
535    
536     /// <summary>
537     /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
538     /// </summary>
539     /// <remarks>
540     /// If found, the value associated with the requested key is copied into the <c>outval</c>
541     /// parameter. This is a more favorable alternative to the indexer operator since the
542     /// indexer implementation can and will create new entries for every request that
543     /// </remarks>
544     /*void TryGetValue( const Key& key, T& outval ) const
545     {
546     // GCC doesn't like this for some reason -- says const_iterator can't be found.
547     // Fortunately nothing uses these functions yet, so I just commented them out. --air
548     const_iterator iter = find( key );
549     if( iter != end() )
550     outval = iter->second;
551     }*/
552    
553     const T& GetValue( Key key ) const
554     {
555 william 62 return (find( key ))->second;
556 william 31 }
557     };
558    
559     /// <summary>
560     /// This class implements a hashmap that uses fundamental types such as <c>int</c> or <c>std::string</c>
561     /// as keys.
562     /// </summary>
563     /// <remarks>
564     /// This class is provided so that you don't have to jump through hoops in order to use fundamental types as
565     /// hash keys. The <see cref="HashMap" /> class isn't suited to the task since it requires the key type to
566     /// include a set of unary methods. Obviously predicates cannot be added to fundamentals after the fact. :)
567     /// Note:
568     /// Do not use <c>char *</c> or <c>wchar_t *</c> as key types. Use <c>std::string</c> and <c>std::wstring</c>
569     /// instead, as performance of those types will generally be superior due to string length caching. For that
570     /// matter, don't use this class at all! Use the string-specialized classes <see cref="Dictionary" /> and
571     /// <see cref="UnicodeDictionary" />.
572     /// </remarks>
573 william 62 template< class Key, class T, class HashFunctor=CommonHashClass >
574     class HashMap : public google::dense_hash_map<Key, T, HashFunctor>
575 william 31 {
576 william 62 DeclareNoncopyableObject( HashMap );
577 william 31
578 william 62 typedef typename google::dense_hash_map<Key, T, HashFunctor> _parent;
579    
580 william 31 public:
581     using _parent::operator[];
582     using _parent::end;
583     typedef typename _parent::const_iterator const_iterator;
584    
585     virtual ~HashMap() {}
586    
587     /// <summary>
588     /// Constructor.
589     /// </summary>
590     /// <remarks>
591     /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
592     /// are *not* used as actual values in the set.
593     /// </remarks>
594     HashMap( const Key& emptyKey, const Key& deletedKey, int initialCapacity=33 ) :
595 william 62 google::dense_hash_map<Key, T, HashFunctor>( initialCapacity )
596 william 31 {
597     set_empty_key( emptyKey );
598     set_deleted_key( deletedKey );
599     }
600    
601     /// <summary>
602     /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
603     /// </summary>
604     /// <remarks>
605     /// If found, the value associated with the requested key is copied into the <c>outval</c>
606     /// parameter. This is a more favorable alternative to the indexer operator since the
607     /// indexer implementation can and will create new entries for every request that
608     /// </remarks>
609 william 62 bool TryGetValue( const Key& key, T& outval ) const
610 william 31 {
611     const_iterator iter( find(key) );
612     if( iter != end() )
613 william 62 {
614 william 31 outval = iter->second;
615 william 62 return true;
616     }
617     return false;
618 william 31 }
619    
620     const T& GetValue( Key key ) const
621     {
622 william 62 return (find( key ))->second;
623 william 31 }
624 william 62
625     bool Find( Key key ) const
626     {
627     return find(key) != end();
628     }
629 william 31 };
630    
631     /// <summary>
632     /// A shortcut class for easy implementation of string-based hash maps.
633     /// </summary>
634     /// <remarks>
635     /// Note:
636     /// This class does not support Unicode character sets natively. To use Unicode strings as keys,
637     /// use <see cref="UnicodeDictionary"/> instead.
638     /// </remarks>
639     template< class T >
640     class Dictionary : public HashMap<std::string, T>
641     {
642     public:
643     virtual ~Dictionary() {}
644    
645 william 62 Dictionary( int initialCapacity=33, const std::string& emptyKey = "@@-EMPTY-@@", const std::string& deletedKey = "@@-DELETED-@@" )
646     : HashMap<std::string, T>( emptyKey, deletedKey, initialCapacity)
647 william 31 {
648     }
649     };
650    
651     /// <summary>
652     /// A shortcut class for easy implementation of string-based hash maps.
653     /// </summary>
654     /// <remarks>
655     /// Note:
656     /// This class does incur some amount of additional overhead over <see cref="Dictionary"/>, as it
657     /// requires twice as much memory and much hash twice as much data.
658     /// If you're only using the hash for friendly named array access (via string constants)
659     /// then you should probably just stick to using the regular dictionary.
660     /// </remarks>
661     template< class T >
662     class UnicodeDictionary : public HashMap<std::wstring, T>
663     {
664     public:
665     virtual ~UnicodeDictionary() {}
666    
667 william 62 UnicodeDictionary( int initialCapacity=33, const std::wstring& emptyKey = L"@@-EMPTY-@@", const std::wstring& deletedKey = L"@@-DELETED-@@" )
668     : HashMap<std::wstring, T>( emptyKey, deletedKey, initialCapacity)
669 william 31 {
670     }
671     };
672    
673     }
674 william 62
675     template< class T, class HashFunctor=HashTools::CommonHashClass >
676     class pxDictionary : public HashTools::HashMap<wxString, T, HashFunctor>
677     {
678     public:
679     virtual ~pxDictionary() {}
680    
681     pxDictionary( int initialCapacity=33, const wxString& emptyKey = L"@@-EMPTY-@@", const wxString& deletedKey = L"@@-DELETED-@@" )
682     : HashTools::HashMap<wxString, T, HashFunctor>( emptyKey, deletedKey, initialCapacity)
683     {
684     }
685     };

  ViewVC Help
Powered by ViewVC 1.1.22