vector.c

Boosting is a meta-learning approach that aims at combining an ensemble of weak classifiers to form

/* Copyright (C) (2007) (Benoit Favre) <[e-mail]>

This program is free software; you can redistribute it and/or 
modify it under the terms of the GNU General Public License 
as published by the Free Software Foundation; either 
version 2 of the License, or (at your option) any later 
version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

#include "vector.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

// implementations for vector of void*
vector_t* vector_new(size_t initialSize) { return _vector_new(initialSize,sizeof(void*)); }
void vector_push(vector_t* v, void* value) { _vector_push(v,&value); }
void* vector_pop(vector_t* v) { void** output=(void**) _vector_pop(v); return output==NULL?NULL:*output; }
void* vector_remove_element(vector_t* v, size_t index) { void** output=(void**) _vector_remove_element(v, index); return output==NULL?NULL:*output; }
void* vector_shift(vector_t* v) { void** output=(void**) _vector_shift(v); return output==NULL?NULL:*output; }
void vector_unshift(vector_t* v, void* value) { _vector_unshift(v, &value); }
size_t vector_search(vector_t* v, void* value) { return _vector_search(v ,&value); }
size_t vector_search_sorted(vector_t* v, void* value, int (*comparator)(const void*,const void*)) { return _vector_search_sorted(v, &value, comparator); }
extern void* vector_get(vector_t* v, size_t index) { return *(void**) _vector_get(v, index); }
extern void vector_set(vector_t* v, size_t index, void* value) { _vector_set(v, index, &value); }
void vector_insert_element(vector_t* v, int index, void* value) { _vector_insert_element(v, index, &value); }

size_t vector_memory_size(vector_t* input)
{
	size_t size=sizeof(vector_t);
	size+=input->size*input->element_size;
	return size;
}

void _vector_resize(vector_t* v,size_t newSize)
{
	if(newSize==v->size)return;
	if(newSize<1)newSize=1;
	v->data=REALLOC(v->data,v->element_size*newSize);
	/*void* newData=MALLOC(v->element_size*newSize);
	if(v->data!=NULL)
	{
		memcpy(newData,v->data,v->length*v->element_size);
		FREE(v->data);
	}
	v->data=newData;*/
	if(v->data==NULL)warn("_vector_resize(%zd), reallocating vector from %zd", newSize, v->size);
	v->size=newSize;
}

void vector_optimize(vector_t* v)
{
	_vector_resize(v,v->length);
}

void vector_free(vector_t* v)
{
	FREE(v->data);
	FREE(v);
}

void _vector_push(vector_t* v, void* data)
{
	if(v->length>=v->size)
	{
		_vector_resize(v,v->size+v->size/2+1);
	}
	memcpy(v->data+v->length*v->element_size,data,v->element_size);
	v->length++;
}

void* _vector_pop(vector_t* v)
{
	if(v->length==0)return NULL;
	void* value=v->data+v->element_size*(v->length-1);
	v->length--;
	if(v->size>2 && v->length<v->size/2)_vector_resize(v,v->length+v->length/2); // value should still be allocated
	return value;
}

void* _vector_remove_element(vector_t* v, size_t index)
{
#ifdef DEBUG
	if(index>=v->length) warn("vector_remove_element(%zd), out-of-bounds, index>=%zd", index, v->length);
#endif
	void* element=v->data+index*v->element_size;
	if(index!=v->length-1)
		memmove(v->data+index*v->element_size,v->data+(index+1)*v->element_size,v->element_size*(v->length-index-1));
	v->length--;
	if(v->size>2 && v->length<v->size/2)_vector_resize(v,v->length+v->length/2);
	return element;
}

void* _vector_shift(vector_t* v)
{
	if(v->length==0)return NULL;
	return _vector_remove_element(v,0);
}

void _vector_unshift(vector_t* v, void* value)
{
	if(v->length>0)
	{
		_vector_push(v,v->data+v->element_size*(v->length-1));
		memmove(v->data+v->element_size,v->data,v->element_size*(v->length-2));
		memcpy(v->data,value,v->element_size);
	}
	else
	{
		_vector_push(v, value);
	}
}

void vector_append(vector_t* v,vector_t* u)
{
#ifdef DEBUG
	if(v->element_size!=u->element_size)warn("vector_append(%p,%p), different element size (%zd!=%zd)",v,u,v->element_size,u->element_size);
#endif
	if(v->length+u->length>=v->size)_vector_resize(v,((v->length+u->length)*3)/2+1);
	memmove(v->data+v->element_size*v->length,u->data,v->element_size*(u->length));
	v->length+=u->length;
}

void vector_prepend(vector_t* v,vector_t* u)
{
#ifdef DEBUG
	if(v->element_size!=u->element_size)warn("vector_prepend(%p,%p), different element size (%zd!=%zd)",v,u,v->element_size,u->element_size);
#endif
	if(v->length+u->length>=v->size)_vector_resize(v,((v->length+u->length)*3)/2+1);
	memmove(v->data+v->element_size*(u->length),v->data,v->element_size*(v->length));
	memmove(v->data,u->data,v->element_size*(u->length));
	v->length+=u->length;
}

void _vector_insert_element(vector_t* v, int index, void* value)
{
	if(index<0) _vector_unshift(v, value);
	else if(index>=v->length) _vector_push(v, value);
	else
	{
		if(v->length>=v->size) _vector_resize(v,v->size+v->size/2+1);
		memmove(v->data+v->element_size*(index+1),v->data+v->element_size*index,v->element_size*(v->length-index-1));
		v->length++;
		memcpy(v->data+v->element_size*index,value,v->element_size);
	}
}

void vector_insert(vector_t* v, size_t index, vector_t* peer)
{
#ifdef DEBUG
	if(v->element_size!=peer->element_size)warn("vector_insert(%p,%zd,%p), different element size (%zd!=%zd)",v,index,peer,
			v->element_size,peer->element_size);
#endif
	if(index<0) vector_prepend(v, peer);
	else if(index>=v->length) vector_append(v, peer);
	else {
		if(v->length+peer->length>=v->size)
		{
			_vector_resize(v,v->size+peer->size+v->size/2+1);
		}
		memmove(v->data+v->element_size*(index+peer->length),v->data+v->element_size*(index),v->element_size*(v->length-index-1));
		v->length+=peer->length;
		memcpy(v->data+v->element_size*index,peer->data,peer->length*v->element_size);
	}
}

vector_t* vector_fusion(vector_t* v, vector_t* u)
{
	vector_append(v,u);
	vector_free(u);
	return v;
}

void vector_reverse(vector_t* v)
{
	size_t i=0;
	size_t j=v->length-1;
	char tmp[v->element_size];
	for(;i<v->length/2;i++)
	{
		memcpy(tmp, v->data+v->element_size*i, v->element_size);
		memcpy(v->data+v->element_size*i, v->data+v->element_size*j, v->element_size);
		memcpy(v->data+v->element_size*j, tmp, v->element_size);
		j--;
	}
}

void vector_remove(vector_t* v, size_t from, size_t to)
{
	if(from<0)from=0;
	if(to>v->length)to=v->length;
	if(to<=from)return;
	if(to!=v->length)
	{
		memmove(v->data+v->element_size*from,v->data+v->element_size*to,v->element_size*(to-from));
	}
	v->length-=to-from;
	if(v->length<v->size/2)_vector_resize(v,v->length+v->length/2);
}

vector_t* _vector_new(size_t initialSize, size_t element_size)
{
	vector_t* v=MALLOC(sizeof(vector_t));
	if(v==NULL)return NULL;
	v->data=NULL;//MALLOC(v->element_size*initialSize);
	v->size=0;
	v->element_size=element_size;
	v->length=0;
	_vector_resize(v,initialSize);
	if(v->data==NULL)
	{
		FREE(v);
		return NULL;
	}
	return v;
}

vector_t* vector_subpart(vector_t* v, size_t from, size_t to)
{
	if(from<0)from=0;
	if(to>v->length)to=v->length;
	vector_t* output=vector_new(to-from);
	output->element_size=v->element_size;
	memcpy(output->data,v->data+v->element_size*from,(to-from)*v->element_size);
	output->length=to-from;
	return output;
}

extern void* _vector_get(vector_t* v, size_t index)
{
#ifdef DEBUG
	if(index>=v->length) warn("vector_get(%zd), out-of-bounds, index>=%zd", index, v->length);
#endif
	return v->data+v->element_size*index;
}

extern void _vector_set(vector_t* v, size_t index, void* value)
{
#ifdef DEBUG
	if(index>=v->length) warn("vector_set(%zd, %p), out-of-bounds, index>=%zd", index, value, v->length);
#endif
	memcpy(v->data+v->element_size*index,value,v->element_size);
}

vector_t* vector_copy(vector_t* input)
{
	vector_t* output=_vector_new(input->length,input->element_size);
	memcpy(output->data,input->data,input->length*input->element_size);
	output->length=input->length;
	return output;
}

vector_t* vector_copy_and_duplicate_pointers(vector_t* input, size_t value_size)
{
	vector_t* output=_vector_new(input->length,input->element_size);
	size_t i;
	for(i=0;i<input->length;i++)
	{
		void* value=MALLOC(value_size);
		memcpy(output->data+output->element_size*i, &value, sizeof(value));
		memcpy(*(void**)(output->data+output->element_size*i), *(void**)(input->data+input->element_size*i), value_size);
	}
	output->length=input->length;
	return output;
}

void vector_remove_duplicates(vector_t* v)
{
	size_t i,j=0;
	for(i=0;i<v->length && j<v->length;i++)
	{
		memmove(v->data+v->element_size*i,v->data+v->element_size*j,v->element_size);
		j++;
		while(j<v->length && memcmp(v->data+v->element_size*i,v->data+v->element_size*j, v->element_size)==0)j++;
	}
	v->length=i;
}

size_t _vector_search(vector_t* v, void* value)
{
	size_t i;
	for(i=0;i<v->length;i++)
	{
		if(memcmp(v->data+v->element_size*i,value,v->element_size)==0)return i;
	}
	return -1;
}

size_t _vector_search_sorted(vector_t* v, void* value, int (*comparator)(const void*,const void*))
{
	void* found=bsearch(value,v->data,v->length,v->element_size,comparator);
	if(found!=NULL)return (found-v->data)/v->element_size;
	return -1;
}

void vector_sort(vector_t* v,int (*comparator)(const void*,const void*))
{
	qsort(v->data,v->length,v->element_size,comparator);
}

void vector_apply(vector_t* v, void (*callback)(void* data, void* metadata),void* metadata)
{
	size_t i;
	for(i=0;i<v->length;i++)callback(v->data+v->element_size*i,metadata);
}

void vector_freedata(void* data,void* metadata)
{
	FREE(*(void**)data);
}