Introduction to ACF (Another C++ Framework)

//---------------------------------------------------------------------
//
// Copyright (C) 2004 Yingle Jia
//
// Permission to copy, use, modify, sell and distribute this software is 
// granted provided this copyright notice appears in all copies. 
// This software is provided "as is" without express or implied warranty, 
// and with no claim as to its suitability for any purpose.
//
// AcfDictionary.h - defines class Dictionary
//

#ifndef __Acf_Dictionary__
#define __Acf_Dictionary__

namespace Acf {
	namespace Collections {

//---------------------------------------------------------------------
// class KeyNotFoundException

class KeyNotFoundException : public Exception
{
};

//---------------------------------------------------------------------
// class Dictionary

template < typename K, typename V, class KTr = CollectionTraits<K>, class VTr = CollectionTraits<V> >
class Dictionary : public Object, public IDictionary<K, V, KTr, VTr>
{
public:
    using Object::AddRef;
    using Object::Release;

// Declaractions
private:
    typedef typename KTr::InArgType   KeyInArgType;
    typedef typename VTr::InArgType   ValueInArgType;

    class EnumeratorBase;
    friend class EnumeratorBase;

    enum BucketFlags
    {
        BucketFlagsNone = 0,
        BucketFlagsInUse = 0x01,    // the bucket is in use
        BucketFlagsCollision = 0x02, // there is a collision
    };
    struct Bucket
    {
        K Key;
        V Value;
        int HashCode;
        int Flags;
    };

// Fields
private:
    RefPtr< Array<Bucket> > _buckets;
    int _count; // total number of entries
    int _loadsize;
    float _loadFactor;
    int _modifications;
    RefPtr< ICollection<K, KTr> > _keys;
    RefPtr< ICollection<V, VTr> > _values;

// Constructors
public:
    Dictionary(int capacity = 0, float loadFactor = 1.0f)
    {
        if (capacity < 0)
            throw ArgumentOutOfRangeException();
        if (!(loadFactor >= 0.1f && loadFactor <= 1.0f))
            throw ArgumentOutOfRangeException();

        this->_loadFactor = 0.72f * loadFactor;

        double rawSize = capacity / this->_loadFactor;
        if (rawSize > Int32::MaxValue)
            throw ArgumentException();

        int hashSize = GetPrime((int) rawSize);
        this->_buckets = new Array<Bucket>(hashSize);

        this->_loadsize = (int) (this->_loadFactor * hashSize);
        if (this->_loadsize >= hashSize)
            this->_loadsize = hashSize - 1;
    }

    Dictionary(IDictionary<K, V, KTr, VTr>* d, float loadFactor = 1.0f)
    {
        if (d == null)
            throw ArgumentNullException();

        new(this) Dictionary(d->Count, loadFactor);

        RefPtr< IEnumerator< KeyValuePair<K, V, KTr, VTr> > > e = d->GetEnumerator();
        if (e != null)
        {
            while (e->MoveNext())
            {
                KeyValuePair<K, V, KTr, VTr> entry = e->Current;
                Add(entry.Key, entry.Value);
            }
        }
    }

// Methods
public:
    //
    // IEnumerable Members
    //

    virtual RefPtr< IEnumerator< KeyValuePair<K, V, KTr, VTr> > > GetEnumerator()
    {
		return new Enumerator(this);
    }

    //
    // ICollection Members
    //

    virtual int get_Count()
    {
        return this->_count;
    }

    virtual bool get_IsReadOnly()
    {
        return false;
    }

    virtual int Add(const KeyValuePair<K, V, KTr, VTr>& pair)
    {
        Add(pair.Key, pair.Value);
        return this->Count;
    }

    virtual bool Remove(const KeyValuePair<K, V, KTr, VTr>& pair)
    {
        // TODO:
        return false;
    }

    virtual void Clear()
    {
        if (this->_count == 0)
            return;

        Bucket* buckets = this->_buckets->GetBuffer();
        for (int i = 0; i < this->_buckets->Length; i++)
        {
            buckets[i].Flags = BucketFlagsNone;
            buckets[i].HashCode = 0;

            KTr::Clear(&buckets[i].Key, 1);
            VTr::Clear(&buckets[i].Value, 1);
        }

        this->_count = 0;
        this->_modifications++;
    }

    virtual bool Contains(const KeyValuePair<K, V, KTr, VTr>& pair)
    {
        // TODO:
        return false;
    }

    virtual void CopyTo(Array< KeyValuePair<K, V, KTr, VTr> >* array, int arrayIndex)
    {
        Acf::VerifyArrayRange(array, arrayIndex, this->_count);

        CopyEntries(array, arrayIndex);
    }

    //
    // IDictionary Members
    //

    virtual V get_Item(KeyInArgType key)
    {
        uint hashCode;
        uint seed;
        uint incr;

        RefPtr< Array<Bucket> > buckets = this->_buckets;
        seed = hashCode = InitHash(key, buckets->Length, &incr);
        int ntry = 0;

        while (true)
        {
            int index = (int) (seed % (uint) buckets->Length);
            Bucket b = buckets->Item[index];

            if ((b.Flags & BucketFlagsInUse) == 0)
                throw KeyNotFoundException();

            if ((b.HashCode == hashCode) && KTr::Equals(key, b.Key))
                return b.Value;

            if ((b.Flags & BucketFlagsCollision) == 0 || 
                ++ntry >= buckets->Length)
                throw KeyNotFoundException();

            seed += incr;
        }
    }

    virtual void set_Item(KeyInArgType key, ValueInArgType value)
    {
        Insert(key, value, false);
    }

    virtual RefPtr< ICollection<K, KTr> > get_Keys()
    {
        if (this->_keys == null)
            this->_keys = new KeyCollection(this);

        return this->_keys;
    }

    virtual RefPtr< ICollection<V, VTr> > get_Values()
    {
        if (this->_values == null)
            this->_values = new ValueCollection(this);

        return this->_values;
    }

    virtual void Add(KeyInArgType key, ValueInArgType value)
    {
        Insert(key, value, true);
    }

    virtual bool Remove(KeyInArgType key)
    {
        uint hashCode;
        uint seed;
        uint incr;

        RefPtr< Array<Bucket> > buckets = this->_buckets;
        seed = hashCode = InitHash(key, buckets->Length, &incr);
        int ntry = 0;

        while (true)
        {
            int index = (int) (seed % (uint) buckets->Length);
            Bucket* pb = buckets->GetItemAddress(index);

            if ((pb->HashCode == hashCode) && KTr::Equals(key, pb->Key))
            {
                pb->HashCode = 0;
                pb->Flags &= ~BucketFlagsInUse; // keep the collision flag
                KTr::Clear(&pb->Key, 1);
                VTr::Clear(&pb->Value, 1);
                this->_count--;
                this->_modifications++;
                return true;
            }

            if ((pb->Flags & BucketFlagsCollision) == 0 || 
                ++ntry >= buckets->Length)
            {
                return false;
            }

            seed += incr;
        }
    }

    virtual bool ContainsKey(KeyInArgType key)
    {
        uint hashCode;
        uint seed;
        uint incr;

        RefPtr< Array<Bucket> > buckets = this->_buckets;
        seed = hashCode = InitHash(key, buckets->Length, &incr);
        int ntry = 0;

        while (true)
        {
            int index = (int) (seed % (uint) buckets->Length);
            Bucket b = buckets->Item[index];

            if ((b.Flags & BucketFlagsInUse) == 0)
                return false;

            if ((b.HashCode == hashCode) && KTr::Equals(key, b.Key))
                return true;

            if ((b.Flags & BucketFlagsCollision) == 0 || 
                ++ntry >= buckets->Length)
                return false;

            seed += incr;
        }
    }

    //
    // Dictionary Members
    //

    bool ContainsValue(ValueInArgType value)
    {
        for (int i = this->_buckets->Length; --i >= 0;)
        {
            Bucket b = this->_buckets->Item[i];
            if ((b.Flags & BucketFlagsInUse) == 0)
                continue;
            if (VTr::Equals(b.Value, value))
                return true;
        }

        return false;
    }

    void CopyEntries(Array< KeyValuePair<K, V, KTr, VTr> >* array, int arrayIndex)
    {
        if (array == null)
            throw ArgumentNullException();

        RefPtr< Array<Bucket> > buckets = this->_buckets;

        for (int i = buckets->Length; --i >= 0;)
        {
            Bucket b = buckets->Item[i];
            if ((b.Flags & BucketFlagsInUse) != 0)
                array->Item[arrayIndex++] = KeyValuePair<K, V, KTr, VTr>(b.Key, b.Value);
        }
    }

    void CopyKeys(Array<K, KTr>* array, int arrayIndex)
    {
        if (array == null)
            throw ArgumentNullException();

        RefPtr< Array<Bucket> > buckets = this->_buckets;

        for (int i = buckets->Length; --i >= 0;)
        {
            Bucket b = buckets->Item[i];
            if ((b.Flags & BucketFlagsInUse) != 0)
                array->Item[arrayIndex++] = b.Key;
        }
    }

    void CopyValues(Array<V, VTr>* array, int arrayIndex)
    {
        if (array == null)
            throw ArgumentNullException();

        RefPtr< Array<Bucket> > buckets = this->_buckets;

        for (int i = buckets->Length; --i >= 0;)
        {
            Bucket b = buckets->Item[i];
            if ((b.Flags & BucketFlagsInUse) != 0)
                array->Item[arrayIndex++] = b.Value;
        }
    }

private:
    // Inserts an entry into this hashtable. This method is called from the Set
    // and Add methods. If the add parameter is true and the given key already
    // exists in the hashtable, an exception is thrown.
    void Insert(KeyInArgType key, ValueInArgType value, bool add)
    {
        if (this->_count >= this->_loadsize)
            Expand();

        uint hashCode;
        uint seed;
        uint incr;

        // Assume we only have one thread writing concurrently. Modify
        // _buckets to contain new data, as long as we insert in the right order.
        seed = hashCode = InitHash(key, this->_buckets->Length, &incr);
        int ntry = 0;
        int emptySlotNumber = -1; // Used to cache the first empty slot. We chose to reuse slots
        // create by remove that have the collision bit set over using up new slots.

        while (true)
        {
            int index = (int) (seed % (uint) this->_buckets->Length);
            Bucket* pb = this->_buckets->GetItemAddress(index);

            // If this bucket is not in use, and has the collision flag...
            if (emptySlotNumber == -1 && 
                (pb->Flags & (BucketFlagsInUse | BucketFlagsCollision)) == BucketFlagsCollision)
                emptySlotNumber = index;

            if ((pb->Flags & BucketFlagsInUse) == 0)
            {
                if (emptySlotNumber != -1) // reuse slot
                    pb = this->_buckets->GetItemAddress(emptySlotNumber);

                // We pretty much have to insert in this order.  Don't set hash
                // code until the value & key are set appropriately.
                pb->Flags |= BucketFlagsInUse;
                pb->Value = value;
                pb->Key = key;
                pb->HashCode = (int) hashCode;

                this->_count++;
                this->_modifications++;
                return;
            }

            if (pb->HashCode == hashCode && KTr::Equals(key, pb->Key))
            {
                if (add)
                    throw ArgumentException();

                pb->Value = value;
                this->_modifications++;
                return;
            }

            if (emptySlotNumber == -1)
                pb->Flags |= BucketFlagsCollision;

            if (++ntry >= this->_buckets->Length)
                break;

            seed += incr;
        }

        ACFASSERT(emptySlotNumber != -1);
        if (emptySlotNumber == -1)
            throw InvalidOperationException();

        Bucket* pb = this->_buckets->GetItemAddress(emptySlotNumber);
        pb->Flags |= BucketFlagsInUse;
        pb->Value = value;
        pb->Key = key;
        pb->HashCode = (int) hashCode;

        this->_count++;
        this->_modifications++;
    }

    // Increases the Bucket count of this hashtable. This method is called from
    // the Insert method when the actual load factor of the hashtable reaches
    // the upper limit specified when the hashtable was constructed. The number
    // of buckets in the hashtable is increased to the smallest prime number
    // that is larger than twice the current number of buckets, and the entries
    // in the hashtable are redistributed into the new buckets using the cached
    // hashcodes.
    void Expand()
    {
        int oldHashSize = this->_buckets->Length;
        int rawSize = 1 + oldHashSize * 2;

        if (rawSize < 0)
            throw ArgumentException();

        int hashSize = GetPrime(rawSize);

        // Don't replace any internal state until we've finished adding to the 
        // new Bucket[]. This serves two purposes: 1) Allow concurrent readers
        // to see valid hashtable contents at all times and 2) Protect against
        // an OutOfMemoryException while allocating this new Bucket[].
        RefPtr< Array<Bucket> > newBuckets = new Array<Bucket>(hashSize);

        // Rehash table into new buckets
        for (int i = 0; i < oldHashSize; i++)
        {
            Bucket oldb = this->_buckets->Item[i];
            if ((oldb.Flags & BucketFlagsInUse) != 0)
            {
                PutEntry(newBuckets, oldb.Key, oldb.Value, oldb.HashCode);
            }
        }

        // New Bucket[] is good to go - replace _buckets and other internal state.
        this->_modifications++;
        this->_buckets = newBuckets;
        this->_loadsize = (int) (this->_loadFactor * hashSize);
        if (this->_loadsize >= hashSize)
            this->_loadsize = hashSize - 1;
    }

    static void PutEntry(Array<Bucket>* newBuckets, KeyInArgType key, ValueInArgType value, int hashCode)
    {
        uint seed = (uint) hashCode;
        uint incr = (uint) (1 + (((seed >> 5) + 1) % ((uint) newBuckets->Length - 1)));

        while (true)
        {
            int index = (int) (seed % (uint) newBuckets->Length);
            Bucket* pb = newBuckets->GetItemAddress(index);

            if ((pb->Flags & BucketFlagsInUse) == 0)
            {
                pb->Flags |= BucketFlagsInUse;
                pb->Key = key;
                pb->Value = value;
                pb->HashCode = hashCode;
                return;
            }

            pb->Flags |= BucketFlagsCollision;
            seed += incr;
        }
    }

    // Computes the hash function: h(key, i) = h1(key) + i * h2(key, hashSize).
    // The out parameter seed is h1(key), while the out parameter 
    // incr is h2(key, hashSize). Callers of this function should 
    // add incr each time through a loop.
    static uint InitHash(KeyInArgType key, int hashSize, uint* incr)
    {
        uint hashCode = (uint) KTr::GetHashCode(key);
        // Restriction: incr MUST be between 1 and hashSize - 1, inclusive for
        // the modular arithmetic to work correctly. This guarantees you'll
        // visit every Bucket in the table exactly once within hashSize 
        // iterations. Violate this and it'll cause obscure bugs forever.
        // If you change this calculation for h2(key), update PutEntry too!
        *incr = (uint) (1 + (((hashCode >> 5) + 1) % ((uint) hashSize - 1)));
        return hashCode;
    }

    static bool Primep(int candidate)
    {
        if ((candidate & 1) != 0)
        {
            int limit = (int) Math::Sqrt(candidate);

            for (int divisor = 3; divisor <= limit; divisor += 2)
            {
                if ((candidate % divisor) == 0)
                    return false;
            }

            return true;
        }
        else
        {
            return (candidate == 2);
        }
    }

    static int GetPrime(int minSize)
    {
        // Table of prime numbers to use as hash table sizes. Each entry is the
        // smallest prime number larger than twice the previous entry.
        static const int primes[] =
        {
            11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 
            353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 
            3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 
            21023, 25229,30293,36353,43627,52361,62851,75431,90523, 108631, 
            130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 
            560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 
            2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 
        };

        for (int i = 0; i < sizeof(primes) / sizeof(int); i++)
        {
            int size = primes[i];
            if (size >= minSize)
                return size;
        }

        // outside of our predefined table. 
        // compute the hard way. 
        for (int j = (minSize | 1); j < Int32::MaxValue; j += 2)
        {
            if (Primep(j))
                return j;
        }

        return minSize;
    }

private:
    // class KeyCollection
    class KeyCollection : public Object, public ICollection<K, KTr>
    {
    // Fields
    private:
        RefPtr< Dictionary<K, V, KTr, VTr> > _table;

    // Consructor
    public:
        KeyCollection(Dictionary<K, V, KTr, VTr>* table)
        {
            this->_table = table;
        }

    // Methods
    public:
        virtual RefPtr< IEnumerator<K> > GetEnumerator()
        {
			return new KeyEnumerator(this->_table);
        }

        virtual int get_Count()
        {
            return this->_table->Count;
        }

        virtual bool get_IsReadOnly()
        {
            return true;
        }

        virtual int Add(InArgType value)
        {
            throw InvalidOperationException();
            return -1;
        }

        virtual bool Remove(InArgType value)
        {
            throw InvalidOperationException();
            return false;
        }

        virtual void Clear()
        {
            throw InvalidOperationException();
        }

        virtual bool Contains(InArgType value)
        {
            return this->_table->ContainsKey(value);
        }

        virtual void CopyTo(Array<K, KTr>* array, int arrayIndex)
        {
            Acf::VerifyArrayRange(array, arrayIndex, this->_table->Count);

            this->_table->CopyKeys(array, arrayIndex);
        }
    };

    // class ValueCollection
    class ValueCollection : public Object, public ICollection<V, VTr>
    {
    // Fields
    private:
        RefPtr< Dictionary<K, V, KTr, VTr> > _table;

    // Consructor
    public:
        ValueCollection(Dictionary<K, V, KTr, VTr>* table)
        {
            this->_table = table;
        }

    // Methods
    public:
        virtual RefPtr< IEnumerator<V> > GetEnumerator()
        {
			return new ValueEnumerator(this->_table);
        }

        virtual int get_Count()
        {
            return this->_table->Count;
        }

        virtual bool get_IsReadOnly()
        {
            return true;
        }

        virtual int Add(InArgType value)
        {
            throw InvalidOperationException();
            return -1;
        }

        virtual bool Remove(InArgType value)
        {
            throw InvalidOperationException();
            return false;
        }

        virtual void Clear()
        {
            throw InvalidOperationException();
        }

        virtual bool Contains(InArgType value)
        {
            return this->_table->ContainsValue(value);
        }

        virtual void CopyTo(Array<V, VTr>* array, int arrayIndex)
        {
            Acf::VerifyArrayRange(array, arrayIndex, this->_table->Count);

            this->_table->CopyValues(array, arrayIndex);
        }
    };

    // class EnumeratorBase
    class EnumeratorBase : public Object
    {
    // Fields
    protected:
        KeyValuePair<K, V, KTr, VTr> Entry;

    private:
        RefPtr< Dictionary<K, V, KTr, VTr> > _table;
        int _index;
        bool _valid;
        int _modifications;

    // Consructor
    public:
        EnumeratorBase(Dictionary<K, V, KTr, VTr>* table)
        {
            this->_table = table;
            this->_index = table->_buckets->Length;
            this->_valid = false;
            this->_modifications = table->_modifications;
        }

    // Methods
    public:
        bool MoveNextImpl()
        {
            if (this->_modifications != this->_table->_modifications)
                throw InvalidOperationException();

            while (this->_index > 0)
            {
                this->_index--;
                Bucket b = this->_table->_buckets->Item[this->_index];

                if ((b.Flags & BucketFlagsInUse) != 0)
                {
                    this->Entry.Key = b.Key;
                    this->Entry.Value = b.Value;
                    this->_valid = true;
                    return true;
                }
            }

    		this->_valid = false;
            return false;
        }
    };

    // class Enumerator
    class Enumerator : public EnumeratorBase, 
        public IEnumerator< KeyValuePair<K, V, KTr, VTr> >
    {
    public:
        Enumerator(Dictionary<K, V, KTr, VTr>* table) : EnumeratorBase(table)
        {
        }

    public:
        virtual bool MoveNext()
        {
            return MoveNextImpl();
        }
        virtual KeyValuePair<K, V, KTr, VTr> get_Current()
        {
            return this->Entry;
        }
    };

    // class KeyEnumerator
    class KeyEnumerator : public EnumeratorBase, public IEnumerator<K>
    {
    public:
        KeyEnumerator(Dictionary<K, V, KTr, VTr>* table) : EnumeratorBase(table)
        {
        }

    public:
        virtual bool MoveNext()
        {
            return MoveNextImpl();
        }
        virtual K get_Current()
        {
            return this->Entry.Key;
        }
    };

    // class ValueEnumerator
    class ValueEnumerator : public EnumeratorBase, public IEnumerator<V>
    {
    public:
        ValueEnumerator(Dictionary<K, V, KTr, VTr>* table) : EnumeratorBase(table)
        {
        }

    public:
        virtual bool MoveNext()
        {
            return MoveNextImpl();
        }
        virtual V get_Current()
        {
            return this->Entry.Value;
        }
    };
};

	} // namespace Collections
} // namespace Acf

#endif // #ifndef __Acf_Dictionary__