c_vector.c

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/*
Copyright (c) 2007 Wenbo Lao(Rob Lao)

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

    1. The origin of this software must not be misrepresented; you must not
    claim that you wrote the original software. If you use this software
    in a product, an acknowledgment in the product documentation would be
    appreciated but is not required.

    2. Altered source versions must be plainly marked as such, and must not be
    misrepresented as being the original software.

    3. This notice may not be removed or altered from any source
    distribution.

	Wenbo Lao(Rob Lao) 
	viewpl(at)gmail.com
*/

#include "c_vector.h"
#include "c_algo.h"
#include "c_memory.h"

typedef value_type node_t;
typedef node_t  * pnode_t;

typedef struct _c_vector_impl
{
	pnode_t _start;
	pnode_t _finish;
	pnode_t _end_of_storage;
} _c_vector_impl;

static c_iterator _A_get_iterator(pnode_t pn);
static c_reverse_iterator _A_get_reverse_iterator(pnode_t pn);

static c_iterator _c_vector_iterator_assign(c_piterator thiz, const c_piterator val)
{
	if(thiz != val)
		thiz->_i = val->_i;
	return *thiz;
}

static value_type _c_vector_iterator_ref(c_piterator thiz)
{
	return *(pnode_t)thiz->_i;
}

static value_type _c_vector_iterator_ref_assign(c_piterator thiz, const value_type val)
{
	return *(pnode_t)thiz->_i = val;
}

static c_iterator _c_vector_iterator_inc(c_piterator thiz)
{
	pnode_t pn = thiz->_i;
	++ pn;
	thiz->_i = pn;
	return *thiz;
}

static c_iterator _c_vector_iterator_inc_n(c_piterator thiz, difference_type n)
{
	pnode_t pn = thiz->_i;
	pn += n;
	thiz->_i = pn;
	return *thiz;
}

static c_iterator _c_vector_iterator_dec(c_piterator thiz)
{
	pnode_t pn = thiz->_i;
	-- pn;
	thiz->_i = pn;
	return *thiz;
}

static c_iterator _c_vector_iterator_dec_n(c_piterator thiz, difference_type n)
{
	pnode_t pn = thiz->_i;
	pn -= n;
	thiz->_i = pn;
	return *thiz;   
}
    
static difference_type _c_vector_iterator_diff(c_piterator thiz, const c_piterator val)
{
	return ((pnode_t)thiz->_i - (pnode_t)val->_i);
}

static value_type _c_vector_iterator_at(c_piterator thiz, difference_type n)
{
	return *((pnode_t)thiz->_i + n);
}

static c_iterator _c_vector_iterator_positive_n(c_piterator thiz, difference_type n)
{
	c_iterator iter;
	pnode_t pn = thiz->_i;
	pn += n;    
	iter = _A_get_iterator(pn);
	return iter;    
}

static c_iterator _c_vector_iterator_negative_n(c_piterator thiz, difference_type n)
{
	c_iterator iter;
	pnode_t pn = thiz->_i;
	pn -= n;    
	iter = _A_get_iterator(pn);
	return iter;
}

static c_bool _c_vector_iterator_equal(c_piterator thiz, const c_piterator val)
{
	return (thiz->_i == val->_i &&
				thiz->_pft == val->_pft);
}

static c_bool _c_vector_iterator_less(c_piterator thiz, const c_piterator val)
{
	return ((pnode_t)thiz->_i < (pnode_t)val->_i);
}

static c_iterator_ft _c_vector_iter_ft = 
{
	_c_vector_iterator_assign,
	_c_vector_iterator_ref,
	_c_vector_iterator_ref_assign,
	_c_vector_iterator_inc,
	_c_vector_iterator_inc_n,
	_c_vector_iterator_dec,
	_c_vector_iterator_dec_n,
	_c_vector_iterator_diff,
	_c_vector_iterator_at,
	_c_vector_iterator_positive_n,
	_c_vector_iterator_negative_n,
	_c_vector_iterator_equal,
	_c_vector_iterator_less
};

static c_reverse_iterator _c_vector_reverse_iterator_assign(c_preverse_iterator thiz, const c_preverse_iterator val)
{
	if(thiz != val)
		thiz->_i = val->_i;
	return *thiz;    
}

static value_type _c_vector_reverse_iterator_ref(c_preverse_iterator thiz)
{
	return *(pnode_t)thiz->_i;
}

static value_type _c_vector_reverse_iterator_ref_assign(c_preverse_iterator thiz, const value_type val)
{
	return *(pnode_t)thiz->_i = val; 
}

static c_reverse_iterator _c_vector_reverse_iterator_inc(c_preverse_iterator thiz)
{
	pnode_t pn = thiz->_i;
	-- pn;
	thiz->_i = pn;
	return *thiz;
}

static c_reverse_iterator _c_vector_reverse_iterator_inc_n(c_preverse_iterator thiz, difference_type n)
{
	pnode_t pn = thiz->_i;
	pn -= n;
	thiz->_i = pn;
	return *thiz;
}

static c_reverse_iterator _c_vector_reverse_iterator_dec(c_preverse_iterator thiz)
{
	pnode_t pn = thiz->_i;
	++ pn;
	thiz->_i = pn;
	return *thiz;
}

static c_reverse_iterator _c_vector_reverse_iterator_dec_n(c_preverse_iterator thiz, difference_type n)
{    
	pnode_t pn = thiz->_i;
	pn += n;
	thiz->_i = pn;
	return *thiz; 
}

static difference_type _c_vector_reverse_iterator_diff(c_preverse_iterator thiz, const c_preverse_iterator val)
{  
	return ((pnode_t)val->_i - (pnode_t)thiz->_i);    
}

static value_type _c_vector_reverse_iterator_at(c_preverse_iterator thiz, difference_type n)
{
	return *((pnode_t)thiz->_i - n);
}

static c_reverse_iterator _c_vector_reverse_iterator_positive_n(c_preverse_iterator thiz, difference_type n)
{
	c_reverse_iterator iter;
	pnode_t pn = thiz->_i;
	pn -= n;    
	iter = _A_get_reverse_iterator(pn);
	return iter;  
}

static c_reverse_iterator _c_vector_reverse_iterator_negative_n(c_preverse_iterator thiz, difference_type n)
{
	c_reverse_iterator iter;
	pnode_t pn = thiz->_i;
	pn += n;    
	iter = _A_get_reverse_iterator(pn);
	return iter;
}

static c_bool _c_vector_reverse_iterator_equal(c_preverse_iterator thiz, const c_preverse_iterator val)
{
	return (thiz->_i == val->_i &&
				thiz->_pft == val->_pft);
}

static c_bool _c_vector_reverse_iterator_less(c_preverse_iterator thiz, const c_preverse_iterator val)
{
	return ((pnode_t)thiz->_i > (pnode_t)val->_i);
}

static c_reverse_iterator_ft _c_vector_rev_iter_ft = 
{
	_c_vector_reverse_iterator_assign,
	_c_vector_reverse_iterator_ref,
	_c_vector_reverse_iterator_ref_assign,
	_c_vector_reverse_iterator_inc,
	_c_vector_reverse_iterator_inc_n,
	_c_vector_reverse_iterator_dec,
	_c_vector_reverse_iterator_dec_n,
	_c_vector_reverse_iterator_diff,
	_c_vector_reverse_iterator_at,
	_c_vector_reverse_iterator_positive_n,
	_c_vector_reverse_iterator_negative_n,
	_c_vector_reverse_iterator_equal,
	_c_vector_reverse_iterator_less
};

static c_iterator _A_get_iterator(pnode_t pn)
{
	c_iterator iter;
	iter._pft = &_c_vector_iter_ft;
	iter._i = pn;
	return iter;
}

static c_reverse_iterator _A_get_reverse_iterator(pnode_t pn)
{   
	c_reverse_iterator iter;
	iter._pft = &_c_vector_rev_iter_ft;
	iter._i = pn;
	return iter;
}

static pnode_t _A_allocate(c_pvector thiz, size_t n)
{
	return __c_malloc(n * sizeof(node_t));
}

static void _A_deallocate(c_pvector thiz, pnode_t p, size_t n)
{
	if(n > 0)
		__c_free(p);
}

static c_iterator _A_allocate_and_copy(c_pvector thiz, size_type n, c_const_iterator first, c_const_iterator last)
{
	c_iterator result = _A_get_iterator(_A_allocate(thiz, n));
	c_uninitialized_copy(first, last, result);
	return result;
}

static void _A_insert_aux1(c_pvector thiz, c_iterator pos, node_t val)
{
	_c_vector_impl * pl = thiz->_l;
	if(pl->_finish != pl->_end_of_storage)
	{
		node_t node;
		*pl->_finish = *(pl->_finish - 1);
		++ pl->_finish;
		node = val;
		c_copy_backward(pos,
				_A_get_iterator(pl->_finish - 2),
				_A_get_iterator(pl->_finish - 1));
		ITER_REF_ASSIGN(pos, node);
	}
	else
	{
		const size_type old_size = c_vector_size(thiz);
		const size_type len = old_size != 0 ? 2 * old_size : 1;
		c_iterator new_start = _A_get_iterator(_A_allocate(thiz, len));
		c_iterator new_finish = new_start;
		new_finish = c_copy(_A_get_iterator(pl->_start), pos, new_start);
		ITER_REF_ASSIGN(new_finish, val);
		ITER_INC(new_finish);
		new_finish = c_copy(pos, _A_get_iterator(pl->_finish), new_finish);
		_A_deallocate(thiz, pl->_start, abs(pl->_end_of_storage - pl->_start));
		pl->_start = new_start._i;
		pl->_finish = new_finish._i;
		pl->_end_of_storage = pl->_start + len;
	}
}

void __c_vector(c_pvector thiz, COMPARER pcmp)
{
	thiz->_cmp = pcmp;
	thiz->_l = __c_malloc(sizeof(_c_vector_impl));
	((_c_vector_impl *)thiz->_l)->_start = NULL;
	((_c_vector_impl *)thiz->_l)->_finish = NULL;
	((_c_vector_impl *)thiz->_l)->_end_of_storage = NULL;
}

void __c_rotcev(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	_A_deallocate(thiz, pl->_start, abs(pl->_end_of_storage - pl->_start));
	__c_free(thiz->_l);
}

c_iterator c_vector_begin(c_pvector thiz)
{
	return _A_get_iterator(((_c_vector_impl*)thiz->_l)->_start);
}

c_iterator c_vector_end(c_pvector thiz)
{
	return _A_get_iterator(((_c_vector_impl*)thiz->_l)->_finish);
}

c_reverse_iterator c_vector_rbegin(c_pvector thiz)
{
	return _A_get_reverse_iterator(((_c_vector_impl*)thiz->_l)->_finish - 1);    
}

c_reverse_iterator c_vector_rend(c_pvector thiz)
{
	return _A_get_reverse_iterator(((_c_vector_impl*)thiz->_l)->_start - 1);
}

size_type c_vector_size(c_pvector thiz)
{
	c_iterator b = c_vector_begin(thiz), e = c_vector_end(thiz);
	return abs(ITER_DIFF(e, b));
}

size_type c_vector_max_size(c_pvector thiz)
{
	return (size_type)(-1) / sizeof(node_t);
}

size_type c_vector_capacity(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	return abs(pl->_end_of_storage - pl->_start);
}

c_bool c_vector_empty(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	return (pl->_start == pl->_finish);
}

value_type c_vector_at(c_pvector thiz, size_type n)
{
	_c_vector_impl * pl = thiz->_l;
	return *(pl->_start + n);
}

c_pvector c_vector_assign(c_pvector thiz, const c_pvector V)
{
	if(V != thiz)
	{
		_c_vector_impl * pl = thiz->_l;
		const size_type vlen = c_vector_size(V);
		if(vlen > c_vector_capacity(thiz))
		{
			c_iterator tmp = _A_allocate_and_copy(thiz,
								vlen,
								c_vector_begin(V),
								c_vector_end(V));
			_A_deallocate(thiz, 
					pl->_start, 
					abs(pl->_end_of_storage - pl->_start));
			pl->_start = tmp._i;
			pl->_end_of_storage = pl->_start + vlen;
		}
		else if(c_vector_size(thiz) >= vlen)
		{
			c_copy(c_vector_begin(V), c_vector_end(V), c_vector_begin(thiz));
		}
		else
		{
			c_iterator bg = c_vector_begin(thiz);
			c_copy(bg, ITER_POSITIVE_N(bg, c_vector_size(thiz)), _A_get_iterator(pl->_start));
			c_uninitialized_copy(ITER_POSITIVE_N(bg, c_vector_size(thiz)),
						c_vector_end(thiz),
						_A_get_iterator(pl->_finish));
		}
		pl->_finish = pl->_start + vlen;
	}
	return thiz;
}

void c_vector_reserve(c_pvector thiz, size_t n)
{
	if(c_vector_capacity(thiz) < n)
	{
		_c_vector_impl * pl = thiz->_l;
		const size_type old_size = c_vector_size(thiz);
		c_iterator tmp = _A_allocate_and_copy(thiz, n, c_vector_begin(thiz), c_vector_end(thiz));
		_A_deallocate(thiz, pl->_start, abs(pl->_end_of_storage - pl->_start));
		pl->_start = tmp._i;
		pl->_finish = pl->_start + old_size;
		pl->_end_of_storage = pl->_start + n;
	}    
}

value_type c_vector_front(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	return *pl->_start;
}

value_type c_vector_back(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	return *(pl->_finish - 1);
}

void c_vector_push_back(c_pvector thiz, const value_type val)
{
	_c_vector_impl * pl = thiz->_l;
	if(pl->_finish != pl->_end_of_storage)
	{
		*pl->_finish = val;
		++ pl->_finish;
	}
	else
		_A_insert_aux1(thiz, c_vector_end(thiz), val);
}

void c_vector_pop_back(c_pvector thiz)
{
	_c_vector_impl * pl = thiz->_l;
	-- pl->_finish;
}

void c_vector_swap(c_pvector thiz, c_pvector V)
{
	c_vector tmp;
	C_SWAP(*thiz, *V, tmp);
}

c_iterator c_vector_insert(c_pvector thiz, c_iterator pos, const value_type val)
{
	c_iterator begin = c_vector_begin(thiz);
	c_iterator end = c_vector_end(thiz);
	size_type n = abs(ITER_DIFF(pos, begin));
	_c_vector_impl * pl = thiz->_l;
	if((pl->_finish != pl->_end_of_storage) && 
		ITER_EQUAL(pos, end))
	{
		*pl->_finish = val;
		++ pl->_finish;
	}
	else
		_A_insert_aux1(thiz, pos, val);
	return ITER_POSITIVE_N(begin, n);
}

void c_vector_insert2(c_pvector thiz, c_iterator pos, c_iterator first, c_iterator last)
{
	if(!ITER_EQUAL(first, last))
	{
		_c_vector_impl * pl = thiz->_l;
		difference_type dn = 0;
		size_type n = 0;
		c_distance1(first, last, &dn);
		n = abs(dn);
		if(abs(pl->_end_of_storage - pl->_finish) >= n)
		{
			const size_type elems_after = pl->_finish - (pnode_t)pos._i;
			c_iterator old_finish = c_vector_end(thiz);
			if(elems_after > n)
			{
				c_uninitialized_copy(_A_get_iterator(pl->_finish - n),
							_A_get_iterator(pl->_finish),
							_A_get_iterator(pl->_finish));
				pl->_finish += n;
				c_copy_backward(pos, ITER_NEGATIVE_N(old_finish, n), old_finish);
				c_copy(first, last, pos);
			}
			else
			{
				c_uninitialized_copy(ITER_POSITIVE_N(first, elems_after), 
							last, 
							_A_get_iterator(pl->_finish));
				pl->_finish += n - elems_after;
				c_uninitialized_copy(pos, old_finish, _A_get_iterator(pl->_finish));
				pl->_finish += elems_after;
				c_copy(first, ITER_POSITIVE_N(first, elems_after), pos);
			}
		}
		else
		{
			const size_type old_size = c_vector_size(thiz);
			const size_type len = old_size + C_MAX(old_size, n);
			c_iterator new_start = _A_get_iterator(_A_allocate(thiz, len));
			c_iterator new_finish = new_start;
			new_finish = c_uninitialized_copy(_A_get_iterator(pl->_start), pos, new_start);
			new_finish = c_uninitialized_copy(first, last, new_finish);
			new_finish = c_uninitialized_copy(pos, _A_get_iterator(pl->_finish), new_finish);
			_A_deallocate(thiz, pl->_start, abs(pl->_end_of_storage - pl->_start));
			pl->_start = new_start._i;
			pl->_finish = new_finish._i;
			pl->_end_of_storage = ITER_POSITIVE_N(new_start, len)._i;
		}
	}
}

void c_vector_fill_insert(c_pvector thiz, c_iterator pos, size_type n, const value_type val)
{
	_c_vector_impl * pl = thiz->_l;
	if(n != 0)
	{
		if(abs(pl->_end_of_storage - pl->_finish) >= n)
		{
			value_type val_copy = val;
			const size_type elems_after = pl->_finish - (pnode_t)pos._i;
			c_iterator old_finish = c_vector_end(thiz);
			if(elems_after > n)
			{
				c_uninitialized_copy(_A_get_iterator(pl->_finish - n),
							_A_get_iterator(pl->_finish),
							_A_get_iterator(pl->_finish));
				pl->_finish += n;
				c_copy_backward(pos, 
						ITER_NEGATIVE_N(old_finish, n),
						old_finish);
				c_fill(pos, ITER_POSITIVE_N(pos, n), val_copy);
			}
			else
			{
				c_uninitialized_fill_n(c_vector_end(thiz), n - elems_after, val_copy);
				pl->_finish += n - elems_after;
				c_uninitialized_copy(pos, old_finish, c_vector_end(thiz));
				pl->_finish += elems_after;
				c_fill(pos, old_finish, val_copy);
			}
		}
		else
		{
			const size_type old_size = c_vector_size(thiz);
			const size_type len = old_size + C_MAX(old_size, n);
			c_iterator new_start = _A_get_iterator(_A_allocate(thiz, len));
			c_iterator new_finish = new_start;
			new_finish = c_uninitialized_copy(_A_get_iterator(pl->_start),
								pos,
								new_start);
			new_finish = c_uninitialized_fill_n(new_finish, n, val);
			new_finish = c_uninitialized_copy(pos, _A_get_iterator(pl->_finish), new_finish);
			_A_deallocate(thiz, pl->_start, abs(pl->_end_of_storage - pl->_start));
			pl->_start = new_start._i;
			pl->_finish = new_finish._i;
			pl->_end_of_storage = pl->_start + len;
        	}
	}
}

c_iterator c_vector_erase(c_pvector thiz, c_iterator pos)
{
	c_iterator pos_1 = ITER_POSITIVE_N(pos, 1);
	c_iterator end = c_vector_end(thiz);
	_c_vector_impl * pl = thiz->_l;
	if(!ITER_EQUAL(pos_1, end))
		c_copy(pos_1, _A_get_iterator(pl->_finish), pos);
	-- pl->_finish;
	return pos;
}

c_iterator c_vector_erase2(c_pvector thiz, c_iterator first, c_iterator last)
{
	_c_vector_impl * pl = thiz->_l;
	c_copy(last, _A_get_iterator(pl->_finish), first);
	pl->_finish = pl->_finish - abs(ITER_DIFF(last, first));
	return first;
}

void c_vector_clear(c_pvector thiz)
{
	c_vector_erase2(thiz, c_vector_begin(thiz), c_vector_end(thiz));
}

void c_vector_resize(c_pvector thiz, size_t n)
{
	c_iterator begin = c_vector_begin(thiz);
	if(n < c_vector_size(thiz))
		c_vector_erase2(thiz, ITER_POSITIVE_N(begin, n), c_vector_end(thiz));
	else
		c_vector_fill_insert(thiz, c_vector_end(thiz), n, NULL);
}

c_bool c_vector_equal(c_pvector thiz, const c_pvector V)
{
	c_binary_predicate bp =  c_binary_negate(thiz->_cmp);
	return (c_vector_size(thiz) == c_vector_size(V)) &&
			c_equal2(c_vector_begin(thiz),
					c_vector_end(thiz),
					c_vector_begin(V),
					bp);
}

c_bool c_vector_less(c_pvector thiz, const c_pvector V)
{
	return c_lexicographical_compare(c_vector_begin(thiz),
						c_vector_end(thiz),
						c_vector_begin(V),
						c_vector_end(V),
						thiz->_cmp);
}