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