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

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file llstl.h
  3.  * @brief helper object & functions for use with the stl.
  4.  *
  5.  * $LicenseInfo:firstyear=2003&license=viewergpl$
  6.  * 
  7.  * Copyright (c) 2003-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_LLSTL_H
  33. #define LL_LLSTL_H
  34. #include <functional>
  35. #include <algorithm>
  36. #include <map>
  37. #include <vector>
  38. #include <set>
  39. #include <deque>
  40. // Use to compare the first element only of a pair
  41. // e.g. typedef std::set<std::pair<int, Data*>, compare_pair<int, Data*> > some_pair_set_t; 
  42. template <typename T1, typename T2>
  43. struct compare_pair_first
  44. {
  45. bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
  46. {
  47. return a.first < b.first;
  48. }
  49. };
  50. template <typename T1, typename T2>
  51. struct compare_pair_greater
  52. {
  53. bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
  54. {
  55. if (!(a.first < b.first))
  56. return true;
  57. else if (!(b.first < a.first))
  58. return false;
  59. else
  60. return !(a.second < b.second);
  61. }
  62. };
  63. // Use to compare the contents of two pointers (e.g. std::string*)
  64. template <typename T>
  65. struct compare_pointer_contents
  66. {
  67. typedef const T* Tptr;
  68. bool operator()(const Tptr& a, const Tptr& b) const
  69. {
  70. return *a < *b;
  71. }
  72. };
  73. // DeletePointer is a simple helper for deleting all pointers in a container.
  74. // The general form is:
  75. //
  76. //  std::for_each(cont.begin(), cont.end(), DeletePointer());
  77. //  somemap.clear();
  78. //
  79. // Don't forget to clear()!
  80. struct DeletePointer
  81. {
  82. template<typename T> void operator()(T* ptr) const
  83. {
  84. delete ptr;
  85. }
  86. };
  87. struct DeletePointerArray
  88. {
  89. template<typename T> void operator()(T* ptr) const
  90. {
  91. delete[] ptr;
  92. }
  93. };
  94. // DeletePairedPointer is a simple helper for deleting all pointers in a map.
  95. // The general form is:
  96. //
  97. //  std::for_each(somemap.begin(), somemap.end(), DeletePairedPointer());
  98. struct DeletePairedPointer
  99. {
  100. template<typename T> void operator()(T &ptr) const
  101. {
  102. delete ptr.second;
  103. ptr.second = NULL;
  104. }
  105. };
  106. struct DeletePairedPointerArray
  107. {
  108. template<typename T> void operator()(T &ptr) const
  109. {
  110. delete[] ptr.second;
  111. ptr.second = NULL;
  112. }
  113. };
  114. // Alternate version of the above so that has a more cumbersome
  115. // syntax, but it can be used with compositional functors.
  116. // NOTE: The functor retuns a bool because msdev bombs during the
  117. // composition if you return void. Once we upgrade to a newer
  118. // compiler, the second unary_function template parameter can be set
  119. // to void.
  120. //
  121. // Here's a snippit showing how you use this object:
  122. //
  123. // typedef std::map<int, widget*> map_type;
  124. // map_type widget_map;
  125. // ... // add elements
  126. // // delete them all
  127. // for_each(widget_map.begin(),
  128. //          widget_map.end(),
  129. //          llcompose1(DeletePointerFunctor<widget>(),
  130. //                     llselect2nd<map_type::value_type>()));
  131. template<typename T>
  132. struct DeletePointerFunctor : public std::unary_function<T*, bool>
  133. {
  134. bool operator()(T* ptr) const
  135. {
  136. delete ptr;
  137. return true;
  138. }
  139. };
  140. // See notes about DeleteArray for why you should consider avoiding this.
  141. template<typename T>
  142. struct DeleteArrayFunctor : public std::unary_function<T*, bool>
  143. {
  144. bool operator()(T* ptr) const
  145. {
  146. delete[] ptr;
  147. return true;
  148. }
  149. };
  150. // CopyNewPointer is a simple helper which accepts a pointer, and
  151. // returns a new pointer built with the copy constructor. Example:
  152. //
  153. //  transform(in.begin(), in.end(), out.end(), CopyNewPointer());
  154. struct CopyNewPointer
  155. {
  156. template<typename T> T* operator()(const T* ptr) const
  157. {
  158. return new T(*ptr);
  159. }
  160. };
  161. // Simple function to help with finding pointers in maps.
  162. // For example:
  163. //  typedef  map_t;
  164. //  std::map<int, const char*> foo;
  165. // foo[18] = "there";
  166. // foo[2] = "hello";
  167. //  const char* bar = get_ptr_in_map(foo, 2); // bar -> "hello"
  168. //  const char* baz = get_ptr_in_map(foo, 3); // baz == NULL
  169. template <typename K, typename T>
  170. inline T* get_ptr_in_map(const std::map<K,T*>& inmap, const K& key)
  171. {
  172. // Typedef here avoids warnings because of new c++ naming rules.
  173. typedef typename std::map<K,T*>::const_iterator map_iter;
  174. map_iter iter = inmap.find(key);
  175. if(iter == inmap.end())
  176. {
  177. return NULL;
  178. }
  179. else
  180. {
  181. return iter->second;
  182. }
  183. };
  184. // helper function which returns true if key is in inmap.
  185. template <typename K, typename T>
  186. inline bool is_in_map(const std::map<K,T>& inmap, const K& key)
  187. {
  188. typedef typename std::map<K,T>::const_iterator map_iter;
  189. if(inmap.find(key) == inmap.end())
  190. {
  191. return false;
  192. }
  193. else
  194. {
  195. return true;
  196. }
  197. }
  198. // Similar to get_ptr_in_map, but for any type with a valid T(0) constructor.
  199. // To replace LLSkipMap getIfThere, use:
  200. //   get_if_there(map, key, 0)
  201. // WARNING: Make sure default_value (generally 0) is not a valid map entry!
  202. template <typename K, typename T>
  203. inline T get_if_there(const std::map<K,T>& inmap, const K& key, T default_value)
  204. {
  205. // Typedef here avoids warnings because of new c++ naming rules.
  206. typedef typename std::map<K,T>::const_iterator map_iter;
  207. map_iter iter = inmap.find(key);
  208. if(iter == inmap.end())
  209. {
  210. return default_value;
  211. }
  212. else
  213. {
  214. return iter->second;
  215. }
  216. };
  217. // Useful for replacing the removeObj() functionality of LLDynamicArray
  218. // Example:
  219. //  for (std::vector<T>::iterator iter = mList.begin(); iter != mList.end(); )
  220. //  {
  221. //    if ((*iter)->isMarkedForRemoval())
  222. //      iter = vector_replace_with_last(mList, iter);
  223. //    else
  224. //      ++iter;
  225. //  }
  226. template <typename T, typename Iter>
  227. inline Iter vector_replace_with_last(std::vector<T>& invec, Iter iter)
  228. {
  229. typename std::vector<T>::iterator last = invec.end(); --last;
  230. if (iter == invec.end())
  231. {
  232. return iter;
  233. }
  234. else if (iter == last)
  235. {
  236. invec.pop_back();
  237. return invec.end();
  238. }
  239. else
  240. {
  241. *iter = *last;
  242. invec.pop_back();
  243. return iter;
  244. }
  245. };
  246. // Useful for replacing the removeObj() functionality of LLDynamicArray
  247. // Example:
  248. //   vector_replace_with_last(mList, x);
  249. template <typename T>
  250. inline bool vector_replace_with_last(std::vector<T>& invec, const T& val)
  251. {
  252. typename std::vector<T>::iterator iter = std::find(invec.begin(), invec.end(), val);
  253. if (iter != invec.end())
  254. {
  255. typename std::vector<T>::iterator last = invec.end(); --last;
  256. *iter = *last;
  257. invec.pop_back();
  258. return true;
  259. }
  260. return false;
  261. }
  262. // Append N elements to the vector and return a pointer to the first new element.
  263. template <typename T>
  264. inline T* vector_append(std::vector<T>& invec, S32 N)
  265. {
  266. U32 sz = invec.size();
  267. invec.resize(sz+N);
  268. return &(invec[sz]);
  269. }
  270. // call function f to n members starting at first. similar to std::for_each
  271. template <class InputIter, class Size, class Function>
  272. Function ll_for_n(InputIter first, Size n, Function f)
  273. {
  274. for ( ; n > 0; --n, ++first)
  275. f(*first);
  276. return f;
  277. }
  278. // copy first to result n times, incrementing each as we go
  279. template <class InputIter, class Size, class OutputIter>
  280. OutputIter ll_copy_n(InputIter first, Size n, OutputIter result)
  281. {
  282. for ( ; n > 0; --n, ++result, ++first)
  283. *result = *first;
  284. return result;
  285. }
  286. // set  *result = op(*f) for n elements of f
  287. template <class InputIter, class OutputIter, class Size, class UnaryOp>
  288. OutputIter ll_transform_n(
  289. InputIter first,
  290. Size n,
  291. OutputIter result,
  292. UnaryOp op)
  293. {
  294. for ( ; n > 0; --n, ++result, ++first)
  295. *result = op(*first);
  296. return result;
  297. }
  298. /*
  299.  *
  300.  * Copyright (c) 1994
  301.  * Hewlett-Packard Company
  302.  *
  303.  * Permission to use, copy, modify, distribute and sell this software
  304.  * and its documentation for any purpose is hereby granted without fee,
  305.  * provided that the above copyright notice appear in all copies and
  306.  * that both that copyright notice and this permission notice appear
  307.  * in supporting documentation.  Hewlett-Packard Company makes no
  308.  * representations about the suitability of this software for any
  309.  * purpose.  It is provided "as is" without express or implied warranty.
  310.  *
  311.  *
  312.  * Copyright (c) 1996-1998
  313.  * Silicon Graphics Computer Systems, Inc.
  314.  *
  315.  * Permission to use, copy, modify, distribute and sell this software
  316.  * and its documentation for any purpose is hereby granted without fee,
  317.  * provided that the above copyright notice appear in all copies and
  318.  * that both that copyright notice and this permission notice appear
  319.  * in supporting documentation.  Silicon Graphics makes no
  320.  * representations about the suitability of this software for any
  321.  * purpose.  It is provided "as is" without express or implied warranty.
  322.  */
  323. // helper to deal with the fact that MSDev does not package
  324. // select... with the stl. Look up usage on the sgi website.
  325. template <class _Pair>
  326. struct _LLSelect1st : public std::unary_function<_Pair, typename _Pair::first_type> {
  327.   const typename _Pair::first_type& operator()(const _Pair& __x) const {
  328.     return __x.first;
  329.   }
  330. };
  331. template <class _Pair>
  332. struct _LLSelect2nd : public std::unary_function<_Pair, typename _Pair::second_type>
  333. {
  334.   const typename _Pair::second_type& operator()(const _Pair& __x) const {
  335.     return __x.second;
  336.   }
  337. };
  338. template <class _Pair> struct llselect1st : public _LLSelect1st<_Pair> {};
  339. template <class _Pair> struct llselect2nd : public _LLSelect2nd<_Pair> {};
  340. // helper to deal with the fact that MSDev does not package
  341. // compose... with the stl. Look up usage on the sgi website.
  342. template <class _Operation1, class _Operation2>
  343. class ll_unary_compose :
  344. public std::unary_function<typename _Operation2::argument_type,
  345.    typename _Operation1::result_type>
  346. {
  347. protected:
  348.   _Operation1 __op1;
  349.   _Operation2 __op2;
  350. public:
  351.   ll_unary_compose(const _Operation1& __x, const _Operation2& __y)
  352.     : __op1(__x), __op2(__y) {}
  353.   typename _Operation1::result_type
  354.   operator()(const typename _Operation2::argument_type& __x) const {
  355.     return __op1(__op2(__x));
  356.   }
  357. };
  358. template <class _Operation1, class _Operation2>
  359. inline ll_unary_compose<_Operation1,_Operation2>
  360. llcompose1(const _Operation1& __op1, const _Operation2& __op2)
  361. {
  362.   return ll_unary_compose<_Operation1,_Operation2>(__op1, __op2);
  363. }
  364. template <class _Operation1, class _Operation2, class _Operation3>
  365. class ll_binary_compose
  366.   : public std::unary_function<typename _Operation2::argument_type,
  367.    typename _Operation1::result_type> {
  368. protected:
  369.   _Operation1 _M_op1;
  370.   _Operation2 _M_op2;
  371.   _Operation3 _M_op3;
  372. public:
  373.   ll_binary_compose(const _Operation1& __x, const _Operation2& __y,
  374. const _Operation3& __z)
  375.     : _M_op1(__x), _M_op2(__y), _M_op3(__z) { }
  376.   typename _Operation1::result_type
  377.   operator()(const typename _Operation2::argument_type& __x) const {
  378.     return _M_op1(_M_op2(__x), _M_op3(__x));
  379.   }
  380. };
  381. template <class _Operation1, class _Operation2, class _Operation3>
  382. inline ll_binary_compose<_Operation1, _Operation2, _Operation3>
  383. llcompose2(const _Operation1& __op1, const _Operation2& __op2,
  384.          const _Operation3& __op3)
  385. {
  386.   return ll_binary_compose<_Operation1,_Operation2,_Operation3>
  387.     (__op1, __op2, __op3);
  388. }
  389. // helpers to deal with the fact that MSDev does not package
  390. // bind... with the stl. Again, this is from sgi.
  391. template <class _Operation>
  392. class llbinder1st :
  393. public std::unary_function<typename _Operation::second_argument_type,
  394.    typename _Operation::result_type> {
  395. protected:
  396.   _Operation op;
  397.   typename _Operation::first_argument_type value;
  398. public:
  399.   llbinder1st(const _Operation& __x,
  400.   const typename _Operation::first_argument_type& __y)
  401.       : op(__x), value(__y) {}
  402. typename _Operation::result_type
  403. operator()(const typename _Operation::second_argument_type& __x) const {
  404. return op(value, __x);
  405. }
  406. };
  407. template <class _Operation, class _Tp>
  408. inline llbinder1st<_Operation>
  409. llbind1st(const _Operation& __oper, const _Tp& __x)
  410. {
  411.   typedef typename _Operation::first_argument_type _Arg1_type;
  412.   return llbinder1st<_Operation>(__oper, _Arg1_type(__x));
  413. }
  414. template <class _Operation>
  415. class llbinder2nd
  416. : public std::unary_function<typename _Operation::first_argument_type,
  417.  typename _Operation::result_type> {
  418. protected:
  419. _Operation op;
  420. typename _Operation::second_argument_type value;
  421. public:
  422. llbinder2nd(const _Operation& __x,
  423. const typename _Operation::second_argument_type& __y)
  424. : op(__x), value(__y) {}
  425. typename _Operation::result_type
  426. operator()(const typename _Operation::first_argument_type& __x) const {
  427. return op(__x, value);
  428. }
  429. };
  430. template <class _Operation, class _Tp>
  431. inline llbinder2nd<_Operation>
  432. llbind2nd(const _Operation& __oper, const _Tp& __x)
  433. {
  434.   typedef typename _Operation::second_argument_type _Arg2_type;
  435.   return llbinder2nd<_Operation>(__oper, _Arg2_type(__x));
  436. }
  437. #endif // LL_LLSTL_H