liblash

lash_tree.c.fail (8414B)

---

 #include <stdlib.h>
 #include "liblash/lash_tree.h"
 #include <stdio.h>
 
 lash_tree_t *lashTreeInit(lash_tree_t *tree, const unsigned int size) {
 	int i;
 	tree = (lash_tree_t*)malloc(sizeof(lash_tree_t));
 	tree->heap = (long int*)malloc(sizeof(long int) * size);
 	//tree->content = (void*)malloc(sizeof(void*) * size);
 	tree->local = (unsigned int*)calloc(size, sizeof(unsigned int*));
 	tree->idx = (unsigned int*)malloc(sizeof(unsigned int) * size);
 	if (tree->heap == NULL || tree->idx == NULL)
 		return NULL;
 
 	tree->position = 0;
 	tree->capacity = size;
 	*tree->idx = 0;
 	
 	return tree;
 }
 
 
 int lashTreePush(lash_tree_t *tree, const long int sortvalue, const int local) {
 	
 	if (tree->position == tree->capacity)
 		return -1;
 	
 	tree->position++;
 	
 	// put the new number at the end of the content array and update the current position
 	if (*(tree->idx + tree->position - 1) == 0)
 		*(tree->idx + tree->position - 1) = tree->position;
 	*(tree->heap + tree->position - 1) = sortvalue;
 	*(tree->local + tree->position - 1) = local;
 	
 	// put the content array index to the new number on the index array
 	
 	
 	// increase the average (for faster searching later)
 	int tmpaverage = tree->average;
 	tmpaverage *= (tree->position - 1);
 	tmpaverage += sortvalue;
 	tmpaverage /= tree->position;
 	tree->average = tmpaverage; 
 	
 	return lashTreeItemProcess(tree, tree->position);
 }
 
 int lashTreeShift(lash_tree_t *tree, long int *number, unsigned int *local) {
 	return lashTreeRemove(tree, 0, number, local);
 }
 
 // note that here position is 1 for first, not 0
 int lashTreeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) {	
 	long int currentnumber;
 	long int currentindex;
 	int i;
 	
 	if (tree->position == 0)
 		return -1;
 	
 	if (position > tree->position) 
 		return -1;
 		
 	// if there is only one item, retrieve this and finish	
 	if (tree->position == 1) {
 		if (number != NULL)
 			*number = *(tree->heap + *(tree->idx) - 1);
 		if (local != NULL)
 			*local = *(tree->local + *(tree->idx) - 1);
 		tree->position = 0;
 		//tree->idx = 0;
 		return 0;
 	}
 	
 	// if no position is set, then take the top of the heap
 	if (position == 0)
 		position = 1;
 	
 	// remove the number on the supplied index, and move the number from the bottom in its place
 	currentindex = *(tree->idx + position - 1);
 	currentnumber = *(tree->heap + currentindex - 1);
 	
 	if (number != NULL)
 		*number = currentnumber;
 	if (local != NULL)
 		*local = *(tree->local + currentindex - 1);
 		
 	*(tree->local + currentindex - 1) = *(tree->local + *(tree->idx + tree->position - 1) - 1);
 	*(tree->heap + currentindex - 1) = *(tree->heap + *(tree->idx + tree->position - 1)  - 1);
 	*(tree->idx + position - 1) = *(tree->idx + tree->position - 1);
 	*(tree->idx + tree->position - 1) = currentindex;
 	
 	tree->position--;
 	
 	// decrease the average (for faster searching later)
 	if (tree->position == 0) {
 		tree->average = 0;
 	} else {
 		int tmpaverage = tree->average;
 		tmpaverage *= (tree->position + 1);
 		//tmpaverage -= *number;
 		tmpaverage -= currentnumber;
 		tmpaverage /= tree->position;
 		tree->average = tmpaverage;
 	}
 	
 	return lashTreeItemProcess(tree, position);
 	
 }
 
 // note that here currentposition is 1 for first, not 0
 int lashTreeItemProcess(lash_tree_t *tree, unsigned int currentposition) {
 	
 	// choose direction (-1 is up / push, 1 is down / shift)
 	int direction = 0;
 	unsigned int newposition = 0;
 	
 	fprintf(stderr, "processing pos %d for heap value %li\n", currentposition, *(tree->heap + *(tree->idx + currentposition - 1) - 1));
 	
 	// if it has only one element, there is nothing to do
 	if (tree->position == 1) {
 		return (int)1;
 		fprintf(stderr, "is only element\n");
 	// if it's at the top, we can only go down
 	} else if (currentposition <= 1) {
 		currentposition = 1;
 		direction = 1;
 		newposition = currentposition * 2;
 		fprintf(stderr, "is topelement, direction is down, newposition is %d\n", newposition);
 		// if it's the first value
 	
 	// if the current position is not at the end of the array it's replacing a value that was removed, and there is room to move it down one level in the tree
 	} else if (currentposition * 2 <= tree->position) {
 	// this it must traverse down the tree, compare to the position of twice the value, and also the value adjacent ("right") to it to see if those values are lower, in which case they should be swapped
 		if (*(tree->heap + *(tree->idx + currentposition - 1) - 1) > *(tree->heap + *(tree->idx + (currentposition * 2) - 1) - 1) || *(tree->heap + *(tree->idx + currentposition - 1) - 1) > *(tree->heap + *(tree->idx + (currentposition * 2)) - 1)) {
 			direction = 1;
 			newposition = (currentposition * 2);
 			fprintf(stderr, "inside tree, has lower value below, direction is down, newposition is %d\n", newposition);
 		}
 	// if the value in the current position is lower than the value halfway up the array (up one level in the tree), then it should be swapped
 	} else if (*(tree->heap + *(tree->idx + currentposition - 1) - 1) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1) - 1)) {
 		direction = -1;	
 		newposition = (unsigned int)currentposition / 2;
 		fprintf(stderr, "at bottom, has lower value halfway up, direction is up, newposition is %d\n", newposition);
 	}
 	
 	switch (direction) {
 		case -1:
 			// move the content index up the index array until the number above in the heap is smaller or equal, or until we hit the start of the heap
 			while (newposition > 0) {
 				long int newheap = *(tree->heap + *(tree->idx + newposition - 1) - 1);
 				long int oldheap = *(tree->heap + *(tree->idx + currentposition - 1) - 1);
 				fprintf(stderr, "Comparing old %li pos %d to new %li pos %d\n", oldheap, currentposition, newheap, newposition);
 				if (*(tree->heap + *(tree->idx + newposition - 1) - 1) > *(tree->heap + *(tree->idx + currentposition - 1) - 1)) {
 					unsigned int tmpindex = *(tree->idx + newposition - 1);
 					*(tree->idx + newposition - 1) = *(tree->idx + currentposition - 1);
 					*(tree->idx + currentposition - 1) = tmpindex;
 				} else {
 					break;
 				}
 				currentposition = newposition;
 				newposition = (unsigned int)newposition / 2;
 			}
 			break;
 		case 1:
 			// until end of heap is reached, or the next number is higher
 			while (newposition <= tree->position) {
 				unsigned int swapposition = currentposition;
 				// move to next level if the next level child is higher
 				if (*(tree->heap + *(tree->idx + newposition - 1) - 1) < *(tree->heap + *(tree->idx + currentposition - 1) - 1)) {
 					swapposition = newposition;
 					// check if either of the left or right children are higher (if there are two children, if not we're at the end of the heap)
 					if (newposition + 1 <= tree->position)
 						// if the right child is higher, then move there
 						if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + newposition - 1) - 1))
 							swapposition = newposition + 1;
 				} else if (newposition + 1 <= tree->position) {
 					if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + currentposition - 1) - 1))
 						// if the right child is higher, then move there
 						if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + newposition - 1) - 1))
 							swapposition = newposition + 1;
 				}
 		
 				// if a move has taken place
 				if (swapposition != currentposition) {
 					unsigned int tmpindex = *(tree->idx + currentposition - 1);
 					*(tree->idx + currentposition - 1) = *(tree->idx + swapposition - 1);
 					*(tree->idx + swapposition - 1) = tmpindex;
 				} else {
 					break;
 				}
 		
 				currentposition = swapposition;
 				newposition = swapposition * 2;
 			}
 			break;
 		default:
 			currentposition = 0;
 			newposition = 0;
 	}
 	
 	return (int)currentposition;
 }
 
 int lashTreeFindByLocal(lash_tree_t *tree, const int local) {
 	int i;
 	for (i = tree->position - 1; i >= 0; i--) {
 		if (*(tree->local + *(tree->idx + i) - 1) == local)
 			return i;
 	}
 	return -1;
 }
 
 int lashTreeFindBySort(lash_tree_t *tree, const int sortvalue) {
 	int i;
 	for (i = tree->position - 1; i >= 0; i--) {
 		if (*(tree->heap + *(tree->idx + i) - 1) == sortvalue)		
 			return i;
 	}
 	return -1;
 }
 
 void lashTreeFree(lash_tree_t *tree) {
 	if (tree != NULL) {
 		if (tree->local != NULL)
 			free(tree->local);
 		if (tree->heap != NULL)
 			free(tree->heap);
 		if (tree->idx != NULL)
 			free(tree->idx);
 		free(tree);
 	}
 }