/*

 *  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 <stdio.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();}

}