/*

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

     const float Dictionary::kMaxLoadFactor = 0.75;

     // 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.get(key);

         if (kv) {

             free(kv);

             return true;

         } else

             return false;

     }

     void HashDictionary::removeAll() {

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

             free(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;

     }

 }