Saf/Algo/Struct/HashTable.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published 
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Saf 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_ALGO_STRUCT_HASHTABLE_H
#define SAF_ALGO_STRUCT_HASHTABLE_H

#include "../../Type.h"
#include "../../Mem/Alloc.h"
#include "../../Collection/Pair.h"
#include "../../Collection/Array.h"
#include "../../Collection/List.h"
#include "../Swap.h"

namespace Saf
{
    namespace Algo
    {        
        namespace Struct
        {
            template <class KeyType, class RecType, class KeySelectorType, class HashFuncType, 
                class HashPolicyType, class CompType>
            class HashTable
            {
            protected:
                typedef HashTable<KeyType,RecType,KeySelectorType,HashFuncType,HashPolicyType,CompType> MyType;

            public:
                typedef typename Collection::List<RecType>::Iterator Iterator;
                typedef typename Collection::List<RecType>::ConstIterator ConstIterator;

            protected:
                typedef typename Collection::Pair<Iterator,Iterator> BucketType;

            private:
                Collection::List<RecType> m_list;
                Size m_elems;
                Collection::Array<1,BucketType> m_bucket;

                KeySelectorType m_keyExtractFunc;
                HashFuncType m_hashFunc;
                HashPolicyType m_hashPolicy;
                CompType m_compFunc;

            protected:
                void SafeResizeBuckets(Size buckets)
                {
                    if (buckets != Buckets())
                    {
                        Collection::Array<1,BucketType> newBuckets;

                        newBuckets.Resize(buckets, BucketType(End(), End()));
                        Algo::Swap(m_bucket, newBuckets);
                    }
                }

                Size ValBucketIndex(const RecType& val) const
                {
                    return KeyBucketIndex(m_keyExtractFunc(val));
                }

                void BucketInsertUpdate(Iterator it, BucketType& bucket)
                {
                    if (bucket.m_first == End())
                    {
                        bucket.m_first = it;
                        bucket.m_second = it;
                    }
                    else
                    {
                        bucket.m_first = it;
                    }
                }

                void BucketEraseUpdate(Iterator it, BucketType& bucket)
                {
                    if (it == bucket.m_first)
                    {                        
                        if (it == bucket.m_second)
                        {                    
                            bucket.m_first = End();
                            bucket.m_second = End();
                        }
                        else
                        {
                            ++bucket.m_first;
                        }
                    }
                    else
                    {
                        if (it == bucket.m_second)
                        {
                            --bucket.m_second;
                        }
                    }
                }

                Iterator BucketFind(const KeyType& key, const BucketType& bucket)
                {
                    Iterator ipos = bucket.m_first;

                    if (ipos != End())
                    {
                        Iterator ilast = bucket.m_second;
                        ++ilast;

                        while (ipos != ilast)
                        {                        
                            if (m_compFunc(m_keyExtractFunc(*ipos), key))
                            {
                                return ipos;
                            }

                            ++ipos;
                        }
                    }

                    return End();
                }

                ConstIterator BucketFind(const KeyType& key, const BucketType& bucket) const
                {
                    Iterator ipos = bucket.m_first;

                    if (ipos != End())
                    {
                        Iterator ilast = bucket.m_second;
                        ++ilast;

                        while (ipos != ilast)
                        {                        
                            if (m_compFunc(m_keyExtractFunc(*ipos), key))
                            {
                                return ipos;
                            }

                            ++ipos;
                        }
                    }

                    return End();
                }

                void Reinsert(Iterator last)
                {
                    if (last != Begin())
                    {
                        Iterator icur;
                        --last; // Sentinel

                        do
                        {
                            // Processed element
                            icur = Begin();

                            // Find bucket
                            BucketType &bucket = m_bucket[ValBucketIndex(*icur)];

                            // Reinsert
                            m_list.SpliceBefore(bucket.m_first, icur);
                            BucketInsertUpdate(icur, bucket);
                        } while (icur != last);
                    }
                }

                void ResizeTable(Size buckets)
                {
                    SafeResizeBuckets(buckets);
                    Reinsert(End());
                }

            public:
                explicit HashTable(Size bucketHint)
                    : m_elems(0)
                {
                    // Allocate the optimum number of buckets
                    SafeResizeBuckets(m_hashPolicy.NextBucketCount(bucketHint));
                }

                HashTable(const MyType& ht) 
                    : m_elems(0)
                {
                    *this = ht; 
                }

                ~HashTable() 
                {}

                MyType& Free() 
                {
                    // Try to reset the bucket count
                    SafeResizeBuckets(m_hashPolicy.NextBucketCount(0));

                    // Free all values
                    m_list.Free();
                    m_elems = 0;

                    return *this;
                }

                MyType& operator=(const MyType& ht)
                {
                    if (&ht != this)
                    {
                        // Reset the table
                        Free();

                        // Try to allocate new bucket array and copy the elements
                        Collection::Array<1,BucketType> newBuckets;
                        Collection::List<RecType> newList;

                        newList = ht.m_list;
                        newBuckets.Resize(ht.Buckets(), BucketType(newList.End(), newList.End()));

                        // Hopefully, these do not throw
                        m_keyExtractFunc = ht.m_keyExtractFunc;
                        m_hashFunc = ht.m_hashFunc;
                        m_hashPolicy = ht.m_hashPolicy;
                        m_compFunc = ht.m_compFunc;
                        
                        // Everything went ok, swap the pointers and restore the table
                        Algo::Swap(m_bucket, newBuckets);
                        Algo::Swap(m_list, newList);

                        m_elems = ht.m_elems;
                        Reinsert(End());
                    }

                    return *this;
                }

                MyType& Swap(MyType& ht)
                {
                    if (&ht != this)
                    {
                        Algo::Swap(m_list, ht.m_list);
                        Algo::Swap(m_elems, ht.m_elems);
                        Algo::Swap(m_bucket, ht.m_bucket);
                        
                        Algo::Swap(m_keyExtractFunc, ht.m_keyExtractFunc);
                        Algo::Swap(m_hashFunc, ht.m_hashFunc);
                        Algo::Swap(m_hashPolicy, ht.m_hashPolicy);
                        Algo::Swap(m_compFunc, ht.m_compFunc);
                    }

                    return *this;
                }

                bool IsEmpty() const 
                { 
                    return (m_elems == 0);
                }

                Size Elements() const
                {
                    return m_elems;
                }

                Size Buckets() const
                {
                    return m_bucket.Elements();
                }

                Size KeyBucketIndex(const KeyType& key) const
                {
                    Size hash = m_hashFunc(key);
                    return m_hashPolicy.BucketIndex(hash, Buckets());
                }

                Iterator BucketBegin(Size bucket)
                {
                    return Iterator(m_bucket[bucket].m_first);
                }

                ConstIterator BucketBegin(Size bucket) const
                {
                    return ConstIterator(m_bucket[bucket].m_first);
                }

                Iterator BucketEnd(Size bucket)
                {
                    Iterator end = m_bucket[bucket].m_second;
                    return end == End() ? end : ++end;
                }

                ConstIterator BucketEnd(Size bucket) const
                {
                    ConstIterator end = m_bucket[bucket].m_second;
                    return end == End() ? end : ++end;
                }

                MyType& Rehash(Size bucketHint)
                {
                    ResizeTable(m_hashPolicy.OptimalBucketCount(bucketHint, m_elems));
                    return *this;
                }

                Collection::Pair<Iterator,bool> Insert(const RecType& val)
                {
                    // Bucket for the new element
                    BucketType &bucket = m_bucket[ValBucketIndex(val)];

                    // Check if already exists
                    Iterator ipos = BucketFind(m_keyExtractFunc(val), bucket);
                    if (ipos != End())
                    {
                        return Collection::Pair<Iterator,bool>(ipos, false);
                    }

                    // Insert new element                    
                    ipos = m_list.InsertBefore(bucket.m_first, val);
                    m_elems++;

                    // Update bucket info
                    BucketInsertUpdate(ipos, bucket);

                    // Check if table resizing is required
                    Collection::Pair<bool,Size> cg = m_hashPolicy.ShouldResize(Elements() + 1, Buckets());
                    if (cg.m_first)
                    {
                        ResizeTable(cg.m_second);
                    }

                    return Collection::Pair<Iterator,bool>(ipos, true);
                }

                Iterator Erase(Iterator it)
                {
                    // Update iterators
                    BucketType& bucket = m_bucket[ValBucketIndex(*it)];
                    BucketEraseUpdate(it, bucket);
                    
                    // Update element counter
                    m_elems--;

                    // Erase element
                    return m_list.Erase(it);
                }

                Iterator Find(const KeyType& key)
                {
                    return BucketFind(key, m_bucket[KeyBucketIndex(key)]);
                }

                ConstIterator Find(const KeyType& key) const
                {
                    return BucketFind(key, m_bucket[KeyBucketIndex(key)]);
                }

                bool Contains(const KeyType& key) const
                {
                    return (Find(key) != End());
                }

                Iterator Begin()
                {
                    return m_list.Begin();
                }

                ConstIterator Begin() const
                {
                    return m_list.Begin();
                }

                Iterator End()
                {
                    return m_list.End();
                }

                ConstIterator End() const
                {
                    return m_list.End();
                }

                Iterator Front()
                {
                    return Begin();
                }

                ConstIterator Front() const
                {
                    return Begin();
                }

                Iterator Back()
                {
                    return m_list.Back();
                }

                ConstIterator Back() const
                {
                    return m_list.Back();
                }
            };
        }

        // Swap specialization for hash tables.
        template <class KeyType, class RecType, class KeySelectorType, class HashFuncType, 
                class HashPolicyType, class CompType>
        struct SwapFunc< Struct::HashTable<KeyType,RecType,KeySelectorType,HashFuncType,HashPolicyType,CompType> >
        {
            void operator()(Struct::HashTable<KeyType,RecType,KeySelectorType,HashFuncType,HashPolicyType,CompType>& x, 
                Struct::HashTable<KeyType,RecType,KeySelectorType,HashFuncType,HashPolicyType,CompType>& y)
            {
                x.Swap(y);
            }
        };
    }
}

#endif