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

  ViewVC Help
Powered by ViewVC 1.1.22