/*
Written by Sui Huang, McMaster University at Mar 3, 2007
*/


#include <stdlib.h>
#include "VectorAdt.h"


typedef struct NodeStruct{
	struct NodeStruct* last;
	struct NodeStruct* next;
	float x;
	float y;
	int count;
} Node;

// module variables
static Vector ListHead=NULL;

// function declarations
float get_x(Vector v);
float get_y(Vector v);
Vector i_vector();
Vector j_vector();
Vector mul(float r, Vector v);
Vector add(Vector u, Vector v);


// private function definitions
static int vec_less_than(Vector v1, Vector v2){
	if ((v1==NULL)&&(v2!=NULL)) return 1;
	else if ((v1!=NULL)&&(v2==NULL)) return 4;
	else if ((v1==NULL)&&(v2==NULL)) return 6;
	else if (v1->x<v2->x) return 1;
	else if (v1->x>v2->x) return -1;
	else if (v1->y<v2->y) return 1;
	else if (v1->y>v2->y) return -1;
	else return 0;
}

static Vector vec_insert(float a, float b){

	Vector vp1, vp2;
	Vector vtmp;

	// initialize the vector that will be insert
	vtmp = (Vector)malloc(sizeof(Node));
	vtmp->x=a;
	vtmp->y=b;
	// handle the special case that the link list is empty
	if (ListHead==NULL) {
		ListHead=vtmp;
		vtmp->last=NULL;
		vtmp->next=NULL;
		vtmp->count=1;
		return vtmp;
	}
	// handle the special case that the first vector is (a,b)
	if (vec_less_than(vtmp, ListHead)==0){
		(ListHead->count)++;
		return ListHead;
	}
	// handle the special case that (a,b) is less than the first element
	if (vec_less_than(vtmp, ListHead)==1){
		vtmp->next = ListHead;
		vtmp->last = NULL;
		ListHead = vtmp;
        return vtmp;
	}
	// search for the vector (a,b) in link list and do
	// manipulation according to different situations
	vp1 = ListHead;
	vp2 = vp1->next;
    while (1){
		if (vec_less_than(vtmp,vp2)==0) {
			// handle the case that (a,b) already in list
			(vp2->count)++;
			return vtmp;
		}
		else if (vec_less_than(vtmp,vp2)==1) {
			// handle the case that a vector greater than (a,b) is found
            vtmp->next = vp2;
            vtmp->last = vp1;
            vtmp->count = 1;
            vp2->last = vtmp;
            vp1->next = vtmp;
            return vtmp;
		}else if (vp2==NULL){
			// handle the case that (a,b) is neither in the list nor
			// smaller than any vector in the list
			vtmp->next = NULL;
			vtmp->last = vp1;
			vtmp->count = 1;
			vp1->next = vtmp;
			return vtmp;
		}
		vp1 = vp2;
		vp2 = vp2->next;
	}

}

// public function definitions
float get_x(Vector v){
	return v->x;
}

float get_y(Vector v){
	return v->y;
}


Vector i_vector(){
	return vec_insert(1,0);
}

Vector j_vector(){
	return vec_insert(0,1);
}

Vector mul(float r, Vector v){
	return vec_insert(r*(v->x),r*(v->y));
}

Vector add(Vector u, Vector v){
	return vec_insert((u->x)+(v->x), (u->y)+(v->y));
}