/*

 *  Dictionary.cpp

 *  Ottoman

 *

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

 *  Copyright 2009 Jens Alfke. All rights reserved.

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

 */

#include "Dictionary.h"

#include "Hash.h"

#include <assert.h>

#include <algorithm>

#include <math.h>

namespace Mooseyard {

    Dictionary::Dictionary() {

    }

    Dictionary::~Dictionary() {

    }

    Dictionary::Iterator::~Iterator() {

    }

    const int Dictionary::kMinSize = 8;

    const float Dictionary::kMinLoadFactor = 0.25f;

    const float Dictionary::kMaxLoadFactor = 0.75f;

    // Choose the smallest power of two that's large enough to hold the given capacity

    // of entries with no greater than the given load (fraction full).

    int Dictionary::choosePowerOfTwoSize (int capacity, float load) {

        int idealSize = capacity / load;

        int size;

        for (size=kMinSize; size<idealSize; size *= 2)

            ;

        return size;

    }

    int Dictionary::chooseAnyOldSize (int capacity, float load) {

        return std::max((int)::ceil(capacity / load), 2);

    }

    //-----------------------------------------------------------------------------

    // MurmurHashNeutral2, by Austin Appleby

    // http://murmurhash.googlepages.com/MurmurHashNeutral2.cpp

    // Same as MurmurHash2, but endian- and alignment-neutral.

    // Half the speed though, alas.

    static uint32_t MurmurHashNeutral2 ( const void * key, int32_t len, uint32_t seed )

    {

        static const uint32_t m = 0x5bd1e995;

        static const int32_t r = 24;

        uint32_t h = seed ^ len;

        const unsigned char * data = (const unsigned char *)key;

        while(len >= 4)

        {

            uint32_t k;

            k  = data[0];

            k |= data[1] << 8;

            k |= data[2] << 16;

            k |= data[3] << 24;

            k *= m; 

            k ^= k >> r; 

            k *= m;

            h *= m;

            h ^= k;

            data += 4;

            len -= 4;

        }

        switch(len)

        {

            case 3: h ^= data[2] << 16;

            case 2: h ^= data[1] << 8;

            case 1: h ^= data[0];

                h *= m;

        };

        h ^= h >> 13;

        h *= m;

        h ^= h >> 15;

        return h;

    } 

    HashCode Key::computeHash (Blob key) {

        return MurmurHashNeutral2(key.bytes, key.length, 0);

    }

    void MutableDictionary::add (Dictionary* dict) {

        Iterator *it = dict->iterate();

        for (; *it; it->next())

            put(it->key(), it->value());

        delete it;

    }

    const Dictionary& Dictionary::kEmpty = * new HashDictionary();

#pragma mark -

#pragma mark KEY AND VALUE

    class KeyAndValue {

    public:

        static KeyAndValue* create (Blob key, Blob value) {

            size_t size = 2*sizeof(uint32_t) + key.length;

            size = (size + 0x3) & ~0x3; // 32-bit align start of value

            if (value!=kDeletedValue)

                size += value.length;

            KeyAndValue *kv = (KeyAndValue*) ::operator new(size);

            kv->_keyLength = key.length;

            memcpy(&kv->_keyLength + 1, key.bytes, key.length);

            uint32_t *valueLengthPtr = const_cast<uint32_t*>(kv->valueLengthPtr());

            *valueLengthPtr = value.length;

            if (value!=kDeletedValue)

                memcpy(valueLengthPtr + 1, value.bytes, value.length);

            return kv;

        }

        Blob key() const {

            return Blob(&_keyLength+1, _keyLength);

        }

        Blob value() const{

            const uint32_t *v = this->valueLengthPtr();

            if (*v != kDeletedValue.length)

                return Blob(v+1, *v);

            else

                return kDeletedValue;

        }

        /** Magic value OverlayDictionary stores in me to represent a deleted value. */

        static const Blob kDeletedValue;

    private:

        const uint32_t* valueLengthPtr() const {

            size_t ptr = (size_t)(&_keyLength + 1) + _keyLength;

            ptr = (ptr + 0x3) & ~0x3;       // 32-bit align

            return (uint32_t*)ptr;

        }

        uint32_t _keyLength;

        //...there follows the key, valueLength and value...

    };

    const Blob KeyAndValue::kDeletedValue(NULL, (size_t)-1);

#pragma mark -

#pragma mark HASH DICTIONARY:

    HashDictionary::~HashDictionary() {

        removeAll();

    }

    Blob HashDictionary::_convertValue (void *value) {

        return value ?((KeyAndValue*)value)->value() :Blob();

    }

    bool HashDictionary::contains (Key key) const {

        Blob value = get(key);

        return value.bytes || value.length;

    }

    void HashDictionary::put (Key key, Blob value) {

        // Allocate a block to store both the Blob struct and the data

        KeyAndValue *kv = KeyAndValue::create(key,value);

        _hash.put(Key(kv->key(),key.hash), kv);

    }

    bool HashDictionary::remove (Key key) {

        KeyAndValue *kv = (KeyAndValue*) _hash.remove(key);

        if (kv) {

            delete kv;

            return true;

        } else

            return false;

    }

    void HashDictionary::removeAll() {

        for (Hash::Iterator it(&_hash); it; ++it)

            delete (KeyAndValue*) it.value();

        _hash.removeAll();

    }

#pragma mark -

#pragma mark OVERLAY DICTIONARY:

    OverlayDictionary::OverlayDictionary (const Dictionary *base)

    :_base(base),

     _overlay(new HashDictionary()),

     _count(base->count()),

     _allRemoved(false)

    { }

    OverlayDictionary::~OverlayDictionary() {

        delete _overlay;

    }

    int OverlayDictionary::count() const {

        return _count;

    }

    bool OverlayDictionary::isChanged() const {

        return _overlay->count() > 0;

    }

    Blob OverlayDictionary::get (Key key) const {

        Blob result = _overlay->get(key);

        if (!result) {

            if (result==KeyAndValue::kDeletedValue)

                result = Blob();                // It's been marked as deleted

            else if (!_allRemoved)

                result = _base->get(key);

        }

        return result;

    }

    bool OverlayDictionary::contains (Key key) const {

        Blob result = _overlay->get(key);

        if (result)

            return true;

        else if (result==KeyAndValue::kDeletedValue)

            return false;

        else if (!_allRemoved)

            return _base->get(key);

        else 

            return false;

    }

    void OverlayDictionary::put (Key key, Blob value) {

        assert(value.bytes || value.length==0);    // make sure it doesn't look like magic kDeletedValue

        _overlay->put(key,value);

        if (_allRemoved || !_base->contains(key))

            _count++;

    }

    bool OverlayDictionary::remove (Key key) {

        if (!_allRemoved && _base->contains(key)) {

            _overlay->put(key,KeyAndValue::kDeletedValue);

            _count--;

            return true;

        } else if (_overlay->remove(key)) {

            _count--;

            return true;

        } else

            return false;

    }

    void OverlayDictionary::removeAll() {

        _allRemoved = true;

        _count = 0;

    }

    void OverlayDictionary::revert() {

        _overlay->removeAll();

        _count = _base->count();

        _allRemoved = false;

    }

    void OverlayDictionary::revertTo (const Dictionary* newBase) {

        _base = newBase;

        revert();

    }

    void OverlayDictionary::rebase (const Dictionary* newBase) {

        _base = newBase;

    }

    OverlayDictionary::Iterator::Iterator (const OverlayDictionary &dict)

        :_iter(dict.base()->iterate()),

         _overlay(dict._overlay)

    {

        if (skipCurrentState())

            next();

    }

    Key OverlayDictionary::Iterator::key() const        {return _iter ?_iter->key() :Key();}

    Blob OverlayDictionary::Iterator::value() const     {return _iter ?_iter->value() :Blob();}

    bool OverlayDictionary::Iterator::next() {

        if (_iter) {

            do {

                _iter->next();

            } while (skipCurrentState());

        }

        return _iter && *_iter;

    }

    bool OverlayDictionary::Iterator::skipCurrentState() {

        if (_iter) {

            if (*_iter) {

                if (_overlay) {

                    if (_overlay->contains(_iter->key()))

                        return true;        // Skip overridden value in base dict

                } else {

                    if (_iter->value() == KeyAndValue::kDeletedValue)

                        return true;        // Skip marked-deleted value in overlay dict

                }

            } else {

                delete _iter;

                if (_overlay) {

                    // end of base iterator; switch to overlay

                    _iter = _overlay->iterate();

                    _overlay = NULL;

                    return skipCurrentState();

                } else {

                    _iter = NULL;

                }

            }

        }

        return false;

    }

#pragma mark -

#pragma mark CHANGE ITERATOR:

    Dictionary::ChangeIterator::ChangeIterator (const Dictionary *dict1, const Dictionary *dict2) {

        _init(dict1, dict2);

    }

    Dictionary::ChangeIterator::ChangeIterator (const OverlayDictionary *overlay) {

        _init(overlay->_overlay, overlay->base());

    }

    void Dictionary::ChangeIterator::_init(const Dictionary *dict1, const Dictionary *dict2) {

        _dict2 = dict2;

        _iter = dict1->iterate();

        if (*_iter)

            _skipMatching();

    }

    Dictionary::ChangeIterator::~ChangeIterator() {

        delete _iter;

    }

    bool Dictionary::ChangeIterator::next() {

        return _iter->next() && this->_skipMatching();

    }

    bool Dictionary::ChangeIterator::_skipMatching() {

        do{

            _otherValue = _dict2->get(_iter->key());

            if (!_otherValue.equals(_iter->value()))

                return true;

        }while (_iter->next());

        return false;

    }

}