0,0 → 1,884 |
/* Copyright (C) 2004 Garrett A. Kajmowicz |
This file is part of the uClibc++ Library. |
This library is free software; you can redistribute it and/or |
modify it under the terms of the GNU Lesser General Public |
License as published by the Free Software Foundation; either |
version 2.1 of the License, or (at your option) any later version. |
|
This library is distributed in the hope that it will be useful, |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
Lesser General Public License for more details. |
|
You should have received a copy of the GNU Lesser General Public |
License along with this library; if not, write to the Free Software |
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
|
*/ |
|
|
#include <memory> |
#include <iterator> |
#include <stdexcept> |
|
#pragma GCC visibility push(default) |
|
#ifndef __STD_HEADER_DEQUE |
#define __STD_HEADER_DEQUE |
|
|
namespace std{ |
template <class T, class Allocator = allocator<T> > class deque; |
template <class T, class Allocator> bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> void swap(deque<T,Allocator>& x, deque<T,Allocator>& y); |
|
template <class T, class Allocator> class _UCXXEXPORT deque { |
public: |
friend bool operator==<>(const deque<T, Allocator>& x, const deque<T, Allocator>& y); |
friend class deque_iter; |
friend class deque_citer; |
class deque_iter; |
class deque_citer; |
|
typedef typename Allocator::reference reference; |
typedef typename Allocator::const_reference const_reference; |
typedef deque_iter iterator; |
typedef deque_citer const_iterator; |
typedef typename Allocator::size_type size_type; |
typedef typename Allocator::difference_type difference_type; |
typedef T value_type; |
typedef Allocator allocator_type; |
typedef typename Allocator::pointer pointer; |
typedef typename Allocator::const_pointer const_pointer; |
typedef std::reverse_iterator<iterator> reverse_iterator; |
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
|
explicit deque(const Allocator& al = Allocator()); |
explicit deque(size_type n, const T& value = T(), const Allocator& al = Allocator()); |
template <class InputIterator> deque(InputIterator first, InputIterator last, const Allocator& = Allocator()); |
deque(const deque<T,Allocator>& x); |
~deque(); |
|
deque<T,Allocator>& operator=(const deque<T,Allocator>& x); |
template <class InputIterator> void assign(InputIterator first, InputIterator last); |
template <class Size, class U> void assign(Size n, const U& u = U()); |
allocator_type get_allocator() const; |
|
iterator begin(); |
const_iterator begin() const; |
iterator end(); |
const_iterator end() const; |
reverse_iterator rbegin(); |
const_reverse_iterator rbegin() const; |
reverse_iterator rend(); |
const_reverse_iterator rend() const; |
|
size_type size() const; |
size_type max_size() const; |
void resize(size_type sz, T c = T()); |
bool empty() const; |
|
reference operator[](size_type n); |
const_reference operator[](size_type n) const; |
reference at(size_type n); |
const_reference at(size_type n) const; |
reference front(); |
const_reference front() const; |
reference back(); |
const_reference back() const; |
|
void push_front(const T& x); |
void push_back(const T& x); |
iterator insert(iterator position, const T& x = T()); |
void insert(iterator position, size_type n, const T& x); |
template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); |
void pop_front(); |
void pop_back(); |
|
iterator erase(iterator position); |
iterator erase(iterator first, iterator last); |
void swap(deque<T,Allocator>&); |
void clear(); |
|
protected: |
void reserve(size_type n); |
inline size_type array_element(size_type deque_element) const{ |
if(deque_element < (data_size - first_element)){ |
return first_element + deque_element; |
} |
return deque_element - (data_size - first_element); |
} |
inline size_type first_subtract(size_type sub_size) const{ |
if(sub_size > first_element){ |
return (data_size - first_element) - sub_size; |
} |
return first_element - sub_size; |
} |
|
T * data; |
size_type data_size; //Physical size of array |
size_type elements; //Elements in array |
size_type first_element; //Element number of array 0..n |
size_type last_element; //Element number of array 0..n |
Allocator a; |
|
}; |
|
|
template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_iter |
: public std::iterator< |
random_access_iterator_tag, |
T, |
typename Allocator::difference_type, |
typename Allocator::pointer, |
typename Allocator::reference |
> |
{ |
friend class deque<T, Allocator>; |
protected: |
deque<T, Allocator> * container; |
typename Allocator::size_type element; |
|
public: |
deque_iter() : container(0), element(0) { } |
deque_iter(const deque_iter & d) : container (d.container), element(d.element) { } |
deque_iter(deque<T, Allocator> * c, typename Allocator::size_type e) |
: container(c), element(e) |
{ |
return; |
} |
~deque_iter() { } |
deque_iter & operator=(const deque_iter & d){ |
container = d.container; |
element = d.element; |
return *this; |
} |
T & operator*(){ |
return container->data[container->array_element(element)]; |
} |
T * operator->(){ |
return container->data + container->array_element(element); |
} |
const T & operator*() const{ |
return container->data[container->array_element(element)]; |
} |
const T * operator->() const{ |
return container->data + container->array_element(element); |
} |
bool operator==(const deque_iter & d) const{ |
if(container == d.container && element == d.element){ |
return true; |
} |
return false; |
} |
bool operator==(const deque_citer & d) const{ |
if(container == d.container && element == d.element){ |
return true; |
} |
return false; |
} |
bool operator!=(const deque_iter & d) const{ |
if(container != d.container || element != d.element){ |
return true; |
} |
return false; |
} |
bool operator!=(const deque_citer & d) const{ |
if(container != d.container || element != d.element){ |
return true; |
} |
return false; |
} |
bool operator<(const deque_iter & d) const{ |
if(element < d.element){ |
return true; |
} |
return false; |
} |
bool operator<(const deque_citer & d) const{ |
if(element < d.element){ |
return true; |
} |
return false; |
} |
bool operator<=(const deque_iter & d) const{ |
if(element <= d.element){ |
return true; |
} |
return false; |
} |
bool operator<=(const deque_citer & d) const{ |
if(element <= d.element){ |
return true; |
} |
return false; |
} |
bool operator>(const deque_iter & d) const{ |
if(element > d.element){ |
return true; |
} |
return false; |
} |
bool operator>(const deque_citer & d) const{ |
if(element > d.element){ |
return true; |
} |
return false; |
} |
bool operator>=(const deque_iter & d) const{ |
if(element >= d.element){ |
return true; |
} |
return false; |
} |
bool operator>=(const deque_citer & d) const{ |
if(element >= d.element){ |
return true; |
} |
return false; |
} |
deque_iter & operator++(){ |
++element; |
return *this; |
} |
deque_iter operator++(int){ |
deque_iter temp(container, element); |
++element; |
return temp; |
} |
deque_iter operator+(typename Allocator::size_type n){ |
deque_iter temp(container, element + n); |
return temp; |
} |
deque_iter & operator+=(typename Allocator::size_type n){ |
element += n; |
return *this; |
} |
deque_iter & operator--(){ |
--element; |
return *this; |
} |
deque_iter operator--(int){ |
deque_iter temp(container, element); |
--element; |
return temp; |
} |
deque_iter operator-(typename Allocator::size_type n){ |
deque_iter temp(container, element - n); |
return temp; |
} |
deque_iter & operator-=(typename Allocator::size_type n){ |
element -= n; |
return *this; |
} |
typename Allocator::size_type operator-(const deque_iter & d){ |
return element - d.element; |
} |
|
}; |
|
template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_citer |
: public std::iterator< |
random_access_iterator_tag, |
T, |
typename Allocator::difference_type, |
typename Allocator::const_pointer, |
typename Allocator::const_reference |
> |
{ |
friend class deque<T, Allocator>; |
protected: |
const deque<T, Allocator> * container; |
typename Allocator::size_type element; |
|
public: |
deque_citer() : container(0), element(0) { } |
deque_citer(const deque_citer & d) : container (d.container), element(d.element) { } |
deque_citer(const deque_iter & d) : container (d.container), element(d.element) { } |
deque_citer(const deque<T, Allocator> * c, typename Allocator::size_type e) |
: container(c), element(e) |
{ |
return; |
} |
~deque_citer() { } |
deque_citer & operator=(const deque_iter & d){ |
container = d.container; |
element = d.element; |
return *this; |
} |
const T & operator*() const{ |
return container->data[container->array_element(element)]; |
} |
const T * operator->() const{ |
return container->data + container->array_element(element); |
} |
bool operator==(const deque_citer & d) const{ |
if(container == d.container && element == d.element){ |
return true; |
} |
return false; |
} |
bool operator==(const deque_iter & d) const{ |
if(container == d.container && element == d.element){ |
return true; |
} |
return false; |
} |
bool operator!=(const deque_citer & d) const{ |
if(container != d.container || element != d.element){ |
return true; |
} |
return false; |
} |
bool operator!=(const deque_iter & d) const{ |
if(container != d.container || element != d.element){ |
return true; |
} |
return false; |
} |
bool operator<(const deque_citer & d) const{ |
if(element < d.element){ |
return true; |
} |
return false; |
} |
bool operator<(const deque_iter & d) const{ |
if(element < d.element){ |
return true; |
} |
return false; |
} |
bool operator<=(const deque_citer & d) const{ |
if(element <= d.element){ |
return true; |
} |
return false; |
} |
bool operator<=(const deque_iter & d) const{ |
if(element <= d.element){ |
return true; |
} |
return false; |
} |
bool operator>(const deque_citer & d) const{ |
if(element > d.element){ |
return true; |
} |
return false; |
} |
bool operator>(const deque_iter & d) const{ |
if(element > d.element){ |
return true; |
} |
return false; |
} |
bool operator>=(const deque_citer & d){ |
if(element >= d.element){ |
return true; |
} |
return false; |
} |
bool operator>=(const deque_iter & d){ |
if(element >= d.element){ |
return true; |
} |
return false; |
} |
deque_citer & operator++(){ |
++element; |
return *this; |
} |
deque_citer operator++(int){ |
deque_citer temp(container, element); |
++element; |
return temp; |
} |
deque_citer operator+(typename Allocator::size_type n){ |
deque_citer temp(container, element + n); |
return temp; |
} |
deque_citer & operator+=(typename Allocator::size_type n){ |
element += n; |
return *this; |
} |
deque_citer & operator--(){ |
--element; |
return *this; |
} |
deque_citer operator--(int){ |
deque_citer temp(container, element); |
--element; |
return temp; |
} |
deque_citer operator-(typename Allocator::size_type n){ |
deque_citer temp(container, element - n); |
return temp; |
} |
deque_citer & operator-=(typename Allocator::size_type n){ |
element -= n; |
return *this; |
} |
typename Allocator::size_type operator-(const deque_citer & d){ |
return element - d.element; |
} |
|
}; |
|
template<class T, class Allocator> deque<T, Allocator>::deque(const Allocator& al) |
: data(0), |
data_size(0), elements(0), first_element(0), last_element(0), a(al) |
{ |
data_size = __UCLIBCXX_STL_BUFFER_SIZE__; |
data = a.allocate(data_size); |
first_element = data_size /2; |
last_element = first_element; |
} |
|
|
template<class T, class Allocator> deque<T, Allocator>::deque( |
size_type n, const T& value, const Allocator& al) |
: data(0), |
elements(n), first_element(0), last_element(0), a(al) |
{ |
data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__; |
data = a.allocate(data_size); |
first_element = (data_size - elements) / 2; |
last_element = first_element; |
|
for(n=first_element ; n < last_element; ++n ){ |
a.construct(data+n, value); |
} |
} |
|
|
template<class T, class Allocator> template <class InputIterator> |
deque<T, Allocator>::deque(InputIterator first, InputIterator last, const Allocator& al) |
: data(0), |
data_size(0), elements(0), first_element(0), last_element(0), a(al) |
{ |
data_size = __UCLIBCXX_STL_BUFFER_SIZE__; |
data = a.allocate(data_size); |
first_element = data_size / 4; //Note sure how big, but let's add a little space... |
last_element = first_element; |
while(first != last){ |
push_back(*first); |
++first; |
} |
} |
|
|
template<class T, class Allocator> deque<T, Allocator>::deque(const deque<T,Allocator>& x) |
: data(0), |
elements(0), first_element(0), last_element(0), a(x.a) |
{ |
data_size = x.elements + __UCLIBCXX_STL_BUFFER_SIZE__; |
data = a.allocate(data_size); |
first_element = (data_size - x.elements) / 2; |
last_element = first_element; |
for(size_type i=0; i < x.elements; ++i){ |
push_back(x[i]); |
} |
} |
|
|
template<class T, class Allocator> deque<T, Allocator>::~deque(){ |
clear(); |
a.deallocate(data, data_size); |
} |
|
template<class T, class Allocator> deque<T,Allocator>& deque<T, Allocator>:: |
operator=(const deque<T,Allocator>& x) |
{ |
if(&x == this){ |
return *this; |
} |
resize(x.elements); |
for(size_t i = 0; i < elements; ++i){ |
data[array_element(i)] = x[i]; |
} |
return *this; |
} |
|
|
template<class T, class Allocator> template <class InputIterator> void |
deque<T, Allocator>::assign(InputIterator first, InputIterator last) |
{ |
clear(); |
while(first !=last){ |
push_back(*first); |
++first; |
} |
} |
|
|
template<class T, class Allocator> template <class Size, class U> void |
deque<T, Allocator>::assign(Size n, const U& u) |
{ |
if(&u == this){ |
return; |
} |
clear(); |
for(size_type i = 0; i < n; ++i){ |
push_back(u); |
} |
} |
|
|
template<class T, class Allocator> typename deque<T, Allocator>::allocator_type |
deque<T, Allocator>::get_allocator() const |
{ |
return a; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::iterator deque<T, Allocator>::begin() |
{ |
return deque_iter(this, 0); |
} |
|
|
template<class T, class Allocator> typename deque<T, Allocator>::const_iterator |
deque<T, Allocator>::begin() const |
{ |
return deque_citer(this, 0); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::iterator deque<T, Allocator>::end() |
{ |
return deque_iter(this, elements); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_iterator deque<T, Allocator>::end() const |
{ |
return deque_citer(this, elements); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rbegin() |
{ |
return reverse_iterator(end()); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rbegin() const |
{ |
return const_reverse_iterator(end()); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rend() |
{ |
return reverse_iterator(begin()); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rend() const |
{ |
return const_reverse_iterator(begin()); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::size_type deque<T, Allocator>::size() const |
{ |
return elements; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::size_type deque<T, Allocator>::max_size() const |
{ |
return ((size_type)(-1)) / sizeof(T); |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::resize(size_type sz, T c){ |
reserve(sz); |
while(sz > size()){ |
push_back(c); |
} |
while(sz < size()){ |
pop_back(); |
} |
} |
|
template<class T, class Allocator> bool deque<T, Allocator>::empty() const{ |
return (elements == 0); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reference deque<T, Allocator>::operator[](size_type n) |
{ |
return data[array_element(n)]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reference deque<T, Allocator>::operator[](size_type n) const |
{ |
return data[array_element(n)]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reference deque<T, Allocator>::at(size_type n) |
{ |
if(n > elements){ |
__throw_out_of_range("Out of deque range"); |
} |
return data[array_element(n)]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reference deque<T, Allocator>::at(size_type n) const |
{ |
if(n > elements){ |
__throw_out_of_range("Out of deque range"); |
} |
return data[array_element(n)]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reference deque<T, Allocator>::front() |
{ |
return data[first_element]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reference deque<T, Allocator>::front() const |
{ |
return data[first_element]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::reference deque<T, Allocator>::back() |
{ |
return data[array_element(elements-1)]; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::const_reference deque<T, Allocator>::back() const |
{ |
return data[array_element(elements-1)]; |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::push_front(const T& x){ |
reserve(elements + 1); |
first_element = first_subtract(1); |
a.construct(data + first_element, x); |
++elements; |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::push_back(const T& x){ |
reserve(elements + 1); |
a.construct(data + last_element, x); |
++elements; |
last_element = array_element(elements); |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::iterator deque<T, Allocator>::insert(iterator position, const T& x) |
{ |
reserve(elements+1); |
if(position.element > (elements/2)){ |
//Push all elements back 1 |
push_back(x); |
for(size_type i = elements-1; i > position.element; --i){ |
at(i) = at(i-1); |
} |
}else{ |
//Push all elements forward 1 |
push_front(x); |
for(size_type i = 0; i < position.element; ++i){ |
at(i) = at(i+1); |
} |
} |
at(position.element) = x; |
return deque_iter(this, position.element); |
} |
|
template<class T, class Allocator> void deque<T, Allocator>:: |
insert(typename deque<T, Allocator>::iterator position, size_type n, const T& x) |
{ |
reserve(elements + n); |
for(size_t i =0; i < n; ++i){ |
position = insert(position, x); |
} |
} |
|
template<class T, class Allocator> template <class InputIterator> |
void deque<T, Allocator>::insert (iterator position, InputIterator first, InputIterator last) |
{ |
while(first != last){ |
position = insert(position, *first); |
++first; |
} |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::pop_front(){ |
if(elements == 0){ |
__throw_out_of_range("deque pop_front"); |
} |
a.destroy(data + first_element); |
first_element = array_element(1); |
--elements; |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::pop_back(){ |
last_element = array_element(elements - 1); |
a.destroy(data + last_element); |
--elements; |
} |
|
template<class T, class Allocator> typename |
deque<T, Allocator>::iterator deque<T, Allocator>::erase(typename deque<T, Allocator>::iterator position) |
{ |
if(position.element > (elements /2)){ |
for(size_type i = position.element; i < elements - 1; ++i){ |
at(i) = at(i+1); |
} |
pop_back(); |
}else{ |
for(size_type i = position.element; i > 0; --i){ |
at(i) = at(i-1); |
} |
pop_front(); |
} |
return deque_iter(this, position.element); |
} |
|
template<class T, class Allocator> typename deque<T, Allocator>::iterator |
deque<T, Allocator>:: |
erase(typename deque<T, Allocator>::iterator first, typename deque<T, Allocator>::iterator last) |
{ |
//Shift backwards |
size_type num_move = last.element - first.element; |
if( first.element > (elements - last.element) ){ |
for(size_type i = last.element; i < elements ; ++i){ |
at(i-num_move) = at(i); |
} |
for(size_type i = 0; i < num_move ; ++i){ |
pop_back(); |
} |
}else{ |
for(size_type i = 0; i < first.element ; ++i){ |
at(last.element - i - 1) = at(first.element - i - 1); |
} |
for(size_type i = 0; i < num_move ; ++i){ |
pop_front(); |
} |
} |
return deque_iter(this, first.element); |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::swap(deque<T,Allocator>& x) |
{ |
T * temp_data; |
typename deque<T,Allocator>::size_type temp_size; |
|
//Swap data pointers |
temp_data = x.data; |
x.data = data; |
data = temp_data; |
|
//Swap array sizes |
temp_size = x.data_size; |
x.data_size = data_size; |
data_size = temp_size; |
|
//Swap num array elements |
temp_size = x.elements; |
x.elements = elements; |
elements = temp_size; |
|
//Swap first_pointer |
temp_size = x.first_element; |
x.first_element = first_element; |
first_element = temp_size; |
|
//Swap last_pointer |
temp_size = x.last_element; |
x.last_element = last_element; |
last_element = temp_size; |
} |
|
template<class T, class Allocator> void deque<T, Allocator>::clear() |
{ |
while(elements > 0 ){ |
pop_back(); |
} |
} |
|
|
template<class T, class Allocator> void deque<T, Allocator>::reserve(typename deque<T, Allocator>::size_type n) |
{ |
if(data_size >= n){ |
return; |
} |
|
size_type size_temp; |
size_type first_temp; |
T * data_temp; |
size_temp = n + __UCLIBCXX_STL_BUFFER_SIZE__; //Reserve extra 'cause we can |
data_temp = a.allocate(size_temp); |
|
first_temp = (size_temp - elements) / 2; |
for(size_type i = 0; i < elements; ++i){ |
a.construct(data_temp + first_temp + i, data[array_element(i)]); |
a.destroy(data + array_element(i)); |
} |
|
//Now shuffle pointers |
a.deallocate(data, data_size); |
data = data_temp; |
data_size = size_temp; |
first_element = first_temp; |
last_element = first_element + elements; |
} |
|
|
template <class T, class Allocator> _UCXXEXPORT |
bool |
operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y) |
{ |
if(x.elements != y.elements){ |
return false; |
} |
for(typename deque<T,Allocator>::size_type i = 0; i < x.elements; ++i){ |
if(x[i] < y[i] || y[i] < x[i]){ |
return false; |
} |
} |
return true; |
} |
|
template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> _UCXXEXPORT |
bool |
operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y) |
{ |
if(x == y){ |
return false; |
} |
return true; |
} |
template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); |
template <class T, class Allocator> _UCXXEXPORT void swap(deque<T,Allocator>& x, deque<T,Allocator>& y){ |
x.swap(y); |
} |
|
|
|
} |
|
#pragma GCC visibility pop |
|
#endif |
|
|
|
|