deque

mpeg4 video codec mpeg4 video codec

		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);
		data = 0;
		data_size = 0;
		first_element = 0;
		last_element = 0;
	}

	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, defaultValue);
		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>&)
	{
		abort();
	}

	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){
		T * temp_data;
//		T temp_value;
		typename deque<T,Allocator>::size_type temp_size;

		//Swap data pointers
		temp_data = x.data;
		x.data = y.data;
		y.data = temp_data;

		//Swap temp values;
//		temp_value = x.defaultValue;
//		x.defaultValue = y.defaultValue;
//		y.defaultValue = temp_value;

		//Swap array sizes
		temp_size = x.data_size;
		x.data_size = y.data_size;
		y.data_size = temp_size;

		//Swap num array elements
		temp_size  = x.elements;
		x.elements = y.elements;
		y.elements = temp_size;

		//Swap first_pointer
		temp_size = x.first_element;
		x.first_element = y.first_element;
		y.first_element = temp_size;

		//Swap last_pointer
		temp_size = x.last_element;
		x.last_element = y.last_element;
		y.last_element = temp_size;
	}



}


#endif