/*

  *  Hash.h

  *  Ottoman

  *

  *  Created by Jens Alfke on 8/20/09.

  *  Copyright 2009 Jens Alfke. All rights reserved.

  *  BSD-Licensed: See the file "LICENSE.txt" for details.

  */

 #ifndef _MOOSEYARD_HASH_

 #define _MOOSEYARD_HASH_

 #include "Base.h"

 #include "Dictionary.h"

 namespace Mooseyard {

     /** A fairly low-level hash-table class whose keys and values are arbitrary data blobs.

         This class does no memory management of the keys and values: the memory ranges

         pointed to by the key and value parameters to put() must remain valid as long as

         that key or value remains in the hash-table. */

     class Hash {

     public:

         typedef void* Value;

         /** Creates a new, empty Hash. */

         explicit Hash (int capacity = 50);

         ~Hash();

         /** Gets the value associated with the given key. */

         Value get(Key) const;

         Value operator[] (Key key) const                        {return get(key);}

         /** Returns the number of values in the Hash. */

         int count() const                                       {return _count;}

         /** Sets the given value for the given key, replacing any existing value. */

         void put(Key, Value);

         /** Removes the value with the given key. */

         bool remove(Key);

         /** Removes all values. */

         void removeAll();

         void dump() const;

         class IndexEntry;

         class Iterator {

         public:

             Iterator (const Hash *h);

             Iterator (const Hash &h);

             operator bool() const                           {return hasValue();}

             Value operator*() const                         {return value();}

             Iterator& operator++()                          {next(); return *this;}

             Key key() const;

             Value value() const;

             bool hasValue() const                           {return _entry < _end;}

             bool next();

         private:

             Iterator (IndexEntry *start, IndexEntry*end);

             IndexEntry* _entry;

             IndexEntry* const _end;

             UNCOPYABLE(Iterator);

         };

     private:

         IndexEntry& _find (Key key) const;

         IndexEntry& _findForPut (const IndexEntry &newEntry);

         void _resize(int newSize);

         void _read();

         UNCOPYABLE(Hash);

         int _count;

         int _tableSize;

         IndexEntry *_table;

         friend class Iterator;

     };

     /** A concrete Dictionary implemented with a Hash. */

     class HashDictionary :public MutableDictionary {

     public:

         explicit HashDictionary (int capacity =50)  :_hash(capacity) { }

         virtual ~HashDictionary();

         virtual int count() const                   {return _hash.count();}

         virtual bool contains (Key) const;

         virtual Blob get (Key key) const            {return _convertValue(_hash.get(key));}

         virtual void put (Key, Blob value);

         virtual bool remove (Key);

         virtual void removeAll();

         virtual Iterator* iterate() const           {return new Iterator(*this);}

         class Iterator :public Dictionary::Iterator {

         public:

             explicit Iterator (const HashDictionary &d)      :_it(d._hash) { }

             virtual Key key() const                 {return _it.key();}

             virtual Blob value() const              {return _convertValue(_it.value());}

             virtual bool hasValue() const           {return _it.hasValue();}

             virtual bool next()                     {return _it.next();}

         private:

             Hash::Iterator _it;

         };

     private:

         static Blob _convertValue (void*);

         Hash _hash;

         friend class Iterator;

     };

 }

 #endif _MOOSEYARD_HASH_