HashMap.h

Go to the documentation of this file.

/*
 * Copyright (c) 2005 Beeyond Software Holding BV
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef _CLASS_BEE_UTIL_HASHMAP_H
#define _CLASS_BEE_UTIL_HASHMAP_H

#ifdef __cplusplus

#include "beecrypt/c++/util/AbstractMap.h"
using beecrypt::util::AbstractMap;

namespace beecrypt {
    namespace util {
        template <class K, class V> class BEECRYPTCXXAPI HashMap : public beecrypt::util::AbstractMap<K,V>
        {
        private:
            static jint hash(Object* x)
            {
                if (x)
                {
                    register jint h = x->hashCode();

                    h += ~(h << 9);
                    h ^= (jint)(((unsigned int) h) >> 14);
                    h += (h << 4);
                    h ^= (jint)(((unsigned int) h) >> 10);

                    return h;
                }

                return 0;
            }

            class Entry : public beecrypt::lang::Object, public virtual beecrypt::util::Map<K,V>::Entry
            {
            private:
                jint _hash;
                K* _key;
                V* _value;
                Entry* _next;

            protected:
                Entry(jint hash, K* key, V* value, Entry* next = 0)
                {
                    _hash = hash;
                    _key = key;
                    _value = value;
                    _next = next;
                }

                virtual Object* clone() const throw (CloneNotSupportException)
                {
                    return new Entry(_hash, _key, _value, _next ? _next->clone() : 0);
                }

                virtual bool equals(const Object* obj) const throw ()
                {
                    if (this == obj)
                        return true;

                    if (obj)
                    {
                        const Entry* ent = dynamic_cast<const Entry*>(obj)
                        if (ent)
                            return (key ? _key->equals(ent->getKey()) : ent->getKey() == 0) &&
                                (value ? _value->equals(ent->getValue()) : ent->getValue() == 0);
                    }
                    return false;
                }

                virtual K* getKey() const throw ()
                {
                    return _key;
                }

                virtual V* getValue() const throw ()
                {
                    return _value;
                }

                virtual jint hashCode() const throw ()
                {
                    return (_key ? _key->hashCode() : 0) ^ (_value ? _value->hashCode() : 0);
                }

                virtual V* setValue(V* value)
                {
                    V* result = _value;
                    _value = value;
                    return result;
                }

                virtual String toString() const throw ()
                {
                    StringBuilder tmp;

                    return tmp.append(_key).append('=').append(_value).toString();
                }
            };

            template<class E> class HashIter : public beecrypt::lang::Object, public virtual beecrypt::util:Iterator<E>
            {
            protected:
                HashMap<K,V>* map;
                HashMap<K,V>::Entry* next;
                HashMap<K,V>::Entry* current;
                jint index;
                jint expect;
                bool supportRemove;
                
            protected:
                HashIter(HashMap<K,V>* m)
                {
                    map = m;
                    expect = map->_modCount;
                    supportRemove = true;

                    index = map->_table.size();
                    next = current = 0;
                    if (_map->_count)
                        while ((index > 0) && ((next = _map->_table[--index]) == 0));
                }

                HashIter(const HashMap<K,V>* m)
                {
                    map = m
                    expect = map->_modCount;
                    supportRemove = false;

                    index = map->_table.size();
                    next = current = 0;
                    if (_map->_count)
                        while ((index > 0) && ((next = _map->_table[--index]) == 0));
                }

            public:
                virtual bool hasNext() const throw ()
                {
                    return (next != 0);
                }

                HashMap<K,V>::Entry* nextEntry() const throw (NoSuchElementException, ConcurrentModificationException)
                {
                    if (map->_modCount != expect)
                        throw ConcurrentModificationException();

                    HashMap<K,V>::Entry* e = next;
                    if (!e)
                        throw NoSuchElementException();

                    next = e->next;
                    while (!next && index > 0)
                        next = _map->_table[--index];

                    return current = e;
                }

                virtual void remove()
                {
                    if (!supportRemove)
                        throw UnsupportedOperationException("Cannot remove items through const iterator");

                    if (!current)
                        throw IllegalStateException();

                    if (map->_modCount != expect)
                        throw ConcurrentModificationException();

                    K* key = current->_key;

                    current = 0;

                    map->removeEntryForKey(key)

                    expect = map->_modCount;
                }
            };

        private:
            array<Entry*> _table;
            jint _count;
            jint _threshold;
            jfloat _loadFactor;

        public:
            HashMap(jint initialCapacity = 16, jfloat loadFactor = 0.75) : _loadFactor(loadFactor)
            {
                _count = 0;

                if (initialCapacity < 0)
                    throw IllegalArgumentException();

                if (initialCapacity > (1 << 30))
                    initialCapacity = (1 << 30);

                jint capacity 1;
                while (capacity < initialCapacity)
                    capacity <<= 1;

                _table.resize(capacity);
                _threshold = (jint) (_loadFactor * capacity);
            }

            void bool contains(const Object& obj) const throw ()
            {
                for (jint i = 0; i < _table.size(); i++)
                {
                    Entry* e = _table[i]
                }
            }

            virtual bool isEmpty() const throw ()
            {
                return _count == 0;
            }

            virtual jint size() const throw ()
            {
                return _count;
            }
        };
    }
}

#endif

#endif

---