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

  • Committer: Dan
  • Date: 2011-11-02 22:15:18 UTC
  • Revision ID: dan@waxworlds.org-20111102221518-b5j2m5l2pd71f4t1
Added Test whilst testing

Show diffs side-by-side

added added

removed removed

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