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
- browse files at revision 57
- compare with another revision
- download diff
- download tarball
- view history from revision 57
- Committer: edam
- Date: 2012-02-25 01:31:43 UTC
- Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc
- files added:
- arduino.mk
- project
- src/utility
- test/fan-test
- test/fan-test/Makefile
- test/led-test
- test/led-test/Makefile
- test/phantom-button-presses
- test/phantom-button-presses/Makefile
- files removed:
- COPYING
- files renamed:
- Notes => notes
- propeller-clock/ => src/
- propeller-clock/propeller-clock.pde => src/propeller-clock.ino
- propeller-clock/utility/ => src/util/
- fan-test/ => test/
- fan-test/fan-test.pde => test/fan-test/fan-test.ino
- files modified:
- .bzrignore
- src/Makefile
added
removed
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
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0