/elec/propeller-clock

To get this branch, use:
bzr branch http://bzr.ed.am/elec/propeller-clock
57 by edam
added ulibc
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