Vectors

Vectors:

Vectors are essentially dynamic arrays. With an array, you have a set amount
of variables of a specified type. You can not change the size if you need to
add another variable, or decide to take a variable out. In order to do this, you
need a vector. Also, you might need this for multiple data types, and due to
the nature of C, you need to specify which data type. My idea (which very well
has been thought of years before now) is to create a generic vector, thru the
use of pointers. This is how it will be laid out:

  struct _vector{
    size_t _cap;
    size_t _amount;
    void **_data;
  };

  typedef struct _vector vector_t;

Using void ** allows me to have an array of void pointers, which can be
addresses of specific data . So what are the functions used to work with this?

  vector_t * initVector(vector_t * out,size_t size);
  vector_t * mallocVector(size_t size);
  void freeVector(vector_t * vec);

  void * vectorGetTail(vector_t * vec);

  void vectorResize(vector_t * vec, size_t size);

  void vectorPushBack(vector_t * vec, void * data);
  void vectorPushFront(vector_t *vec, void * data);

  void * vectorPopBack(vector_t * vec);
  void * vectorPopFront(vector_t * vec);

  void * vectorGetAtIndex(vector_t * vec);

Lets start from the beginning. Allocating memory for a vector. Keep in mind
I am talking about the data within the vector, not the actual vector itself. That
must be allocated before doing any of these. First we want to initialize the cap
with the size of the vector. (_cap stands for capacity). Next we want to set the
amount to 0. This will be the index of the last variable in the vector. This will
help us determine when we need to resize a vector. Last , we will allocate the
data. Also, After writing this, i decided i could write a malloc vector function
as well so i threw that in there as well:

//vector_t * must be malloced before this....
vector_t * initVector(vector_t * out,size_t size){

  out->_cap = size;
  out->_amount = 0;
  out->_data = malloc(sizeof(void*)*size);

  return out;

}

  vector_t * mallocVector(size_t size){
  	vector_t * ret = malloc(sizeof(vector_t));
  	ret->_amount = 0;
  	ret->_cap = size;
  	ret->_data = malloc(sizeof(void*)*size);
  	return ret;
  }

Freeing should be easy, we can set everything to 0, free the data and then
itself:

void freeVector(vector_t * vec){

  free(vec->_data);
  vec->_cap = 0;
  vec->_amount = 0;
  free(vec);

}

Getting the tail is a matter of determining the amount that is in the vector
and just looking at that location:

void * vectorGetTail(vector_t * vec){
  return vec->_data[vec->_amount - 1];
}

For now, resizing is just a matter of realloc and changing the capacity of the
vector.

void vectorResize(vector_t * vec,size_t size){
  vec->_cap = size;
  vec->_data = realloc(vec->_data, size));
}

Next is the PushBack function, which pushes a new variable onto the back
of the vector:

void vectorPushBack(vector_t * vec, void * data){
  if(vec->_amount == vec->_cap){
  vectorResize(vec, vec->_cap*2);
  }

  vec->_data[vec->_amount] = data;
  vec->_amount++;
}

The PushFront function was interesting, it took me a second to work out
an algorithm, and I’m sure it is not the most efficient, so if you have any
other ideas, please feel free to modify this document.

void vectorPushFront(vector_t *vec, void * data){
  //fist error check
  if(vec->_amount == vec->_cap){
  vectorResize(vec, vec->_cap*2);
  }

//create a temporary vector
  vector_t * temp = malloc(sizeof(vector_t));
  initVector(temp,vec->_cap);
  temp->_data[0] = data;

//place the rest of the contents into temp
  size_t i = 0;
  while(i != vec->_amount){
    temp->_data[i+1] = vec->_data[i];
    i++;
  }

//place everything back into vec
  size_t j = 0;
  while(j != vec->_amount){
    vec->_data[j] = temp->_data[j];
    j++;
  }
	vec->_amount++;
}

Popping the vector is easy, from the back, we just put the data into a
return variable, decrement the amount, clear the space in the vector, and return
the return variable.

void * vectorPopBack(vector_t * vec){
  void * ret = vectorGetTail(vec);
  vec->_data[vec->_amount] = 0;
  vec->_amount--;

  return ret;
}

From the front, we want to get the first variable into its return variable,
then we place the variable in the next block into the previous. Last we return.

void * vectorPopFront(vector_t * vec){
  void * ret = vec->_data[0];
  size_t i = 1;
  while( i <= vec->_amount){
    if(vec->_data[i] == NULL)
      break;

    vec->_data[i-1] = vec->_data[i];
    i++;
  }

  vec->_amount--;
  return ret;

}

And the last couple functions are getters and setters:

void vectorSetAtIndex(vector_t * vec,size_t index, void * data){
  if(index >= vec->_cap){
    vectorResize(vec, index+1);
    }

    vec->_data[index] = data;
}

void * vectorGetAtIndex(vector_t * vec,size_t index){
  return vec->_data[index];
}

I Created a little print function to test this as well as a file called vec.c
I plan on placing this in its own library of collections when the time comes.

The full code to vec.c:

#include <stdio.h>
#include <stdlib.h>

  struct _vector{
    size_t _cap;
    size_t _amount;
    void **_data;
  };

  typedef struct _vector vector_t;

	//vector_t * must be malloced before this....
  vector_t * initVector(vector_t * out,size_t size){

	out->_cap = size;
	out->_amount = 0;
	out->_data = malloc(sizeof(void*)*size);

	return out;
	}

void freeVector(vector_t * vec){

  free(vec->_data);
  vec->_cap = 0;
  vec->_amount = 0;
  free(vec);

}

  void * vectorGetTail(vector_t * vec){
		return vec->_data[vec->_amount - 1];
	}

  void vectorResize(vector_t * vec,size_t size){
		vec->_cap = size;
		vec->_data = realloc(vec->_data, size);
	}

  void vectorPushBack(vector_t * vec, void * data){
		if(vec->_amount == vec->_cap){
		vectorResize(vec, vec->_cap*2);
		}

		vec->_data[vec->_amount] = data;
		vec->_amount++;
}

  void vectorPushFront(vector_t *vec, void * data){
		//fist error check
		if(vec->_amount == vec->_cap){
		vectorResize(vec, vec->_cap*2);
		}

	//create a temporary vector
	vector_t * temp = malloc(sizeof(vector_t));
	initVector(temp,vec->_cap);
	temp->_data[0] = data;

	//place the rest of the contents into temp
	size_t i = 0;
	while(i <= vec->_amount){
	temp->_data[i+1] = vec->_data[i];
	i++;
	}

	//place everything back into vec
	size_t j = 0;
	while(j <= vec->_amount){
	vec->_data[j] = temp->_data[j];
	j++;
	}

	vec->_amount++;

}

	void * vectorPopBack(vector_t * vec){
		void * ret = vectorGetTail(vec);
		vec->_data[vec->_amount-1] = NULL;
		vec->_amount--;

		return ret;
	}

  void * vectorPopFront(vector_t * vec){
	void * ret = vec->_data[0];
	size_t i = 1;
	while( i <= vec->_amount){
		if(vec->_data[i] == NULL)
			break;

		vec->_data[i-1] = vec->_data[i];
		i++;
	}

	vec->_amount--;
	return ret;

}

  void vectorSetAtIndex(vector_t * vec,size_t index, void * data){

	if(index >= vec->_cap){
		vectorResize(vec, index+1);
	}

	vec->_data[index] = data;
	}

  void * vectorGetAtIndex(vector_t * vec,size_t index){
	return vec->_data[index];
	}

	//Little Utility Function
	void printvec(vector_t * vec){
		size_t i = 0;

		while(i != vec->_amount){
			printf("%d, ", *(int*)vec->_data[i]);
			i++;
		}
		printf("\n");
		}

int main(int argc, char *argv[]){

	vector_t * foo = malloc(sizeof(vector_t));

	//Init example
	initVector(foo,16);
	printf("Foo Capacity = %d\n",foo->_cap);

	int bar = 5;
	int baz = 8;
	int taco = 15;

	//vector push back example
	vectorPushBack(foo,&bar);
	//vector Get Tail Example
	printf("Foo Pushed %d, current amount :  %d\n",*(int*)vectorGetTail(foo),foo->_amount);
	vectorPushBack(foo,&baz);
	printf("Foo Pushed %d, current amount :  %d\n",*(int*)vectorGetTail(foo),foo->_amount);

	printvec(foo);

	int bob = 11;
	// Vector Push Front Example
	vectorPushFront(foo,&bob);
	printf("Foo Pushed %d, current amount :  %d\n",bob,foo->_amount);
	vectorPushBack(foo,&taco);
	printf("Foo Pushed %d, current amount :  %d\n",*(int*)vectorGetTail(foo),foo->_amount);
	printvec(foo);

	//vector Pop back example
	int clim = *(int*)vectorPopBack(foo);
	printf("Foo Popped %d, current amount :  %d\n",clim,foo->_amount);
	printvec(foo);

	//vector pop front example:
	int dude = *(int*)vectorPopFront(foo);
	printf("Foo Popped %d, current amount :  %d\n",dude,foo->_amount);
	printvec(foo);

	//free example
	freeVector(foo);
	return 0;
}

 

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s