Range Array implementation in C/C++   Leave a comment

#ifndef __RANGE_ARRAY_STL_CONTAINER_h__
#define __RANGE_ARRAY_STL_CONTAINER_h__

#include <iostream>
#include <iterator>
#include <string>
#include <algorithm>

#include <stdexcept> //out_of_range exception

using namespace std;

#pragma warning(disable: 4786)

#ifdef _UNICODE
typedef basic_string<wchar_t> __tstring;
#else
typedef basic_string __tstring;
#endif

//the range array stl container impl.
#define MAX_CAPACITY 20

template >
    class range_array
{
	signed int length;
	signed int _capacity;
	int lowerbound;
	int upperbound;
	_A _allocator;
public:
	//required stl starndard typedefs...
	typedef _T value_type;
	typedef _A allocator_type;
	typedef typename _A::reference reference;
	typedef typename _A::const_reference const_reference;
	typedef typename _A::size_type size_type;
	typedef typename _A::difference_type difference_type;
	typedef typename _A::pointer pointer;
	typedef typename _A::const_pointer const_pointer;

	//forward iterators
	typedef pointer iterator;
	typedef const_pointer const_iterator;

public:
	//constructors
	range_array(){
		length = 0;
		_capacity = MAX_CAPACITY;
		lowerbound = upperbound = 0;
		array_ptr = _allocator.allocate(_capacity, 0);
		if(!array_ptr)
			throw bad_alloc("insufficient memory for this allocation range!");		
	}

	//construct a zero-based array of num elements initialized to _Vy, 
	//required by for STL com patibility
	range_array(size_type num, const _T& _Vy){
		////hlm my impl
		_capacity = length = num;
		lowerbound = 0;
		upperbound = length-1;
		array_ptr = _allocator.allocate(length, 0);
		//init values ranging from _F to _L
		if(!array_ptr)
			throw bad_alloc("insufficient memory for this allocation range!");

		iterator _F = begin();
		iterator _L = end();

		while(_F!=_L) _allocator.construct(_F++, _Vy); //*_F++ = _Vy;
	}

	//construct an array of the specified range with each element initialized to _Vy
	range_array(int lbound, int hbound, const _T& _Vy){
		//htm my impl
		if(lbound >= hbound)
			throw range_error("invalid lower and upper bound for this range-array object!");
		lowerbound	= lbound;
		upperbound	= hbound;
		length		= (upperbound-lowerbound) + 1;
		_capacity	= length;
		array_ptr = _allocator.allocate(length, 0);
		iterator _F = begin();
		iterator _L = end();

		while(_F!=_L) _allocator.construct(_F++, _Vy);
	}

	//construct an array from a range of iterators
	range_array(iterator _F, iterator _L){
		//htm my impl
		array_ptr = _allocator.allocate(_L - _F, 0);
		if(!array_ptr)
			throw bad_alloc("insufficient memory for this allocation range!");

		iterator _Ft = begin();
		length		= 0;
		_capacity	= 0;
		lowerbound	= 0;
		upperbound	= 0;
		while(_F!=_L){
			_allocator.construct(_Ft++, *_F++);
			upperbound = length++;
		}
		_capacity	= length;
	}

	//copy ctor
	range_array(const range_array& _ra){ 
		//htm my impl.		
		array_ptr = _allocator.allocate(_ra.capacity(), 0);
		if(!array_ptr)
			throw bad_alloc("insufficient memory for this allocation range!");

		iterator _Fs = const_cast(_ra.begin());
		iterator _Ls = const_cast(_ra.end());
		iterator _Ft = begin();

		while(_Fs!=_Ls){ 
			_allocator.construct(_Ft++, *_Fs++);
		}
		length	   = _ra.length;
		_capacity  = _ra._capacity;
		lowerbound = _ra.lowerbound;
		upperbound = _ra.upperbound;
	}	
public:
	~range_array(){
		//call destructors for elements in the container...
		for(size_type index=0;index < size(); index++)
			_allocator.destroy(&array_ptr[index]);
		_allocator.deallocate(array_ptr, length);
	}
private:
	pointer array_ptr; //dynamic array ptr
public:
	iterator begin(){
		return &array_ptr[0];
	}
	iterator end(){
		return &array_ptr[length];
	}

	const_iterator begin() const{
		return &array_ptr[0];
	}
	const_iterator end() const{
		return &array_ptr[length];
	}
public:
	//operators
	reference operator[](int _i){ //_T&
		return array_ptr[_i-lowerbound];
	}
	const_reference operator[](int _i) const{ //const _T&
		return array_ptr[_i-lowerbound];
	}
	//assignment
	range_array& operator=(const range_array& _ra){
		//hlm my impl
		if(this!=&_ra){
			iterator _F = begin();
			iterator _L = end();
			while(_F!=_L) {
				_allocator.destroy(_F);
				_F++;
			}
			_allocator.deallocate(array_ptr, length);
			array_ptr = _allocator.allocate(_ra.capacity(), 0);
			if(!array_ptr)
				throw bad_alloc("insufficient memory for this allocation range!");

			iterator _Fs = const_cast(_ra.begin());
			iterator _Ls = const_cast(_ra.end());
			_F = begin();

			while(_Fs!=_Ls){ 
				*_F++ = *_Fs++;
			}
			length	   = _ra.length;
			_capacity  = _ra.capacity();
			lowerbound = _ra.lowerbound;
			upperbound = _ra.upperbound;
		}
		return *this;
	}
public:
	//insert functions

	//insert at p value _Vy
	iterator insert(iterator p, const _T& _Vy){
		//hlm my impl		
		iterator _insp = p;		
		size_type _new_capacity = _capacity;
		if(size() < capacity()){
			if(p==end()){
				_allocator.construct(&array_ptr[length], _Vy);
				_insp = &array_ptr[length++];
				upperbound = ((length + lowerbound) - 1);
				return _insp;
			}
			//if(p==begin())
			//	_new_capacity++;
		}
		else
			_new_capacity += MAX_CAPACITY;
		pointer nptrar = 0;
		if(_capacity < _new_capacity)
			nptrar = _allocator.allocate(_new_capacity, 0);
		else
			nptrar = array_ptr;
		if(!nptrar)
			throw bad_alloc("insufficient memory for this insertion operation!");

		if(1){	
			iterator fi = begin();
			int index = 0;
			//copy from beginning and before p
			if(_capacity < _new_capacity)
			{								
				while(fi!=p){
					nptrar[index] = *fi++;
					index++;
				}
				//assign _Vy to current p iterator position
				_insp = &(nptrar[index++] = _Vy);
				//copy from p and before end
				iterator pf = p;
				iterator fe = end();
				while(pf!=fe){
					nptrar[index] = *pf++;
					index++;
				}
				//deallocate current array...
				_allocator.deallocate(array_ptr, length);				
				_capacity = _new_capacity;
				//point to new array
				array_ptr = nptrar;
			}else{								
				unsigned int offset = length;
				while(p < (nptrar + offset)){
					nptrar[offset] = nptrar[offset-1];
					--offset;
				}
				//assign _Vy to current p iterator position
				_insp = (pointer)&(nptrar[offset] = _Vy);
			}
			length++;
			//set the new relative offsets...
			if((lowerbound < upperbound) || (lowerbound ==0 && upperbound==0)/*for default ctor*/) 			{ 				if(p==begin()) 					lowerbound--; 				else 					upperbound++; 			} 		} 		return _insp; 	} 	//insert num of copies of _Vy at p 	void insert(iterator p, size_type num, const _T& _Vy){ 		for(; num > 0; num--) p = insert(p, _Vy) + 1;
	}
	//insert a range specified from _F to _L
	void insert(iterator p, iterator _F, iterator _L){
		while(_F!=_L){
			p = insert(p, *_F) + 1;
			_F++;
		}
	}
public:
	//erase functions

	//erase element at p
	iterator erase(iterator p){
		//html my impl
		iterator nptr = p;
		if(length > 0 && p!=end()){
			iterator ptr = begin();
			unsigned int index = 0;
			while(ptr < p){
				ptr++;
				index++;
			}
			while(index < length){
				array_ptr[index] = array_ptr[index + 1];				
				index++;
			}
			length--;
			//set the new relative offsets...
			if(lowerbound < upperbound) 			{ 				if(p==begin()) 					lowerbound++; 				else  					upperbound--; 			}			 		} 		return nptr; 	} 	//erase elements in a specified range... 	iterator erase(iterator _F, iterator _L){ 		//htm my impl 		iterator p = _F; 		int ecount = (_L - _F); 		for(int i=ecount; i > 0; i--)
			 p = erase(p);		
		return p;
	}
public:
	//push and pop functions
	void push_back(const _T& _Vy){
		//insert at end or simple append...
		insert(end(), _Vy);
	}
	//remove element from end...
	void pop_back(){
		erase(end()-1);
	}
	//add element to front
	void push_front(const _T& _Vy){
		insert(begin(), _Vy);
	}
	//erase from start...
	void pop_front(){
		erase(begin());
	}

public:
	//front and back functions
	_T& at(int _i){
		if(_iupperbound)
			throw out_of_range("subscript or index is out of range!");
		return operator[](_i);
	}
	const _T& at(int _i) const{
		if(_iupperbound)
			throw out_of_range("subscript or index is out of range!");
		return operator[](_i);
	}
	//first element
	_T& front(){
		return at(lowerbound);
	}
	const _T& front() const{
		return at(lowerbound);
	}
	_T& back(){
		return at(upperbound);
	}
	const _T& back() const{
		return at(upperbound);
	}

public:
	//other stl compliant members
	size_type size(){
		return end()-begin(); //length
	}

	size_type max_size(){
		return _allocator.max_size();
	}
	bool empty(){
		return (size()==0);
	}

	void swap(range_array& _ra){
		range_array<_T> tmp = *this;
		*this = _ra;
		_ra = tmp;
	}
	//remove and destroy all elements.
	void clear(){
		erase(begin(), end());
	}
	int capacity() const{
		return _capacity;
	}
public:
	//non-STL functions
	int lbound(){
		return lowerbound;
	}
	int ubound(){
		return upperbound;
	}
};

//relation operators
template
bool operator==(range_array<_T, _A>& ra1, range_array<_T, _A>& ra2){
	return (ra1.size()==ra2.size()) && (equal(ra1.begin(), ra1.end(), ra2.begin()));
}

template
bool operator!=(const range_array<_T, _A>& ra1, const range_array<_T, _A>& ra2){
	return !(ra1==ra2);
}

template
bool operator<(const range_array<_T, _A>& ra1, const range_array<_T, _A>& ra2)
{
	return lexicographical_compare(ra1.begin(), ra1.end(), 
									ra2.begin(), ra2.end());
}

template
bool operator>(const range_array<_T, _A>& ra1, const range_array<_T, _A>& ra2){
	return (ra2 < ra1);
}

template
bool operator<=(const range_array<_T, _A>& ra1, const range_array<_T, _A>& ra2){
	return !(ra2 < ra1); //(ra1 < ra2) || (ra1==ra2);
}

template
bool operator>=(const range_array<_T, _A>& ra1, const range_array<_T, _A>& ra2){
	return !(ra1 < ra2); //(ra1 > ra2) || (ra1==ra2);
}

#endif //__RANGE_ARRAY_STL_CONTAINER_h__
Advertisements

Posted February 2, 2013 by hmarzan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: