/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: Dan
  • Date: 2011-11-02 22:26:25 UTC
  • Revision ID: dan@waxworlds.org-20111102222625-fo8prx1bigkjecbt
just deleted the test file

Show diffs side-by-side

added added

removed removed

Lines of Context:
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