hashedstring.h

/***************************************************************************
   copyright            : (C) 2006 by David Nolden
   email                : david.nolden.kdevelop@art-master.de
***************************************************************************/
 
/***************************************************************************
 *                                                                         *
 *   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<tqstring.h>
#include<tqdatastream.h>
#include<ksharedptr.h>
#include<set>
#include <ext/hash_map>
#include <string>

class HashedString {
  public:
    HashedString() : m_hash( 0 ) {}
 
    HashedString( const TQString& str ) : m_str( str ) {
      initHash();
    }
    
    HashedString( const char* str ) : m_str( str ) {
      initHash();
    }
 
    inline size_t hash() const {
      return m_hash;
    }
 
    TQString 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;
    }

    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 TQString& str );
 
  private:
    void initHash();
 
    TQString m_str;
    size_t m_hash;
 
    friend TQDataStream& operator << ( TQDataStream& stream, const HashedString& str );
    friend TQDataStream& operator >> ( TQDataStream& stream, HashedString& str );
};
 
TQDataStream& operator << ( TQDataStream& stream, const HashedString& str );
 
TQDataStream& operator >> ( TQDataStream& stream, HashedString& str );
 
class HashedStringSetData;
class HashedStringSetGroup;

class HashedStringSet {
  public:
    HashedStringSet();
 
    ~HashedStringSet();

    HashedStringSet( const HashedString& file );
 
    HashedStringSet( const HashedStringSet& rhs );
 
    int size() const;
 
    HashedStringSet& operator = ( const HashedStringSet& rhs );
    bool operator[] ( const HashedString& rhs ) const;
 
    void insert( const HashedString& str );
 
    HashedStringSet& operator +=( const HashedStringSet& );
    
    HashedStringSet& operator -=( const HashedStringSet& );

    bool operator <= ( const HashedStringSet& rhs ) const;
 
    bool operator == ( const HashedStringSet& rhs ) const;
 
    void read( TQDataStream& stream );
    void write( TQDataStream& stream ) const;
 
    std::string print() const;
 
  size_t hash() const;
  private:
    friend class HashedStringSetGroup;
    void makeDataPrivate();
    TDESharedPtr<HashedStringSetData> m_data; //this implies some additional cost because TDEShared's destructor is virtual. Maybe change that by copying TDEShared 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();
  }
};
}

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