Dictionary.h

Go to the documentation of this file.

/***************************************************************
 
 Mini Grand Challenge 2010
 Pennsylvania State University - Robotics Club
 Learn more at www.psurobotics.org
 Protected by the GNU General Public License
 
 This source file is developed and maintained by:
 + Jeremy Bridon jgbridon@gmail.com
 
 File: Dictionary.h
 Info: A simple template list hash-table (dictionary) implementation. Keys
 are string based. Linked-list implemented for collisions. The hash
 algorithm is based off of the jenkins-once-at-a-time hash. Read
 about it here: http://en.wikipedia.org/wiki/Hash_table Note that the
 "linked list" is simply a jagged array, not a single-linked-list.
 
***************************************************************/

// Inclusion guard
#ifndef __DICTIONARY_H_
#define __DICTIONARY_H_

// Includes
#include "Utilities.h"
#include "List.h"
#include "Stack.h"

template <typename Type> struct DictionaryNode
{
        DictionaryNode(const char* givenKey, Type givenData)
        {
                // Copy the given data and set the next pointer to null
                key = new char[strlen(givenKey) + 1];
                strcpy(key, givenKey);
                data = givenData;
                next = NULL;
        }

        ~DictionaryNode()
        {
                delete[] key;
        }

        Type data;                                      
        char* key;                                      
        DictionaryNode<Type> *next;     
};

template <typename Type> class Dictionary
{
public:

        Dictionary(int size = DEFAULT_PAGE_SIZE, int RehashBound = DEFAULT_REHASH_BOUND)
                : data(size)
        {
                // Set the data list pointers to null
                for(int i = 0; i < data.GetSize(); i++)
                        data[i] = NULL;

                // Get the rehash count
                rehashConflictCount = RehashBound;
                elemCount = 0;
        }

        ~Dictionary()
        {
                // Just call release, everything gets released through stack-popping
                Release();
        }
        
        void Release()
        {
                // For each linked-list
                for(int i = 0; i < data.GetSize(); i++)
                {
                        // For each element in the linked-list
                        DictionaryNode<Type> *current = data[i];
                        
                        while(current != NULL)
                        {
                                DictionaryNode<Type> *next = current->next;
                                delete current;
                                current = next;
                        }
                }
                
                // Set list size to zero
                data.Resize(0);
        }

        void Insert(const char* key, Type obj)
        {
                // Let us check that we do not already have this data, to prevent repeats
                if(Find(key, obj))
                        return; // Already exists

                // Get the key
                unsigned int keyIndex = CreateKey(key);

                // Create a DictionaryNode
                DictionaryNode<Type> *newObj = new DictionaryNode<Type>(key, obj);

                // Find the next valid spot in this chain (May 16: Optimized with pointer usage)
                int depth = 0;
                if(data[keyIndex % data.GetSize()] == NULL)
                        data[keyIndex % data.GetSize()] = newObj;
                else
                {
                        // Find a valid end of list to append to, but count our depth
                        DictionaryNode<Type> *current = data[keyIndex % data.GetSize()];

                        while(current->next != NULL)
                        {
                                current = current->next;
                                depth++;
                        }

                        // We found a valid pointer to place our new object
                        current->next = newObj;
                }

                // Grow the element counter
                elemCount++;

                // Check if we need to rehash
                if(depth >= rehashConflictCount)
                        Rehash();
        }

        void Delete(const char* key)
        {
                // Get the key
                unsigned int keyIndex = CreateKey(key);

                // Find the next valid spot in this chain
                DictionaryNode<Type> *current = data[keyIndex % data.GetSize()];
                DictionaryNode<Type> *prev = NULL;

                while(current = NULL)
                {
                        // Check for match
                        if(strcmp(current->key, key) == 0)
                        {
                                // This is the parent of the list, update parent location
                                if(prev == NULL)
                                {
                                        DictionaryNode<Type> *next = current->next;
                                        delete current;
                                        data[keyIndex % data.GetSize()] = next;
                                }
                                // Remove current node and fix previous and next nodes
                                else
                                {
                                        prev->next = current->next;
                                        delete current;
                                }

                                // Remove the number from the list and return
                                elemCount--;
                                return;
                        }

                        // Set the previous nodes
                        prev = current;
                        current = current->next;
                }

                // Nothing found, thus nothing removed
        }

        bool Find(const char* key, Type &obj) // Ew at the "pass by reference" - Need to change this!
        {
                // Get the key
                unsigned int keyIndex = CreateKey(key);

                // Find the next valid spot in this chain
                DictionaryNode<Type> *current = data[keyIndex % data.GetSize()];

                while(current != NULL)
                {
                        // Check for a match
                        if(strcmp(current->key, key) == 0)
                        {
                                // Copy over the data
                                // This might be a design error without memcpy() due to complex structs that can't direct copy
                                obj = current->data;
                                return true;
                        }

                        // Look at the next current
                        current = current->next;
                }

                // No match, return false
                return false;
        }

        int GetCount()
        {
                return elemCount;
        }

private:

        unsigned int CreateKey(const char* key)
        {
                unsigned int hash = 0;
                for(unsigned int i = 0; i < strlen(key); i++)
                {
                        hash += key[i];
                        hash += (hash << 10);
                        hash ^= (hash >> 6);
                }
                hash += (hash << 3);
                hash ^= (hash >> 11);
                hash += (hash << 15);

                // Return the hash index for the given data size
                return (hash % data.GetSize());
        } 

        void Rehash()
        {
                // Create a stack for all data
                Stack<DictionaryNode<Type>*> stack(data.GetSize());

                // Collect all data and push into the stack
                for(int i = 0; i < data.GetSize(); i++)
                {
                        // Find the next valid spot in this chain
                        DictionaryNode<Type> *current = data[i];

                        while(current != NULL)
                        {
                                // Push current on stack and set current to next
                                stack.Push(current);
                                current = current->next;
                        }
                }

                // Grow the data list and clear it out (by a page)
                data.Resize(data.GetSize() + DEFAULT_PAGE_SIZE);
                for(int i = 0; i < data.GetSize(); i++)
                        data[i] = NULL;

                // Pop back in the data
                elemCount = 0;
                while(stack.IsEmpty())
                {
                        DictionaryNode<Type> *node;
                        node = stack.Pop();
                        Insert(node->key, node->data);
                }
        }

        static const int DEFAULT_PAGE_SIZE = 16;

        static const int DEFAULT_REHASH_BOUND = 4;

        int elemCount;                                          
        int rehashConflictCount;                        
        
public:
        
        // Note that we make this public so we can manually release all data!
        List<DictionaryNode<Type>*> data;       
};

#endif

---