/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/list

  • Committer: edam
  • Date: 2012-02-25 01:31:43 UTC
  • Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
/*      Copyright (C) 2004 Garrett A. Kajmowicz
 
2
 
 
3
        This file is part of the uClibc++ Library.
 
4
 
 
5
        This library is free software; you can redistribute it and/or
 
6
        modify it under the terms of the GNU Lesser General Public
 
7
        License as published by the Free Software Foundation; either
 
8
        version 2.1 of the License, or (at your option) any later version.
 
9
 
 
10
        This library is distributed in the hope that it will be useful,
 
11
        but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
        Lesser General Public License for more details.
 
14
 
 
15
        You should have received a copy of the GNU Lesser General Public
 
16
        License along with this library; if not, write to the Free Software
 
17
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
*/
 
19
 
 
20
#include <memory>
 
21
#include <iterator>
 
22
#include <algorithm>
 
23
 
 
24
#ifndef __STD_HEADER_LIST
 
25
#define __STD_HEADER_LIST 1
 
26
 
 
27
#pragma GCC visibility push(default)
 
28
 
 
29
namespace std{
 
30
 
 
31
        template <class T, class Allocator = allocator<T> > class _UCXXEXPORT list {
 
32
        public:
 
33
                typedef typename Allocator::reference           reference;
 
34
                typedef typename Allocator::const_reference     const_reference;
 
35
                typedef typename Allocator::size_type           size_type;
 
36
                typedef typename Allocator::difference_type     difference_type;
 
37
                typedef T                                       value_type;
 
38
                typedef Allocator                               allocator_type;
 
39
                typedef typename Allocator::pointer             pointer;
 
40
                typedef typename Allocator::const_pointer       const_pointer;
 
41
 
 
42
        protected:
 
43
                class node;
 
44
                class iter_list;
 
45
 
 
46
                node * list_start;
 
47
                node * list_end;
 
48
                size_type elements;
 
49
                Allocator a;
 
50
 
 
51
        public:
 
52
 
 
53
                typedef iter_list                               iterator;
 
54
                typedef iter_list                               const_iterator;
 
55
                typedef std::reverse_iterator<iterator>         reverse_iterator;
 
56
                typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
 
57
 
 
58
                explicit list(const Allocator& = Allocator());
 
59
                explicit list(size_type n, const T& value = T(), const Allocator& = Allocator());
 
60
                template <class InputIterator> list(InputIterator first, InputIterator last, 
 
61
                        const Allocator& al= Allocator());
 
62
                list(const list<T,Allocator>& x);
 
63
                ~list();
 
64
 
 
65
                list<T,Allocator>& operator=(const list<T,Allocator>& x){
 
66
                        if(&x == this){
 
67
                                return *this;
 
68
                        }
 
69
                        clear();
 
70
                        iterator i = x.begin();
 
71
                        while(i != x.end()){
 
72
                                push_back(*i);
 
73
                                ++i;
 
74
                        }
 
75
                        return *this;
 
76
                }
 
77
 
 
78
                template <class InputIterator> void assign(InputIterator first, InputIterator last);
 
79
                template <class Size, class U> void assign(Size n, const U& u = U());
 
80
                allocator_type get_allocator() const;
 
81
 
 
82
                iterator                begin();
 
83
                const_iterator          begin() const;
 
84
                iterator                end();
 
85
                const_iterator          end() const;
 
86
                reverse_iterator        rbegin();
 
87
                const_reverse_iterator  rbegin() const;
 
88
                reverse_iterator        rend();
 
89
                const_reverse_iterator  rend() const;
 
90
 
 
91
                bool      empty() const;
 
92
                size_type size() const;
 
93
                size_type max_size() const;
 
94
                void      resize(size_type sz, T c = T());
 
95
 
 
96
                reference       front();
 
97
                const_reference front() const;
 
98
                reference       back();
 
99
                const_reference back() const;
 
100
 
 
101
                void push_front(const T& x);
 
102
                void pop_front();
 
103
                void push_back(const T& x);
 
104
                void pop_back();
 
105
                iterator insert(iterator position, const T& x = T());
 
106
                void     insert(iterator position, size_type n, const T& x);
 
107
                template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last);
 
108
                iterator erase(iterator position);
 
109
                iterator erase(iterator position, iterator last);
 
110
                void     swap(list<T,Allocator>&);
 
111
                void     clear();
 
112
 
 
113
                void splice(iterator position, list<T,Allocator>& x);
 
114
                void splice(iterator position, list<T,Allocator>& x, iterator i);
 
115
                void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
 
116
                void remove(const T& value);
 
117
                template <class Predicate> void remove_if(Predicate pred);
 
118
                void unique();
 
119
                template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
 
120
                void merge(list<T,Allocator>& x);
 
121
                template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
 
122
                void sort();
 
123
                template <class Compare> void sort(Compare comp);
 
124
                void reverse();
 
125
        protected:
 
126
                void swap_nodes(node * x, node * y);
 
127
        };
 
128
 
 
129
 
 
130
        //Implementations of List
 
131
 
 
132
        //List node
 
133
        template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::node{
 
134
        public:
 
135
                node * previous;
 
136
                node * next;
 
137
                T * val;
 
138
 
 
139
                node(): previous(0), next(0), val(0){ }
 
140
                node(const T & t ): previous(0), next(0), val(0) {
 
141
                        val = new T(t);
 
142
                        //FIXME use allocator somehow but only call constructor once
 
143
                }
 
144
                node(const T & t, node * p, node * n): previous(p), next(n), val(0) {
 
145
                        val = new T(t);
 
146
                }
 
147
                ~node(){ }
 
148
        };
 
149
 
 
150
        //List iterator
 
151
        template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::iter_list
 
152
                : public std::iterator<
 
153
                        bidirectional_iterator_tag, 
 
154
                        T, 
 
155
                        typename Allocator::difference_type, 
 
156
                        typename Allocator::pointer, 
 
157
                        typename Allocator::reference
 
158
                >
 
159
        {
 
160
        private:
 
161
                node * current;
 
162
        public:
 
163
                iter_list():current(0) { }
 
164
                iter_list( typename list<T, Allocator>::node * n): current(n) { }
 
165
                iter_list(const list<T, Allocator>::iter_list & l): current(l.current) { }
 
166
                ~iter_list(){ }
 
167
 
 
168
                iter_list & operator=(const list<T, Allocator>::iter_list & right ){
 
169
                        current = right.current;
 
170
                        return *this;
 
171
                }
 
172
 
 
173
                T & operator*(){
 
174
                        return *(current->val);
 
175
                }
 
176
                T * operator->(){
 
177
                        return current->val;
 
178
                }
 
179
                const T & operator*() const{
 
180
                        return *current->val;
 
181
                }
 
182
                const T * operator->() const{
 
183
                        return current->val;
 
184
                }
 
185
 
 
186
                bool operator==(const list<T, Allocator>::iter_list & right) const {
 
187
                        return (current == right.current);
 
188
                }
 
189
 
 
190
                bool operator!=(const list<T, Allocator>::iter_list & right) const {
 
191
                        return (current != right.current);
 
192
                }
 
193
 
 
194
                iter_list & operator++(){
 
195
                        current = current->next;
 
196
                        return *this;
 
197
                }
 
198
 
 
199
                iter_list operator++(int){
 
200
                        iter_list temp(current);
 
201
                        current = current->next;
 
202
                        return temp;
 
203
                }               
 
204
                iter_list & operator--(){
 
205
                        current = current->previous;
 
206
                        return *this;
 
207
                }
 
208
 
 
209
                iter_list operator--(int){
 
210
                        iter_list temp(current);
 
211
                        current = current->previous;
 
212
                        return temp;
 
213
                }
 
214
                node * link_struct(){
 
215
                        return current;
 
216
                }
 
217
                iter_list & operator+=(unsigned int n){
 
218
                        for(unsigned int i = 0; i < n; ++i){
 
219
                                current = current->next;
 
220
                        }
 
221
                        return *this;
 
222
                }
 
223
                iter_list & operator-=(unsigned int n){
 
224
                        for(unsigned int i = 0; i < n; ++i){
 
225
                                current = current->previous;
 
226
                        }
 
227
                        return *this;
 
228
                }
 
229
        };
 
230
 
 
231
 
 
232
        template<class T, class Allocator> list<T, Allocator>::list(const Allocator& al)
 
233
                :list_start(0), list_end(0), elements(0), a(al)
 
234
        {
 
235
                //End node
 
236
                list_start = new node();
 
237
                list_end = list_start;
 
238
                return;
 
239
        }
 
240
 
 
241
        template<class T, class Allocator> list<T, Allocator>::list
 
242
                (typename Allocator::size_type n, const T& value, const Allocator& al)
 
243
                :list_start(0), list_end(0), elements(0), a(al)
 
244
        {
 
245
                //End node
 
246
                list_start = new node();
 
247
                list_end = list_start;
 
248
 
 
249
                for(typename Allocator::size_type i = 0; i < n ; ++i){
 
250
                        push_back(value);
 
251
                }
 
252
        }
 
253
 
 
254
        template<class T, class Allocator> template <class InputIterator>
 
255
                list<T, Allocator>::list
 
256
                (InputIterator first, InputIterator last, const Allocator& al)
 
257
                : list_start(0), list_end(0), elements(0), a(al)
 
258
        {
 
259
                list_start = new node();
 
260
                list_end = list_start;
 
261
                while(first != last){
 
262
                        push_back(*first);
 
263
                        ++first;
 
264
                }
 
265
        }
 
266
 
 
267
        template<class T, class Allocator> list<T, Allocator>::list(const list<T,Allocator>& x)
 
268
                : list_start(0), list_end(0), elements(0), a(x.a)
 
269
        {
 
270
                list_start = new node();
 
271
                list_end = list_start;
 
272
 
 
273
                iterator i = x.begin();
 
274
                while(i != x.end()){
 
275
                        push_back( *i);
 
276
                        ++i;
 
277
                }
 
278
        }
 
279
 
 
280
        template<class T, class Allocator> list<T, Allocator>::~list(){
 
281
                while(elements > 0){
 
282
                        pop_front();
 
283
                }
 
284
                delete list_start->val;
 
285
#if UCLIBCXX_DEBUG
 
286
                list_start->val = 0;
 
287
#endif
 
288
                delete list_start;
 
289
#if UCLIBCXX_DEBUG
 
290
                list_start = 0;
 
291
                list_end = 0;
 
292
#endif
 
293
        }
 
294
 
 
295
 
 
296
        template<class T, class Allocator> void list<T, Allocator>::swap_nodes(node * x, node * y){
 
297
                T * v = x->val;
 
298
                x->val = y->val;
 
299
                y->val = v;
 
300
        }
 
301
 
 
302
        template<class T, class Allocator> typename list<T, Allocator>::iterator 
 
303
                list<T, Allocator>::begin()
 
304
        {
 
305
                return iterator(list_start);
 
306
        }
 
307
 
 
308
        
 
309
        template<class T, class Allocator> typename list<T, Allocator>::const_iterator
 
310
                list<T, Allocator>::begin() const
 
311
        {
 
312
                return const_iterator(list_start);
 
313
        }
 
314
 
 
315
        
 
316
        template<class T, class Allocator> typename list<T, Allocator>::iterator
 
317
                list<T, Allocator>::end()
 
318
        {
 
319
                return iterator(list_end);
 
320
        }
 
321
 
 
322
        template<class T, class Allocator> typename list<T, Allocator>::const_iterator
 
323
                list<T, Allocator>::end() const
 
324
        {
 
325
                return const_iterator(list_end);
 
326
        }
 
327
 
 
328
        template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
 
329
                list<T, Allocator>::rbegin()
 
330
        {
 
331
                return reverse_iterator(end());
 
332
        }
 
333
 
 
334
        template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
 
335
                list<T, Allocator>::rbegin() const
 
336
        {
 
337
                return const_reverse_iterator(end());
 
338
        }
 
339
 
 
340
        template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
 
341
                list<T, Allocator>::rend()
 
342
        {
 
343
                return reverse_iterator(begin());
 
344
        }
 
345
 
 
346
        template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
 
347
                list<T, Allocator>::rend() const
 
348
        {
 
349
                return const_reverse_iterator(begin());
 
350
        }
 
351
 
 
352
        template<class T, class Allocator> bool list<T, Allocator>::empty() const{
 
353
                return (elements == 0);
 
354
        }
 
355
        template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::size() const{
 
356
                return elements;
 
357
        }
 
358
        template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::max_size() const{
 
359
                return ((size_type)(-1)) / (sizeof(T) + sizeof(node));
 
360
        }
 
361
        template<class T, class Allocator> void list<T, Allocator>::resize(typename Allocator::size_type sz, T c){
 
362
//              if(sz > elements){
 
363
                        for(typename Allocator::size_type i = elements; i < sz; ++i){
 
364
                                push_back(c);
 
365
                        }
 
366
//              }
 
367
//              if(sz < elements){
 
368
                        for(typename Allocator::size_type i = elements; i > sz; --i){
 
369
                                pop_back();
 
370
                        }
 
371
//              }
 
372
        }
 
373
 
 
374
        template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::front(){
 
375
                return *(list_start->val);
 
376
        }
 
377
        template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::front() const{
 
378
                return *(list_start->val);
 
379
        }
 
380
        template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::back(){
 
381
                return *(list_end->previous->val);
 
382
        }
 
383
        template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::back() const{
 
384
                return *(list_end->previous->val);
 
385
        }
 
386
 
 
387
 
 
388
        template<class T, class Allocator> void list<T, Allocator>::push_front(const T& x){
 
389
                node * temp = new node(x);
 
390
                list_start->previous = temp;
 
391
                temp->previous = 0;
 
392
                temp->next = list_start;
 
393
                list_start = temp;
 
394
                ++elements;
 
395
        }
 
396
 
 
397
        template<class T, class Allocator> void list<T, Allocator>::pop_front(){
 
398
                if(elements > 0){
 
399
                        list_start = list_start->next;
 
400
                        delete list_start->previous->val;
 
401
#if UCLIBCXX_DEBUG
 
402
                        list_start->previous->val = 0;
 
403
                        list_start->previous->next = 0;
 
404
                        list_start->previous->previous = 0;
 
405
#endif
 
406
                        delete list_start->previous;
 
407
                        list_start->previous = 0;
 
408
                        --elements;
 
409
                }
 
410
        }
 
411
 
 
412
        template<class T, class Allocator> void list<T, Allocator>::push_back(const T& x){
 
413
                if(elements == 0){
 
414
                        //The list is completely empty
 
415
                        list_start = new node(x);
 
416
                        list_end->previous = list_start;
 
417
                        list_start->previous = 0;
 
418
                        list_start->next = list_end;
 
419
                        elements = 1;
 
420
                }else{
 
421
                        node * temp = new node(x);
 
422
                        temp->previous = list_end->previous;
 
423
                        temp->next = list_end;
 
424
                        list_end->previous->next = temp;
 
425
                        list_end->previous = temp;
 
426
                        ++elements;
 
427
                }
 
428
        }
 
429
 
 
430
        template<class T, class Allocator> void list<T, Allocator>::pop_back(){
 
431
                if(elements > 0){
 
432
                        node * temp = list_end->previous;
 
433
                        if(temp == list_start){
 
434
                                list_end->previous = 0;
 
435
                                list_start = list_end;
 
436
                        }else{
 
437
                                temp->previous->next = temp->next;
 
438
                                list_end->previous = temp->previous;
 
439
                        }
 
440
                        delete temp->val;
 
441
#if UCLIBCXX_DEBUG
 
442
                        temp->val = 0;
 
443
                        temp->next = 0;
 
444
                        temp->previous = 0;
 
445
#endif
 
446
                        delete temp;
 
447
#if UCLIBCXX_DEBUG
 
448
                        temp = 0;
 
449
#endif
 
450
                        --elements;
 
451
                }
 
452
        }
 
453
 
 
454
 
 
455
        template<class T, class Allocator> typename list<T, Allocator>::iterator 
 
456
                list<T, Allocator>::insert(iterator position, const T& x)
 
457
        {
 
458
                node * temp = new node(x);
 
459
 
 
460
                temp->previous = position.link_struct()->previous;
 
461
                temp->next = position.link_struct();
 
462
 
 
463
                if(temp->previous == 0){
 
464
                        list_start = temp;
 
465
                }else{
 
466
                        position.link_struct()->previous->next = temp;
 
467
                }
 
468
 
 
469
                position.link_struct()->previous = temp;
 
470
 
 
471
                ++elements;
 
472
                --position;
 
473
                return position;
 
474
        }
 
475
 
 
476
        template<class T, class Allocator> void list<T, Allocator>::insert(iterator position, size_type n, const T& x){
 
477
                for(typename list<T, Allocator>::size_type i = 0; i < n; ++i){
 
478
                        position = insert(position, x);
 
479
                }
 
480
        }
 
481
 
 
482
        template<class T, class Allocator> template <class InputIterator> void
 
483
                list<T, Allocator>::insert(iterator position, InputIterator first, InputIterator last)
 
484
        {
 
485
                while(first !=last){
 
486
                        insert(position, *first);
 
487
                        ++first;
 
488
                }
 
489
        }
 
490
        template<class T, class Allocator> typename list<T, Allocator>::iterator
 
491
                list<T, Allocator>::erase(iterator position)
 
492
        {
 
493
                if(position != end() ){
 
494
                        node * temp = position.link_struct();
 
495
                        if(temp == list_start){
 
496
                                ++position;
 
497
                                temp->next->previous = 0;
 
498
                                list_start = temp->next;
 
499
                        }else{
 
500
                                --position;
 
501
                                temp->next->previous = temp->previous;
 
502
                                temp->previous->next = temp->next;
 
503
                                ++position;
 
504
                        }
 
505
                        delete temp->val;
 
506
#if UCLIBCXX_DEBUG
 
507
                        temp->next = 0;
 
508
                        temp->previous = 0;
 
509
                        temp->val = 0;
 
510
#endif
 
511
                        delete temp;
 
512
#if UCLIBCXX_DEBUG
 
513
                        temp = 0;
 
514
#endif
 
515
                        --elements;
 
516
                }
 
517
                return position;
 
518
        }
 
519
        template<class T, class Allocator> typename list<T, Allocator>::iterator
 
520
                list<T, Allocator>::erase(iterator position, iterator last)
 
521
        {
 
522
                iterator temp = position;
 
523
                while(position !=last){
 
524
                        position = erase(position);
 
525
                }
 
526
                return position;
 
527
        }
 
528
        template<class T, class Allocator> void list<T, Allocator>::swap(list<T,Allocator>& l){
 
529
                node * temp;
 
530
                size_type tempel;
 
531
 
 
532
                temp = list_start;
 
533
                list_start = l.list_start;
 
534
                l.list_start = temp;
 
535
 
 
536
                temp = list_end;
 
537
                list_end = l.list_end;
 
538
                l.list_end = temp;
 
539
 
 
540
                tempel = elements;
 
541
                elements = l.elements;
 
542
                l.elements = tempel;
 
543
        }
 
544
        template<class T, class Allocator> void list<T, Allocator>::clear(){
 
545
                while(elements > 0){
 
546
                        pop_front();
 
547
                }
 
548
        }
 
549
 
 
550
        template<class T, class Allocator>
 
551
                void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x)
 
552
        {
 
553
 
 
554
                //Can't add non-existant elements
 
555
                if(x.elements == 0){
 
556
                        return;
 
557
                }
 
558
 
 
559
                elements += x.elements;
 
560
                x.elements = 0;
 
561
 
 
562
 
 
563
                //Chaining to the begining
 
564
                if(position == begin()){
 
565
                        x.list_end->previous->next = list_start;
 
566
                        list_start->previous = x.list_end->previous;
 
567
 
 
568
                        list_start = x.list_start;
 
569
 
 
570
                        x.list_start = x.list_end;
 
571
                        x.list_end->previous = 0;
 
572
 
 
573
                        return;
 
574
                }
 
575
 
 
576
                //Link everything we need
 
577
                x.list_start->previous = position.link_struct()->previous;
 
578
                position.link_struct()->previous->next = x.list_start;
 
579
        
 
580
                position.link_struct()->previous = x.list_end->previous;
 
581
                x.list_end->previous->next = position.link_struct();
 
582
 
 
583
                //Clean up the other list
 
584
                
 
585
                x.list_start = x.list_end;
 
586
                x.list_end->previous=0;
 
587
 
 
588
        }
 
589
 
 
590
        template<class T, class Allocator>
 
591
                void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x, iterator i)
 
592
        {
 
593
                //Invalid conditions
 
594
                if( x.elements == 0 || i == position || position.link_struct() == i.link_struct()->next ){
 
595
                        return;
 
596
                }
 
597
 
 
598
 
 
599
                //Do we need to adjust the begining pointer?
 
600
                if(i == x.begin()){
 
601
                        x.list_start = x.list_start->next;
 
602
                        x.list_start->previous = 0;
 
603
                }
 
604
 
 
605
 
 
606
                //Insert at begining special case
 
607
                if(position == begin()){
 
608
 
 
609
                        i.link_struct()->previous->next = i.link_struct()->next;
 
610
                        i.link_struct()->next->previous = i.link_struct()->previous;
 
611
 
 
612
                        i.link_struct()->previous = 0;
 
613
                        i.link_struct()->next = position.link_struct();
 
614
                        position.link_struct()->previous = i.link_struct();
 
615
 
 
616
                        list_start = i.link_struct();
 
617
 
 
618
                        --x.elements;
 
619
                        ++elements;
 
620
                        return;
 
621
                }
 
622
 
 
623
                if( i.link_struct()->previous != 0){
 
624
                        i.link_struct()->previous->next = i.link_struct()->next;
 
625
                        i.link_struct()->next->previous = i.link_struct()->previous;
 
626
                }else{
 
627
                        i.link_struct()->next->previous = 0;
 
628
                        x.list_start = i.link_struct()->next;
 
629
                }
 
630
                
 
631
                i.link_struct()->previous = position.link_struct()->previous;
 
632
                position.link_struct()->previous->next = i.link_struct();
 
633
 
 
634
                i.link_struct()->next = position.link_struct();
 
635
                position.link_struct()->previous = i.link_struct();
 
636
 
 
637
                --x.elements;
 
638
                ++elements;
 
639
        }
 
640
 
 
641
        template<class T, class Allocator>
 
642
                void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x,
 
643
                        iterator first, iterator last)
 
644
        {
 
645
                if(x.elements == 0){
 
646
                        return;
 
647
                }
 
648
 
 
649
                iterator temp;
 
650
                while(first != last){
 
651
                        temp = first;
 
652
                        ++first;
 
653
                        splice(position, x, temp);
 
654
                }
 
655
        }
 
656
 
 
657
 
 
658
        template<class T, class Allocator> void list<T, Allocator>::remove(const T& value){
 
659
                iterator temp = begin();
 
660
                while( temp != end() ){
 
661
                        if(*temp == value){
 
662
                                temp = erase(temp);
 
663
                        }else{
 
664
                                ++temp;
 
665
                        }
 
666
                }
 
667
        }
 
668
 
 
669
 
 
670
        template<class T, class Allocator> template <class Predicate> void list<T, Allocator>::remove_if(Predicate pred){
 
671
                iterator temp = begin();
 
672
                while( temp != end() ){
 
673
                        if( pred(*temp) ){
 
674
                                temp = erase(temp);
 
675
                        }else{
 
676
                                ++temp;
 
677
                        }
 
678
                }
 
679
        }
 
680
 
 
681
 
 
682
        template<class T, class Allocator> void list<T, Allocator>::unique(){
 
683
                equal_to<typename iterator_traits<iterator>::value_type> p;
 
684
                unique(p);
 
685
        }
 
686
 
 
687
        template<class T, class Allocator> template <class BinaryPredicate>
 
688
                void list<T, Allocator>::unique(BinaryPredicate binary_pred)
 
689
        {
 
690
                iterator temp1 = begin();
 
691
                iterator temp2;
 
692
                ++temp1;
 
693
                while( temp1 != end() ){
 
694
                        temp2 = temp1;
 
695
                        --temp2;
 
696
                        if( binary_pred(*temp1, *temp2) ){
 
697
                                erase(temp1);
 
698
                                temp1 = temp2;
 
699
                        }
 
700
                        ++temp1;
 
701
                }
 
702
        }
 
703
 
 
704
        template<class T, class Allocator> void list<T, Allocator>::merge(list<T,Allocator>& x){
 
705
                less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
 
706
                merge(x, c);
 
707
        }
 
708
 
 
709
        template<class T, class Allocator> template <class Compare> 
 
710
                void list<T, Allocator>::merge(list<T,Allocator>& x, Compare comp)
 
711
        {
 
712
                iterator source = x.begin();
 
713
                iterator temp;
 
714
                iterator dest  = begin();
 
715
 
 
716
                while(source != x.end()){
 
717
                        while( dest != end() && comp (*dest, *source) ){
 
718
                                ++dest;
 
719
                        }
 
720
                        ++elements;
 
721
                        --x.elements;
 
722
 
 
723
                        temp = source;
 
724
                        ++temp;
 
725
 
 
726
                        if(dest == begin()){
 
727
                                dest.link_struct()->previous = source.link_struct();
 
728
                                source.link_struct()->next = dest.link_struct();
 
729
                                source.link_struct()->previous = 0;
 
730
                                list_start = source.link_struct();
 
731
                        }else{
 
732
                                source.link_struct()->previous = dest.link_struct()->previous;
 
733
                                dest.link_struct()->previous->next = source.link_struct();
 
734
                                source.link_struct()->next = dest.link_struct();
 
735
                                dest.link_struct()->previous = source.link_struct();
 
736
                        }
 
737
                        source = temp;
 
738
                }
 
739
 
 
740
                //Fix up x;
 
741
                x.list_start = x.list_end;
 
742
                x.list_start->previous = 0;
 
743
        }
 
744
 
 
745
        template<class T, class Allocator> void list<T, Allocator>::sort(){
 
746
                less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
 
747
                sort(c);
 
748
        }
 
749
 
 
750
        template<class T, class Allocator> template <class Compare>
 
751
                void list<T, Allocator>::sort(Compare comp)
 
752
        {
 
753
                typename list<T, Allocator>::iterator i, j, k;
 
754
 
 
755
                //FIXME - bubble sort
 
756
 
 
757
                if(elements == 0){
 
758
                        return;
 
759
                }
 
760
 
 
761
                i = end();
 
762
                --i;
 
763
                while(i != begin()){
 
764
                        j = begin();
 
765
                        k = j;
 
766
                        ++k;
 
767
                        while(j != i){
 
768
                                if( comp(*k, *j) ){
 
769
                                        swap_nodes(k.link_struct(), j.link_struct());
 
770
                                }
 
771
                                ++j;
 
772
                                ++k;
 
773
                        }
 
774
                        --i;
 
775
                }
 
776
        }
 
777
 
 
778
 
 
779
        template<class T, class Allocator> void list<T, Allocator>::reverse(){
 
780
                if(elements == 0){
 
781
                        return;
 
782
                }
 
783
 
 
784
                node * current;
 
785
                node * following;
 
786
                node * temp;
 
787
 
 
788
                //Need to move the list_end element to the begining
 
789
 
 
790
                temp = list_end;
 
791
                list_end = temp->previous;
 
792
                list_end->next = 0;
 
793
 
 
794
                list_start->previous = temp;
 
795
                temp->previous = 0;
 
796
                temp->next = list_start;
 
797
                list_start = temp;
 
798
 
 
799
                current = list_start;
 
800
 
 
801
                while( current != list_end ){
 
802
                        following = current->next;
 
803
 
 
804
                        //Swap the values pointed to/at with the current node
 
805
                        temp = current->next;
 
806
                        current->next = current->previous;
 
807
                        current->previous = temp;
 
808
 
 
809
                        current = following;
 
810
                }
 
811
 
 
812
                //Swap pointers on the end node
 
813
                temp = list_end->next;
 
814
                list_end->next = list_end->previous;
 
815
                list_end->previous = temp;
 
816
 
 
817
 
 
818
                //Swap the fixed pointers
 
819
                temp = list_start;
 
820
                list_start = list_end;
 
821
                list_end = temp;
 
822
 
 
823
        }
 
824
 
 
825
        template <class T, class Allocator>
 
826
        bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y){
 
827
                if(x.size() != y.size()){
 
828
                        return false;
 
829
                }
 
830
                typename list<T,Allocator>::const_iterator i = x.begin();
 
831
                typename list<T,Allocator>::const_iterator j = y.begin();
 
832
 
 
833
                while(i != x.end()){
 
834
                        if( *i != *j){
 
835
                                return false;
 
836
                        }
 
837
                        ++i;
 
838
                        ++j;
 
839
                }
 
840
                return true;
 
841
        }
 
842
 
 
843
        template <class T, class Allocator>
 
844
        bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y){
 
845
                typename list<T,Allocator>::const_iterator i = x.begin();
 
846
                typename list<T,Allocator>::const_iterator j = y.begin();
 
847
                while(i != x.end() && j != y.end()){
 
848
                        if( *i < *j){
 
849
                                return true;
 
850
                        }
 
851
                        if(*j < *i){
 
852
                                return false;
 
853
                        }
 
854
                        ++i;
 
855
                        ++j;
 
856
                }
 
857
                return (i == x.end() && j != y.end());
 
858
        }
 
859
 
 
860
        template <class T, class Allocator>
 
861
        bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y){
 
862
                return !(x == y);
 
863
        }
 
864
 
 
865
        template <class T, class Allocator>
 
866
        bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y){
 
867
                typename list<T,Allocator>::const_iterator i = x.begin();
 
868
                typename list<T,Allocator>::const_iterator j = y.begin();
 
869
                while(i != x.end() && j != y.end()){
 
870
                        if( *i > *j){
 
871
                                return true;
 
872
                        }
 
873
                        if( *j > *i){
 
874
                                return false;
 
875
                        }
 
876
                        ++i;
 
877
                        ++j;
 
878
                }
 
879
                return (i != x.end() && j == y.end());
 
880
        }
 
881
 
 
882
        template <class T, class Allocator>
 
883
        bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y){
 
884
                typename list<T,Allocator>::const_iterator i = x.begin();
 
885
                typename list<T,Allocator>::const_iterator j = y.begin();
 
886
                while(i != x.end() && j != y.end()){
 
887
                        if( *i >= *j){
 
888
                                return true;
 
889
                        }
 
890
                        if(*j >= *i){
 
891
                                return false;
 
892
                        }
 
893
                        ++i;
 
894
                        ++j;
 
895
                }
 
896
                return (i != x.end() && j == y.end());
 
897
        }
 
898
 
 
899
        template <class T, class Allocator>
 
900
        bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y){
 
901
                typename list<T,Allocator>::const_iterator i = x.begin();
 
902
                typename list<T,Allocator>::const_iterator j = y.begin();
 
903
                while(i != x.end() && j != y.end()){
 
904
                        if( *i <= *j){
 
905
                                return true;
 
906
                        }
 
907
                        if(*j <= *i){
 
908
                                return false;
 
909
                        }
 
910
                        ++i;
 
911
                        ++j;
 
912
                }
 
913
                return (i == x.end());
 
914
        }
 
915
 
 
916
        template <class T, class Allocator>
 
917
        void swap(list<T,Allocator>& x, list<T,Allocator>& y){
 
918
                x.swap(y);
 
919
        }
 
920
 
 
921
}
 
922
 
 
923
#pragma GCC visibility pop
 
924
 
 
925
#endif
 
926
 
 
927