_algo.c 74 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040
  1. /*
  2. *
  3. * Copyright (c) 1994
  4. * Hewlett-Packard Company
  5. *
  6. * Copyright (c) 1996,1997
  7. * Silicon Graphics Computer Systems, Inc.
  8. *
  9. * Copyright (c) 1997
  10. * Moscow Center for SPARC Technology
  11. *
  12. * Copyright (c) 1999
  13. * Boris Fomitchev
  14. *
  15. * This material is provided "as is", with absolutely no warranty expressed
  16. * or implied. Any use is at your own risk.
  17. *
  18. * Permission to use or copy this software for any purpose is hereby granted
  19. * without fee, provided the above notices are retained on all copies.
  20. * Permission to modify the code and to distribute modified code is granted,
  21. * provided the above notices are retained, and a notice that the code was
  22. * modified is included with the above copyright notice.
  23. *
  24. */
  25. #ifndef _STLP_ALGO_C
  26. #define _STLP_ALGO_C
  27. #if !defined (_STLP_INTERNAL_ALGO_H)
  28. # include <stl/_algo.h>
  29. #endif
  30. #ifndef _STLP_INTERNAL_TEMPBUF_H
  31. # include <stl/_tempbuf.h>
  32. #endif
  33. #ifdef _STLP_SGX_CONFIG
  34. # include "sgx_trts.h"
  35. #endif
  36. _STLP_BEGIN_NAMESPACE
  37. _STLP_MOVE_TO_PRIV_NAMESPACE
  38. template <class _BidirectionalIter, class _Distance, class _Compare>
  39. void __merge_without_buffer(_BidirectionalIter __first,
  40. _BidirectionalIter __middle,
  41. _BidirectionalIter __last,
  42. _Distance __len1, _Distance __len2,
  43. _Compare __comp);
  44. template <class _BidirectionalIter1, class _BidirectionalIter2,
  45. class _BidirectionalIter3, class _Compare>
  46. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  47. _BidirectionalIter1 __last1,
  48. _BidirectionalIter2 __first2,
  49. _BidirectionalIter2 __last2,
  50. _BidirectionalIter3 __result,
  51. _Compare __comp);
  52. template <class _Tp>
  53. #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  54. inline
  55. #endif
  56. const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  57. if (__a < __b)
  58. if (__b < __c)
  59. return __b;
  60. else if (__a < __c)
  61. return __c;
  62. else
  63. return __a;
  64. else if (__a < __c)
  65. return __a;
  66. else if (__b < __c)
  67. return __c;
  68. else
  69. return __b;
  70. }
  71. template <class _Tp, class _Compare>
  72. #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  73. inline
  74. #endif
  75. const _Tp&
  76. __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
  77. if (__comp(__a, __b)) {
  78. _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  79. if (__comp(__b, __c)) {
  80. _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  81. return __b;
  82. }
  83. else if (__comp(__a, __c)) {
  84. _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  85. return __c;
  86. }
  87. else
  88. return __a;
  89. }
  90. else if (__comp(__a, __c)) {
  91. _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  92. return __a;
  93. }
  94. else if (__comp(__b, __c)) {
  95. _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  96. return __c;
  97. }
  98. else
  99. return __b;
  100. }
  101. _STLP_MOVE_TO_STD_NAMESPACE
  102. template <class _ForwardIter1, class _ForwardIter2>
  103. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  104. _ForwardIter2 __first2, _ForwardIter2 __last2) {
  105. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  106. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  107. // Test for empty ranges
  108. if (__first1 == __last1 || __first2 == __last2)
  109. return __first1;
  110. // Test for a pattern of length 1.
  111. _ForwardIter2 __p1(__first2);
  112. if ( ++__p1 == __last2 )
  113. return find(__first1, __last1, *__first2);
  114. // General case.
  115. for ( ; ; ) { // __first1 != __last1 will be checked in find below
  116. __first1 = find(__first1, __last1, *__first2);
  117. if (__first1 == __last1)
  118. return __last1;
  119. _ForwardIter2 __p = __p1;
  120. _ForwardIter1 __current = __first1;
  121. if (++__current == __last1)
  122. return __last1;
  123. while (*__current == *__p) {
  124. if (++__p == __last2)
  125. return __first1;
  126. if (++__current == __last1)
  127. return __last1;
  128. }
  129. ++__first1;
  130. }
  131. return __first1;
  132. }
  133. _STLP_MOVE_TO_PRIV_NAMESPACE
  134. template <class _RandomAccessIter, class _Integer, class _Tp,
  135. class _BinaryPred, class _Distance>
  136. _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
  137. _Integer __count, const _Tp& __val, _BinaryPred __pred,
  138. _Distance*, const random_access_iterator_tag &)
  139. {
  140. _Distance __tailSize = __last - __first;
  141. const _Distance __pattSize = __count;
  142. const _Distance __skipOffset = __pattSize - 1;
  143. _RandomAccessIter __backTrack;
  144. _Distance __remainder, __prevRemainder;
  145. for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
  146. //__lookAhead here is always pointing to the last element of next possible match.
  147. __tailSize -= __pattSize;
  148. while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
  149. if (__tailSize < __pattSize)
  150. return __last;
  151. __lookAhead += __pattSize;
  152. __tailSize -= __pattSize;
  153. }
  154. if ( __skipOffset == 0 ) {
  155. return (__lookAhead - __skipOffset); //Success
  156. }
  157. __remainder = __skipOffset;
  158. for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
  159. if (--__remainder == 0)
  160. return (__lookAhead - __skipOffset); //Success
  161. }
  162. if (__remainder > __tailSize)
  163. return __last; //failure
  164. __lookAhead += __remainder;
  165. __tailSize -= __remainder;
  166. while ( __pred(*__lookAhead, __val) ) {
  167. __prevRemainder = __remainder;
  168. __backTrack = __lookAhead;
  169. do {
  170. if (--__remainder == 0)
  171. return (__lookAhead - __skipOffset); //Success
  172. } while (__pred(*--__backTrack, __val));
  173. //adjust remainder for next comparison
  174. __remainder += __pattSize - __prevRemainder;
  175. if (__remainder > __tailSize)
  176. return __last; //failure
  177. __lookAhead += __remainder;
  178. __tailSize -= __remainder;
  179. }
  180. //__lookAhead here is always pointing to the element of the last mismatch.
  181. }
  182. return __last; //failure
  183. }
  184. template <class _ForwardIter, class _Integer, class _Tp,
  185. class _Distance, class _BinaryPred>
  186. _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
  187. _Integer __count, const _Tp& __val, _BinaryPred __pred,
  188. _Distance*, const forward_iterator_tag &) {
  189. for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
  190. while (__first != __last) {
  191. _Integer __n = __count - 1;
  192. _ForwardIter __i = __first;
  193. ++__i;
  194. while (__i != __last && __n != 0 && __pred(*__i, __val)) {
  195. ++__i;
  196. --__n;
  197. }
  198. if (__n == 0)
  199. return __first;
  200. else if (__i != __last)
  201. for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
  202. else
  203. break;
  204. }
  205. return __last;
  206. }
  207. _STLP_MOVE_TO_STD_NAMESPACE
  208. // search_n. Search for __count consecutive copies of __val.
  209. template <class _ForwardIter, class _Integer, class _Tp>
  210. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  211. _Integer __count, const _Tp& __val) {
  212. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  213. if (__count <= 0)
  214. return __first;
  215. if (__count == 1)
  216. //We use find when __count == 1 to use potential find overload.
  217. return find(__first, __last, __val);
  218. return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
  219. _STLP_DISTANCE_TYPE(__first, _ForwardIter),
  220. _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  221. }
  222. template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
  223. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  224. _Integer __count, const _Tp& __val,
  225. _BinaryPred __binary_pred) {
  226. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  227. if (__count <= 0)
  228. return __first;
  229. return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
  230. _STLP_DISTANCE_TYPE(__first, _ForwardIter),
  231. _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  232. }
  233. template <class _ForwardIter1, class _ForwardIter2>
  234. _ForwardIter1
  235. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  236. _ForwardIter2 __first2, _ForwardIter2 __last2) {
  237. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  238. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  239. return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
  240. #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
  241. _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
  242. _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
  243. #else
  244. forward_iterator_tag(),
  245. forward_iterator_tag(),
  246. #endif
  247. _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
  248. );
  249. }
  250. // unique and unique_copy
  251. _STLP_MOVE_TO_PRIV_NAMESPACE
  252. template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
  253. class _Tp>
  254. _STLP_INLINE_LOOP _OutputIterator
  255. __unique_copy(_InputIterator __first, _InputIterator __last,
  256. _OutputIterator __result,
  257. _BinaryPredicate __binary_pred, _Tp*) {
  258. _Tp __val = *__first;
  259. *__result = __val;
  260. while (++__first != __last)
  261. if (!__binary_pred(__val, *__first)) {
  262. __val = *__first;
  263. *++__result = __val;
  264. }
  265. return ++__result;
  266. }
  267. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  268. inline _OutputIter
  269. __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  270. _BinaryPredicate __binary_pred, const output_iterator_tag &) {
  271. return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
  272. _STLP_VALUE_TYPE(__first, _InputIter));
  273. }
  274. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  275. _STLP_INLINE_LOOP _ForwardIter
  276. __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
  277. _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
  278. *__result = *__first;
  279. while (++__first != __last)
  280. if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  281. return ++__result;
  282. }
  283. #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  284. template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
  285. inline _BidirectionalIterator
  286. __unique_copy(_InputIterator __first, _InputIterator __last,
  287. _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
  288. const bidirectional_iterator_tag &) {
  289. return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
  290. }
  291. template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
  292. inline _RandomAccessIterator
  293. __unique_copy(_InputIterator __first, _InputIterator __last,
  294. _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
  295. const random_access_iterator_tag &) {
  296. return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
  297. }
  298. #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
  299. _STLP_MOVE_TO_STD_NAMESPACE
  300. template <class _InputIter, class _OutputIter>
  301. _OutputIter
  302. unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
  303. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  304. if (__first == __last) return __result;
  305. return _STLP_PRIV __unique_copy(__first, __last, __result,
  306. _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
  307. _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
  308. }
  309. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  310. _OutputIter
  311. unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  312. _BinaryPredicate __binary_pred) {
  313. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  314. if (__first == __last) return __result;
  315. return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
  316. _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
  317. }
  318. // rotate and rotate_copy, and their auxiliary functions
  319. _STLP_MOVE_TO_PRIV_NAMESPACE
  320. template <class _ForwardIter, class _Distance>
  321. _ForwardIter __rotate_aux(_ForwardIter __first,
  322. _ForwardIter __middle,
  323. _ForwardIter __last,
  324. _Distance*,
  325. const forward_iterator_tag &) {
  326. if (__first == __middle)
  327. return __last;
  328. if (__last == __middle)
  329. return __first;
  330. _ForwardIter __first2 = __middle;
  331. do {
  332. _STLP_STD::swap(*__first++, *__first2++);
  333. if (__first == __middle)
  334. __middle = __first2;
  335. } while (__first2 != __last);
  336. _ForwardIter __new_middle = __first;
  337. __first2 = __middle;
  338. while (__first2 != __last) {
  339. _STLP_STD::swap (*__first++, *__first2++);
  340. if (__first == __middle)
  341. __middle = __first2;
  342. else if (__first2 == __last)
  343. __first2 = __middle;
  344. }
  345. return __new_middle;
  346. }
  347. template <class _BidirectionalIter, class _Distance>
  348. _BidirectionalIter __rotate_aux(_BidirectionalIter __first,
  349. _BidirectionalIter __middle,
  350. _BidirectionalIter __last,
  351. _Distance*,
  352. const bidirectional_iterator_tag &) {
  353. if (__first == __middle)
  354. return __last;
  355. if (__last == __middle)
  356. return __first;
  357. _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag());
  358. _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag());
  359. while (__first != __middle && __middle != __last)
  360. _STLP_STD::swap(*__first++, *--__last);
  361. if (__first == __middle) {
  362. _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag());
  363. return __last;
  364. }
  365. else {
  366. _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag());
  367. return __first;
  368. }
  369. }
  370. // rotate and rotate_copy, and their auxiliary functions
  371. template <class _EuclideanRingElement>
  372. _STLP_INLINE_LOOP
  373. _EuclideanRingElement __gcd(_EuclideanRingElement __m,
  374. _EuclideanRingElement __n) {
  375. while (__n != 0) {
  376. _EuclideanRingElement __t = __m % __n;
  377. __m = __n;
  378. __n = __t;
  379. }
  380. return __m;
  381. }
  382. template <class _RandomAccessIter, class _Distance, class _Tp>
  383. _RandomAccessIter __rotate_aux(_RandomAccessIter __first,
  384. _RandomAccessIter __middle,
  385. _RandomAccessIter __last,
  386. _Distance *, _Tp *) {
  387. _Distance __n = __last - __first;
  388. _Distance __k = __middle - __first;
  389. _Distance __l = __n - __k;
  390. _RandomAccessIter __result = __first + (__last - __middle);
  391. if (__k == 0) /* __first == middle */
  392. return __last;
  393. if (__k == __l) {
  394. _STLP_STD::swap_ranges(__first, __middle, __middle);
  395. return __result;
  396. }
  397. _Distance __d = _STLP_PRIV __gcd(__n, __k);
  398. for (_Distance __i = 0; __i < __d; __i++) {
  399. _Tp __tmp = *__first;
  400. _RandomAccessIter __p = __first;
  401. if (__k < __l) {
  402. for (_Distance __j = 0; __j < __l/__d; __j++) {
  403. if (__p > __first + __l) {
  404. *__p = *(__p - __l);
  405. __p -= __l;
  406. }
  407. *__p = *(__p + __k);
  408. __p += __k;
  409. }
  410. }
  411. else {
  412. for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
  413. if (__p < __last - __k) {
  414. *__p = *(__p + __k);
  415. __p += __k;
  416. }
  417. *__p = * (__p - __l);
  418. __p -= __l;
  419. }
  420. }
  421. *__p = __tmp;
  422. ++__first;
  423. }
  424. return __result;
  425. }
  426. template <class _RandomAccessIter, class _Distance>
  427. inline _RandomAccessIter
  428. __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
  429. _Distance * __dis, const random_access_iterator_tag &) {
  430. return _STLP_PRIV __rotate_aux(__first, __middle, __last,
  431. __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
  432. }
  433. template <class _ForwardIter>
  434. _ForwardIter
  435. __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
  436. _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  437. _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  438. return __rotate_aux(__first, __middle, __last,
  439. _STLP_DISTANCE_TYPE(__first, _ForwardIter),
  440. _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  441. }
  442. _STLP_MOVE_TO_STD_NAMESPACE
  443. template <class _ForwardIter>
  444. void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
  445. _STLP_PRIV __rotate(__first, __middle, __last);
  446. }
  447. // Return a random number in the range [0, __n). This function encapsulates
  448. // whether we're using rand (part of the standard C library) or lrand48
  449. // (not standard, but a much better choice whenever it's available).
  450. _STLP_MOVE_TO_PRIV_NAMESPACE
  451. template <class _Distance>
  452. inline _Distance __random_number(_Distance __n) {
  453. #ifdef _STLP_NO_DRAND48
  454. # ifdef _STLP_SGX_CONFIG
  455. _Distance __rand;
  456. if (SGX_SUCCESS != sgx_read_rand(__REINTERPRET_CAST(unsigned char*, &__rand), sizeof(__rand))) {
  457. _STLP_ABORT();
  458. }
  459. return abs(__rand) % __n;
  460. # else
  461. return rand() % __n;
  462. # endif
  463. #else
  464. return lrand48() % __n;
  465. #endif
  466. }
  467. _STLP_MOVE_TO_STD_NAMESPACE
  468. template <class _RandomAccessIter>
  469. void random_shuffle(_RandomAccessIter __first,
  470. _RandomAccessIter __last) {
  471. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  472. if (__first == __last) return;
  473. for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  474. iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
  475. }
  476. template <class _RandomAccessIter, class _RandomNumberGenerator>
  477. void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
  478. _RandomNumberGenerator &__rand) {
  479. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  480. if (__first == __last) return;
  481. for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  482. iter_swap(__i, __first + __rand((__i - __first) + 1));
  483. }
  484. #if !defined (_STLP_NO_EXTENSIONS)
  485. // random_sample and random_sample_n (extensions, not part of the standard).
  486. template <class _ForwardIter, class _OutputIter, class _Distance>
  487. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  488. _OutputIter __out_ite, const _Distance __n) {
  489. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  490. _Distance __remaining = _STLP_STD::distance(__first, __last);
  491. _Distance __m = (min) (__n, __remaining);
  492. while (__m > 0) {
  493. if (_STLP_PRIV __random_number(__remaining) < __m) {
  494. *__out_ite = *__first;
  495. ++__out_ite;
  496. --__m;
  497. }
  498. --__remaining;
  499. ++__first;
  500. }
  501. return __out_ite;
  502. }
  503. template <class _ForwardIter, class _OutputIter, class _Distance,
  504. class _RandomNumberGenerator>
  505. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  506. _OutputIter __out_ite, const _Distance __n,
  507. _RandomNumberGenerator& __rand) {
  508. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  509. _Distance __remaining = _STLP_STD::distance(__first, __last);
  510. _Distance __m = (min) (__n, __remaining);
  511. while (__m > 0) {
  512. if (__rand(__remaining) < __m) {
  513. *__out_ite = *__first;
  514. ++__out_ite;
  515. --__m;
  516. }
  517. --__remaining;
  518. ++__first;
  519. }
  520. return __out_ite;
  521. }
  522. _STLP_MOVE_TO_PRIV_NAMESPACE
  523. template <class _InputIter, class _RandomAccessIter, class _Distance>
  524. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  525. _RandomAccessIter __out_ite,
  526. const _Distance __n) {
  527. _Distance __m = 0;
  528. _Distance __t = __n;
  529. for ( ; __first != __last && __m < __n; ++__m, ++__first)
  530. __out_ite[__m] = *__first;
  531. while (__first != __last) {
  532. ++__t;
  533. _Distance __M = __random_number(__t);
  534. if (__M < __n)
  535. __out_ite[__M] = *__first;
  536. ++__first;
  537. }
  538. return __out_ite + __m;
  539. }
  540. template <class _InputIter, class _RandomAccessIter,
  541. class _RandomNumberGenerator, class _Distance>
  542. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  543. _RandomAccessIter __out_ite,
  544. _RandomNumberGenerator& __rand,
  545. const _Distance __n) {
  546. _Distance __m = 0;
  547. _Distance __t = __n;
  548. for ( ; __first != __last && __m < __n; ++__m, ++__first)
  549. __out_ite[__m] = *__first;
  550. while (__first != __last) {
  551. ++__t;
  552. _Distance __M = __rand(__t);
  553. if (__M < __n)
  554. __out_ite[__M] = *__first;
  555. ++__first;
  556. }
  557. return __out_ite + __m;
  558. }
  559. _STLP_MOVE_TO_STD_NAMESPACE
  560. template <class _InputIter, class _RandomAccessIter>
  561. _RandomAccessIter
  562. random_sample(_InputIter __first, _InputIter __last,
  563. _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
  564. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  565. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
  566. return _STLP_PRIV __random_sample(__first, __last,
  567. __out_first, __out_last - __out_first);
  568. }
  569. template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
  570. _RandomAccessIter
  571. random_sample(_InputIter __first, _InputIter __last,
  572. _RandomAccessIter __out_first, _RandomAccessIter __out_last,
  573. _RandomNumberGenerator& __rand) {
  574. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  575. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
  576. return _STLP_PRIV __random_sample(__first, __last,
  577. __out_first, __rand,
  578. __out_last - __out_first);
  579. }
  580. #endif /* _STLP_NO_EXTENSIONS */
  581. // partition, stable_partition, and their auxiliary functions
  582. _STLP_MOVE_TO_PRIV_NAMESPACE
  583. template <class _ForwardIter, class _Predicate>
  584. _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
  585. _ForwardIter __last,
  586. _Predicate __pred,
  587. const forward_iterator_tag &) {
  588. if (__first == __last) return __first;
  589. while (__pred(*__first))
  590. if (++__first == __last) return __first;
  591. _ForwardIter __next = __first;
  592. while (++__next != __last) {
  593. if (__pred(*__next)) {
  594. _STLP_STD::swap(*__first, *__next);
  595. ++__first;
  596. }
  597. }
  598. return __first;
  599. }
  600. template <class _BidirectionalIter, class _Predicate>
  601. _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
  602. _BidirectionalIter __last,
  603. _Predicate __pred,
  604. const bidirectional_iterator_tag &) {
  605. for (;;) {
  606. for (;;) {
  607. if (__first == __last)
  608. return __first;
  609. else if (__pred(*__first))
  610. ++__first;
  611. else
  612. break;
  613. }
  614. --__last;
  615. for (;;) {
  616. if (__first == __last)
  617. return __first;
  618. else if (!__pred(*__last))
  619. --__last;
  620. else
  621. break;
  622. }
  623. iter_swap(__first, __last);
  624. ++__first;
  625. }
  626. }
  627. #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  628. template <class _BidirectionalIter, class _Predicate>
  629. inline
  630. _BidirectionalIter __partition(_BidirectionalIter __first,
  631. _BidirectionalIter __last,
  632. _Predicate __pred,
  633. const random_access_iterator_tag &) {
  634. return __partition(__first, __last, __pred, bidirectional_iterator_tag());
  635. }
  636. #endif
  637. _STLP_MOVE_TO_STD_NAMESPACE
  638. template <class _ForwardIter, class _Predicate>
  639. _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
  640. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  641. return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  642. }
  643. /* __pred_of_first: false if we know that __pred(*__first) is false,
  644. * true when we don't know the result of __pred(*__first).
  645. * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
  646. * false when we don't know the result of __pred(*--__last).
  647. */
  648. _STLP_MOVE_TO_PRIV_NAMESPACE
  649. template <class _ForwardIter, class _Predicate, class _Distance>
  650. _ForwardIter __inplace_stable_partition(_ForwardIter __first,
  651. _ForwardIter __last,
  652. _Predicate __pred, _Distance __len,
  653. bool __pred_of_first, bool __pred_of_before_last) {
  654. if (__len == 1)
  655. return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
  656. _ForwardIter __middle = __first;
  657. _Distance __half_len = __len / 2;
  658. _STLP_STD::advance(__middle, __half_len);
  659. return _STLP_PRIV __rotate(_STLP_PRIV __inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
  660. __middle,
  661. _STLP_PRIV __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
  662. }
  663. template <class _ForwardIter, class _Pointer, class _Predicate,
  664. class _Distance>
  665. _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
  666. _ForwardIter __last,
  667. _Predicate __pred, _Distance __len,
  668. _Pointer __buffer, _Distance __buffer_size,
  669. bool __pred_of_first, bool __pred_of_before_last) {
  670. if (__len <= __buffer_size) {
  671. _ForwardIter __result1 = __first;
  672. _Pointer __result2 = __buffer;
  673. if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
  674. *__result2 = *__first;
  675. ++__result2; ++__first; --__len;
  676. }
  677. for (; __first != __last ; ++__first, --__len) {
  678. if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
  679. ((__len != 1) && __pred(*__first))){
  680. *__result1 = *__first;
  681. ++__result1;
  682. }
  683. else {
  684. *__result2 = *__first;
  685. ++__result2;
  686. }
  687. }
  688. _STLP_STD::copy(__buffer, __result2, __result1);
  689. return __result1;
  690. }
  691. else {
  692. _ForwardIter __middle = __first;
  693. _Distance __half_len = __len / 2;
  694. _STLP_STD::advance(__middle, __half_len);
  695. return _STLP_PRIV __rotate(_STLP_PRIV __stable_partition_adaptive(__first, __middle, __pred,
  696. __half_len, __buffer, __buffer_size,
  697. __pred_of_first, false),
  698. __middle,
  699. _STLP_PRIV __stable_partition_adaptive(__middle, __last, __pred,
  700. __len - __half_len, __buffer, __buffer_size,
  701. true, __pred_of_before_last));
  702. }
  703. }
  704. template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
  705. inline _ForwardIter
  706. __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
  707. _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last) {
  708. _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
  709. _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
  710. return (__buf.size() > 0) ?
  711. __stable_partition_adaptive(__first, __last, __pred,
  712. _Distance(__buf.requested_size()),
  713. __buf.begin(), __buf.size(),
  714. false, __pred_of_before_last) :
  715. __inplace_stable_partition(__first, __last, __pred,
  716. _Distance(__buf.requested_size()),
  717. false, __pred_of_before_last);
  718. _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
  719. }
  720. template <class _ForwardIter, class _Predicate>
  721. _ForwardIter
  722. __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
  723. const forward_iterator_tag &) {
  724. return __stable_partition_aux_aux(__first, __last, __pred,
  725. _STLP_VALUE_TYPE(__first, _ForwardIter),
  726. _STLP_DISTANCE_TYPE(__first, _ForwardIter), false);
  727. }
  728. template <class _BidirectIter, class _Predicate>
  729. _BidirectIter
  730. __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
  731. const bidirectional_iterator_tag &) {
  732. for (--__last;;) {
  733. if (__first == __last)
  734. return __first;
  735. else if (!__pred(*__last))
  736. --__last;
  737. else
  738. break;
  739. }
  740. ++__last;
  741. //Here we know that __pred(*--__last) is true
  742. return __stable_partition_aux_aux(__first, __last, __pred,
  743. _STLP_VALUE_TYPE(__first, _BidirectIter),
  744. _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
  745. }
  746. #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  747. template <class _BidirectIter, class _Predicate>
  748. _BidirectIter
  749. __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
  750. const random_access_iterator_tag &) {
  751. return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
  752. }
  753. #endif
  754. _STLP_MOVE_TO_STD_NAMESPACE
  755. template <class _ForwardIter, class _Predicate>
  756. _ForwardIter
  757. stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
  758. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  759. for (;;) {
  760. if (__first == __last)
  761. return __first;
  762. else if (__pred(*__first))
  763. ++__first;
  764. else
  765. break;
  766. }
  767. return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
  768. _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  769. }
  770. _STLP_MOVE_TO_PRIV_NAMESPACE
  771. template <class _RandomAccessIter, class _Tp, class _Compare>
  772. _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
  773. _RandomAccessIter __last,
  774. _Tp __pivot, _Compare __comp) {
  775. for (;;) {
  776. while (__comp(*__first, __pivot)) {
  777. _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  778. ++__first;
  779. }
  780. --__last;
  781. while (__comp(__pivot, *__last)) {
  782. _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  783. --__last;
  784. }
  785. if (!(__first < __last))
  786. return __first;
  787. iter_swap(__first, __last);
  788. ++__first;
  789. }
  790. }
  791. // sort() and its auxiliary functions.
  792. #define __stl_threshold 16
  793. template <class _RandomAccessIter, class _Tp, class _Compare>
  794. void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
  795. _Compare __comp) {
  796. _RandomAccessIter __next = __last;
  797. --__next;
  798. while (__comp(__val, *__next)) {
  799. _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  800. *__last = *__next;
  801. __last = __next;
  802. --__next;
  803. }
  804. *__last = __val;
  805. }
  806. template <class _RandomAccessIter, class _Tp, class _Compare>
  807. inline void __linear_insert(_RandomAccessIter __first,
  808. _RandomAccessIter __last, _Tp __val, _Compare __comp) {
  809. //*TY 12/26/1998 - added __val as a paramter
  810. // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller
  811. if (__comp(__val, *__first)) {
  812. _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  813. copy_backward(__first, __last, __last + 1);
  814. *__first = __val;
  815. }
  816. else
  817. __unguarded_linear_insert(__last, __val, __comp);
  818. }
  819. template <class _RandomAccessIter, class _Tp, class _Compare>
  820. void __insertion_sort(_RandomAccessIter __first,
  821. _RandomAccessIter __last,
  822. _Tp *, _Compare __comp) {
  823. if (__first == __last) return;
  824. for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  825. __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val
  826. }
  827. template <class _RandomAccessIter, class _Tp, class _Compare>
  828. void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
  829. _RandomAccessIter __last,
  830. _Tp*, _Compare __comp) {
  831. for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  832. __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
  833. }
  834. template <class _RandomAccessIter, class _Compare>
  835. inline void __unguarded_insertion_sort(_RandomAccessIter __first,
  836. _RandomAccessIter __last,
  837. _Compare __comp) {
  838. __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  839. }
  840. template <class _RandomAccessIter, class _Compare>
  841. void __final_insertion_sort(_RandomAccessIter __first,
  842. _RandomAccessIter __last, _Compare __comp) {
  843. if (__last - __first > __stl_threshold) {
  844. __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  845. __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  846. }
  847. else
  848. __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  849. }
  850. template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
  851. void __introsort_loop(_RandomAccessIter __first,
  852. _RandomAccessIter __last, _Tp*,
  853. _Size __depth_limit, _Compare __comp) {
  854. while (__last - __first > __stl_threshold) {
  855. if (__depth_limit == 0) {
  856. partial_sort(__first, __last, __last, __comp);
  857. return;
  858. }
  859. --__depth_limit;
  860. _RandomAccessIter __cut =
  861. __unguarded_partition(__first, __last,
  862. _Tp(__median(*__first,
  863. *(__first + (__last - __first)/2),
  864. *(__last - 1), __comp)),
  865. __comp);
  866. __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
  867. __last = __cut;
  868. }
  869. }
  870. _STLP_MOVE_TO_STD_NAMESPACE
  871. template <class _RandomAccessIter>
  872. void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  873. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  874. if (__first != __last) {
  875. _STLP_PRIV __introsort_loop(__first, __last,
  876. _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  877. _STLP_PRIV __lg(__last - __first) * 2,
  878. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  879. _STLP_PRIV __final_insertion_sort(__first, __last,
  880. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  881. }
  882. }
  883. template <class _RandomAccessIter, class _Compare>
  884. void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
  885. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  886. if (__first != __last) {
  887. _STLP_PRIV __introsort_loop(__first, __last,
  888. _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  889. _STLP_PRIV __lg(__last - __first) * 2, __comp);
  890. _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
  891. }
  892. }
  893. // stable_sort() and its auxiliary functions.
  894. _STLP_MOVE_TO_PRIV_NAMESPACE
  895. template <class _RandomAccessIter, class _Compare>
  896. void __inplace_stable_sort(_RandomAccessIter __first,
  897. _RandomAccessIter __last, _Compare __comp) {
  898. if (__last - __first < 15) {
  899. __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  900. return;
  901. }
  902. _RandomAccessIter __middle = __first + (__last - __first) / 2;
  903. __inplace_stable_sort(__first, __middle, __comp);
  904. __inplace_stable_sort(__middle, __last, __comp);
  905. __merge_without_buffer(__first, __middle, __last,
  906. __middle - __first,
  907. __last - __middle,
  908. __comp);
  909. }
  910. template <class _RandomAccessIter1, class _RandomAccessIter2,
  911. class _Distance, class _Compare>
  912. void __merge_sort_loop(_RandomAccessIter1 __first,
  913. _RandomAccessIter1 __last,
  914. _RandomAccessIter2 __result, _Distance __step_size,
  915. _Compare __comp) {
  916. _Distance __two_step = 2 * __step_size;
  917. while (__last - __first >= __two_step) {
  918. __result = merge(__first, __first + __step_size,
  919. __first + __step_size, __first + __two_step,
  920. __result,
  921. __comp);
  922. __first += __two_step;
  923. }
  924. __step_size = (min) (_Distance(__last - __first), __step_size);
  925. merge(__first, __first + __step_size,
  926. __first + __step_size, __last,
  927. __result,
  928. __comp);
  929. }
  930. const int __stl_chunk_size = 7;
  931. template <class _RandomAccessIter, class _Distance, class _Compare>
  932. void __chunk_insertion_sort(_RandomAccessIter __first,
  933. _RandomAccessIter __last,
  934. _Distance __chunk_size, _Compare __comp) {
  935. while (__last - __first >= __chunk_size) {
  936. __insertion_sort(__first, __first + __chunk_size,
  937. _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  938. __first += __chunk_size;
  939. }
  940. __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  941. }
  942. template <class _RandomAccessIter, class _Pointer, class _Distance,
  943. class _Compare>
  944. void __merge_sort_with_buffer(_RandomAccessIter __first,
  945. _RandomAccessIter __last, _Pointer __buffer,
  946. _Distance*, _Compare __comp) {
  947. _Distance __len = __last - __first;
  948. _Pointer __buffer_last = __buffer + __len;
  949. _Distance __step_size = __stl_chunk_size;
  950. __chunk_insertion_sort(__first, __last, __step_size, __comp);
  951. while (__step_size < __len) {
  952. __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  953. __step_size *= 2;
  954. __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  955. __step_size *= 2;
  956. }
  957. }
  958. template <class _BidirectionalIter1, class _BidirectionalIter2,
  959. class _Distance>
  960. _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  961. _BidirectionalIter1 __middle,
  962. _BidirectionalIter1 __last,
  963. _Distance __len1, _Distance __len2,
  964. _BidirectionalIter2 __buffer,
  965. _Distance __buffer_size) {
  966. if (__len1 > __len2 && __len2 <= __buffer_size) {
  967. _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
  968. _STLP_STD::copy_backward(__first, __middle, __last);
  969. return _STLP_STD::copy(__buffer, __buffer_end, __first);
  970. }
  971. else if (__len1 <= __buffer_size) {
  972. _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
  973. _STLP_STD::copy(__middle, __last, __first);
  974. return _STLP_STD::copy_backward(__buffer, __buffer_end, __last);
  975. }
  976. else
  977. return _STLP_PRIV __rotate(__first, __middle, __last);
  978. }
  979. template <class _BidirectionalIter, class _Distance, class _Pointer,
  980. class _Compare>
  981. void __merge_adaptive(_BidirectionalIter __first,
  982. _BidirectionalIter __middle,
  983. _BidirectionalIter __last,
  984. _Distance __len1, _Distance __len2,
  985. _Pointer __buffer, _Distance __buffer_size,
  986. _Compare __comp) {
  987. if (__len1 <= __len2 && __len1 <= __buffer_size) {
  988. _Pointer __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
  989. _STLP_STD::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  990. }
  991. else if (__len2 <= __buffer_size) {
  992. _Pointer __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
  993. _STLP_PRIV __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  994. __comp);
  995. }
  996. else {
  997. _BidirectionalIter __first_cut = __first;
  998. _BidirectionalIter __second_cut = __middle;
  999. _Distance __len11 = 0;
  1000. _Distance __len22 = 0;
  1001. if (__len1 > __len2) {
  1002. __len11 = __len1 / 2;
  1003. _STLP_STD::advance(__first_cut, __len11);
  1004. __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp);
  1005. __len22 += _STLP_STD::distance(__middle, __second_cut);
  1006. }
  1007. else {
  1008. __len22 = __len2 / 2;
  1009. _STLP_STD::advance(__second_cut, __len22);
  1010. __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp);
  1011. __len11 += _STLP_STD::distance(__first, __first_cut);
  1012. }
  1013. _BidirectionalIter __new_middle =
  1014. __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  1015. __len22, __buffer, __buffer_size);
  1016. __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  1017. __len22, __buffer, __buffer_size, __comp);
  1018. __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  1019. __len2 - __len22, __buffer, __buffer_size, __comp);
  1020. }
  1021. }
  1022. template <class _RandomAccessIter, class _Pointer, class _Distance,
  1023. class _Compare>
  1024. void __stable_sort_adaptive(_RandomAccessIter __first,
  1025. _RandomAccessIter __last, _Pointer __buffer,
  1026. _Distance __buffer_size, _Compare __comp) {
  1027. _Distance __len = (__last - __first + 1) / 2;
  1028. _RandomAccessIter __middle = __first + __len;
  1029. if (__len > __buffer_size) {
  1030. __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
  1031. __comp);
  1032. __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
  1033. __comp);
  1034. }
  1035. else {
  1036. __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
  1037. __comp);
  1038. __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
  1039. __comp);
  1040. }
  1041. __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
  1042. _Distance(__last - __middle), __buffer, __buffer_size,
  1043. __comp);
  1044. }
  1045. template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
  1046. void __stable_sort_aux(_RandomAccessIter __first,
  1047. _RandomAccessIter __last, _Tp*, _Distance*,
  1048. _Compare __comp) {
  1049. _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  1050. if (buf.begin() == 0)
  1051. __inplace_stable_sort(__first, __last, __comp);
  1052. else
  1053. __stable_sort_adaptive(__first, __last, buf.begin(),
  1054. _Distance(buf.size()),
  1055. __comp);
  1056. }
  1057. _STLP_MOVE_TO_STD_NAMESPACE
  1058. template <class _RandomAccessIter>
  1059. void stable_sort(_RandomAccessIter __first,
  1060. _RandomAccessIter __last) {
  1061. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1062. _STLP_PRIV __stable_sort_aux(__first, __last,
  1063. _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1064. _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1065. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1066. }
  1067. template <class _RandomAccessIter, class _Compare>
  1068. void stable_sort(_RandomAccessIter __first,
  1069. _RandomAccessIter __last, _Compare __comp) {
  1070. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1071. _STLP_PRIV __stable_sort_aux(__first, __last,
  1072. _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1073. _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1074. __comp);
  1075. }
  1076. // partial_sort, partial_sort_copy, and auxiliary functions.
  1077. _STLP_MOVE_TO_PRIV_NAMESPACE
  1078. template <class _RandomAccessIter, class _Tp, class _Compare>
  1079. void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1080. _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1081. make_heap(__first, __middle, __comp);
  1082. for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
  1083. if (__comp(*__i, *__first)) {
  1084. _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1085. __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
  1086. _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
  1087. }
  1088. }
  1089. sort_heap(__first, __middle, __comp);
  1090. }
  1091. _STLP_MOVE_TO_STD_NAMESPACE
  1092. template <class _RandomAccessIter>
  1093. void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1094. _RandomAccessIter __last) {
  1095. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1096. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1097. _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1098. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1099. }
  1100. template <class _RandomAccessIter, class _Compare>
  1101. void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1102. _RandomAccessIter __last, _Compare __comp) {
  1103. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1104. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1105. _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1106. }
  1107. _STLP_MOVE_TO_PRIV_NAMESPACE
  1108. template <class _InputIter, class _RandomAccessIter, class _Compare,
  1109. class _Distance, class _Tp>
  1110. _RandomAccessIter __partial_sort_copy(_InputIter __first,
  1111. _InputIter __last,
  1112. _RandomAccessIter __result_first,
  1113. _RandomAccessIter __result_last,
  1114. _Compare __comp, _Distance*, _Tp*) {
  1115. if (__result_first == __result_last) return __result_last;
  1116. _RandomAccessIter __result_real_last = __result_first;
  1117. while(__first != __last && __result_real_last != __result_last) {
  1118. *__result_real_last = *__first;
  1119. ++__result_real_last;
  1120. ++__first;
  1121. }
  1122. make_heap(__result_first, __result_real_last, __comp);
  1123. while (__first != __last) {
  1124. if (__comp(*__first, *__result_first)) {
  1125. _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1126. __adjust_heap(__result_first, _Distance(0),
  1127. _Distance(__result_real_last - __result_first),
  1128. _Tp(*__first),
  1129. __comp);
  1130. }
  1131. ++__first;
  1132. }
  1133. sort_heap(__result_first, __result_real_last, __comp);
  1134. return __result_real_last;
  1135. }
  1136. _STLP_MOVE_TO_STD_NAMESPACE
  1137. template <class _InputIter, class _RandomAccessIter>
  1138. _RandomAccessIter
  1139. partial_sort_copy(_InputIter __first, _InputIter __last,
  1140. _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  1141. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1142. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  1143. return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
  1144. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
  1145. _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1146. _STLP_VALUE_TYPE(__first, _InputIter));
  1147. }
  1148. template <class _InputIter, class _RandomAccessIter, class _Compare>
  1149. _RandomAccessIter
  1150. partial_sort_copy(_InputIter __first, _InputIter __last,
  1151. _RandomAccessIter __result_first,
  1152. _RandomAccessIter __result_last, _Compare __comp) {
  1153. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1154. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  1155. return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
  1156. __comp,
  1157. _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1158. _STLP_VALUE_TYPE(__first, _InputIter));
  1159. }
  1160. // nth_element() and its auxiliary functions.
  1161. _STLP_MOVE_TO_PRIV_NAMESPACE
  1162. template <class _RandomAccessIter, class _Tp, class _Compare>
  1163. void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1164. _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1165. while (__last - __first > 3) {
  1166. _RandomAccessIter __cut =
  1167. __unguarded_partition(__first, __last,
  1168. _Tp(__median(*__first,
  1169. *(__first + (__last - __first)/2),
  1170. *(__last - 1),
  1171. __comp)),
  1172. __comp);
  1173. if (__cut <= __nth)
  1174. __first = __cut;
  1175. else
  1176. __last = __cut;
  1177. }
  1178. __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
  1179. }
  1180. _STLP_MOVE_TO_STD_NAMESPACE
  1181. template <class _RandomAccessIter>
  1182. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1183. _RandomAccessIter __last) {
  1184. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  1185. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  1186. _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1187. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1188. }
  1189. template <class _RandomAccessIter, class _Compare>
  1190. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1191. _RandomAccessIter __last, _Compare __comp) {
  1192. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  1193. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  1194. _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1195. }
  1196. // Binary search (lower_bound, upper_bound, equal_range, binary_search).
  1197. _STLP_MOVE_TO_PRIV_NAMESPACE
  1198. template <class _ForwardIter, class _Tp,
  1199. class _Compare1, class _Compare2, class _Distance>
  1200. _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1201. _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
  1202. _Distance __len = _STLP_STD::distance(__first, __last);
  1203. _Distance __half;
  1204. while (__len > 0) {
  1205. __half = __len >> 1;
  1206. _ForwardIter __middle = __first;
  1207. _STLP_STD::advance(__middle, __half);
  1208. if (__comp2(__val, *__middle)) {
  1209. _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1210. __len = __half;
  1211. }
  1212. else {
  1213. __first = __middle;
  1214. ++__first;
  1215. __len = __len - __half - 1;
  1216. }
  1217. }
  1218. return __first;
  1219. }
  1220. template <class _ForwardIter, class _Tp,
  1221. class _Compare1, class _Compare2, class _Distance>
  1222. pair<_ForwardIter, _ForwardIter>
  1223. __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1224. _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
  1225. _Distance __len = _STLP_STD::distance(__first, __last);
  1226. _Distance __half;
  1227. while (__len > 0) {
  1228. __half = __len >> 1;
  1229. _ForwardIter __middle = __first;
  1230. _STLP_STD::advance(__middle, __half);
  1231. if (__comp1(*__middle, __val)) {
  1232. _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1233. __first = __middle;
  1234. ++__first;
  1235. __len = __len - __half - 1;
  1236. }
  1237. else if (__comp2(__val, *__middle)) {
  1238. _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1239. __len = __half;
  1240. }
  1241. else {
  1242. _ForwardIter __left = _STLP_PRIV __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
  1243. //Small optim: If lower_bound haven't found an equivalent value
  1244. //there is no need to call upper_bound.
  1245. if (__comp1(*__left, __val)) {
  1246. _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1247. return pair<_ForwardIter, _ForwardIter>(__left, __left);
  1248. }
  1249. _STLP_STD::advance(__first, __len);
  1250. _ForwardIter __right = _STLP_PRIV __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
  1251. return pair<_ForwardIter, _ForwardIter>(__left, __right);
  1252. }
  1253. }
  1254. return pair<_ForwardIter, _ForwardIter>(__first, __first);
  1255. }
  1256. _STLP_MOVE_TO_STD_NAMESPACE
  1257. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1258. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1259. _InputIter2 __first2, _InputIter2 __last2,
  1260. _OutputIter __result) {
  1261. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1262. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1263. while (__first1 != __last1 && __first2 != __last2) {
  1264. if (*__first2 < *__first1) {
  1265. *__result = *__first2;
  1266. ++__first2;
  1267. }
  1268. else {
  1269. *__result = *__first1;
  1270. ++__first1;
  1271. }
  1272. ++__result;
  1273. }
  1274. return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
  1275. }
  1276. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1277. class _Compare>
  1278. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1279. _InputIter2 __first2, _InputIter2 __last2,
  1280. _OutputIter __result, _Compare __comp) {
  1281. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1282. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1283. while (__first1 != __last1 && __first2 != __last2) {
  1284. if (__comp(*__first2, *__first1)) {
  1285. _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1286. *__result = *__first2;
  1287. ++__first2;
  1288. }
  1289. else {
  1290. *__result = *__first1;
  1291. ++__first1;
  1292. }
  1293. ++__result;
  1294. }
  1295. return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
  1296. }
  1297. _STLP_MOVE_TO_PRIV_NAMESPACE
  1298. template <class _BidirectionalIter, class _Distance, class _Compare>
  1299. void __merge_without_buffer(_BidirectionalIter __first,
  1300. _BidirectionalIter __middle,
  1301. _BidirectionalIter __last,
  1302. _Distance __len1, _Distance __len2,
  1303. _Compare __comp) {
  1304. if (__len1 == 0 || __len2 == 0)
  1305. return;
  1306. if (__len1 + __len2 == 2) {
  1307. if (__comp(*__middle, *__first)) {
  1308. _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1309. iter_swap(__first, __middle);
  1310. }
  1311. return;
  1312. }
  1313. _BidirectionalIter __first_cut = __first;
  1314. _BidirectionalIter __second_cut = __middle;
  1315. _Distance __len11 = 0;
  1316. _Distance __len22 = 0;
  1317. if (__len1 > __len2) {
  1318. __len11 = __len1 / 2;
  1319. _STLP_STD::advance(__first_cut, __len11);
  1320. __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp);
  1321. __len22 += _STLP_STD::distance(__middle, __second_cut);
  1322. }
  1323. else {
  1324. __len22 = __len2 / 2;
  1325. _STLP_STD::advance(__second_cut, __len22);
  1326. __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp);
  1327. __len11 += _STLP_STD::distance(__first, __first_cut);
  1328. }
  1329. _BidirectionalIter __new_middle
  1330. = _STLP_PRIV __rotate(__first_cut, __middle, __second_cut);
  1331. __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  1332. __comp);
  1333. __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  1334. __len2 - __len22, __comp);
  1335. }
  1336. template <class _BidirectionalIter1, class _BidirectionalIter2,
  1337. class _BidirectionalIter3, class _Compare>
  1338. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  1339. _BidirectionalIter1 __last1,
  1340. _BidirectionalIter2 __first2,
  1341. _BidirectionalIter2 __last2,
  1342. _BidirectionalIter3 __result,
  1343. _Compare __comp) {
  1344. if (__first1 == __last1)
  1345. return copy_backward(__first2, __last2, __result);
  1346. if (__first2 == __last2)
  1347. return copy_backward(__first1, __last1, __result);
  1348. --__last1;
  1349. --__last2;
  1350. for (;;) {
  1351. if (__comp(*__last2, *__last1)) {
  1352. _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1353. *--__result = *__last1;
  1354. if (__first1 == __last1)
  1355. return copy_backward(__first2, ++__last2, __result);
  1356. --__last1;
  1357. }
  1358. else {
  1359. *--__result = *__last2;
  1360. if (__first2 == __last2)
  1361. return copy_backward(__first1, ++__last1, __result);
  1362. --__last2;
  1363. }
  1364. }
  1365. }
  1366. template <class _BidirectionalIter, class _Tp,
  1367. class _Distance, class _Compare>
  1368. inline void __inplace_merge_aux(_BidirectionalIter __first,
  1369. _BidirectionalIter __middle,
  1370. _BidirectionalIter __last, _Tp*, _Distance*,
  1371. _Compare __comp) {
  1372. _Distance __len1 = _STLP_STD::distance(__first, __middle);
  1373. _Distance __len2 = _STLP_STD::distance(__middle, __last);
  1374. _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  1375. if (__buf.begin() == 0)
  1376. __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  1377. else
  1378. __merge_adaptive(__first, __middle, __last, __len1, __len2,
  1379. __buf.begin(), _Distance(__buf.size()),
  1380. __comp);
  1381. }
  1382. _STLP_MOVE_TO_STD_NAMESPACE
  1383. template <class _BidirectionalIter>
  1384. void inplace_merge(_BidirectionalIter __first,
  1385. _BidirectionalIter __middle,
  1386. _BidirectionalIter __last) {
  1387. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1388. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1389. if (__first == __middle || __middle == __last)
  1390. return;
  1391. _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
  1392. _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1393. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1394. }
  1395. template <class _BidirectionalIter, class _Compare>
  1396. void inplace_merge(_BidirectionalIter __first,
  1397. _BidirectionalIter __middle,
  1398. _BidirectionalIter __last, _Compare __comp) {
  1399. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  1400. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  1401. if (__first == __middle || __middle == __last)
  1402. return;
  1403. _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
  1404. _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1405. __comp);
  1406. }
  1407. _STLP_MOVE_TO_PRIV_NAMESPACE
  1408. template <class _InputIter1, class _InputIter2, class _Compare>
  1409. bool __includes(_InputIter1 __first1, _InputIter1 __last1,
  1410. _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1411. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1412. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1413. while (__first1 != __last1 && __first2 != __last2)
  1414. if (__comp(*__first2, *__first1)) {
  1415. _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1416. return false;
  1417. }
  1418. else if (__comp(*__first1, *__first2))
  1419. ++__first1;
  1420. else
  1421. ++__first1, ++__first2;
  1422. return __first2 == __last2;
  1423. }
  1424. _STLP_MOVE_TO_STD_NAMESPACE
  1425. template <class _InputIter1, class _InputIter2, class _Compare>
  1426. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1427. _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1428. return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
  1429. }
  1430. template <class _InputIter1, class _InputIter2>
  1431. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1432. _InputIter2 __first2, _InputIter2 __last2) {
  1433. return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
  1434. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1435. }
  1436. _STLP_MOVE_TO_PRIV_NAMESPACE
  1437. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1438. class _Compare>
  1439. _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
  1440. _InputIter2 __first2, _InputIter2 __last2,
  1441. _OutputIter __result, _Compare __comp) {
  1442. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1443. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1444. while (__first1 != __last1 && __first2 != __last2) {
  1445. if (__comp(*__first1, *__first2)) {
  1446. _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1447. *__result = *__first1;
  1448. ++__first1;
  1449. }
  1450. else if (__comp(*__first2, *__first1)) {
  1451. _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1452. *__result = *__first2;
  1453. ++__first2;
  1454. }
  1455. else {
  1456. *__result = *__first1;
  1457. ++__first1;
  1458. ++__first2;
  1459. }
  1460. ++__result;
  1461. }
  1462. return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
  1463. }
  1464. _STLP_MOVE_TO_STD_NAMESPACE
  1465. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1466. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1467. _InputIter2 __first2, _InputIter2 __last2,
  1468. _OutputIter __result) {
  1469. return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
  1470. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1471. }
  1472. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1473. class _Compare>
  1474. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1475. _InputIter2 __first2, _InputIter2 __last2,
  1476. _OutputIter __result, _Compare __comp) {
  1477. return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
  1478. }
  1479. _STLP_MOVE_TO_PRIV_NAMESPACE
  1480. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1481. class _Compare>
  1482. _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1483. _InputIter2 __first2, _InputIter2 __last2,
  1484. _OutputIter __result, _Compare __comp) {
  1485. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1486. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1487. while (__first1 != __last1 && __first2 != __last2)
  1488. if (__comp(*__first1, *__first2)) {
  1489. _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1490. ++__first1;
  1491. }
  1492. else if (__comp(*__first2, *__first1))
  1493. ++__first2;
  1494. else {
  1495. *__result = *__first1;
  1496. ++__first1;
  1497. ++__first2;
  1498. ++__result;
  1499. }
  1500. return __result;
  1501. }
  1502. _STLP_MOVE_TO_STD_NAMESPACE
  1503. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1504. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1505. _InputIter2 __first2, _InputIter2 __last2,
  1506. _OutputIter __result) {
  1507. return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
  1508. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1509. }
  1510. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1511. class _Compare>
  1512. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1513. _InputIter2 __first2, _InputIter2 __last2,
  1514. _OutputIter __result, _Compare __comp) {
  1515. return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
  1516. }
  1517. _STLP_MOVE_TO_PRIV_NAMESPACE
  1518. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1519. class _Compare>
  1520. _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1521. _InputIter2 __first2, _InputIter2 __last2,
  1522. _OutputIter __result, _Compare __comp) {
  1523. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1524. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1525. while (__first1 != __last1 && __first2 != __last2)
  1526. if (__comp(*__first1, *__first2)) {
  1527. _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1528. *__result = *__first1;
  1529. ++__first1;
  1530. ++__result;
  1531. }
  1532. else if (__comp(*__first2, *__first1))
  1533. ++__first2;
  1534. else {
  1535. ++__first1;
  1536. ++__first2;
  1537. }
  1538. return _STLP_STD::copy(__first1, __last1, __result);
  1539. }
  1540. _STLP_MOVE_TO_STD_NAMESPACE
  1541. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1542. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1543. _InputIter2 __first2, _InputIter2 __last2,
  1544. _OutputIter __result) {
  1545. return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
  1546. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1547. }
  1548. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1549. class _Compare>
  1550. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1551. _InputIter2 __first2, _InputIter2 __last2,
  1552. _OutputIter __result, _Compare __comp) {
  1553. return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1554. }
  1555. _STLP_MOVE_TO_PRIV_NAMESPACE
  1556. template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1557. _OutputIter
  1558. __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1559. _InputIter2 __first2, _InputIter2 __last2,
  1560. _OutputIter __result, _Compare __comp) {
  1561. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  1562. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  1563. while (__first1 != __last1 && __first2 != __last2) {
  1564. if (__comp(*__first1, *__first2)) {
  1565. _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1566. *__result = *__first1;
  1567. ++__first1;
  1568. ++__result;
  1569. }
  1570. else if (__comp(*__first2, *__first1)) {
  1571. *__result = *__first2;
  1572. ++__first2;
  1573. ++__result;
  1574. }
  1575. else {
  1576. ++__first1;
  1577. ++__first2;
  1578. }
  1579. }
  1580. return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
  1581. }
  1582. _STLP_MOVE_TO_STD_NAMESPACE
  1583. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1584. _OutputIter
  1585. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1586. _InputIter2 __first2, _InputIter2 __last2,
  1587. _OutputIter __result) {
  1588. return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
  1589. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1590. }
  1591. template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1592. _OutputIter
  1593. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1594. _InputIter2 __first2, _InputIter2 __last2,
  1595. _OutputIter __result,
  1596. _Compare __comp) {
  1597. return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1598. }
  1599. // min_element and max_element, with and without an explicitly supplied
  1600. // comparison function.
  1601. template <class _ForwardIter>
  1602. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  1603. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1604. if (__first == __last) return __first;
  1605. _ForwardIter __result = __first;
  1606. while (++__first != __last)
  1607. if (*__result < *__first) {
  1608. _STLP_VERBOSE_ASSERT(!(*__first < *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1609. __result = __first;
  1610. }
  1611. return __result;
  1612. }
  1613. template <class _ForwardIter, class _Compare>
  1614. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  1615. _Compare __comp) {
  1616. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1617. if (__first == __last) return __first;
  1618. _ForwardIter __result = __first;
  1619. while (++__first != __last) {
  1620. if (__comp(*__result, *__first)) {
  1621. _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1622. __result = __first;
  1623. }
  1624. }
  1625. return __result;
  1626. }
  1627. template <class _ForwardIter>
  1628. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  1629. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1630. if (__first == __last) return __first;
  1631. _ForwardIter __result = __first;
  1632. while (++__first != __last)
  1633. if (*__first < *__result) {
  1634. _STLP_VERBOSE_ASSERT(!(*__result < *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1635. __result = __first;
  1636. }
  1637. return __result;
  1638. }
  1639. template <class _ForwardIter, class _Compare>
  1640. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  1641. _Compare __comp) {
  1642. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1643. if (__first == __last) return __first;
  1644. _ForwardIter __result = __first;
  1645. while (++__first != __last) {
  1646. if (__comp(*__first, *__result)) {
  1647. _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1648. __result = __first;
  1649. }
  1650. }
  1651. return __result;
  1652. }
  1653. // next_permutation and prev_permutation, with and without an explicitly
  1654. // supplied comparison function.
  1655. _STLP_MOVE_TO_PRIV_NAMESPACE
  1656. template <class _BidirectionalIter, class _Compare>
  1657. bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1658. _Compare __comp) {
  1659. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1660. if (__first == __last)
  1661. return false;
  1662. _BidirectionalIter __i = __first;
  1663. ++__i;
  1664. if (__i == __last)
  1665. return false;
  1666. __i = __last;
  1667. --__i;
  1668. for(;;) {
  1669. _BidirectionalIter __ii = __i;
  1670. --__i;
  1671. if (__comp(*__i, *__ii)) {
  1672. _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1673. _BidirectionalIter __j = __last;
  1674. while (!__comp(*__i, *--__j)) {}
  1675. iter_swap(__i, __j);
  1676. reverse(__ii, __last);
  1677. return true;
  1678. }
  1679. if (__i == __first) {
  1680. reverse(__first, __last);
  1681. return false;
  1682. }
  1683. }
  1684. #if defined (_STLP_NEED_UNREACHABLE_RETURN)
  1685. return false;
  1686. #endif
  1687. }
  1688. _STLP_MOVE_TO_STD_NAMESPACE
  1689. template <class _BidirectionalIter>
  1690. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1691. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1692. return _STLP_PRIV __next_permutation(__first, __last,
  1693. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1694. }
  1695. template <class _BidirectionalIter, class _Compare>
  1696. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1697. _Compare __comp) {
  1698. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1699. return _STLP_PRIV __next_permutation(__first, __last, __comp);
  1700. }
  1701. _STLP_MOVE_TO_PRIV_NAMESPACE
  1702. template <class _BidirectionalIter, class _Compare>
  1703. bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1704. _Compare __comp) {
  1705. if (__first == __last)
  1706. return false;
  1707. _BidirectionalIter __i = __first;
  1708. ++__i;
  1709. if (__i == __last)
  1710. return false;
  1711. __i = __last;
  1712. --__i;
  1713. for(;;) {
  1714. _BidirectionalIter __ii = __i;
  1715. --__i;
  1716. if (__comp(*__ii, *__i)) {
  1717. _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1718. _BidirectionalIter __j = __last;
  1719. while (!__comp(*--__j, *__i)) {}
  1720. iter_swap(__i, __j);
  1721. reverse(__ii, __last);
  1722. return true;
  1723. }
  1724. if (__i == __first) {
  1725. reverse(__first, __last);
  1726. return false;
  1727. }
  1728. }
  1729. #if defined (_STLP_NEED_UNREACHABLE_RETURN)
  1730. return false;
  1731. #endif
  1732. }
  1733. _STLP_MOVE_TO_STD_NAMESPACE
  1734. template <class _BidirectionalIter>
  1735. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1736. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1737. return _STLP_PRIV __prev_permutation(__first, __last,
  1738. _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1739. }
  1740. template <class _BidirectionalIter, class _Compare>
  1741. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1742. _Compare __comp) {
  1743. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1744. return _STLP_PRIV __prev_permutation(__first, __last, __comp);
  1745. }
  1746. #if !defined (_STLP_NO_EXTENSIONS)
  1747. // is_heap, a predicate testing whether or not a range is
  1748. // a heap. This function is an extension, not part of the C++
  1749. // standard.
  1750. _STLP_MOVE_TO_PRIV_NAMESPACE
  1751. template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
  1752. bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
  1753. _Distance __n) {
  1754. _Distance __parent = 0;
  1755. for (_Distance __child = 1; __child < __n; ++__child) {
  1756. if (__comp(__first[__parent], __first[__child])) {
  1757. _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1758. return false;
  1759. }
  1760. if ((__child & 1) == 0)
  1761. ++__parent;
  1762. }
  1763. return true;
  1764. }
  1765. _STLP_MOVE_TO_STD_NAMESPACE
  1766. template <class _RandomAccessIter>
  1767. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
  1768. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1769. return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
  1770. }
  1771. template <class _RandomAccessIter, class _StrictWeakOrdering>
  1772. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  1773. _StrictWeakOrdering __comp) {
  1774. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1775. return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
  1776. }
  1777. _STLP_MOVE_TO_PRIV_NAMESPACE
  1778. template <class _ForwardIter, class _StrictWeakOrdering>
  1779. bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
  1780. _StrictWeakOrdering __comp) {
  1781. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  1782. if (__first == __last)
  1783. return true;
  1784. _ForwardIter __next = __first;
  1785. for (++__next; __next != __last; __first = __next, ++__next) {
  1786. if (__comp(*__next, *__first)) {
  1787. _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  1788. return false;
  1789. }
  1790. }
  1791. return true;
  1792. }
  1793. _STLP_MOVE_TO_STD_NAMESPACE
  1794. #endif /* _STLP_NO_EXTENSIONS */
  1795. _STLP_END_NAMESPACE
  1796. #undef __stl_threshold
  1797. #endif /* _STLP_ALGO_C */
  1798. // Local Variables:
  1799. // mode:C++
  1800. // End: