DS_Map.h

Go to the documentation of this file.

#ifndef __RAKNET_MAP_H
#define __RAKNET_MAP_H

#include "DS_OrderedList.h"
#include "Export.h"
#include "RakMemoryOverride.h"
#include "RakAssert.h"

// If I want to change this to a red-black tree, this is a good site: http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
// This makes insertions and deletions faster.  But then traversals are slow, while they are currently fast.

namespace DataStructures
{
        template <class key_type>
                int defaultMapKeyComparison(const key_type &a, const key_type &b)
        {
                if (a<b) return -1; if (a==b) return 0; return 1;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&, const key_type&)=defaultMapKeyComparison<key_type> >
        class RAK_DLL_EXPORT Map
        {
        public:
                static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<key_type>(key_type(),key_type());}

                struct MapNode
                {
                        MapNode() {}
                        MapNode(key_type _key, data_type _data) : mapNodeKey(_key), mapNodeData(_data) {}
                        MapNode& operator = ( const MapNode& input ) {mapNodeKey=input.mapNodeKey; mapNodeData=input.mapNodeData; return *this;}
                        MapNode( const MapNode & input) {mapNodeKey=input.mapNodeKey; mapNodeData=input.mapNodeData;}
                        key_type mapNodeKey;
                        data_type mapNodeData;
                };

                // Has to be a static because the comparison callback for DataStructures::OrderedList is a C function
                static int NodeComparisonFunc(const key_type &a, const MapNode &b)
                {
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
                        return key_comparison_func(a, b.mapNodeKey);
                }

                Map();
                ~Map();
                Map( const Map& original_copy );
                Map& operator= ( const Map& original_copy );

                data_type& Get(const key_type &key) const; 
                data_type Pop(const key_type &key);
                // Add if needed
                void Set(const key_type &key, const data_type &data);
                // Must already exist
                void SetExisting(const key_type &key, const data_type &data);
                // Must add
                void SetNew(const key_type &key, const data_type &data);
                bool Has(const key_type &key) const;
                bool Delete(const key_type &key);
                data_type& operator[] ( const unsigned int position ) const;
                key_type GetKeyAtIndex( const unsigned int position ) const;
                unsigned GetIndexAtKey( const key_type &key );
                void RemoveAtIndex(const unsigned index);
                void Clear(void);
                unsigned Size(void) const;

        protected:
                DataStructures::OrderedList< key_type,MapNode,&Map::NodeComparisonFunc > mapNodeList;

                void SaveLastSearch(const key_type &key, unsigned index) const;
                bool HasSavedSearchResult(const key_type &key) const;

                unsigned lastSearchIndex;
                key_type lastSearchKey;
                bool lastSearchIndexValid;
        };

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        Map<key_type, data_type, key_comparison_func>::Map()
        {
                lastSearchIndexValid=false;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        Map<key_type, data_type, key_comparison_func>::~Map()
        {
                Clear();
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        Map<key_type, data_type, key_comparison_func>::Map( const Map& original_copy )
        {
                mapNodeList=original_copy.mapNodeList;
        lastSearchIndex=original_copy.lastSearchIndex;
                lastSearchKey=original_copy.lastSearchKey;
                lastSearchIndexValid=original_copy.lastSearchIndexValid;
        }

    template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        Map<key_type, data_type, key_comparison_func>& Map<key_type, data_type, key_comparison_func>::operator= ( const Map& original_copy )
        {
                mapNodeList=original_copy.mapNodeList;
                lastSearchIndex=original_copy.lastSearchIndex;
                lastSearchKey=original_copy.lastSearchKey;
                lastSearchIndexValid=original_copy.lastSearchIndexValid;
                return *this;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        data_type& Map<key_type, data_type, key_comparison_func>::Get(const key_type &key) const
        {
                if (HasSavedSearchResult(key))
                        return mapNodeList[lastSearchIndex].mapNodeData;

                bool objectExists;
                unsigned index;
                index=mapNodeList.GetIndexFromKey(key, &objectExists);
                RakAssert(objectExists);
                SaveLastSearch(key,index);
                return mapNodeList[index].mapNodeData;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        unsigned Map<key_type, data_type, key_comparison_func>::GetIndexAtKey( const key_type &key )
        {
                if (HasSavedSearchResult(key))
                        return lastSearchIndex;

                bool objectExists;
                unsigned index;
                index=mapNodeList.GetIndexFromKey(key, &objectExists);
                if (objectExists==false)
                {
                        RakAssert(objectExists);
                }
                SaveLastSearch(key,index);
                return index;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::RemoveAtIndex(const unsigned index)
        {
                mapNodeList.RemoveAtIndex(index);
                lastSearchIndexValid=false;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
                data_type Map<key_type, data_type, key_comparison_func>::Pop(const key_type &key)
        {
                bool objectExists;
                unsigned index;
                if (HasSavedSearchResult(key))
                        index=lastSearchIndex;
                else
                {
                        index=mapNodeList.GetIndexFromKey(key, &objectExists);
                        RakAssert(objectExists);
                }               
                data_type tmp = mapNodeList[index].mapNodeData;
                mapNodeList.RemoveAtIndex(index);
                lastSearchIndexValid=false;
                return tmp;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::Set(const key_type &key, const data_type &data)
        {
                bool objectExists;
                unsigned index;

                if (HasSavedSearchResult(key))
                {
                        mapNodeList[lastSearchIndex].mapNodeData=data;
                        return;
                }
                
                index=mapNodeList.GetIndexFromKey(key, &objectExists);

                if (objectExists)
                {
                        SaveLastSearch(key,index);
                        mapNodeList[index].mapNodeData=data;
                }
                else
                {
                        SaveLastSearch(key,mapNodeList.Insert(key,MapNode(key,data), true, __FILE__,__LINE__));
                }
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::SetExisting(const key_type &key, const data_type &data)
        {
                bool objectExists;
                unsigned index;

                if (HasSavedSearchResult(key))
                {
                        index=lastSearchIndex;
                }
                else
                {
                        index=mapNodeList.GetIndexFromKey(key, &objectExists);
                        RakAssert(objectExists);
                        SaveLastSearch(key,index);
                }               

                mapNodeList[index].mapNodeData=data;
        }       

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::SetNew(const key_type &key, const data_type &data)
        {
#ifdef _DEBUG
                bool objectExists;
                mapNodeList.GetIndexFromKey(key, &objectExists);
                RakAssert(objectExists==false);
#endif
                SaveLastSearch(key,mapNodeList.Insert(key,MapNode(key,data), true, __FILE__,__LINE__));
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        bool Map<key_type, data_type, key_comparison_func>::Has(const key_type &key) const
        {
                if (HasSavedSearchResult(key))
                        return true;

                bool objectExists;
                unsigned index;
                index=mapNodeList.GetIndexFromKey(key, &objectExists);
                if (objectExists)
                        SaveLastSearch(key,index);
                return objectExists;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        bool Map<key_type, data_type, key_comparison_func>::Delete(const key_type &key)
        {
                if (HasSavedSearchResult(key))
                {
                        lastSearchIndexValid=false;
                        mapNodeList.RemoveAtIndex(lastSearchIndex);   
                        return true;
                }

                bool objectExists;
                unsigned index;
                index=mapNodeList.GetIndexFromKey(key, &objectExists);
                if (objectExists)
                {
                        lastSearchIndexValid=false;
                        mapNodeList.RemoveAtIndex(index);
                        return true;
                }
                else
                        return false;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::Clear(void)
        {
                lastSearchIndexValid=false;
                mapNodeList.Clear(false, __FILE__, __LINE__);
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        data_type& Map<key_type, data_type, key_comparison_func>::operator[]( const unsigned int position ) const
        {
                return mapNodeList[position].mapNodeData;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
                key_type Map<key_type, data_type, key_comparison_func>::GetKeyAtIndex( const unsigned int position ) const
        {
                return mapNodeList[position].mapNodeKey;
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        unsigned Map<key_type, data_type, key_comparison_func>::Size(void) const
        {
                return mapNodeList.Size();
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        void Map<key_type, data_type, key_comparison_func>::SaveLastSearch(const key_type &key, const unsigned index) const
        {
                (void) key;
                (void) index;

                /*
                lastSearchIndex=index;
                lastSearchKey=key;
                lastSearchIndexValid=true;
                */
        }

        template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
        bool Map<key_type, data_type, key_comparison_func>::HasSavedSearchResult(const key_type &key) const
        {
                (void) key;

                // Not threadsafe!
                return false;
                // return lastSearchIndexValid && key_comparison_func(key,lastSearchKey)==0;
        }
}

#endif