liblash

lash_tree.c (7330B)

---

 #include <stdlib.h>
 #include "liblash/lash_tree.h"
 #include <stdio.h>
 #include "liblash/lash_tree_dump.h"
 
 lash_tree_t *lash_treeInit(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->local = (unsigned int*)calloc(size, sizeof(unsigned int*));
 	tree->idx = (int*)malloc(sizeof(int) * size);
 	if (tree->heap == NULL || tree->idx == NULL)
 		return NULL;
 	
 	for (i = 0; i < size; i++)
 		*(tree->idx + i) = -1;
 		
 	tree->position = 0;
 	tree->capacity = size;
 	*tree->idx = 0;
 	
 	return tree;
 }
 
 
 //int lash_treePush(lash_tree_t *ptree, const long int sortvalue, void *content) {
 int lash_treePush(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
 	*(tree->idx + tree->position - 1) = tree->position - 1;
 	*(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 lash_treeItemProcess(tree, tree->position);
 }
 
 int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local) {
 	return lash_treeRemove(tree, 0, number, local);
 }
 
 // note that here position is 1 for first, not 0
 int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) {	
 	long int currentnumber;
 	long int currentindex;
 	int i;
 	int result;
 	
 	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);
 		if (local != NULL)
 			*local = *(tree->local + *tree->idx);
 		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);
 	
 	if (number != NULL)
 		*number = currentnumber;
 	if (local != NULL)
 		*local = *(tree->local + currentindex);
 		
 	*(tree->idx + currentindex) = tree->position - 1;
 	
 	//*(tree->local + currentindex) = *(tree->local + *(tree->idx + tree->position - 1));
 	//*(tree->heap + currentindex) = *(tree->heap + *(tree->idx + tree->position - 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;
 	}
 	
 	result = lash_treeItemProcess(tree, position);
 	
 	// this probably defeats the speed gain from binary tree.
 	for (i = position; i <= tree->position; i++) {
 		*(tree->heap + i - 1) = *(tree->heap + i);
 		*(tree->local + i - 1) = *(tree->local + i);
 		*(tree->idx + i - 1) -= 1;
 	}
 	
 	return result;
 	
 	
 }
 
 // note that here currentposition is 1 for first, not 0
 int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition) {
 	
 	// choose direction (-1 is up, 1 is down)
 	int direction = 0;
 	unsigned int newposition = 0;
 	
 	if (tree->position == 1) {
 		return (int)1;
 	} else if (currentposition <= 1) {
 		currentposition = 1;
 		direction = 1;
 		newposition = currentposition * 2;
 		// if it's the first value
 		
 	} else if (currentposition * 2 <= tree->position) {
 		if (*(tree->heap + *(tree->idx + currentposition - 1)) > *(tree->heap + *(tree->idx + (currentposition * 2) - 1)) || *(tree->heap + *(tree->idx + currentposition - 1)) > *(tree->heap + *(tree->idx + (currentposition * 2)))) {
 			direction = 1;
 			newposition = (currentposition * 2);
 		}
 	} else if (*(tree->heap + *(tree->idx + currentposition - 1)) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1))) {
 		direction = -1;	
 		newposition = (unsigned int)currentposition / 2;
 	}
 	
 	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) {
 				if (*(tree->heap + *(tree->idx + newposition - 1)) > *(tree->heap + *(tree->idx + currentposition - 1))) {
 					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)) < *(tree->heap + *(tree->idx + currentposition - 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)) < *(tree->heap + *(tree->idx + newposition - 1)))
 							swapposition = newposition + 1;
 				} else if (newposition + 1 <= tree->position) {
 					if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + currentposition - 1)))
 						// if the right child is higher, then move there
 						if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 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 lash_treeFindByLocal(lash_tree_t *tree, const int local) {
 	int i;
 	for (i = tree->position - 1; i >= 0; i--) {
 		if (*(tree->local + *(tree->idx + i)) == local)
 			return i;
 	}
 	return -1;
 }
 
 int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue) {
 	int i;
 	for (i = tree->position - 1; i >= 0; i--) {
 		if (*(tree->heap + *(tree->idx + i)) == sortvalue)		
 			return i;
 	}
 	return -1;
 }
 
 void lash_treeFree(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);
 	}
 }