/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: 2011-12-02 19:57:07 UTC
  • Revision ID: edam@waxworlds.org-20111202195707-lko4ap3pfe1jrgd9
renamed code directories and updated the comments in the code

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