llassoclist.h
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:7k
- /**
- * @file llassoclist.h
- * @brief LLAssocList class header file
- *
- * $LicenseInfo:firstyear=2001&license=viewergpl$
- *
- * Copyright (c) 2001-2010, Linden Research, Inc.
- *
- * Second Life Viewer Source Code
- * The source code in this file ("Source Code") is provided by Linden Lab
- * to you under the terms of the GNU General Public License, version 2.0
- * ("GPL"), unless you have obtained a separate licensing agreement
- * ("Other License"), formally executed by you and Linden Lab. Terms of
- * the GPL can be found in doc/GPL-license.txt in this distribution, or
- * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
- *
- * There are special exceptions to the terms and conditions of the GPL as
- * it is applied to this Source Code. View the full text of the exception
- * in the file doc/FLOSS-exception.txt in this software distribution, or
- * online at
- * http://secondlifegrid.net/programs/open_source/licensing/flossexception
- *
- * By copying, modifying or distributing this software, you acknowledge
- * that you have read and understood your obligations described above,
- * and agree to abide by those obligations.
- *
- * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
- * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
- * COMPLETENESS OR PERFORMANCE.
- * $/LicenseInfo$
- */
- #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