idr_binomial.c from EmStar at Krugle

Show idr_binomial.c syntax highlighted

/*
 *
 * Copyright (c) 2003 The Regents of the University of California.  All 
 * rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Neither the name of the University nor the names of its
 *   contributors may be used to endorse or promote products derived
 *   from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */
 

#include <stdio.h>
#include <sys/time.h>


#include "idr_i.h"
#include "idr_binomial.h"

struct element *create_list(struct node *element)
{
	struct element *head;
	
	head=(struct element *)malloc(sizeof(struct element));
	head->next=NULL;
	head->element=element;

	return head;
}


void add_element(struct element **head, struct element *entry) 
{

	if (entry==NULL || *head==NULL || head==NULL) {
		printf("add_element: NULL pointer\n");
	}

	entry->next=*head;
	*head=entry;
}


struct element *delete_element(struct element *entry) 
{
	struct element *next;

	if (entry==NULL) {
		printf("delete_element: NULL entry pointer\n");
		return NULL;
	}

	next=entry->next;
	free(entry);

	return next;
}



// returns pointer to head of tree
nodep create_head(struct info *data)
{
	struct node *head;

	head=(struct node *)malloc(sizeof(struct node));
	head->parent=NULL;	// it's the root
	head->child=NULL;
	head->sibling=NULL;
	head->data=*data;
	head->degree=0;
	head->index=data->index;

			
	return head;
}


nodep join_trees(nodep y, nodep z)
{
	if (z==NULL ||y==NULL) {
		printf("join_trees: NULL pointer (y=%d, z=%d)\n",(int)y,(int)z);
	}
	y->parent=z;
	y->sibling=z->child;
	z->child=y;
	z->degree++;
	printf("-");
	return z;
}



nodep create_tree(struct info table[], int elements)
{
	int i=0;
	int recdepth=2<<(elements-1);	// that's a LOT of recursion depth
	nodep head;

	if (recdepth>MAX_RECDEPTH) {
		printf("Recursion depth too large (%d)\n", recdepth);
		exit(1);
	}
	
	// recursion
	if (elements>1) {
		nodep head1;
		nodep head2;
		// split the table in 2 pieces
		struct info t1[elements-1];
		struct info t2[elements-1];

		// first piece of the first table is table[0]
		t1[0]=table[0];
		// first piece of the second table is table[1]
		t2[0]=table[1];
		// the rest are the same
		for (i=1; i<elements-1; i++) {
			t1[i]=table[i+1];
			t2[i]=table[i+1];
		}
		// call myself
		head1=create_tree(t1, elements-1);
		head2=create_tree(t2, elements-1);
		return join_trees(head2, head1);
	} else if (elements==1) {
		// single element, create it
		head=create_head(&table[0]);
		printf(".");
		return head;
	} else {
		// elements <1 ?
		printf("Error\n");
		return NULL;
	}
}	





void print_node_info(nodep n, char silent)
{
	if (silent==1)
		return;

	if (n==NULL) {
		printf("print_node_info: NULL pointer\n");
		return;
	}

	printf("  Degree=%d, Data=%d, Index=%d, Sum=%d\n", 
		n->degree, n->data.data, n->index, n->sum);
}


// walks the tree all the way down using childs
// returns the last element
nodep walk_down(nodep head, int depth, char silent)
{
	struct node *tmp=head;
	int d=0;

	if (depth==0) {
		return tmp;
	}

	while (tmp!=NULL) {
		if (d<=depth) {
			d++;
			print_node_info(tmp, silent);
			if (tmp->child==NULL) {
				return tmp;
			} else {
				tmp=tmp->child;
			}
		} else {
			// I'm too deep, go up 1
			tmp=tmp->parent;
			break;
		}
	}

	return tmp;
}


void walk_tree(nodep head, int depth)
{
	struct node *tmp=head;
	int mydepth=depth;
	
	if (head==NULL) {
		printf("walk_tree: NULL pointer\n");
		return;
	}

	if (depth==0) {
		print_node_info(head, 0);
		return;
	}
	
	// first, go all the way down
	tmp=walk_down(tmp, depth, 0);
//	print_node_info(tmp);

	// I am all the way down to depth, set mydepth=0
	mydepth=0;

	// eventually I will reach the head
	while (tmp!=head) {

		// reached the end, now go up and right (next sibling)
		// try moving to the right first
		while (tmp->sibling!=NULL) {
			tmp=tmp->sibling;
			printf("Sibling=%d\n", tmp->data.data);
			print_node_info(tmp, 0);
			printf("Walking down from %d, mydepth=%d\n", 
					tmp->data.data, mydepth);
			tmp=walk_down(tmp, mydepth, 0);
		}

		// nothing left to the right, now go up	
		tmp=tmp->parent;
		// Moved 1 up, now update mydepth
		mydepth++;
		if (tmp != head) {
			printf("Parent=%d\n", tmp->data.data);
			print_node_info(tmp, 0);
			printf("\n");
		}
	}
}


nodep walk_down_and_sum(nodep head, int depth)
{
	struct node *tmp=head;
	int d=0;

	if (depth==0) {
		return tmp;
	}

	while (tmp!=NULL) {
		if (d<=depth) {
			d++;
			if (tmp->parent != NULL && tmp!=head) {
				tmp->sum=tmp->parent->sum+tmp->data.data;
			} else {
				tmp->sum=tmp->data.data;
			}
			if (tmp->child==NULL) {
				return tmp;
			} else {
				tmp=tmp->child;
			}
		} else {
			// I'm too deep, go up 1
			tmp=tmp->parent;
			break;
		}
	}

	return tmp;
}


void delete_tree(nodep *head)
{
	struct node *tmp=*head;
	struct node *next=NULL;

	if (head==NULL) {
		printf("delete_tree: NULL head pointer\n");
		return;
	}

	// first, go all the way down
	tmp=walk_down(tmp, (*head)->degree, 1);

	// Did we actually go down, or not?
	if (tmp->parent==NULL) {
		// we didn't go down at all because there's nothing underneath
		free(*head);
		*head=NULL;
		return;
	}

	
	// the next pointer should now point to tmp's parent
	next=tmp->parent;
	// remove tmp
	next->child=NULL;	// set my child to NULL, I am about to remove it
	free(tmp);
	printf(".");
	tmp=next;

	while(next!=*head) {
		// first, see if I can go right
		while(next->sibling!=NULL) {
			if (next->child==NULL) {
				// my child is null and I can go right, I should be removed
				tmp=next;
				next=next->sibling;
				printf(".");
				free(tmp);
				tmp=next;
			} else {
				// my child is NOT null, go down
				tmp=walk_down(tmp, (*head)->degree, 1);
				next=tmp->parent;
				next->child=NULL;
				printf(".");
				free(tmp);
				tmp=next;
			}
		}

		// Nothing left in my right or below me. Remove me and go up
		tmp=next;
		next=next->parent;
		next->child=NULL;
		printf(".");
		free(tmp);
		tmp=next;
	}

	// All done, now free the head
	free(*head);	
	*head=NULL;
}

void calculate_sums(nodep head, int depth)
{
	struct node *tmp=head;
	int mydepth=depth;

	if (head==NULL) {
		printf("calculate_sums: NULL head pointer\n");
		return;
	}

	tmp=walk_down_and_sum(tmp, depth);
	mydepth=0;

	while(tmp!=head) {
		while (tmp->sibling!=NULL) {
			tmp=tmp->sibling;
			tmp->sum=tmp->data.data+tmp->parent->sum;
			tmp=walk_down_and_sum(tmp, mydepth);
		}	
		// nothing left to the right or below me
		tmp=tmp->parent;
		mydepth++;
	}

}



void assign_heads(nodep head[])
{
	int i;

	if (head[0]->child==NULL)
		// no children on the head, it's a leaf node
		return;

	head[1]=head[0]->child;	// the second element is the child of the head

	// every other element is the sibling of the previous one
	for (i=2;i<=head[0]->degree;i++) {
		head[i]=head[i-1]->sibling;
	}
}
	
nodep walk_down_and_sum_with_constraint(nodep head, int depth, int min,
										struct element **lh, nodep masterhead)
{
	struct node *tmp=head;
	int d=0;

	if (depth==0) {
		//is this the last binomial tree ?
		// (using data instead of sum, since it's the last tree, so
		// the nodes' parent(which is what the sum value reflects) should
		// be ignored
		if (*lh==NULL && tmp->data.data >= min) {
			*lh=create_list(tmp);
		}
		return tmp;
	}

	while (tmp!=NULL) {
		char check=0;
		if (d<=depth) {
			d++;
			if (tmp->parent != NULL && tmp!=masterhead) {
				tmp->sum=tmp->parent->sum+tmp->data.data;
			} else {
				tmp->sum=tmp->data.data;
			}

			// Sum is calculated, now check
			if (tmp->sum >= min) {
				if (*lh==NULL) {
					*lh=create_list(tmp);
				} else {
					struct element *entry=create_list(tmp);
					add_element(lh, entry);
				}
				check++;
			}

			if (tmp->child==NULL) {
				return tmp;
			} else {
				tmp=tmp->child;
			}
		} else {
			// I'm too deep, go up 1
			tmp=tmp->parent;
			if (check>=1) {
				*lh=delete_element(*lh);
			}
			break;
		}
	}

	return tmp;
}



void calculate_sums_with_constraint(nodep head, int depth, int min, 
									struct element **lh, nodep masterhead)
{
	struct node *tmp=head;
	int mydepth=depth;

	if (head==NULL) {
		printf("calculate_sums_with_constraint: NULL head pointer\n");
		return;
	}

	tmp=walk_down_and_sum_with_constraint(tmp, mydepth, min, lh, masterhead);
	mydepth=0;

	while(tmp!=head) {
		while (tmp->sibling!=NULL) {
//			printf("Moving right\n");
			tmp=tmp->sibling;
			tmp->sum=tmp->data.data+tmp->parent->sum;
			if (tmp->sum >= min) {
				if (*lh==NULL) {
					*lh=create_list(tmp);
				} else {
					struct element *entry=create_list(tmp);
					add_element(lh, entry);
				}
				// added an element. Move the tmp pointer down or the element
				// will be added again
				if (tmp->child!=NULL) {
					tmp=tmp->child;
				}
			}
	//		printf("Going down %d--%d\n", tmp->degree, tmp->data);
			tmp=walk_down_and_sum_with_constraint(tmp, tmp->degree, min, lh,
				 masterhead);
		}	
		// nothing left to the right or below me
//		printf("Moving up\n");
		tmp=tmp->parent;
		mydepth++;
	}

}
See more files for this project here