diff options
Diffstat (limited to 'lib/interfaces/hashedstring.h')
-rw-r--r-- | lib/interfaces/hashedstring.h | 155 |
1 files changed, 155 insertions, 0 deletions
diff --git a/lib/interfaces/hashedstring.h b/lib/interfaces/hashedstring.h new file mode 100644 index 00000000..e62ab2e3 --- /dev/null +++ b/lib/interfaces/hashedstring.h @@ -0,0 +1,155 @@ +/*************************************************************************** + copyright : (C) 2006 by David Nolden + email : [email protected] +***************************************************************************/ + +/*************************************************************************** + * * + * This program 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 of the License, or * + * (at your option) any later version. * + * * + ***************************************************************************/ + +#ifndef HASHED_STRING_H +#define HASHED_STRING_H + +#include<qstring.h> +#include<qdatastream.h> +#include<ksharedptr.h> +#include<set> +#include <ext/hash_map> +#include <string> + +///A simple class that stores a string together with it's appropriate hash-key +class HashedString { + public: + HashedString() : m_hash( 0 ) {} + + HashedString( const QString& str ) : m_str( str ) { + initHash(); + } + + HashedString( const char* str ) : m_str( str ) { + initHash(); + } + + inline size_t hash() const { + return m_hash; + } + + QString str() const { + return m_str; + } + + bool operator == ( const HashedString& rhs ) const { + if ( m_hash != rhs.m_hash ) + return false; + return m_str == rhs.m_str; + } + + ///Does not compare alphabetically, uses the hash-key for ordering. + bool operator < ( const HashedString& rhs ) const { + if ( m_hash < rhs.m_hash ) + return true; + if ( m_hash == rhs.m_hash ) + return m_str < rhs.m_str; + return false; + } + + static size_t hashString( const QString& str ); + + private: + void initHash(); + + QString m_str; + size_t m_hash; + + friend QDataStream& operator << ( QDataStream& stream, const HashedString& str ); + friend QDataStream& operator >> ( QDataStream& stream, HashedString& str ); +}; + +QDataStream& operator << ( QDataStream& stream, const HashedString& str ); + +QDataStream& operator >> ( QDataStream& stream, HashedString& str ); + +class HashedStringSetData; +class HashedStringSetGroup; + +///This is a reference-counting string-set optimized for fast lookup of hashed strings +class HashedStringSet { + public: + HashedStringSet(); + + ~HashedStringSet(); + + ///Constructs a string-set from one single file + HashedStringSet( const HashedString& file ); + + HashedStringSet( const HashedStringSet& rhs ); + + int size() const; + + HashedStringSet& operator = ( const HashedStringSet& rhs ); + ///@return whether the given file-name was included + bool operator[] ( const HashedString& rhs ) const; + + void insert( const HashedString& str ); + + HashedStringSet& operator +=( const HashedStringSet& ); + + HashedStringSet& operator -=( const HashedStringSet& ); + + ///intersection-test + ///Returns true if all files that are part of this set are also part of the given set + bool operator <= ( const HashedStringSet& rhs ) const; + + bool operator == ( const HashedStringSet& rhs ) const; + + void read( QDataStream& stream ); + void write( QDataStream& stream ) const; + + std::string print() const; + + size_t hash() const; + private: + friend class HashedStringSetGroup; + void makeDataPrivate(); + KSharedPtr<HashedStringSetData> m_data; //this implies some additional cost because KShared's destructor is virtual. Maybe change that by copying KShared without the virtual destructor. + friend HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs ); +}; + +HashedStringSet operator + ( const HashedStringSet& lhs, const HashedStringSet& rhs ); + +namespace __gnu_cxx { +template<> +struct hash<HashedString> { + size_t operator () ( const HashedString& str ) const { + return str.hash(); + } +}; +} + +///Used to find all registered HashedStringSet's that contain all strings given to findGroups(..) +class HashedStringSetGroup { + public: + typedef std::set<size_t> ItemSet; + void addSet( size_t id, const HashedStringSet& set ); + void enableSet( size_t id ); + bool isDisabled( size_t id ) const; + void disableSet( size_t id ); + void removeSet( size_t id ); + + //Writes the ids of all registered and not disabled HashedStringSet's that are completely included in the given HashedStringSet efficiently) + void findGroups( HashedStringSet strings, ItemSet& target ) const; + + private: + typedef __gnu_cxx::hash_map<HashedString, ItemSet> GroupMap; + typedef __gnu_cxx::hash_map<size_t, size_t> SizeMap; + GroupMap m_map; + SizeMap m_sizeMap; + ItemSet m_disabled; + ItemSet m_global; +}; +#endif |