/*

  *  Hash.cpp

  *  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.

  */

 #include "Hash.h"

 #include "Dictionary.h"

 #include <algorithm>

 namespace Mooseyard {

     class Hash::IndexEntry {

     public:

         IndexEntry (Key key, Hash::Value value =NULL)

             :_key(key), 

              _value(value) 

         { }

         const Key& key() const                      {return _key;}

         HashCode hash() const                       {return _key.hash;}

         Hash::Value value() const                   {return _key.bytes ?_value :NULL;}

         void setValue (Hash::Value value)           {_value = value;}

         bool isAvailable() const                    {return _value == NULL;}    // false if deleted

         bool hasValue() const                       {return _key.bytes != NULL;}// false if deleted

         bool operator==(const IndexEntry &e) const  {return _key.hash==e._key.hash && _key.equals(e._key);}

         bool operator!=(const IndexEntry &e) const  {return ! (*this==e);}

         void markDeleted()                          {_key.bytes = NULL; _value = (Hash::Value)-1;}

         void markEmpty()                            {_key.bytes = NULL; _value = NULL;}

     private:

         Key _key;                       // bytes will be NULL if empty or deleted

         Hash::Value _value;             // NULL if empty, -1 if deleted

     };

     Hash::Hash (int capacity)

         :_count(0),

          _tableSize( Dictionary::choosePowerOfTwoSize(capacity) ),

          _table( (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry)) )

     { }

     Hash::~Hash() {

         free(_table);

     }

     Hash::IndexEntry& Hash::_find (Key key) const {

         IndexEntry newEntry(key);

         int index = newEntry.hash() % _tableSize;

         IndexEntry *found = &_table[index];

         int probe = 0;

         while (!found->isAvailable() && (!found->hasValue() || *found != newEntry)) {

             index = (index + ++probe) % _tableSize;

             found = &_table[index];

         }

         return *found;

     }

     Hash::IndexEntry& Hash::_findForPut (const Hash::IndexEntry &newEntry) {

         int index = newEntry.hash() % _tableSize;

         IndexEntry *found = &_table[index];

         int probe = 0;

         while (found->hasValue() && *found != newEntry) {

             index = (index + ++probe) % _tableSize;

             found = &_table[index];

         }

         return *found;

     }

     Hash::Value Hash::get(Key key) const {

         return _find(key).value();

     }

     void Hash::put(Key key, Hash::Value value) {

         IndexEntry newEntry = IndexEntry(key,value);

         IndexEntry &found = _findForPut(newEntry);

         if (found.hasValue())

             found.setValue(value);

         else {

             found = newEntry;

             _count++;

             if (_count/(float)_tableSize > Dictionary::kMaxLoadFactor)

                 _resize(2*_tableSize);

         }

     }

     Hash::Value Hash::remove(Key key) {

         IndexEntry &entry = _find(key);

         Value formerValue = entry.value();

         if (!formerValue)

             return NULL;

         entry.markDeleted();

         _count--;

         if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)

             _resize(_tableSize/2);

         return formerValue;

     }

     void Hash::removeAll() {

         memset(_table, 0, _tableSize*sizeof(*_table));

         _count = 0;

     }

     void Hash::dump() const {

         for (int index=0; index<_tableSize; index++)

             if (_table[index].hasValue()) {

                 const Key &key = _table[index].key();

                 printf("%3i: %*s -> %p\n", 

                        index, (int)key.length,(const char*)key.bytes, _table[index].value());

             }

     }

     void Hash::_resize(int newSize) {

         newSize = std::max(newSize, Dictionary::kMinSize);

         if (newSize != _tableSize) {

             IndexEntry* oldTable = _table;

             int oldTableSize = _tableSize;

             _tableSize = newSize;

             _table = (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry));

             // Add existing entries to new table:

             for (int index=0; index<oldTableSize; index++) {

                 IndexEntry &entry = oldTable[index];

                 if (entry.value())

                     _findForPut(entry) = entry;

             }

             free(oldTable);

         }

     }

     Hash::Iterator::Iterator (const Hash *hash)

         :_entry(hash->_table-1), _end(hash->_table+hash->_tableSize)

     {

         next();

     }

     Hash::Iterator::Iterator (const Hash &hash)

         :_entry(hash._table-1), _end(hash._table+hash._tableSize)

     {

         next();

     }

     bool Hash::Iterator::next() {

         while (++_entry < _end) {

             if (_entry->hasValue())

                 return true;

         }

         return false;

     }

     Key Hash::Iterator::key() const                 {return _entry->key();}

     Hash::Value Hash::Iterator::value() const       {return _entry->value();}

 }