llassoclist.h

Go to the documentation of this file.

#ifndef LL_LLASSOCLIST_H
#define LL_LLASSOCLIST_H

//------------------------------------------------------------------------
// LLAssocList is an associative list container class.
//
// The implementation is a single linked list.
// Both index and value objects are stored by value (not reference).
// If pointer values are specified for index and/or value, this
// container does NOT assume ownership of the referenced objects,
// and does NOT delete() them on removal or destruction of the container.
//
// Note that operations are generally not optimized, and may of them
// are O(n) complexity.
//------------------------------------------------------------------------

#include <iostream>

template<class INDEX_TYPE, class VALUE_TYPE>
class LLAssocList
{
private:
        // internal list node type
        class Node
        {
        public:
                Node(const INDEX_TYPE &index, const VALUE_TYPE &value, Node *next)
                {
                        mIndex = index;
                        mValue = value;
                        mNext = next;
                }
                ~Node() { }
                INDEX_TYPE      mIndex;
                VALUE_TYPE      mValue;
                Node            *mNext;
        };

        // head of the linked list
        Node *mHead;

public:
        // Constructor
        LLAssocList()
        {
                mHead = NULL;
        }

        // Destructor
        ~LLAssocList()
        {
                removeAll();
        }

        // Returns TRUE if list is empty.
        BOOL isEmpty()
        {
                return (mHead == NULL);
        }

        // Returns the number of items in the list.
        U32 length()
        {
                U32 count = 0;
                for (   Node *node = mHead;
                                node;
                                node = node->mNext )
                {
                        count++;
                }
                return count;
        }

        // Removes item with the specified index.
        BOOL remove( const INDEX_TYPE &index )
        {
                if (!mHead)
                        return FALSE;

                if (mHead->mIndex == index)
                {
                        Node *node = mHead;
                        mHead = mHead->mNext;
                        delete node;
                        return TRUE;
                }

                for (   Node *prev = mHead;
                                prev->mNext;
                                prev = prev->mNext )
                {
                        if (prev->mNext->mIndex == index)
                        {
                                Node *node = prev->mNext;
                                prev->mNext = prev->mNext->mNext;
                                delete node;
                                return TRUE;
                        }
                }
                return FALSE;
        }

        // Removes all items from the list.
        void removeAll()
        {
                while ( mHead )
                {
                        Node *node = mHead;
                        mHead = mHead->mNext;
                        delete node;
                }
        }

        // Adds a new item to the head of the list,
        // removing any existing item with same index.
        void addToHead( const INDEX_TYPE &index, const VALUE_TYPE &value )
        {
                remove(index);
                Node *node = new Node(index, value, mHead);
                mHead = node;
        }

        // Adds a new item to the end of the list,
        // removing any existing item with the same index.
        void addToTail( const INDEX_TYPE &index, const VALUE_TYPE &value )
        {
                remove(index);
                Node *node = new Node(index, value, NULL);
                if (!mHead)
                {
                        mHead = node;
                        return;
                }
                for (   Node *prev=mHead;
                                prev;
                                prev=prev->mNext )
                {
                        if (!prev->mNext)
                        {
                                prev->mNext=node;
                                return;
                        }
                }
        }

        // Sets the value of a specified index.
        // If index does not exist, a new value will be added only if
        // 'addIfNotFound' is set to TRUE.
        // Returns TRUE if successful.
        BOOL setValue( const INDEX_TYPE &index, const VALUE_TYPE &value, BOOL addIfNotFound=FALSE )
        {
                VALUE_TYPE *valueP = getValue(index);
                if (valueP)
                {
                        *valueP = value;
                        return TRUE;
                }
                if (!addIfNotFound)
                        return FALSE;
                addToTail(index, value);
                return TRUE;
        }

        // Sets the ith value in the list.
        // A new value will NOT be addded, if the ith value does not exist.
        // Returns TRUE if successful.
        BOOL setValueAt( U32 i, const VALUE_TYPE &value )
        {
                VALUE_TYPE *valueP = getValueAt(i);
                if (valueP)
                {
                        *valueP = value;
                        return TRUE;
                }
                return FALSE;
        }

        // Returns a pointer to the value for the specified index,
        // or NULL if no item found.
        VALUE_TYPE *getValue( const INDEX_TYPE &index )
        {
                for (   Node *node = mHead;
                                node;
                                node = node->mNext )
                {
                        if (node->mIndex == index)
                                return &node->mValue;
                }
                return NULL;
        }

        // Returns a pointer to the ith value in the list, or
        // NULL if i is not valid.
        VALUE_TYPE *getValueAt( U32 i )
        {
                U32 count = 0;
                for (   Node *node = mHead;
                                node;
                                node = node->mNext )
                {
                        if (count == i)
                                return &node->mValue;
                        count++;
                }
                return NULL;
        }

        // Returns a pointer to the index for the specified index,
        // or NULL if no item found.
        INDEX_TYPE *getIndex( const INDEX_TYPE &index )
        {
                for (   Node *node = mHead;
                                node;
                                node = node->mNext )
                {
                        if (node->mIndex == index)
                                return &node->mIndex;
                }
                return NULL;
        }

        // Returns a pointer to the ith index in the list, or
        // NULL if i is not valid.
        INDEX_TYPE *getIndexAt( U32 i )
        {
                U32 count = 0;
                for (   Node *node = mHead;
                                node;
                                node = node->mNext )
                {
                        if (count == i)
                                return &node->mIndex;
                        count++;
                }
                return NULL;
        }

        // Returns a pointer to the value for the specified index,
        // or NULL if no item found.
        VALUE_TYPE *operator[](const INDEX_TYPE &index)
        {
                return getValue(index);
        }

        // Returns a pointer to the ith value in the list, or
        // NULL if i is not valid.
        VALUE_TYPE *operator[](U32 i)
        {
                return getValueAt(i);
        }

        // Prints the list contents to the specified stream.
        friend std::ostream &operator<<( std::ostream &os, LLAssocList &map )
        {
                os << "{";
                for (   Node *node = map.mHead;
                                node;
                                node = node->mNext )
                {
                        os << "<" << node->mIndex << ", " << node->mValue << ">";
                        if (node->mNext)
                                os << ", ";
                }
                os << "}";

                return os;
        }
};

#endif // LL_LLASSOCLIST_H

---