/elec/propeller-clock

To get this branch, use:
bzr branch http://bzr.ed.am/elec/propeller-clock

« back to all changes in this revision

Viewing changes to src/utility/algorithm

  • Committer: edam
  • Date: 2012-02-25 14:54:33 UTC
  • Revision ID: edam@waxworlds.org-20120225145433-kih8qs45x05cum46
removed Bounce library and updated/fixed new code

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/utility/algorithm
 
1
/*      Copyright (C) 2004 Garrett A. Kajmowicz
 
2
        This file is part of the uClibc++ Library.
 
3
        This library is free software; you can redistribute it and/or
 
4
        modify it under the terms of the GNU Lesser General Public
 
5
        License as published by the Free Software Foundation; either
 
6
        version 2.1 of the License, or (at your option) any later version.
 
7
 
 
8
        This library is distributed in the hope that it will be useful,
 
9
        but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
11
        Lesser General Public License for more details.
 
12
 
 
13
        You should have received a copy of the GNU Lesser General Public
 
14
        License along with this library; if not, write to the Free Software
 
15
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
*/
 
17
 
 
18
#include <cstdlib>
 
19
#include <iterator>
 
20
#include <utility.h>
 
21
#include <functional>
 
22
 
 
23
#ifndef __STD_HEADER_ALGORITHM
 
24
#define __STD_HEADER_ALGORITHM 1
 
25
 
 
26
//Elliminate any previously defined macro
 
27
#undef min
 
28
#undef max
 
29
 
 
30
#pragma GCC visibility push(default)
 
31
 
 
32
namespace std{
 
33
 
 
34
        // subclause _lib.alg.nonmodifying_, non-modifying sequence operations:
 
35
        template<class InputIterator, class Function> _UCXXEXPORT
 
36
                Function for_each(InputIterator first, InputIterator last, Function f)
 
37
        {
 
38
                while(first !=last){
 
39
                        f(*first);
 
40
                        ++first;
 
41
                }
 
42
                return f;
 
43
        }
 
44
 
 
45
 
 
46
        template<class InputIterator, class T> _UCXXEXPORT
 
47
                InputIterator find(InputIterator first, InputIterator last, const T& value)
 
48
        {
 
49
                while(first !=last && ! ( *first == value ) ){
 
50
                        ++first;
 
51
                }
 
52
                return first;
 
53
        }
 
54
 
 
55
        template<class InputIterator, class Predicate> _UCXXEXPORT
 
56
                InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
 
57
        {
 
58
                while(first !=last && !pred(*first)){
 
59
                        ++first;
 
60
                }
 
61
                return first;
 
62
        }
 
63
 
 
64
        template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT ForwardIterator1
 
65
                find_end(ForwardIterator1 first1, ForwardIterator1 last1,
 
66
                        ForwardIterator2 first2, ForwardIterator2 last2)
 
67
        {
 
68
                ForwardIterator1 retval = last1;
 
69
                while(first1 !=last1){
 
70
                        ForwardIterator1 temp1(first1);
 
71
                        ForwardIterator2 temp2(first2);
 
72
                        while(temp2!=last2 && temp1!= last1){
 
73
                                if(*temp1 != *temp2){
 
74
                                        break;          //Exit while loop
 
75
                                }
 
76
                                ++temp1;
 
77
                                ++temp2;
 
78
                                if(temp2 == last2){     //Have successfully checked the whole sequence
 
79
                                        retval = first1;
 
80
                                }
 
81
                        }
 
82
                }
 
83
                return retval;
 
84
        }
 
85
 
 
86
        template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
 
87
                ForwardIterator1
 
88
                find_end(ForwardIterator1 first1, ForwardIterator1 last1,
 
89
                        ForwardIterator2 first2, ForwardIterator2 last2,
 
90
                        BinaryPredicate pred)
 
91
        {
 
92
                ForwardIterator1 retval = last1;
 
93
                while(first1 !=last1){
 
94
                        ForwardIterator1 temp1(first1);
 
95
                        ForwardIterator2 temp2(first2);
 
96
                        while(temp2!=last2 && temp1!= last1){
 
97
                                if( ! pred(*temp1, *temp2)){
 
98
                                        break;          //Exit while loop
 
99
                                }
 
100
                                ++temp1;
 
101
                                ++temp2;
 
102
                                if(temp2 == last2){     //Have successfully checked the whole sequence
 
103
                                        retval = first1;
 
104
                                }
 
105
                        }
 
106
                }
 
107
                return retval;
 
108
        }
 
109
 
 
110
        template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
 
111
                ForwardIterator1
 
112
                find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
 
113
                        ForwardIterator2 first2, ForwardIterator2 last2)
 
114
        {
 
115
                while(first1 != last1){
 
116
                        ForwardIterator2 temp2(first2);
 
117
                        while(temp2 != last2 ){
 
118
                                if(*temp2 == first1){
 
119
                                        return first1;
 
120
                                }
 
121
                                ++temp2;
 
122
                        }
 
123
                        
 
124
                }
 
125
                return last1;
 
126
        }
 
127
 
 
128
        template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
 
129
                ForwardIterator1
 
130
                find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,  
 
131
                        ForwardIterator2 first2, ForwardIterator2 last2,
 
132
                        BinaryPredicate pred)
 
133
        {
 
134
                while(first1 != last1){
 
135
                        ForwardIterator2 temp2(first2);
 
136
                        while(temp2 != last2 ){
 
137
                                if(*temp2 == first1){
 
138
                                        return first1;
 
139
                                }
 
140
                                ++temp2;
 
141
                        }
 
142
                        
 
143
                }
 
144
                return last1;
 
145
        }
 
146
 
 
147
        template<class ForwardIterator> _UCXXEXPORT ForwardIterator
 
148
                adjacent_find(ForwardIterator first, ForwardIterator last)
 
149
        {
 
150
                ForwardIterator temp;
 
151
                while(first != last){
 
152
                        temp = first;
 
153
                        ++temp;
 
154
                        if(*temp == *first){
 
155
                                return first;
 
156
                        }
 
157
                        ++first;
 
158
                }
 
159
                return first;
 
160
        }
 
161
 
 
162
        template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
 
163
                ForwardIterator
 
164
                adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
 
165
        {
 
166
                ForwardIterator temp;
 
167
                while(first != last){
 
168
                        temp = first;
 
169
                        ++temp;
 
170
                        if( pred(*temp, *first)){
 
171
                                return first;
 
172
                        }
 
173
                        ++first;
 
174
                }
 
175
                return first;
 
176
        }
 
177
 
 
178
        template<class InputIterator, class T> _UCXXEXPORT
 
179
                typename iterator_traits<InputIterator>::difference_type
 
180
                count(InputIterator first, InputIterator last, const T& value)
 
181
        {
 
182
                typename iterator_traits<InputIterator>::difference_type i = 0;
 
183
                while(first!=last){
 
184
                        if(*first == value){
 
185
                                ++i;
 
186
                        }
 
187
                        ++first;
 
188
                }
 
189
                return i;
 
190
        }
 
191
 
 
192
        template<class InputIterator, class Predicate> _UCXXEXPORT
 
193
                typename iterator_traits<InputIterator>::difference_type
 
194
                count_if(InputIterator first, InputIterator last, Predicate pred)
 
195
        {
 
196
                typename iterator_traits<InputIterator>::difference_type i = 0;
 
197
                while(first!=last){
 
198
                        if( pred(*first) ){
 
199
                                ++i;
 
200
                        }
 
201
                        ++first;
 
202
                }
 
203
                return i;
 
204
        }
 
205
 
 
206
        template<class InputIterator1, class InputIterator2> _UCXXEXPORT
 
207
                pair<InputIterator1, InputIterator2>    
 
208
                mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
 
209
        {
 
210
                while(first1 != last1){
 
211
                        if(*first1 != *first2){
 
212
                                break;
 
213
                        }
 
214
                        ++first1;
 
215
                        ++first2;
 
216
                }
 
217
 
 
218
                pair<InputIterator1, InputIterator2> retval;
 
219
                retval.first = first1;
 
220
                retval.second = first2;
 
221
                return retval;
 
222
        }
 
223
 
 
224
        template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
 
225
                pair<InputIterator1, InputIterator2>
 
226
                mismatch(InputIterator1 first1, InputIterator1 last1,
 
227
                        InputIterator2 first2, BinaryPredicate pred)
 
228
        {
 
229
                while(first1 != last1){
 
230
                        if( !pred(*first1, *first2) ){
 
231
                                break;
 
232
                        }
 
233
                        ++first1;
 
234
                        ++first2;
 
235
                }
 
236
 
 
237
                pair<InputIterator1, InputIterator2> retval;
 
238
                retval.first = first1;
 
239
                retval.second = first2;
 
240
                return retval;
 
241
        }
 
242
 
 
243
        template<class InputIterator1, class InputIterator2> _UCXXEXPORT
 
244
                bool
 
245
                equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
 
246
        {
 
247
                while(first1 !=last1){
 
248
                        if(*first1 != *first2){
 
249
                                return false;
 
250
                        }
 
251
                        ++first1;
 
252
                        ++first2;
 
253
                }
 
254
                return true;
 
255
        }
 
256
 
 
257
        template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
 
258
                bool
 
259
                equal(InputIterator1 first1, InputIterator1 last1,
 
260
                        InputIterator2 first2, BinaryPredicate pred)
 
261
        {
 
262
                while(first1 !=last1){
 
263
                        if( !pred(*first1, *first2) ){
 
264
                                return false;
 
265
                        }
 
266
                        ++first1;
 
267
                        ++first2;
 
268
                }
 
269
                return true;
 
270
        }
 
271
 
 
272
        template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
 
273
                ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
 
274
                        ForwardIterator2 first2, ForwardIterator2 last2)
 
275
        {
 
276
                equal_to<typename iterator_traits<ForwardIterator1>::value_type> c;
 
277
                return search(first1, last1, first2, last2, c);
 
278
        }
 
279
 
 
280
 
 
281
        template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
 
282
                ForwardIterator1
 
283
                search(ForwardIterator1 first1, ForwardIterator1 last1,
 
284
                        ForwardIterator2 first2, ForwardIterator2 last2,
 
285
                        BinaryPredicate pred)
 
286
        {
 
287
                while(first1 != last1){
 
288
                        ForwardIterator1 temp1(first1);
 
289
                        ForwardIterator2 temp2(first2);
 
290
                        while(temp2 != last2 && temp1 != last1){
 
291
                                if( !pred(*temp2, *temp1) ){
 
292
                                        break;
 
293
                                }
 
294
                                ++temp1;
 
295
                                ++temp2;
 
296
                                if(temp2 == last2){
 
297
                                        return first1;
 
298
                                }
 
299
                        }
 
300
                        ++first1;
 
301
                }
 
302
                return last1;
 
303
        }
 
304
 
 
305
 
 
306
        template<class ForwardIterator, class Size, class T> _UCXXEXPORT
 
307
                ForwardIterator
 
308
                search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
 
309
        {
 
310
                while( first != last ){
 
311
                        if(*first == value){
 
312
                                ForwardIterator temp(first);
 
313
                                Size i = 1;
 
314
                                ++first;        //Avoid doing the same comparison over again
 
315
                                while(i < count && *temp == value){
 
316
                                        ++first;
 
317
                                        ++i;
 
318
                                }
 
319
                                if(i == count){
 
320
                                        return first;
 
321
                                }
 
322
                        }
 
323
                        ++first;
 
324
                }
 
325
                return first;           
 
326
        }
 
327
 
 
328
 
 
329
        template<class ForwardIterator, class Size, class T, class BinaryPredicate> _UCXXEXPORT
 
330
                ForwardIterator
 
331
                search_n(ForwardIterator first, ForwardIterator last,
 
332
                        Size count, const T& value, BinaryPredicate pred)
 
333
        {
 
334
                while( first != last ){
 
335
                        if( pred(*first, value) ){
 
336
                                ForwardIterator temp(first);
 
337
                                Size i = 1;
 
338
                                ++first;        //Avoid doing the same comparison over again
 
339
                                while(i < count && pred(*temp, value) ){
 
340
                                        ++first;
 
341
                                        ++i;
 
342
                                }
 
343
                                if(i == count){
 
344
                                        return first;
 
345
                                }
 
346
                        }
 
347
                        ++first;
 
348
                }
 
349
                return first;           
 
350
 
 
351
        }
 
352
 
 
353
        // subclause _lib.alg.modifying.operations_, modifying sequence operations:
 
354
 
 
355
        template<class InputIterator, class OutputIterator> _UCXXEXPORT
 
356
                OutputIterator
 
357
                copy(InputIterator first, InputIterator last, OutputIterator result)
 
358
        {
 
359
                while(first != last){
 
360
                        *result = *first;
 
361
                        ++first;
 
362
                        ++result;
 
363
                }
 
364
                return result;
 
365
        }
 
366
 
 
367
        template<class BidirectionalIterator1, class BidirectionalIterator2> _UCXXEXPORT
 
368
                BidirectionalIterator2
 
369
                copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
 
370
                        BidirectionalIterator2 result)
 
371
        {
 
372
                while(first !=last ){
 
373
                        --result;
 
374
                        --last;
 
375
                        *result = *last;
 
376
                }
 
377
                return result;
 
378
        }
 
379
 
 
380
        template<class T> _UCXXEXPORT void swap(T& a, T& b){
 
381
                T temp(a);
 
382
                a = b;
 
383
                b = temp;
 
384
        }
 
385
 
 
386
        template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
 
387
                ForwardIterator2
 
388
                swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
 
389
        {
 
390
                while(first1 != last1){
 
391
                        iter_swap(first1, first2);
 
392
                        ++first1;
 
393
                        ++first2;
 
394
                }
 
395
                return first2;
 
396
        }
 
397
 
 
398
 
 
399
        template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
 
400
                void
 
401
                iter_swap(ForwardIterator1 a, ForwardIterator2 b)
 
402
        {
 
403
                typename iterator_traits<ForwardIterator1>::value_type temp(*a);
 
404
                *a = *b;
 
405
                *b = temp;
 
406
        }
 
407
 
 
408
 
 
409
        template<class InputIterator, class OutputIterator, class UnaryOperation> _UCXXEXPORT
 
410
                OutputIterator
 
411
                transform(InputIterator first, InputIterator last,
 
412
                        OutputIterator result, UnaryOperation op)
 
413
        {
 
414
                while(first != last){
 
415
                        *result = op(*first);
 
416
                        ++first;
 
417
                        ++result;
 
418
                }
 
419
                return result;
 
420
        }
 
421
 
 
422
 
 
423
        template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> _UCXXEXPORT
 
424
                OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
 
425
                        InputIterator2 first2, OutputIterator result,
 
426
                        BinaryOperation binary_op)
 
427
        {
 
428
                while(first1 != last1){
 
429
                        *result = binary_op(*first1, *first2);
 
430
                        ++first1;
 
431
                        ++first2;
 
432
                        ++result;
 
433
                }
 
434
                return result;
 
435
        }
 
436
 
 
437
 
 
438
        template<class ForwardIterator, class T> _UCXXEXPORT
 
439
                void
 
440
                replace(ForwardIterator first, ForwardIterator last,
 
441
                        const T& old_value, const T& new_value)
 
442
        {
 
443
                while(first != last){
 
444
                        if(*first == old_value){
 
445
                                *first = new_value;
 
446
                        }
 
447
                        ++first;
 
448
                }
 
449
        }
 
450
 
 
451
        template<class ForwardIterator, class Predicate, class T> _UCXXEXPORT
 
452
                void
 
453
                replace_if(ForwardIterator first, ForwardIterator last,
 
454
                        Predicate pred, const T& new_value)
 
455
        {
 
456
                while(first != last){
 
457
                        if( pred(*first) ){
 
458
                                *first = new_value;
 
459
                        }
 
460
                        ++first;
 
461
                }
 
462
        }
 
463
 
 
464
 
 
465
        template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
 
466
                OutputIterator
 
467
                replace_copy(InputIterator first, InputIterator last,
 
468
                        OutputIterator result, const T& old_value, const T& new_value)
 
469
        {
 
470
                while(first != last){
 
471
                        if(*first == old_value){
 
472
                                *result = new_value;
 
473
                        }else{
 
474
                                *result = *first;
 
475
                        }
 
476
                        ++first;
 
477
                        ++result;
 
478
                }
 
479
                return result;
 
480
        }
 
481
 
 
482
        template<class Iterator, class OutputIterator, class Predicate, class T> _UCXXEXPORT
 
483
                OutputIterator
 
484
                replace_copy_if(Iterator first, Iterator last,
 
485
                        OutputIterator result, Predicate pred, const T& new_value)
 
486
        {
 
487
                while(first != last){
 
488
                        if( pred(*first) ){
 
489
                                *result = new_value;
 
490
                        }else{
 
491
                                *result = *first;
 
492
                        }
 
493
                        ++first;
 
494
                        ++result;
 
495
                }
 
496
                return result;
 
497
        }
 
498
 
 
499
        template<class ForwardIterator, class T> _UCXXEXPORT
 
500
                void
 
501
                fill(ForwardIterator first, ForwardIterator last, const T& value)
 
502
        {
 
503
                while(first != last){
 
504
                        *first = value;
 
505
                        ++first;
 
506
                }
 
507
        }
 
508
 
 
509
        template<class OutputIterator, class Size, class T> _UCXXEXPORT
 
510
                void
 
511
                fill_n(OutputIterator first, Size n, const T& value)
 
512
        {
 
513
                while(n != 0){
 
514
                        *first = value;
 
515
                        --n;
 
516
                        ++first;
 
517
                }
 
518
        }
 
519
 
 
520
        template<class ForwardIterator, class Generator> _UCXXEXPORT
 
521
                void
 
522
                generate(ForwardIterator first, ForwardIterator last, Generator gen)
 
523
        {
 
524
                while(first != last){
 
525
                        *first = gen();
 
526
                        ++first;
 
527
                }
 
528
        }
 
529
 
 
530
        template<class OutputIterator, class Size, class Generator> _UCXXEXPORT
 
531
                void
 
532
                generate_n(OutputIterator first, Size n, Generator gen)
 
533
        {
 
534
                while(n !=0){
 
535
                        *first = gen();
 
536
                        --n;
 
537
                        ++first;
 
538
                }
 
539
        }
 
540
 
 
541
        template<class ForwardIterator, class T> _UCXXEXPORT
 
542
                ForwardIterator
 
543
                remove(ForwardIterator first, ForwardIterator last, const T& value)
 
544
        {
 
545
                ForwardIterator temp(first);
 
546
                while(temp !=last){
 
547
                        if(*temp == value){
 
548
 
 
549
                        }else{
 
550
                                *first = *temp;
 
551
                                ++first;
 
552
                        }
 
553
                        ++temp;
 
554
                }
 
555
                return first;
 
556
        }
 
557
 
 
558
        template<class ForwardIterator, class Predicate> _UCXXEXPORT
 
559
                ForwardIterator
 
560
                remove_if(ForwardIterator first, ForwardIterator last, Predicate pred)
 
561
        {
 
562
                ForwardIterator temp(first);
 
563
                while(temp !=last){
 
564
                        if( pred(*temp) ){
 
565
 
 
566
                        }else{
 
567
                                *first = *temp;
 
568
                                ++first;
 
569
                        }
 
570
                        ++temp;
 
571
                }
 
572
                return first;
 
573
        }
 
574
 
 
575
 
 
576
        template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
 
577
                OutputIterator
 
578
                remove_copy(InputIterator first, InputIterator last,
 
579
                        OutputIterator result, const T& value)
 
580
        {
 
581
                while(first !=last){
 
582
                        if(*first != value){
 
583
                                *result = *first;
 
584
                                ++result;
 
585
                        }
 
586
                        ++first;
 
587
                }
 
588
                return result;
 
589
        }
 
590
 
 
591
        template<class InputIterator, class OutputIterator, class Predicate> _UCXXEXPORT
 
592
                OutputIterator
 
593
                remove_copy_if(InputIterator first, InputIterator last,
 
594
                        OutputIterator result, Predicate pred)
 
595
        {
 
596
                while(first !=last){
 
597
                        if( !pred(*first) ){
 
598
                                *result = *first;
 
599
                                ++result;
 
600
                        }
 
601
                        ++first;
 
602
                }
 
603
                return result;
 
604
        }
 
605
 
 
606
        template<class ForwardIterator> _UCXXEXPORT
 
607
                ForwardIterator
 
608
                unique(ForwardIterator first, ForwardIterator last)
 
609
        {
 
610
                ForwardIterator new_val(first);
 
611
                ForwardIterator old_val(first);
 
612
 
 
613
                while(new_val !=last){
 
614
                        if(*new_val == *old_val && new_val != old_val){
 
615
 
 
616
                        }else{
 
617
                                *first = *new_val;
 
618
                                old_val = new_val;
 
619
                                ++first;
 
620
                        }
 
621
                        ++new_val;
 
622
                }
 
623
                return first;
 
624
        }
 
625
 
 
626
        template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
 
627
                ForwardIterator
 
628
                unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
 
629
        {
 
630
                ForwardIterator new_val(first);
 
631
                ForwardIterator old_val(first);
 
632
 
 
633
                while(new_val !=last){
 
634
                        if( pred(*new_val, *old_val) && new_val != old_val){
 
635
 
 
636
                        }else{
 
637
                                *first = *new_val;
 
638
                                old_val = new_val;
 
639
                                ++first;
 
640
                        }
 
641
                        ++new_val;
 
642
                }
 
643
                return first;
 
644
        }
 
645
 
 
646
        template<class InputIterator, class OutputIterator> _UCXXEXPORT
 
647
                OutputIterator
 
648
                unique_copy(InputIterator first, InputIterator last, OutputIterator result)
 
649
        {
 
650
                InputIterator temp(first);
 
651
                while(first !=last ){
 
652
                        if(*first == *temp && first != temp){
 
653
 
 
654
                        }else{
 
655
                                *result = *first;
 
656
                                temp = first;
 
657
                                ++result;
 
658
                        }
 
659
                        ++first;
 
660
                }
 
661
                return result;
 
662
        }
 
663
 
 
664
        template<class InputIterator, class OutputIterator, class BinaryPredicate> _UCXXEXPORT
 
665
                OutputIterator
 
666
                unique_copy(InputIterator first, InputIterator last,
 
667
                        OutputIterator result, BinaryPredicate pred)
 
668
        {
 
669
                InputIterator temp(first);
 
670
                while(first !=last ){
 
671
                        if( pred(*first, *temp) && first != temp){
 
672
 
 
673
                        }else{
 
674
                                *result = *first;
 
675
                                temp = first;
 
676
                                ++result;
 
677
                        }
 
678
                        ++first;
 
679
                }
 
680
                return result;
 
681
        }
 
682
 
 
683
        template<class BidirectionalIterator> _UCXXEXPORT
 
684
                void
 
685
                reverse(BidirectionalIterator first, BidirectionalIterator last)
 
686
        {
 
687
                --last;         //Don't work with one past the end element
 
688
                while(first < last){
 
689
                        iter_swap(first, last);
 
690
                        ++first;
 
691
                        --last;
 
692
                }
 
693
        }
 
694
 
 
695
        template<class BidirectionalIterator, class OutputIterator> _UCXXEXPORT
 
696
                OutputIterator
 
697
                reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
 
698
                OutputIterator result)
 
699
        {
 
700
                while(last > first){
 
701
                        --last;
 
702
                        *result = *last;
 
703
                        ++result;
 
704
                }
 
705
                return result;
 
706
        }
 
707
 
 
708
        template<class ForwardIterator> _UCXXEXPORT
 
709
                void
 
710
                rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
 
711
        {
 
712
                if ((first == middle) || (last  == middle)){
 
713
                        return;
 
714
                }
 
715
 
 
716
                ForwardIterator first2 = middle;
 
717
 
 
718
                do {
 
719
                        swap(*first, *first2);
 
720
                        first++;
 
721
                        first2++;
 
722
                        if(first == middle){
 
723
                                middle = first2;
 
724
                        }
 
725
                } while(first2 != last);
 
726
 
 
727
                first2 = middle;
 
728
 
 
729
                while (first2 != last) {
 
730
                        swap(*first, *first2);
 
731
                        first++;
 
732
                        first2++;
 
733
                        if (first == middle){
 
734
                                middle = first2;
 
735
                        }else if (first2 == last){
 
736
                                first2 = middle;
 
737
                        }
 
738
                }
 
739
        }
 
740
 
 
741
        template<class ForwardIterator, class OutputIterator> _UCXXEXPORT
 
742
                OutputIterator
 
743
                rotate_copy(ForwardIterator first, ForwardIterator middle,
 
744
                        ForwardIterator last, OutputIterator result)
 
745
        {
 
746
                ForwardIterator temp(middle);
 
747
                while(temp !=last){
 
748
                        *result = *temp;
 
749
                        ++temp;
 
750
                        ++result;
 
751
                }
 
752
                while(first != middle){
 
753
                        *result = *first;
 
754
                        ++first;
 
755
                        ++result;
 
756
                }
 
757
                return result;
 
758
        }
 
759
 
 
760
 
 
761
        template<class RandomAccessIterator> _UCXXEXPORT
 
762
                void
 
763
                random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
 
764
        {
 
765
                --last;
 
766
                while(first != last){
 
767
                        iter_swap(first, (first + (rand() % (last - first) ) ) );
 
768
                        ++first;
 
769
                }
 
770
        }
 
771
 
 
772
        template<class RandomAccessIterator, class RandomNumberGenerator> _UCXXEXPORT
 
773
                void
 
774
                random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
 
775
                RandomNumberGenerator& rand)
 
776
        {
 
777
                --last;
 
778
                while(first != last){
 
779
                        iter_swap(first, (first + (rand(last - first) ) ) );
 
780
                        ++first;
 
781
                }
 
782
        }
 
783
 
 
784
        // _lib.alg.partitions_, partitions:
 
785
        template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
 
786
                partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
 
787
        {
 
788
                return stable_partition(first, last, pred);
 
789
        }
 
790
 
 
791
        template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
 
792
                stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
 
793
        {
 
794
                //first now points to the first non-desired element
 
795
                while( first != last && pred(*first) ){
 
796
                        ++first;
 
797
                }
 
798
 
 
799
                BidirectionalIterator tempb;
 
800
                BidirectionalIterator tempe = first;
 
801
 
 
802
                while( tempe != last ){
 
803
                        //Find the next desired element
 
804
                        while( !pred(*tempe) ){
 
805
                                ++tempe;
 
806
 
 
807
                                //See if we should exit
 
808
                                if(tempe == last){
 
809
                                        return first;
 
810
                                }
 
811
                        }
 
812
 
 
813
                        //Rotate the element back to the begining
 
814
                        tempb = tempe;
 
815
                        while(tempb != first){
 
816
                                iter_swap(tempb, tempb-1 );
 
817
                                --tempb;
 
818
                        }
 
819
                        //First now has a desired element
 
820
                        ++first;
 
821
                }
 
822
 
 
823
                return first;
 
824
        }
 
825
 
 
826
        template<class RandomAccessIterator> _UCXXEXPORT
 
827
                void sort(RandomAccessIterator first, RandomAccessIterator last)
 
828
        {
 
829
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
830
                sort(first, last, c );
 
831
        }
 
832
 
 
833
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
834
                void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
835
        {
 
836
                stable_sort(first, last, comp);
 
837
        }
 
838
 
 
839
        template<class RandomAccessIterator> _UCXXEXPORT
 
840
                void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
 
841
        {
 
842
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
843
                stable_sort(first, last, c);
 
844
        }
 
845
 
 
846
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
847
                void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
848
        {
 
849
                //FIXME - bubble sort
 
850
                RandomAccessIterator temp;
 
851
                --last;
 
852
                while(last - first > 0){
 
853
                        temp = last;
 
854
                        while(temp != first){
 
855
                                if( comp( *temp, *(temp-1) ) ){
 
856
                                        iter_swap( temp-1, temp);
 
857
                                }
 
858
                                --temp;
 
859
                        }
 
860
                        ++first;
 
861
                }
 
862
        }
 
863
 
 
864
        template<class RandomAccessIterator> _UCXXEXPORT
 
865
                void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
 
866
        {
 
867
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
868
                partial_sort(first, middle, last, c);
 
869
        }
 
870
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
871
                void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
 
872
                        RandomAccessIterator last, Compare comp)
 
873
        {
 
874
                //Fixme - partial bubble sort
 
875
                RandomAccessIterator temp;
 
876
                --last;
 
877
                while(first < middle){
 
878
                        temp = last;
 
879
                        while(temp != first){
 
880
                                if( comp(*temp, *(temp -1 ) ) ) {
 
881
                                        iter_swap( temp-1, temp);
 
882
                                }
 
883
                                --temp;
 
884
                        }
 
885
                        ++first;
 
886
                }
 
887
        }
 
888
        template<class InputIterator, class RandomAccessIterator> _UCXXEXPORT
 
889
                RandomAccessIterator
 
890
                partial_sort_copy(InputIterator first, InputIterator last,
 
891
                        RandomAccessIterator result_first, RandomAccessIterator result_last)
 
892
        {
 
893
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
894
                return partial_sort_copy(first, last, result_first, result_last, c);
 
895
        }
 
896
        template<class InputIterator, class RandomAccessIterator, class Compare> _UCXXEXPORT
 
897
                RandomAccessIterator
 
898
                partial_sort_copy(InputIterator first, InputIterator last,
 
899
                        RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)
 
900
        {
 
901
                size_t output_size = last-first;
 
902
                size_t temp_size = result_last - result_first;
 
903
                if(temp_size < output_size){
 
904
                        output_size = temp_size;
 
905
                }
 
906
 
 
907
                RandomAccessIterator middle = result_first + output_size;
 
908
                RandomAccessIterator temp = result_first;
 
909
 
 
910
                while(temp != middle){
 
911
                        *temp = *first;
 
912
                        ++temp;
 
913
                        ++first;
 
914
                }
 
915
                sort(result_first, middle, comp);
 
916
 
 
917
                while( first != last){
 
918
                        if( comp( *first, *(middle-1) ) ){
 
919
                                *(middle-1) = *first;
 
920
                                sort(result_first, middle, comp);
 
921
                        }
 
922
                        ++first;
 
923
                }
 
924
 
 
925
                return middle;
 
926
        }
 
927
        template<class RandomAccessIterator> _UCXXEXPORT
 
928
                void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
 
929
        {
 
930
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
931
                nth_element(first, nth, last, c);
 
932
        }
 
933
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
934
                void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
 
935
                        RandomAccessIterator last, Compare comp)
 
936
        {
 
937
                partial_sort(first, nth, last, comp);
 
938
        }
 
939
 
 
940
        template<class ForwardIterator, class T> _UCXXEXPORT
 
941
                ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 
942
                        const T& value)
 
943
        {
 
944
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
945
                return lower_bound(first, last, value, c);
 
946
        }
 
947
 
 
948
        template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
 
949
                ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 
950
                        const T& value, Compare comp)
 
951
        {
 
952
                if(first == last){
 
953
                        return last;
 
954
                }
 
955
                //If below or equal to the first element
 
956
                if( comp(*first, value) == false){
 
957
                        return first;
 
958
                }
 
959
                ForwardIterator middle;
 
960
 
 
961
                //If greater than the top element
 
962
                middle = first;
 
963
                advance(middle, distance(first, last) - 1);
 
964
                if( comp(*middle, value) ){
 
965
                        return last;
 
966
                }
 
967
 
 
968
                //Now begin the actual search for the begining
 
969
                while( distance(first, last) > 1 ){
 
970
                        //Find middle
 
971
                        middle = first;
 
972
                        advance(middle, (distance(first, last)/2) );
 
973
                        if( !comp(*middle, value) ){
 
974
                                last = middle;
 
975
                        }else{
 
976
                                first = middle;
 
977
                        }
 
978
                }
 
979
        
 
980
                if( !comp(*first, value) ){
 
981
                        return first;
 
982
                }
 
983
                return last;
 
984
        }
 
985
 
 
986
        template<class ForwardIterator, class T> _UCXXEXPORT
 
987
                ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
 
988
                        const T& value)
 
989
        {
 
990
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
991
                return upper_bound(first, last, value, c);
 
992
        }
 
993
 
 
994
 
 
995
        template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
 
996
                ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
 
997
                        const T& value, Compare comp)
 
998
        {
 
999
                if(first == last){
 
1000
                        return last;
 
1001
                }
 
1002
                //If below the first element
 
1003
                if( comp(value, *first) == true){
 
1004
                        return first;
 
1005
                }
 
1006
 
 
1007
                ForwardIterator middle;
 
1008
 
 
1009
                //If greater than the top element
 
1010
                middle = first;
 
1011
                advance(middle, distance(first, last) - 1);
 
1012
                if( comp(*middle, value) ){
 
1013
                        return last;
 
1014
                }
 
1015
 
 
1016
                //Now begin the actual search for the end
 
1017
                while( distance(first, last) > 1 ){
 
1018
                        //Find middle
 
1019
                        middle = first;
 
1020
                        advance(middle, (distance(first, last)/2) );
 
1021
                        if( comp(value, *middle) ){
 
1022
                                last = middle;
 
1023
                        }else{
 
1024
                                first = middle;
 
1025
                        }
 
1026
                }
 
1027
        
 
1028
                if( comp(value, *first) ){
 
1029
                        return first;
 
1030
                }
 
1031
                return last;
 
1032
        }
 
1033
 
 
1034
 
 
1035
        template<class ForwardIterator, class T> _UCXXEXPORT
 
1036
                pair<ForwardIterator, ForwardIterator>
 
1037
                equal_range(ForwardIterator first, ForwardIterator last, const T& value)
 
1038
        {
 
1039
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
1040
                return equal_range(first, last, value, c);
 
1041
        }
 
1042
 
 
1043
        template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
 
1044
                pair<ForwardIterator, ForwardIterator>
 
1045
                equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
 
1046
        {
 
1047
                pair<ForwardIterator, ForwardIterator> retval;
 
1048
                retval.first = lower_bound(first, last, value, comp);
 
1049
                //Reuse retval.first in order to (possibly) save a few comparisons
 
1050
                retval.second = upper_bound(retval.first, last, value, comp);
 
1051
                return retval;
 
1052
 
 
1053
        }
 
1054
 
 
1055
        template<class ForwardIterator, class T> _UCXXEXPORT
 
1056
                bool binary_search(ForwardIterator first, ForwardIterator last,
 
1057
                        const T& value)
 
1058
        {
 
1059
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
1060
                return binary_search(first, last, value, c);
 
1061
        }
 
1062
 
 
1063
        template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
 
1064
                bool binary_search(ForwardIterator first, ForwardIterator last,
 
1065
                        const T& value, Compare comp)
 
1066
        {
 
1067
                if( distance(first, last) == 0){
 
1068
                        return false;
 
1069
                }
 
1070
 
 
1071
                ForwardIterator middle;
 
1072
 
 
1073
                while( distance(first, last) > 1 ){
 
1074
                        //Set middle between first and last
 
1075
                        middle = first;
 
1076
                        advance(middle, distance(first, last)/2 );
 
1077
 
 
1078
                        if( comp(*middle, value ) == true){
 
1079
                                first = middle;
 
1080
                        }else{
 
1081
                                last = middle;
 
1082
                        }
 
1083
                }
 
1084
 
 
1085
                if( !comp(*first, value) && !comp(value, *first) ){
 
1086
                        return true;
 
1087
                }       
 
1088
                if( !comp(*last, value) && !comp(value, *last) ){
 
1089
                        return true;
 
1090
                }       
 
1091
 
 
1092
                return false;
 
1093
        }
 
1094
 
 
1095
        // _lib.alg.merge_, merge:
 
1096
        template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
 
1097
                OutputIterator
 
1098
                merge(InputIterator1 first1, InputIterator1 last1,
 
1099
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result)
 
1100
        {
 
1101
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1102
                return merge(first1, last1, first2, last2, result, c);
 
1103
        }
 
1104
        template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
 
1105
                OutputIterator
 
1106
                merge(InputIterator1 first1, InputIterator1 last1,
 
1107
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
 
1108
        {
 
1109
                while( first1 != last1 && first2 != last2){
 
1110
                        //If in this order so first1 elements which are equal come first
 
1111
                        if( comp(*first2, *first1) ){
 
1112
                                *result = *first2;
 
1113
                                ++first2;
 
1114
                        }else{
 
1115
                                *result = *first1;
 
1116
                                ++first1;
 
1117
                        }
 
1118
                        ++result;
 
1119
                }
 
1120
                //Clean up remaining elements
 
1121
                while(first1 != last1){
 
1122
                        *result = *first1;
 
1123
                        ++first1;
 
1124
                        ++result;
 
1125
                }
 
1126
                while(first2 != last2){
 
1127
                        *result = *first2;
 
1128
                        ++first2;
 
1129
                        ++result;
 
1130
                }
 
1131
                return result;
 
1132
        }
 
1133
        template<class BidirectionalIterator> _UCXXEXPORT
 
1134
                void inplace_merge(BidirectionalIterator first,
 
1135
                        BidirectionalIterator middle, BidirectionalIterator last)
 
1136
        {
 
1137
                less<typename iterator_traits<BidirectionalIterator>::value_type> c;
 
1138
                inplace_merge(first, middle, last, c);
 
1139
        }
 
1140
        template<class BidirectionalIterator, class Compare> _UCXXEXPORT
 
1141
                void inplace_merge(BidirectionalIterator first,
 
1142
                        BidirectionalIterator middle, BidirectionalIterator last, Compare comp)
 
1143
        {
 
1144
                //FIXME - using a bubble exchange method
 
1145
                while(first != middle && middle !=last){
 
1146
                        if( comp(*middle, *first) ){
 
1147
                                BidirectionalIterator temp(middle);
 
1148
                                while( temp != first){
 
1149
                                        iter_swap(temp, temp-1);
 
1150
                                        --temp;
 
1151
                                }
 
1152
                                ++middle;
 
1153
                        }
 
1154
                        ++first;
 
1155
                }
 
1156
        }
 
1157
 
 
1158
        // _lib.alg.set.operations_, set operations:
 
1159
        template<class InputIterator1, class InputIterator2> _UCXXEXPORT
 
1160
                bool includes(InputIterator1 first1, InputIterator1 last1,
 
1161
                        InputIterator2 first2, InputIterator2 last2)
 
1162
        {
 
1163
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1164
                return includes(first1, last1, first2, last2, c );
 
1165
        }
 
1166
 
 
1167
        template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
 
1168
                bool includes(InputIterator1 first1, InputIterator1 last1,
 
1169
                        InputIterator2 first2, InputIterator2 last2, Compare comp)
 
1170
        {
 
1171
                while(first2 != last2){
 
1172
                        //Advance the large set until no longer smaller than the element we are looking for
 
1173
                        while( comp(*first1, *first2) ){
 
1174
                                ++first1;
 
1175
                                //If we are at the end of the list, we don't have the desired element
 
1176
                                if(first1 == last1){
 
1177
                                        return false;
 
1178
                                }
 
1179
                        }
 
1180
                        //If we are past the element we want, it isn't here
 
1181
                        if( comp(*first2, *first1) ){
 
1182
                                return false;
 
1183
                        }
 
1184
                        ++first2;       //Move to next element
 
1185
                }
 
1186
                return true;
 
1187
        }
 
1188
 
 
1189
        template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
 
1190
                OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
 
1191
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result)
 
1192
        {
 
1193
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1194
                return set_union(first1, last1, first2, last2, result, c);
 
1195
        }
 
1196
 
 
1197
        template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
 
1198
                OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
 
1199
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
 
1200
        {
 
1201
                while( first1 != last1 && first2 != last2){
 
1202
                        if( comp(*first2, *first1) ){
 
1203
                                *result = *first2;
 
1204
 
 
1205
                                //Elliminate duplicates
 
1206
                                InputIterator2 temp = first2;
 
1207
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1208
                                        ++first1;
 
1209
                                }
 
1210
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1211
                                        ++first2;
 
1212
                                }
 
1213
                        }else{
 
1214
                                *result = *first1;
 
1215
                                        //Elliminate duplicates
 
1216
                                InputIterator1 temp = first1;
 
1217
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1218
                                        ++first1;
 
1219
                                }
 
1220
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1221
                                        ++first2;
 
1222
                                }
 
1223
                        }
 
1224
                        ++result;
 
1225
                }
 
1226
 
 
1227
                //Clean up remaining elements
 
1228
                while(first1 != last1){
 
1229
                        *result = *first1;
 
1230
                        ++result;
 
1231
                        InputIterator1 temp = first1;
 
1232
                        while( first1 != last1 && !comp( *temp, *first1) ){
 
1233
                                ++first1;
 
1234
                        }
 
1235
                }
 
1236
 
 
1237
                while(first2 != last2){
 
1238
                        *result = *first2;
 
1239
                        ++result;
 
1240
                        InputIterator2 temp = first2;
 
1241
                        while( first2 != last2 && !comp( *temp, *first2) ){
 
1242
                                ++first2;
 
1243
                        }
 
1244
                }
 
1245
                return result;
 
1246
        }
 
1247
 
 
1248
        template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
 
1249
                OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
 
1250
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result)
 
1251
        {
 
1252
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1253
                return set_intersection(first1, last1, first2, last2, result, c);
 
1254
        }
 
1255
        template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
 
1256
                OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
 
1257
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
 
1258
        {
 
1259
                while( first1 != last1 && first2 != last2){
 
1260
                        if( comp(*first2, *first1) ){
 
1261
                                ++first2;
 
1262
                        }else if( comp(*first1, *first2) ) {
 
1263
                                ++first1;
 
1264
                        }else{
 
1265
                                *result = *first1;
 
1266
                                ++result;
 
1267
                                InputIterator1 temp = first1;
 
1268
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1269
                                        ++first1;
 
1270
                                }
 
1271
                                ++first2;
 
1272
                        }
 
1273
                }
 
1274
                return result;
 
1275
        }
 
1276
        template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
 
1277
                OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
 
1278
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result)
 
1279
        {
 
1280
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1281
                return set_difference(first1, last1, first2, last2, result, c);
 
1282
        }
 
1283
        template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
 
1284
                OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
 
1285
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
 
1286
        {
 
1287
                while( first1 != last1 && first2 != last2){
 
1288
                        if( comp(*first1, *first2) ){
 
1289
                                *result = *first1;
 
1290
                                ++result;
 
1291
 
 
1292
                                //Elliminate duplicates
 
1293
                                InputIterator1 temp = first1;
 
1294
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1295
                                        ++first1;
 
1296
                                }
 
1297
                        }else if( comp(*first2, *first1) ){
 
1298
 
 
1299
                                //Elliminate duplicates
 
1300
                                InputIterator2 temp = first2;
 
1301
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1302
                                        ++first2;
 
1303
                                }
 
1304
                
 
1305
                        }else{  //They are identical - skip
 
1306
                                //Elliminate duplicates
 
1307
                                InputIterator1 temp = first1;
 
1308
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1309
                                        ++first1;
 
1310
                                }
 
1311
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1312
                                        ++first2;
 
1313
                                }
 
1314
                        }
 
1315
                }
 
1316
 
 
1317
                //Clean up remaining elements
 
1318
                while(first1 != last1){
 
1319
                        *result = *first1;
 
1320
                        ++result;
 
1321
                        InputIterator1 temp = first1;
 
1322
                        while( first1 != last1 && !comp( *temp, *first1) ){
 
1323
                                ++first1;
 
1324
                        }
 
1325
                }
 
1326
 
 
1327
                return result;
 
1328
        }
 
1329
        template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
 
1330
                OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
 
1331
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result)
 
1332
        {
 
1333
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1334
                return set_symmetric_difference(first1, last1, first2, last2, result, c);
 
1335
        }
 
1336
        template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
 
1337
                OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
 
1338
                        InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
 
1339
        {
 
1340
                while( first1 != last1 && first2 != last2){
 
1341
                        if( comp(*first1, *first2) ){
 
1342
                                *result = *first1;
 
1343
                                ++result;
 
1344
 
 
1345
                                //Elliminate duplicates
 
1346
                                InputIterator1 temp = first1;
 
1347
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1348
                                        ++first1;
 
1349
                                }
 
1350
                        }else if( comp(*first2, *first1) ){
 
1351
                                *result = *first2;
 
1352
                                ++result;
 
1353
 
 
1354
                                //Elliminate duplicates
 
1355
                                InputIterator2 temp = first2;
 
1356
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1357
                                        ++first2;
 
1358
                                }
 
1359
                
 
1360
                        }else{  //They are identical - skip
 
1361
                                //Elliminate duplicates
 
1362
                                InputIterator1 temp = first1;
 
1363
                                while( first1 != last1 && !comp( *temp, *first1) ){
 
1364
                                        ++first1;
 
1365
                                }
 
1366
                                while( first2 != last2 && !comp( *temp, *first2) ){
 
1367
                                        ++first2;
 
1368
                                }
 
1369
                        }
 
1370
                }
 
1371
 
 
1372
                //Clean up remaining elements
 
1373
                while(first1 != last1){
 
1374
                        *result = *first1;
 
1375
                        ++result;
 
1376
                        InputIterator1 temp = first1;
 
1377
                        while( first1 != last1 && !comp( *temp, *first1) ){
 
1378
                                ++first1;
 
1379
                        }
 
1380
                }
 
1381
 
 
1382
                while(first2 != last2){
 
1383
                        *result = *first2;
 
1384
                        ++result;
 
1385
                        InputIterator2 temp = first2;
 
1386
                        while( first2 != last2 && !comp( *temp, *first2) ){
 
1387
                                ++first2;
 
1388
                        }
 
1389
                }
 
1390
 
 
1391
                return result;
 
1392
        }
 
1393
 
 
1394
        // _lib.alg.heap.operations_, heap operations:
 
1395
 
 
1396
        template<class RandomAccessIterator> _UCXXEXPORT
 
1397
                void push_heap(RandomAccessIterator first, RandomAccessIterator last)
 
1398
        {
 
1399
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
1400
                push_heap(first, last, c);
 
1401
        }
 
1402
 
 
1403
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
1404
                void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
1405
        {
 
1406
                // *(last - 1) is the last element
 
1407
                RandomAccessIterator begin, middle, end;
 
1408
                begin = first;
 
1409
                end = last - 2;
 
1410
                if(last - first < 2){           //Empty heap
 
1411
                        return;
 
1412
                }
 
1413
                if ( comp(*(last-1), *end) ){   //Belongs past the end - already in place
 
1414
                        return;
 
1415
                }
 
1416
                while(end - begin > 1){
 
1417
                        middle = begin + ((end - begin)/2);
 
1418
                        if( comp(*middle, *(last-1) ) ){
 
1419
                                end = middle;
 
1420
                        }else{
 
1421
                                begin = middle;
 
1422
                        }
 
1423
                }
 
1424
 
 
1425
                if( comp(*begin, *(last-1)) ){
 
1426
                        middle = begin;
 
1427
                }else{
 
1428
                        middle = end;
 
1429
                }
 
1430
 
 
1431
                //Now all we do is swap the elements up to the begining
 
1432
                --last;
 
1433
 
 
1434
                while(last > middle){
 
1435
                        iter_swap(last, last-1);
 
1436
                        --last;
 
1437
                }
 
1438
        }
 
1439
 
 
1440
        template<class RandomAccessIterator> _UCXXEXPORT
 
1441
                void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
 
1442
        {
 
1443
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
1444
                pop_heap(first, last, c);
 
1445
        }
 
1446
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
1447
                void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare)
 
1448
        {
 
1449
                --last;
 
1450
                while(first < last){
 
1451
                        iter_swap( first, first+1);
 
1452
                        ++first;
 
1453
                }
 
1454
        }
 
1455
 
 
1456
        template<class RandomAccessIterator> _UCXXEXPORT
 
1457
                void make_heap(RandomAccessIterator first, RandomAccessIterator last)
 
1458
        {
 
1459
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
1460
                make_heap(first, last, c);
 
1461
        }
 
1462
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
1463
                void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
1464
        {
 
1465
                sort( reverse_iterator<RandomAccessIterator>(last), reverse_iterator<RandomAccessIterator>(first), comp);
 
1466
        }
 
1467
        template<class RandomAccessIterator> _UCXXEXPORT
 
1468
                void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
 
1469
        {
 
1470
                less<typename iterator_traits<RandomAccessIterator>::value_type> c;
 
1471
                sort_heap(first, last, c);
 
1472
        }
 
1473
        template<class RandomAccessIterator, class Compare> _UCXXEXPORT
 
1474
                void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
1475
        {
 
1476
                sort( first, last, comp);
 
1477
        }
 
1478
 
 
1479
 
 
1480
        // _lib.alg.min.max_, minimum and maximum:
 
1481
        template<class T> _UCXXEXPORT
 
1482
                const T& min(const T& a, const T& b)
 
1483
        {
 
1484
                if(b < a){
 
1485
                        return b;
 
1486
                }
 
1487
                return a;
 
1488
        }
 
1489
 
 
1490
        template<class T, class Compare> _UCXXEXPORT
 
1491
                const T& min(const T& a, const T& b, Compare comp)
 
1492
        {
 
1493
                if( comp(b, a) == true){
 
1494
                        return b;
 
1495
                }
 
1496
                return a;
 
1497
        }
 
1498
 
 
1499
        template<class T> _UCXXEXPORT
 
1500
                const T& max(const T& a, const T& b)
 
1501
        {
 
1502
                if( a < b){
 
1503
                        return b;
 
1504
                }
 
1505
                return a;
 
1506
        }
 
1507
 
 
1508
        template<class T, class Compare> _UCXXEXPORT
 
1509
                const T& max(const T& a, const T& b, Compare comp)
 
1510
        {
 
1511
                if( comp(a, b) ){
 
1512
                        return b;
 
1513
                }
 
1514
                return a;
 
1515
        }
 
1516
 
 
1517
        template<class ForwardIterator> _UCXXEXPORT
 
1518
                ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
 
1519
        {
 
1520
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
1521
                return min_element(first, last, c);
 
1522
        }
 
1523
 
 
1524
        template<class ForwardIterator, class Compare> _UCXXEXPORT
 
1525
                ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp)
 
1526
        {
 
1527
                ForwardIterator retval = first;
 
1528
                ++first;
 
1529
                while(first != last){
 
1530
                        if( comp( *first, *retval) ){
 
1531
                                retval = first;
 
1532
                        }
 
1533
                        ++first;
 
1534
                }
 
1535
                return retval;
 
1536
        }
 
1537
 
 
1538
        template<class ForwardIterator> _UCXXEXPORT
 
1539
                ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
 
1540
        {
 
1541
                less<typename iterator_traits<ForwardIterator>::value_type> c;
 
1542
                return max_element(first, last, c);
 
1543
        }
 
1544
 
 
1545
        template<class ForwardIterator, class Compare> _UCXXEXPORT
 
1546
                ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp)
 
1547
        {
 
1548
                ForwardIterator retval = first;
 
1549
                ++first;
 
1550
                while(first != last){
 
1551
                        if( comp( *retval, *first ) ){
 
1552
                                retval = first;
 
1553
                        }
 
1554
                        ++first;
 
1555
                }
 
1556
                return retval;
 
1557
        }
 
1558
 
 
1559
        template<class InputIterator1, class InputIterator2> _UCXXEXPORT
 
1560
                bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
 
1561
                        InputIterator2 first2, InputIterator2 last2)
 
1562
        {
 
1563
                less<typename iterator_traits<InputIterator1>::value_type> c;
 
1564
                return lexicographical_compare(first1, last1, first2, last2, c);
 
1565
        }
 
1566
 
 
1567
        template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
 
1568
                bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
 
1569
                        InputIterator2 first2, InputIterator2 last2, Compare comp)
 
1570
        {
 
1571
                while(first1 != last1 && first2 != last2){
 
1572
                        if( comp(*first1, *first2) ){
 
1573
                                return true;
 
1574
                        }
 
1575
                        if( comp(*first2, *first1) ){
 
1576
                                return false;
 
1577
                        }
 
1578
                        ++first1;
 
1579
                        ++first2;
 
1580
                }
 
1581
                return first1==last1 && first2 != last2;
 
1582
        }
 
1583
 
 
1584
        // _lib.alg.permutation.generators_, permutations
 
1585
        template<class BidirectionalIterator> _UCXXEXPORT
 
1586
                bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
 
1587
        {
 
1588
                less<typename iterator_traits<BidirectionalIterator>::value_type> c;
 
1589
                return next_permutation(first, last, c);
 
1590
        }
 
1591
 
 
1592
        template<class BidirectionalIterator, class Compare> _UCXXEXPORT
 
1593
                bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
 
1594
        {
 
1595
                if(first == last){
 
1596
                        return false;   // No data
 
1597
                }
 
1598
                BidirectionalIterator i = last;
 
1599
                --i;
 
1600
                if(i == first){
 
1601
                        return false;   //Only one element
 
1602
                }
 
1603
                BidirectionalIterator ii = i;
 
1604
                --ii;
 
1605
                //If the last two items are in order, swap them and call it done
 
1606
                if( comp(*ii, *i) ){
 
1607
                        iter_swap(ii, i);
 
1608
                        return true;
 
1609
                }
 
1610
 
 
1611
 
 
1612
                //This part of the algorithm copied from G++ header files ver. 3.4.2
 
1613
                i = last;
 
1614
                --i;
 
1615
                for(;;){
 
1616
                        ii = i;
 
1617
                        --i;
 
1618
                        if ( comp(*i, *ii) ){
 
1619
                                BidirectionalIterator j = last;
 
1620
                                --j;
 
1621
                                while ( !comp(*i, *j)){
 
1622
                                        --j;
 
1623
                                }
 
1624
                                iter_swap(i, j);
 
1625
                                reverse(ii, last);
 
1626
                                return true;
 
1627
                        }
 
1628
                        if (i == first){
 
1629
                                reverse(first, last);
 
1630
                                return false;
 
1631
                        }
 
1632
                }
 
1633
                
 
1634
 
 
1635
        }
 
1636
 
 
1637
        template<class BidirectionalIterator> _UCXXEXPORT
 
1638
                bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
 
1639
        {
 
1640
                less<typename iterator_traits<BidirectionalIterator>::value_type> c;
 
1641
                return prev_permutation(first, last, c);
 
1642
        }
 
1643
        
 
1644
        template<class BidirectionalIterator, class Compare> _UCXXEXPORT
 
1645
                bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
 
1646
        {
 
1647
                if(first == last){
 
1648
                        return false;   // No data
 
1649
                }
 
1650
                BidirectionalIterator i = last;
 
1651
                --i;
 
1652
                if(i == first){
 
1653
                        return false;   //Only one element
 
1654
                }
 
1655
                BidirectionalIterator ii = i;
 
1656
                --ii;
 
1657
                //If the last two items are in reverse order, swap them and call it done
 
1658
                if( comp(*i, *ii) ){
 
1659
                        iter_swap(ii, i);
 
1660
                        return true;
 
1661
                }
 
1662
 
 
1663
                //Copied from GNU GCC header files version 3.4.2
 
1664
                i = last;
 
1665
                --i;
 
1666
 
 
1667
                for(;;){
 
1668
                        ii = i;
 
1669
                        --i;
 
1670
                        if ( comp(*ii, *i)){
 
1671
                                BidirectionalIterator j = last;
 
1672
                                --j;
 
1673
                                while ( !comp(*j, *i)){
 
1674
                                        --j;
 
1675
                                }
 
1676
                                iter_swap(i, j);
 
1677
                                reverse(ii, last);
 
1678
                                return true;
 
1679
                        }
 
1680
                        if (i == first){
 
1681
                                reverse(first, last);
 
1682
                                return false;
 
1683
                        }
 
1684
                }
 
1685
 
 
1686
        }
 
1687
 
 
1688
}
 
1689
 
 
1690
#pragma GCC visibility pop
 
1691
 
 
1692
#endif
 
1693
 
 
1694
 
 
1695