avllc.c

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node *node;
typedef struct node *leaf;

typedef struct {
	int last;
	unsigned length;
} chain;

chain max;

leaf create(int);
node insert(node, leaf);
void find(node);

int
main(void) {
	int num;
	node root;
	leaf leaf;

	root = NULL;

	while (scanf(" %d", &num) != EOF) {
		leaf = create(num);
		root = insert(root, leaf);
	}

	find(root);
	if (max.length > 0)
		printf("0: %d-%d (%u)\n",
				(max.last - max.length) + 1, max.last, max.length);
}


#if __OPTIMIZE__
#define assert(x)
#endif

struct node {
	int value;
	struct node *left;
	struct node *right;
	size_t weight;
};

#define WEIGHT(n) ((n) ? (n)->weight : 0)

enum {
	BALANCED,
	LEFT_HEAVY,
	RIGHT_HEAVY,
	DOUBLY_LEFT_HEAVY,
	DOUBLY_RIGHT_HEAVY,
	INVALID
};

int
status(node n) {
	size_t wl, wr;

	if (!n)
		return BALANCED;

	wl = WEIGHT(n->left);
	wr = WEIGHT(n->right);

	if (wl == wr)
		return BALANCED;

	if (wl > wr) {
		switch (wl - wr) {
		case 1:
			return LEFT_HEAVY;
		case 2:
			return DOUBLY_LEFT_HEAVY;
		}
	}
	else {
		switch (wr - wl) {
		case 1:
			return RIGHT_HEAVY;
		case 2:
			return DOUBLY_RIGHT_HEAVY;
		}
	}

	return INVALID;
}

leaf
create(int val) {
	node n;

	n = malloc(sizeof *n);
	if (!n)
		err(1, NULL);

	n->value = val;
	n->left = NULL;
	n->right = NULL;
	n->weight = 1;

	return n;
}

void
update(node n) {
	size_t wl, wr;

	assert(n);

	wl = WEIGHT(n->left);
	wr = WEIGHT(n->right);

	if (wl > wr)
		n->weight = wl + 1;
	else
		n->weight = wr + 1;
}

node
rotate_left(node t) {
	node tmp;

	assert(t && t->right);

	tmp = t->right;

	t->right = tmp->left;
	update(t);

	tmp->left = t;
	update(tmp);
	
	return tmp;
}

node
rotate_right(node t) {
	node tmp;

	assert(t && t->left);

	tmp = t->left;

	t->left = tmp->right;
	update(t);

	tmp->right = t;
	update(tmp);
	
	return tmp;
}

node
rebalance(node t) {
	assert(t);

	switch (status(t)) {
	case DOUBLY_LEFT_HEAVY:
		if (status(t->left) == RIGHT_HEAVY)
			t->left = rotate_left(t->left);
		t = rotate_right(t);
		break;

	case DOUBLY_RIGHT_HEAVY:
		if (status(t->right) == LEFT_HEAVY)
			t->right = rotate_right(t->right);
		t = rotate_left(t);
		break;
	}

	return t;
}

node
insert(node t, leaf n) {
	assert(status(t) != INVALID);
	assert(n->weight == 1);

	if (!t)
		return n;

	if (n->value > t->value)
		t->right = insert(t->right, n);
	else if (n->value < t->value)
		t->left = insert(t->left, n);

	update(t);
	t = rebalance(t);

	return t;
}


chain cur;

void
find(node t) {
	if (cur.length > max.length)
		max = cur;

	if (!t)
		return;

	find(t->left);

	if (t->value == cur.last + 1)
		cur.length++;
	else
		cur.length = 1;

	cur.last = t->value;

	find(t->right);
}

htlc.c

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct state;

struct pair {
	int key;
	unsigned value;
};

void init_table(size_t);
unsigned get_value(int);
void set_value(int, unsigned);
struct state *iterate_pairs(void);
int next_pair(struct state *, struct pair *);

int
main(void) {
	int num;
	struct state *state;
	struct pair curr, max;
	size_t i;
	unsigned valuei;

	init_table(512);

	while (scanf(" %d", &num) != EOF)
		set_value(num, 1);

	max.value = 0;
	state = iterate_pairs();

	while (next_pair(state, &curr)) {
		if (curr.value == 0 || curr.key == INT_MAX)
			continue;

		for (i = curr.key + 1; i < INT_MAX; i += valuei) {
			if ((valuei = get_value(i)) == 0)
				break;

			curr.value += valuei;
			set_value(i, 0);
		}

		set_value(curr.key, curr.value);

		if (curr.value > max.value)
			max = curr;
	}

	if (max.value > 0)
		printf("1: %d-%d (%u)\n",
				max.key, (max.key + max.value) - 1, max.value);
}


void
die(int status, const char *msg) {
	perror(msg);
	exit(status);
}

size_t
xsizemul(size_t x, size_t y) {
	size_t result;

	result = x * y;
	if (y != 0 && result / y != x) {
		errno = EOVERFLOW;
		die(1, NULL);
	}

	return result;
}

void *
xmalloc(size_t size) {
	void *ptr;

	ptr = malloc(size);
	if (ptr == NULL && size > 0)
		die(1, NULL);

	return ptr;
}


struct link {
	int key;
	unsigned value;
	struct link *next;
};

struct {
	struct link **buckets;
	size_t used;
	size_t capacity;
} table;

void insert_pair(struct link *);

void
init_table(size_t capacity) {
	size_t i;

	table.buckets = xmalloc(xsizemul(capacity, sizeof(struct link *)));
	table.capacity = capacity;

	for (i = 0; i < table.capacity; i++)
		table.buckets[i] = NULL;
}

void
maybe_grow_table(void) {
	struct link **old_buckets;
	size_t old_capacity;
	size_t i;
	struct link *curr, *next;

	if (table.used / 4 < table.capacity / 5)
		return;

	old_buckets = table.buckets;
	old_capacity = table.capacity;

	init_table(table.capacity * 2);

	for (i = 0; i < old_capacity; i++) {
		for (curr = old_buckets[i]; curr; curr = next) {
			next = curr->next;
			curr->next = NULL;
			insert_pair(curr);
		}
	}

	free(old_buckets);
}

struct link *
create_pair(int key, unsigned value) {
	struct link *new;

	new = xmalloc(sizeof(struct link));
	new->key = key;
	new->value = value;
	new->next = NULL;

	return new;
}

struct link **
get_bucket(int key) {
	return &table.buckets[key % table.capacity];
}

void
insert_pair(struct link *pair) {
	struct link **bucket;

	maybe_grow_table();

	bucket = get_bucket(pair->key);
	if (!*bucket)
		table.used++;

	pair->next = *bucket;
	*bucket = pair;
}

struct link *
find_link(int key) {
	struct link *link;

	for (link = *get_bucket(key); link; link = link->next)
		if (link->key == key)
			break;

	return link;
}

unsigned
get_value(int key) {
	struct link *link;

	link = find_link(key);
	if (link)
		return link->value;
	else
		return 0;
}

void
set_value(int key, unsigned value) {
	struct link *link;

	link = find_link(key);
	if (link)
		link->value = value;
	else
		insert_pair(create_pair(key, value));
}


struct state {
	size_t next_bucket;
	struct link *curr;
};

struct state *
iterate_pairs(void) {
	struct state *new;

	new = xmalloc(sizeof(struct state));
	new->next_bucket = 0;
	new->curr = NULL;

	return new;
}

int
next_pair(struct state *state, struct pair *pair) {
	while (!state->curr) {
		if (state->next_bucket >= table.capacity) {
			free(state);
			return 0;
		}

		state->curr = table.buckets[state->next_bucket];
		state->next_bucket++;
	}

	pair->key = state->curr->key;
	pair->value = state->curr->value;
	state->curr = state->curr->next;

	return 1;
}