llassoclist.h
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:7k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file llassoclist.h
  3.  * @brief LLAssocList class header file
  4.  *
  5.  * $LicenseInfo:firstyear=2001&license=viewergpl$
  6.  * 
  7.  * Copyright (c) 2001-2010, Linden Research, Inc.
  8.  * 
  9.  * Second Life Viewer Source Code
  10.  * The source code in this file ("Source Code") is provided by Linden Lab
  11.  * to you under the terms of the GNU General Public License, version 2.0
  12.  * ("GPL"), unless you have obtained a separate licensing agreement
  13.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  14.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  15.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  16.  * 
  17.  * There are special exceptions to the terms and conditions of the GPL as
  18.  * it is applied to this Source Code. View the full text of the exception
  19.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  20.  * online at
  21.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  22.  * 
  23.  * By copying, modifying or distributing this software, you acknowledge
  24.  * that you have read and understood your obligations described above,
  25.  * and agree to abide by those obligations.
  26.  * 
  27.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  28.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  29.  * COMPLETENESS OR PERFORMANCE.
  30.  * $/LicenseInfo$
  31.  */
  32. #ifndef LL_LLASSOCLIST_H
  33. #define LL_LLASSOCLIST_H
  34. //------------------------------------------------------------------------
  35. // LLAssocList is an associative list container class.
  36. //
  37. // The implementation is a single linked list.
  38. // Both index and value objects are stored by value (not reference).
  39. // If pointer values are specified for index and/or value, this
  40. // container does NOT assume ownership of the referenced objects,
  41. // and does NOT delete() them on removal or destruction of the container.
  42. //
  43. // Note that operations are generally not optimized, and may of them
  44. // are O(n) complexity.
  45. //------------------------------------------------------------------------
  46. #include <iostream>
  47. template<class INDEX_TYPE, class VALUE_TYPE>
  48. class LLAssocList
  49. {
  50. private:
  51. // internal list node type
  52. class Node
  53. {
  54. public:
  55. Node(const INDEX_TYPE &index, const VALUE_TYPE &value, Node *next)
  56. {
  57. mIndex = index;
  58. mValue = value;
  59. mNext = next;
  60. }
  61. ~Node() { }
  62. INDEX_TYPE mIndex;
  63. VALUE_TYPE mValue;
  64. Node *mNext;
  65. };
  66. // head of the linked list
  67. Node *mHead;
  68. public:
  69. // Constructor
  70. LLAssocList()
  71. {
  72. mHead = NULL;
  73. }
  74. // Destructor
  75. ~LLAssocList()
  76. {
  77. removeAll();
  78. }
  79. // Returns TRUE if list is empty.
  80. BOOL isEmpty()
  81. {
  82. return (mHead == NULL);
  83. }
  84. // Returns the number of items in the list.
  85. U32 length()
  86. {
  87. U32 count = 0;
  88. for ( Node *node = mHead;
  89. node;
  90. node = node->mNext )
  91. {
  92. count++;
  93. }
  94. return count;
  95. }
  96. // Removes item with the specified index.
  97. BOOL remove( const INDEX_TYPE &index )
  98. {
  99. if (!mHead)
  100. return FALSE;
  101. if (mHead->mIndex == index)
  102. {
  103. Node *node = mHead;
  104. mHead = mHead->mNext;
  105. delete node;
  106. return TRUE;
  107. }
  108. for ( Node *prev = mHead;
  109. prev->mNext;
  110. prev = prev->mNext )
  111. {
  112. if (prev->mNext->mIndex == index)
  113. {
  114. Node *node = prev->mNext;
  115. prev->mNext = prev->mNext->mNext;
  116. delete node;
  117. return TRUE;
  118. }
  119. }
  120. return FALSE;
  121. }
  122. // Removes all items from the list.
  123. void removeAll()
  124. {
  125. while ( mHead )
  126. {
  127. Node *node = mHead;
  128. mHead = mHead->mNext;
  129. delete node;
  130. }
  131. }
  132. // Adds a new item to the head of the list,
  133. // removing any existing item with same index.
  134. void addToHead( const INDEX_TYPE &index, const VALUE_TYPE &value )
  135. {
  136. remove(index);
  137. Node *node = new Node(index, value, mHead);
  138. mHead = node;
  139. }
  140. // Adds a new item to the end of the list,
  141. // removing any existing item with the same index.
  142. void addToTail( const INDEX_TYPE &index, const VALUE_TYPE &value )
  143. {
  144. remove(index);
  145. Node *node = new Node(index, value, NULL);
  146. if (!mHead)
  147. {
  148. mHead = node;
  149. return;
  150. }
  151. for ( Node *prev=mHead;
  152. prev;
  153. prev=prev->mNext )
  154. {
  155. if (!prev->mNext)
  156. {
  157. prev->mNext=node;
  158. return;
  159. }
  160. }
  161. }
  162. // Sets the value of a specified index.
  163. // If index does not exist, a new value will be added only if
  164. // 'addIfNotFound' is set to TRUE.
  165. // Returns TRUE if successful.
  166. BOOL setValue( const INDEX_TYPE &index, const VALUE_TYPE &value, BOOL addIfNotFound=FALSE )
  167. {
  168. VALUE_TYPE *valueP = getValue(index);
  169. if (valueP)
  170. {
  171. *valueP = value;
  172. return TRUE;
  173. }
  174. if (!addIfNotFound)
  175. return FALSE;
  176. addToTail(index, value);
  177. return TRUE;
  178. }
  179. // Sets the ith value in the list.
  180. // A new value will NOT be addded, if the ith value does not exist.
  181. // Returns TRUE if successful.
  182. BOOL setValueAt( U32 i, const VALUE_TYPE &value )
  183. {
  184. VALUE_TYPE *valueP = getValueAt(i);
  185. if (valueP)
  186. {
  187. *valueP = value;
  188. return TRUE;
  189. }
  190. return FALSE;
  191. }
  192. // Returns a pointer to the value for the specified index,
  193. // or NULL if no item found.
  194. VALUE_TYPE *getValue( const INDEX_TYPE &index )
  195. {
  196. for ( Node *node = mHead;
  197. node;
  198. node = node->mNext )
  199. {
  200. if (node->mIndex == index)
  201. return &node->mValue;
  202. }
  203. return NULL;
  204. }
  205. // Returns a pointer to the ith value in the list, or
  206. // NULL if i is not valid.
  207. VALUE_TYPE *getValueAt( U32 i )
  208. {
  209. U32 count = 0;
  210. for ( Node *node = mHead;
  211. node;
  212. node = node->mNext )
  213. {
  214. if (count == i)
  215. return &node->mValue;
  216. count++;
  217. }
  218. return NULL;
  219. }
  220. // Returns a pointer to the index for the specified index,
  221. // or NULL if no item found.
  222. INDEX_TYPE *getIndex( const INDEX_TYPE &index )
  223. {
  224. for ( Node *node = mHead;
  225. node;
  226. node = node->mNext )
  227. {
  228. if (node->mIndex == index)
  229. return &node->mIndex;
  230. }
  231. return NULL;
  232. }
  233. // Returns a pointer to the ith index in the list, or
  234. // NULL if i is not valid.
  235. INDEX_TYPE *getIndexAt( U32 i )
  236. {
  237. U32 count = 0;
  238. for ( Node *node = mHead;
  239. node;
  240. node = node->mNext )
  241. {
  242. if (count == i)
  243. return &node->mIndex;
  244. count++;
  245. }
  246. return NULL;
  247. }
  248. // Returns a pointer to the value for the specified index,
  249. // or NULL if no item found.
  250. VALUE_TYPE *operator[](const INDEX_TYPE &index)
  251. {
  252. return getValue(index);
  253. }
  254. // Returns a pointer to the ith value in the list, or
  255. // NULL if i is not valid.
  256. VALUE_TYPE *operator[](U32 i)
  257. {
  258. return getValueAt(i);
  259. }
  260. // Prints the list contents to the specified stream.
  261. friend std::ostream &operator<<( std::ostream &os, LLAssocList &map )
  262. {
  263. os << "{";
  264. for ( Node *node = map.mHead;
  265. node;
  266. node = node->mNext )
  267. {
  268. os << "<" << node->mIndex << ", " << node->mValue << ">";
  269. if (node->mNext)
  270. os << ", ";
  271. }
  272. os << "}";
  273. return os;
  274. }
  275. };
  276. #endif // LL_LLASSOCLIST_H