/*

  *  Dictionary.h

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

  */

 #ifndef _MOOSEYARD_DICTIONARY_

 #define _MOOSEYARD_DICTIONARY_

 #include "Base.h"

 namespace Mooseyard {

     typedef uint32_t HashCode;

     /** A Key is a data blob treated as a dictionary key.

         It carries its hash-code around with it, to avoid redundant computation. */

     struct Key :public Blob {

         HashCode hash;

         Key ()                                          :Blob(), hash(0) { }

         explicit Key (const Blob &b)                    :Blob(b), hash(computeHash(b)) { }

         Key (const Blob &b, HashCode h)                 :Blob(b), hash(h) { }

         Key (const char *str)                           :Blob(str), hash(computeHash(*this)) { }

         Key (const void *bytes, uint32_t len)           :Blob(bytes,len), hash(computeHash(*this)) { }

         Key (const void *b, uint32_t len, HashCode h)   :Blob(b,len), hash(h) { }

         static HashCode computeHash (Blob);

     };

     /** An abstract interface for key/value dictionaries.

         Dictionary itself is read-only; its subclass MutableDictionary allows changes. */

     class Dictionary {

     public:

         class Iterator;

         class ChangeIterator;

         virtual ~Dictionary();

         /** The number of items in the dictionary. */

         virtual int count() const =0;

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

             Keys are compared by exact binary data equality.

             The data pointed to by the value returned is valid at least until the next call to

             this Dictionary; some subclasses may guarantee a longer lifetime.

             If there is no value for the given key, a Blob of {NULL, 0} will be returned. */

         virtual Blob get (Key) const =0;

         /** Returns true iff there is a value associated with the given key. */

         virtual bool contains (Key key) const      {return get(key).bytes != NULL;}

         /** Returns a pointer to a new Iterator object that can be used to iterate this Dictionary.

             The iterator must be deleted when you're done with it. */

         virtual Iterator* iterate() const =0;

         /** A singleton empty Dictionary. */

         static const Dictionary& kEmpty;

         // utilities

         /** Returns a suggested size for a hash table that can hold 'capacity' items without

             being more than the 'load' fraction full; result is always a power of two. */

         static int choosePowerOfTwoSize (int capacity, float load = kMaxLoadFactor);

         static int chooseAnyOldSize (int capacity, float load = kMaxLoadFactor);

         static const int   kMinSize;

         static const float kMinLoadFactor;

         static const float kMaxLoadFactor;

     protected:

         Dictionary();

     };

     /** An abstract interface for mutable key/value dictionaries; extends Dictionary. */

     class MutableDictionary : public Dictionary {

     public:

         /** Stores the given value for the given key, replacing any prior value.

             The memory for the key and value is copied, so you don't need to preserve it after

             the call returns. */

         virtual void put (Key, Blob value) =0;

         /** Adds the contents of the given Dictionary to this one.

             Effectively calls this->put() with every key/value pair in the source Dictionary. */

         virtual void add (Dictionary*);

         /** Removes the value for the given key, if any.

             Returns true if the value was removed, false if there was no value. */

         virtual bool remove (Key) =0;

         /** Removes all keys and values, returning the dictionary to an empty state. */

         virtual void removeAll() = 0;

     };

     /** Abstract iterator interface. Each Dictionary subclass defines its own.

         The order in which items are returned is undefined, and in effect quite random, due to

         the properties of hash tables. */

     class Dictionary::Iterator {

     public:

         virtual ~Iterator();

         /** The current key the iterator is pointing to. */

         virtual Key key() const =0;

         /** The current value the iterator is pointing to. */

         virtual Blob value() const =0;

         /** Returns true if the iterator has a current item, or false if it's reached the end. */

         virtual bool hasValue() const           {return key().bytes != 0;}

         /** Advances the Iterator to the next item. Returns false if it's reached the end.

             (Note that the order of items is undefined and in practice quite random.) */

         virtual bool next() =0;

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

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

     };

     class OverlayDictionary;

     /** An iterator that walks through the differences between two Dictionaries. */

     class Dictionary::ChangeIterator :public Dictionary::Iterator {

     public:

         ChangeIterator (const Dictionary *dict1, const Dictionary *dict2);

         explicit ChangeIterator (const OverlayDictionary*);

         virtual ~ChangeIterator();

         /** Returns the current key, whose values in the two dictionaries differ. */

         virtual Key key() const                 {return _iter->key();}

         /** Returns the corresponding value from dict1.

             May be empty (NULL,0) if the key does not appear in dict1 (i.e. inserted into dict2.) */

         virtual Blob value() const              {return _iter->value();}

         /** Returns the corresponding value from dict2.

             May be empty (NULL,0) if the key does not appear in dict2 (i.e. deleted from dict2.) */

         virtual Blob otherValue() const         {return _otherValue;}

         virtual bool hasValue() const           {return _iter->hasValue();}

         virtual bool next();

     private:

         void _init (const Dictionary *dict1, const Dictionary *dict2);

         bool _skipMatching();

         const Dictionary *_dict2;

         Iterator *_iter;

         Blob _otherValue;

     };

     /** Adapter class that allows a Dictionary to appear to be mutable, by using a separate

         mutable dictionary to remember the changes. */

     class OverlayDictionary :public MutableDictionary {

     public:

         /** Creates a mutable dictionary that overlays base. Initially its contents will appear

             identical to base. It can be changed, but the changes will not affect the base. */

         explicit OverlayDictionary (const Dictionary *base);

         virtual ~OverlayDictionary();

         /** The base dictionary this is overlaying. */

         const Dictionary* base() const              {return _base;}

         /** The dictionary that contains the changes made to the base.

             Only keys/values that have been changed appear here. */

         const Dictionary* overlay() const           {return _overlay;}

         /** Returns true if changes have been made. */

         bool isChanged() const;

         /** Returns true if the base has been completely replaced by calling removeAll. */

         bool baseReplaced() const                   {return _allRemoved;}

         /** Removes all changes, restoring the overlay to look identical to the base. */

         void revert();

         /** Changes the overlay to a new base, clearing all changes. */

         void revertTo (const Dictionary* newBase);

         /** Changes the base without clearing changes. */

         void rebase (const Dictionary* newBase);

         virtual int count() const;

         virtual Blob get (Key) const;

         virtual bool contains (Key) const;

         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 OverlayDictionary&);

             virtual Key key() const;

             virtual Blob value() const;

             virtual bool next();

         private:

             bool skipCurrentState();

             Dictionary::Iterator *_iter;

             const MutableDictionary *_overlay;

         };

     private:

         const Dictionary *_base;

         MutableDictionary *_overlay;

         int _count;

         bool _allRemoved;

         friend class ChangeIterator;

     };

 }

 #endif _MOOSEYARD_DICTIONARY_