/r/dailyprogrammer [10/13/2014] Challenge #184 [Easy] Smart Stack List

stacks.c

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

int Z = 0;
struct LinearNode {
	int value;
	int N;
	struct LinearNode *prev;
	struct LinearNode *next;
	struct LinearNode *lesser;
	struct LinearNode *greater;
};
struct LinearNode *LinearList = NULL;
struct LinearNode *AscendingList = NULL;

int main(int argc, char *argv[]){
	int i;
	int x = 0;
	int n;
	int r;
	int s;
	printf("argc = %d", argc);
	if( argc == 2 ){
		srand(atoi(argv[1]));
	}
	n = 1+ (rand() % 40);
	printf("Generating %d items\n", n);
	for( i = i; i < n; i++ ){
		r = -1000 + ( rand() % 2001 );
		push(r);
	}
	
	display_stack();
	display_ordered();
	x = -1000 + ( rand() % 2001 );
	printf("Removing items greater than  %d\n", x);
	remove_greater(x);
	display_stack();
	display_ordered();
	s = size();
	for( i = 0; i < s/2; i++ ){
		pop();
	}
	display_stack();
	display_ordered();
	
	return 0;
}

int push(int i){
	struct LinearNode *new_node;
	struct LinearNode *temp;
	Z++;
	new_node = (struct LinearNode *) malloc(sizeof(struct LinearNode));
	new_node->value = i;
	new_node->N = Z;
	new_node->prev = NULL;
	new_node->next = NULL;
	new_node->lesser = NULL;
	new_node->greater = NULL;
		
		
	if( LinearList == NULL ){
		LinearList = new_node;
		AscendingList = new_node;
	}else{
		// pushing on the top will never have a prev
		new_node->next = LinearList;
		LinearList->prev = new_node;
		LinearList = new_node;
		
		
		if( new_node->value < AscendingList->value ){
			new_node->greater = AscendingList;
			AscendingList->lesser = new_node;
			AscendingList = new_node;
		}else{
			// new_node IS greater than something
			temp = AscendingList;
			while( new_node->value >= temp->value ){
				if( temp->greater == NULL ){
					temp->greater = new_node;
					new_node->lesser = temp;
					break;
				}else{
					temp = temp->greater;
				}
			}
			if( new_node->value < temp->value ){
				//[A]<->[B]
				//[A]<->[C](n)<->[B](t)
				if( temp->lesser != NULL ){
					temp->lesser->greater = new_node;
				}
				new_node->lesser = temp->lesser;
				new_node->greater = temp;
				temp->lesser = new_node;
			}
			 
		}
		
		
	}
	
	
}
int help_remove(struct LinearNode *node){
	struct LinearNode *left;
	struct LinearNode *right;
	struct LinearNode *up;
	struct LinearNode *down;
	
	left = node->prev;
	right = node->next;
	up = node->greater;
	down = node->lesser;
	
	if( left != NULL ){
		left->next = right;
	}else{
		// Node was LinearList
		LinearList = right;
	}
	if( right != NULL ){
		right->prev = left;
	}
	if( up != NULL ){
		up->lesser = down;
	}
	if( down != NULL ){
		down->greater = up;
	}else{
		// Node was AscendingList
		AscendingList = up;
	}	
	
	
	
}
int pop(){
	struct LinearNode *temp;
	int i;
	if( LinearList == NULL ){
		return 0;
	}
	temp = LinearList; // to remove
	
	i = LinearList->value;
	
	help_remove(temp);
	free(temp);
	return i;
	
}
int size(){
	int i = 0;
	struct LinearNode *temp;
	for( temp = LinearList; temp != NULL; temp = temp->next ){
		i++;
	}
	return i;
}
int remove_greater(int i){
	int x;
	struct LinearNode *temp;
	struct LinearNode *freedom;
	for( temp = AscendingList; temp != NULL; temp = temp->greater ){
		if( temp->value > i ){
			break;
		}
	}
	while( temp != NULL ){
		freedom = temp; // to remove and 
		
		help_remove(temp);
		temp = temp->greater;
		
		free(freedom);
		
		
		
	}
	
}
int display_stack(){
	struct LinearNode *temp;
	int i = 0;
	for( temp = LinearList; temp != NULL; temp = temp->next ){
		printf("L(%d)[%d} ->", temp->N, temp->value );
		i++;
	}
	printf("\n");
}
int display_ordered(){
	struct LinearNode *temp;
	int i = 0;
	for( temp = AscendingList; temp != NULL; temp = temp->greater ){
		printf("O(%d)[%d} ->", temp->N, temp->value );
		i++;
	}
	printf("\n");
	
	return 0;
}